SEHH2241 L101/102 Lecture #2 Sem1 2022

1 Logical Connectives
Let p and q be some propositions. Then the

(1) Negation of p is the statement not p, denoted by ¬p. The truth table is

(2) Conjunction of p and q is the statement p and q, denoted by p ∧ q.

(3) Disjunction of p and q is the statement p or q, denoted by p ∨ q.

(4) Conditional implication from p to q is the statement if p then q, denoted by p → q.

We also say p is a sufficient condition for q, or q is a necessary condition for p.

(5) Biconditional implication of p and q is the statement if p then q and if q then p, or p

if and only if q, denoted by p ↔ q. We say p is a sufficient and necessary condition
of q.

Their truth tables are given by

p ¬p p q p∨q p q p↔q
(1) T F , T T T T T T
F T (3) T F T , (5) T F F
F T T F T F
F F F F F T

p q p∧q p q p→q
T T T T T T
(2) T F F , (4) T F F
F T F F T T
F F F F F T

Remark. A truth table having statements p1 , · · · , pn contains 2n number of rows.

1
 Let p → q. Then

• The converse of p → q is the statement q → p.

• The contrapositive of p → q is the statement ¬q → ¬p.

• The inverse of p → q is the statement ¬p → ¬q.

Exercise 1. Find the truth table of

(a) ¬(¬p). (c) ¬(p ∧ ¬q). (e) (p ∨ q) → r.

(b) p ∨ ¬p. (d) (p → q) → (q → p) (f) p ↔ (¬q ∧ r).

2 Tautologies
• A proposition is called a tautology if it always has the true value no matter what truth
values of its propositional variables are.

• A propositions is called a contradiction if it always has the false value.

• A proposition is called a contingency if it can be either true or false.

• Two propositions p and q are logically equivalent if p ↔ q is a tautology, denoted by

p ⇐⇒ q.

p p→p
Example. p → p is a tautology as its truth table T T has T value in all cases.
F T

Example. p → q, ¬(p ∧ ¬q) and ¬q → ¬p are logically equivalent as they have the same truth table

p q p→q ¬(p ∧ ¬q) ¬q → ¬p

T T T T T
T F F F F .
F T T T T
F F T T T

2
For statement p, q and r, we have

Identity: p ∧ T ⇐⇒ p p ∨ F ⇐⇒ p
Domination: p ∨ T ⇐⇒ T p ∧ F ⇐⇒ F
Idempotent: p ∨ p ⇐⇒ p p ∧ p ⇐⇒ p
Double negation: ¬¬p ⇐⇒ p
Commutative: p ∨ q ⇐⇒ q ∨ p p ∧ q ⇐⇒ q ∧ p
Associative: (p ∨ q) ∨ r ⇐⇒ p ∨ (q ∨ r) (p ∧ q) ∧ r ⇐⇒ p ∧ (q ∧ r)
Distributive: p ∨ (q ∧ r) ⇐⇒ (p ∨ q)∧ p ∧ (q ∨ r) ⇐⇒ (p ∧ q)∨
(p ∨ r) (p ∧ r)
De Morgan’s: ¬(p ∧ q) ⇐⇒ ¬p ∨ ¬q ¬(p ∨ q) ⇐⇒ ¬p ∧ ¬q
tautology/contradiction: p ∨ ¬p ⇐⇒ T p ∧ ¬p ⇐⇒ F

Exercise 2. Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by (i) truth table
and (ii) developing a series of logical equivalences.

3
3 Rules of Inference
Let p1 , p2 , · · · , pn , q be statements. Then

p1
p2
..
.
pn
∴ q

means the statement (p1 ∧ p2 ∧ · · · pn ) → q. We call p1 , p2 , · · · , pn by premises/hypotheses,

and q by the conclusion.

(1) Modus ponens (MP): (5) Conjunction (Conj):

p→q
p
p
q
∴ q
∴ p∧q
(2) Modus tollens (MT):

p→q (6) Hypothetical syllogism (HS):

¬q
p→q
∴ ¬p
q→r
(3) Addition (Add): ∴ p→r
p
∴ p∨q (7) Disjunction (Disj):

(4) Simplification (Simp): p∨q

p∧q ¬p
∴ p ∴ q

4
Example. We want to show that the following argument is valid.

p→q
q→r
¬r
∴ ¬p

Solution.
Step Reason
1. p→q premise
2. q→r premise
3. ¬r premise / ∴ ¬p
4. p→r 1,2 HS
5. ¬p 3,4 MT
"

Exercise 3. Show that the following argument is valid.

p→q
r→s
(q ∨ s) → t
¬t
∴ ¬(p ∨ r)

Exercise 4. Show that the following argument is valid.

Premises: If you send me an e-mail message, then I will finish writing the program. If you do
not send me an e-mail message, then I will go to sleep early. If I go to sleep early, then I will
wake up feeling refreshed.
Conclusion: If I do not finish writing the program, then I will wake up feeling refreshed.

Solution. Let
p : You send me an e-mail message.

q : I will finish writing the program.

r : I will go to sleep early.

s : I will wake up feeling refreshed.

5
Then we have
Step Reason
1. p→q premise
2. ¬p → r premise
3. r→s premise / ∴ ¬q → s
4. ¬q → ¬p contrapositive of 1
5. ¬q → r 2,4 HS
6. ¬q → s 3,5 HS
"

4 Resolution
• A clause is a compound statement with terms separated by “or”, and each term is a
single variable or the negation of a single variable.

• Resolution is the rule of inference

p∨q
¬p ∨ r
∴ q∨r

Example. p ∨ ¬q ∨ r ∨ ¬s is a clause while (p ∧ q) ∨ r ∨ ¬s is not.

Example. Show that the following argument is valid by using resolution.

Premises: Jasmine is skiing or it is not snowing. It is snowing or Bart is playing hockey. Conclusion:
Jasmine is skiing or Bart is playing hockey.

Solution. Let
p : Jasmine is skiing.

q : It is snowing.

r : Bart is playing hockey.

6
Then we have
Step Reason
1. p ∨ ¬q premise
2. q∨r premise / ∴ p ∨ r
3. ¬q ∨ p 1 commutative
4. p∨r 2,3 resolution
"

Exercise 5. Show that the following argument is valid by using resolution.

(p ∧ q) ∨ r
r→s
∴ p∨s