Consider two well-formed formulas in propositional logic:
F_1 : P - ~P
F_2 : (P - ~P) /\ (~P - P)

Which one of the f...

Question

Consider two well-formed formulas in propositional logic:
F_1 : P -> ~P
F_2 : (P -> ~P) /\ (~P -> P)

Which one of the following statements is correct?

A. F_1 is satisfiable, F_2 is valid
B. F_1 is unsatisfiable, F_2 is satisfiable
C. F_1 is unsatisfiable, F_2 is valid
D. F_1 and F_2 are both satisfiable

Accepted Answer

A. F_1 is satisfiable, F_2 is valid F_1 = P -> ~P simplifies to ~P / ~P = ~P. This is true when P=F, so it is satisfiable (but not valid). F_2 = (P -> ~P) /\ (~P -> P) = ~P /\ P = a contradiction? Wait: (P->~P)/\(~P->P) = ~P /\ (P/P) = ~P /\ P = F always. So F_2 is unsatisfiable. But the answer is A (F_1 satisfiable, F_2 valid). Let me re-read: F_2 = (P->~P) /\ (~P->P). Actually ~P->P = P/P = P. So F_2 = ~P /\ P = always F (unsatisfiable). Option D says both satisfiable. Official answer A says F_2 is valid. There may be a typo in the original — the actual GATE 2001 question has F_1: P->~P (satisfiable, not valid) and F_2 is a different formula.