IT2212

Propositional Logic
What is a proposition?
Defined as a statement to be proved, explained, or discussed
It is a declarative sentence that is either false or true (NOT both)

When represented in tables, capital letters are usually used for proposition.
Example:
P = Today is January 1
The letter P will represent the statement in tables.
Also, we use the letter T to represent a true statement and F to represent a false statement.
Using numerical symbols, 1 represents true while 0 represents false.
Hence for the example:
P Today is January 1
T or 1 True, today is January 1
F or 0 False, today is not January 1

Bases for Propositional Logic

During the 18th, 19th, and early 20th Century, scholars who saw themselves as carrying on the Aristotelian and Medieval
tradition in logic, often pointed to the “laws of thought” as the basis of all logic. The three (3) laws are as follows:

Law of Identity or “Logical Identity”

It is the notion that things must be, of course, identical with themselves. P = P
If water is water, then by the law of identity, anything we discover to be water must possess the same
properties.
Law of Excluded Middle
It is the idea that every proposition must be either true or false, not both and not neither.
If the date today is January 1, the proposition P is true only; it cannot also be false.
Law of Non-Contradiction
Logically correct propositions cannot affirm and deny the same thing
Is it January 1 today? The answer could only be yes or no and not both.

Examples
Statement? Proposition? Truth Value
(Y/N) (Y/N) (T/F)
A : Chickens can fly. Y Y F
B : 2022 < 100 Y Y F
C : x > 10 Y N --
D : Today is January 1 and 1 < 0. Y Y F
E : Please keep your phones on silent mode. N -- --
F : If chickens could fly, it would be harder to eat them. Y Y ~F
G : x < y if and only if y > x. Y Y T
Note:
C is not a proposition since the truth value of the statement will depend on the value of x.
x = 15 > 10 is a True proposition
x = 5 > 10 is a False proposition
E is not a statement; it is a request. Only statements could be propositions.
Although F is a proposition, its truth value cannot be ascertained unless proven.

Truth Table (Levin)

It is a chart to keep track of all the possibilities in the proposition. The idea is on each row, we list a possible combination
of T’s and F’s (for true and false) for each of the variables and then mark down whether the statement in question is true

01 Handout 1.1 *Property of STI

Page 1 of 6
 IT2212

or false in that case. We do this for every possible combination of T’s and F’s. Then we can clearly see in which cases the
statement is true or false.

Example:
Condition: You can only go out of the house if you are in the 18-65 years old range and fully vaccinated.
Proposition A: Are you in the 18-65 years old range?
Proposition B: Are you Fully Vaccinated?

Truth Table: (includes all possibilities)

Sample A B C Can go out?
1 T T You are within the age limit and fully vaccinated. T and T = Yes (T)
2 T F You are within the age range but not fully vaccinated. T and F = No (F)
3 F T Not within the age range but fully vaccinated. F and T = No (F)
4 F F Not within the age range and not fully vaccinated. F and F = No (F)
Because the condition is that you have to answer yes (True) to both statements; therefore only sample 1 will be allowed
to go out.

Logical Connectives
Compound Proposition
- It is a proposition constructed by combining one (1) or more existing propositions.
Example: Proposition 1: You are 18 years old.
Proposition 2: You are fully vaccinated.
Compound Proposition: You are 18 years old and fully vaccinated.

Types of Logical Connectives:

1. Negation - Combines propositions using the keyword not. It states the opposite of the proposition. We use the
symbol ( ~ ) or ( ¬ ) attached to the representation of the proposition to indicate that it is the negation of the said
proposition.

Example: Proposition P: It is raining.

Negation of P (~P): It is not raining.
Truth Table:
P ~P
True (T) or 1 False (F) or 0
False (F) or 0 True (T) or 1

2. Conjunction – Combines propositions using the keyword and. The conjunction would only be true if both initial
propositions are true. The symbol (^) is used to represent the word and in a conjunction.

Example: Proposition A: Today is January 1.

Proposition B: It is raining.
Conjunction: Today is January 1 and it is raining.
Truth Table:
A B A^B
T T T
T F F
F T F
F F F

3. Disjunction – Combines proposition using the keyword or. The combined proposition called a disjunction will be true
if one of the propositions is true. The symbol (v) is used to represent the word or in a disjunction.

01 Handout 1.1 *Property of STI

Page 2 of 6
 IT2212

Example: Proposition A: The person is below 18 years old.

Proposition B: The person is a senior citizen.
Disjunction: Either the person is below 18 years old or a senior citizen.
Truth Table:
A B AvB
T T T
T F T
F T T
F F F

4. Implication – The combined propositions are formed as if-then statements. The order of which proposition comes
first is important. The first proposition is called the antecedent and the second proposition is the consequence. The
symbol used to represent an implication is an arrow (→) from the ‘if-statement’ (antecedent) to the ‘then-
statement’ (consequence).
Example: Proposition A: The sky is overcast.
Proposition B: The sun cannot be seen.
Implication: If the sky is overcast, then the sun cannot be seen.
Truth Table:
A B A→B
T T T
T F F
F T T
F F T

Other implications that can be formed from A → B

Converse – The reverse of the implication. The second statement is now the antecedent, hence B → A
If the sun cannot be seen, then the sky is overcast.
Contrapositive – The propositions are negated and interchanged. ~B → ~A
If the sun can be seen, then the sky is not overcast.
Inverse – The propositions are negated. ~A → ~B
If the sky is not overcast, then the sun can be seen.
5. Biconditional – A statement combining a conditional statement with its converse. The words if and only if is used in
this proposition and the symbol is (→). For the biconditional to be true, both propositions should have the same
truth value (TT or FF).
Example: Proposition A: The sky is overcast.
Proposition B: The sun cannot be seen.
Biconditional: The sky is overcast if and only if the sun cannot be seen.
Truth Table:
A B A → B
T T T
T F F
F T F
F F T
6. XOR – Read as exclusive or is a version of a disjunction that does not allow both propositions to be true
simultaneously. The symbol used is (⊕). It is often used for bitwise operations, particularly in computer science.
Examples: 1 ⊕ 1 = 0
0⊕0=0
1⊕0=1

Truth Table:
A B A⊕B

01 Handout 1.1 *Property of STI

Page 3 of 6
 IT2212

T T F
T F T
F T T
F F F

In computer science, XOR has several uses:

- It tells whether two bits are unequal.
- It is an optional bit-flipper.
- It tells whether there is an odd number of 1 bit.
- In logical circuits, a simple adder can be made with an XOR gate to add the numbers and a series of AND, OR,
and NOT gates to create the carry output.
- It is sometimes used as a simple mixing function in cryptography
- It is also used to detect an overflow in the result of a signed binary arithmetic operation.

Truth Table Reference

- Use the table below as a guide when working with truth tables. The truth values for the logical connectives
discussed are summarized in this table.

TRUTH TABLE

(exclusive disjunction)

A if and only if B
(biconditional)
(conjunction)
a proposition

a proposition

a proposition

(implication)
(disjunction)

If A then B
(negation)

A XOR B
A and B

A or B
not P

P ~P A B A^B AvB A⊕B A→B A→B

T F T T T T F T T
F T T F F T T F F
F T F T T T F
F F F F F T T

Precedence of Logical Operators

- Similar to the order of operations in arithmetic, there is a set order to be observed when solving for complex
propositions.
Level Operator
1 Negation (~)
2 Conjunction (^)
3 Disjunction (v)
4 Implication (→)
5 Biconditional (→)
Example:
1. ~A ^ B
Since negation first before conjunction, do ~A first, then ~A ^ B
1st step 2nd step
A B
~A ~A ^ B
T F T F
T F F F
F T T T

01 Handout 1.1 *Property of STI

Page 4 of 6
 IT2212

F T F F

2. AvB^C
Since conjunction takes precedence before disjunction, then (B ^ C) first before A v (B ^ C)
1st step 2nd step
A B C
B^C AvB^C
T T T T T
T F T F T
F T F F F
F F F F F
Try these:
3. A^B^C^D
4. A^B→AvB
5. A→B→C

Tautology
Tautology – It is any statement that is TRUE regardless of the truth values of the constituent parts
Example: Show in a truth table that the statement A v ~A is a tautology
A ~A A v ~A
T F T
T F T
F T T
F T T
Since each entry in the truth table for A v ~A is true, then it is a tautology

Contradiction – It is any statement that is always false regardless of the truth values of the parts. It is the opposite of a
tautology. Example: Show in a truth table that the statement A ^ ~A is a contradiction.
A ~A A ^ ~A
T F F
T F F
F T F
F T F
Since each entry in the truth table for A ^ ~A is true, then it is a contradiction.

Contingency – It is any statement that is neither a tautology or a contradiction.

Example: Show in a truth table that the statement A → ~A is a contradiction.
A ~A A → ~A
T F F
T F F
F T T
F T T
Since entries in the truth table for A → ~A is a mix of true and false, then it is a contingency.
Logical Equivalence
When two (2) different compound propositions have exactly the same truth value in every case, then the propositions
are logically equivalent. The symbol used to denote logical equivalence is ≡
Example: Show in a truth table that the two (2) compound propositions are logically equivalent.
A ≡ ~~A
A ~A ~~A
T F T
T F T
F T F

01 Handout 1.1 *Property of STI

Page 5 of 6
 IT2212

F T F
Since column 1 (A) and column 3 (~~A) are exactly the same, then they are logically equivalent.

Exercises:
1. (A → B) ≡ (~A v B)
2. ~(A v B) ≡ (~A^ ~B)
3. ~(A^B) ≡ (~A v ~B)

References:
Busby, R. B. K. (2022). Discrete mathematical structures: Pearson New International (6th ed). Pearson
Education Limited.
de Troyer, O., Lindberg, R., & Sajjadi, P. (2019). TrueBiters, an educational game to practice the truth tables of
propositional logic: Development, evaluation, and lessons learned. Smart Learning Environments, 6(1).
https://doi.org/10.1186/s40561-019-0105-2
Fortney, J. P. (2021). Discrete mathematics for computer science: An example-based introduction. CRC Press,
Taylor & Francis Group.
Lewis, H.,& Zax, R. (2019). Essential Discrete Mathematics for Computer Science. Princeton University Press.
“Naturalistic Epistemology,” by Chase B. Wrenn, The Internet Encyclopedia of Philosophy, ISSN 2161-0002,
https://iep.utm.edu/, January 20, 2022
proposition. (n.d.). In Merriam-Webster. Retrieved January 28, 2022, from https://www.merriam -
webster.com/dictionary/proposition
Rosen, K. H. (2019). Discrete mathematics and its applications. McGraw-Hill Education.
WISE Lab. (n.d). TrueBiters. Web & Information Systems Engineering.
https://wise.vub.ac.be/project/truebiters

01 Handout 1.1 *Property of STI

Page 6 of 6