##### Tautology

Show that each of these conditional statements is a tautology :

a) (p ∧ q) → p

b) p → (p ∨ q)

c) ¬p → (p → q)

d) (p ∧ q) → (p → q)

e) ¬(p → q) → p

f ) ¬(p → q) → ¬q

Things you need to Understand

Point 1

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology.

Point 2

Observe the truth table for implication (→):

 p q p  → q F F T F T T T F F T T T

Checkpoint : The given compound proposition might fail to be a tautology when the RHS of (→) is False, and LHS is True.

Method 1

Step 1: Make RHS False

Step 2: Try to make LHS True

Step 3: If Step 1 possible , then cannot be tautology

else, given compound proposition is tautology.

a) (p ∧ q) → p

Step 1: Make RHS False

p = F

Step 2: Try to make LHS True

LHS = p ∧ q = F ∧ q = F

∴  LHS → RHS = T

Hence, Tautology

b) p → (p ∨ q)

Step 1: Make RHS False

RHS = (p ∨ q)

for LHS to be False , both p = F and q = F

Step 2: Try to make LHS True

LHS = p = (∵ for RHS we made p = F)

∴ LHS → RHS = T

Hence, Tautology

c) ¬p → (p → q)

Step 1: Make RHS False

RHS = (p → q)

for RHS to be False, p = T and q = F

Step 2: Try to make LHS True

LHS = ¬p = ¬ = F

LHS → RHS = T

Hence, Tautology.

d) (p ∧ q) → (p → q)

Step 1: Make RHS False

RHS = p → q

for RHS to be False, p = T and q = F.

Step 2: Try to make LHS True

LHS =  (p ∧ q) = T  ∧ F = F

LHS → RHS = T

Hence, Tautology.

e) ¬(p → q) → p

Step 1: Make RHS False

RHS = p

for RHS to be False , p = F

Step 2: Try to make LHS True

LHS =  ¬(p → q)  = ¬(F → q) = ¬ (T) = F

∴  LHS → RHS = T

Hence, Tautology

f) ¬(p → q) → ¬q

Step 1: Make RHS False

RHS = ¬q

for RHS to be False,  q= T

Step 2: Try to make LHS True

LHS = ¬(p → q) = ¬(p → T) = ¬ (T) = F

LHS → RHS

Hence, Tautology.