Determine whether each of the following is a tautology, a contradiction, or neither. ('\/' is disjunction, '/\' is conjunction, '->' is implication, '-' is negation, '<->' is biconditional). I. P /\ ~P II. P \/ ~P III. (P /\ Q) -> P IV. P -> (P \/ Q) A. Only I and II B. Only II, III and IV

GATE 2002 · Discrete Mathematics · Propositional Logic · medium

Answer: I is a contradiction; II, III, and IV are tautologies.

1. Classify I: P /\ ~P: P /\ ~P: P=T gives T/\F=F; P=F gives F/\T=F. Always F. Contradiction.
2. Classify II: P \/ ~P: P \/ ~P: P=T gives T\/F=T; P=F gives F\/T=T. Always T. Tautology.
3. Classify III: (P /\ Q) -> P: If P/\Q=T then P=T so implication=T. If P/\Q=F the implication is vacuously T. Always T. Tautology.
4. Classify IV: P -> (P \/ Q): If P=T: P\/Q=T so implication=T. If P=F: implication vacuously T. Always T. Tautology.