MAT01A1:

Propositional logic – Part 2

Logic and proof techniques notes:

Section 1.1
Truth tables
We denote propositional variables with the letters
p, q, r, etc.
We use propositional variables and the logical
connectives to form propositional formulas.
We denote propositional formulas with capital
letters A, B, C, etc.
We use truth tables to find all possible truth
values a propositional formula can have.
In a truth table we need to consider all the possible
combinations for the truth values of the relevant
propositional variables.
If a formula contains n variables, then there are 2n
possible combinations.
Example: Construct a truth table for the
propositional formula ¬(p → q) ∨ (p ∧ q).
I How to ensure that you include all possible combinations
of truth values to the variables, in your truth table:
I Suppose the truth table involves two variables: p and q.
Then there are 22 = 4 possible combinations.
I Write the variables as headings in the two left-most
columns of the truth table.
I Fill in the values for the variable on the right first. Start
with T and alternate between T and F .
I Next fill in the values for the variable on the left.
I Start with T and alternate between two T ’s (i.e., T T )
and two F ’s (i.e., F F ).
p q
T T
T F
F T
F F
Suppose there are three variables, say p, q and r.
Then there are 23 = 8 possible combinations of
truth values.
p q r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
In general, suppose there are n variables. Then
there are 2n possible combinations of truth values
(and hence, 2n rows in the truth table.)
I Write the n variables as headings in the n
left-most columns of the truth-table.
I Begin with the right most variable and,
starting with T , alternate between T and F .
That is, alternate between strings of length
20 = 1 of T ’s and F ’s.
I With each successive variable to the left,
always starting with T , double the length of
the strings of T ’s and F ’s to alternate
between. Conclude with a string of T ’s of
length 2n−1 followed by a string of F ’s of
length 2n−1 for the left-most variable.
Example: Construct a truth table for the
propositional formula p ↔ (q ∨ ¬r).
Tautologies and contradictions
Definition: A tautology is a formula
that obtains a truth value true for any
assignment of truth values to the
variables, i.e. it is a formula that is always
true. Tautologies are also called logically
valid formulas.
Example: Show that the propositional
formula p → (q → p) is a tautology.
Definition: A contradiction is a
formula that obtains a truth value false
for any assignment of truth values, i.e. it
is a formula that is always false.
Example: Show that the propositional
formula ¬(p → (q → p)) is a contradiction.
Example: Is p → (p → q) a contradiction,
a tautology or neither?.
Logical equivalence
 Definition: Propositional formulas A and
B are logically equivalent if for every
assignment of truth values to the variables
in them they obtain identical truth values,
i.e., they have ‘the same truth table’.

We write A ≡ B to indicate that A and B

are logically equivalent.
Note that A ≡ B if, and only if, A ↔ B is a
tautology.
Example: Show that
p → (q → r) ≡ (p ∧ q) → r.
Example: Is (p ∨ q) ∧ r ≡ p ∨ (q ∧ r)?
Known equivalences
Let t denote a tautology and f a contradiction.
Commutative laws: A∧B ≡ B∧A
A∨B ≡ B∨A
Associative laws: (A ∧ B) ∧ C ≡ A ∧ (B ∧ C)
(A ∨ B) ∨ C ≡ A ∨ (B ∨ C)
Distributive laws: A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)
A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)
Identity laws: A∧t ≡ A
A∨f ≡ A
Negation laws: A ∨ ¬A ≡ t
A ∧ ¬A ≡ f
Let t denote a tautology and f a contradiction.
Double negative law: ¬(¬A) ≡ A

Idempotent laws: A∧A ≡ A

A∨A ≡ A
Universal bound laws: A∨t ≡ t
A∧f ≡ f
De Morgan’s laws: ¬(A ∧ B) ≡ ¬A ∨ ¬B
¬(A ∨ B) ≡ ¬A ∧ ¬B
Absorption laws: A ∨ (A ∧ B) ≡ A
A ∧ (A ∨ B) ≡ A
Bioconditional in terms of implication and
conjunction:

A ↔ B ≡ (A → B) ∧ (B → A)

Implication in terms of negation and disjunction:

A → B ≡ ¬A ∨ B

Negation of implication:

¬(A → B) ≡ A ∧ ¬B

Negation of biconditional:

¬(A ↔ B) ≡ (A ∧ ¬B) ∨ (B ∧ ¬A)

Example: Use known equivalences to show
that r ∧ ((p ∨ q) → ¬r) ≡ (r ∧ ¬q) ∧ ¬p.
Example: Use the known logical
equivalences given above to rewrite
(p ↔ q) → ¬(p → ¬r) using only ∧, ∨ and
¬.
Contrapositive, converse,
inverse
The contrapositive of the implication
A → B is ¬B → ¬A.

An implication is logically equivalent to

its contrapositive:

A → B ≡ ¬B → ¬A
 I B → A is the converse of A → B
I ¬A → ¬B is the inverse of A → B.

I An implication and its converse are not

logically equivalent: A → B 6≡ B → A.
I An implication and its inverse are not logically
equivalent: A → B 6≡ ¬A → ¬A.
I The converse and inverse of an implication are
logically equivalent to each other:
¬A → ¬B ≡ B → A.
We can use a truth table to verify these
equivalences.
p q ¬p ¬q p → q ¬q → ¬p q → p ¬p → ¬q
T T F F T T T T
T F F T F F T T
F T T F T T F F
F F T T T T T T

From columns 5 and 6 we see that p → q and

¬q → p have the same truth values for all
assignments of truth values to p and q.
From columns 7 and 8 we see that q → p and
¬p → q have the same truth values for all
assignments of truth values to p and q.
The following example illustrates that a
conditional statement and its converse are
not equivalent:
Implication:
If π is a real number, then π is an integer.
Since “π is a real number” is true, but “π is
an integer” is false, the implication is false.
Converse of the implication:
If π is an integer, then π is a real number.
Since “π is an integer” is false, the converse
of the implication is true.
Example: Write down the contrapositive,
converse and inverse of the following
proposition: “If Rover is a dog, then Rover is
an animal.”
Necessary and sufficient
conditions
If A and B are propositional formulas,
then
I “A is a sufficient condition for B”

means A → B,
I “A is a necessary condition for B”

means B → A, or, equivalently,

¬A → ¬B.
Sufficient condition

“A is a sufficient condition for B”

means
“the truth of A is enough to
guarantee the truth of B”.
In other words:
“if A is true, then B is true”
that is,
“if A, then B”.
Necessary condition

“A is a necessary condition for B”

means
“B can only be true if A is true”.
In other words:
“B only if A”.
Recall that
“B only if A” is equivalent to
“if B, then A”
 Example: Rewrite the following statements
in the if-then form.
1. Being age 18 is sufficient for Mandla being
eligible to vote.
2. Being divisible by 3 is a necessary condition for a
number to be divisible by 9.
Prescribed tut problems

Section 1.1:
7 h)–j); 8 b)–d); 10 a), d)
11 a), b); 12 a), c); 13 a), b).