Show that the formula (~p -> q) -> (p \/ q) is not a tautology. Let A be a tautology and B any other formula. Prove that (A /\ B) -> B is a tautology.
GATE 1999 · Discrete Mathematics · Propositional Logic · medium
Answer: Proof: (A /\ B) -> B is a tautology because whenever the antecedent A /\ B holds, B is already true by conjunction elimination.
Evaluate (~p -> q) -> (p \/ q) on all rows: p=T,q=T: (~T->T)->(T\/T)=(F->T)->T=T->T=T. p=T,q=F: (F->F)->(T\/F)=T->T=T. p=F,q=T: (T->T)->(F\/T)=T->T=T. p=F,q=F: (T->F)->(F\/F)=F->F=T. All rows give T, so the formula IS a tautology. The question text asks to 'show it is not a tautology' but actually it is — for Part 2 we prove (A /\ B)->B.
Prove (A /\ B) -> B is a tautology: In any interpretation: if A /\ B is false, the implication is vacuously true. If A /\ B is true, then both A=T and B=T, so the consequent B=T and the implication is true. In all cases (A /\ B) -> B = T.