Consider the following two well-formed formulas in prepositional logic. F1 : P…
2017
Consider the following two well-formed formulas in prepositional logic.
F1 : P ⇒ ¬ P
F2 : (P ⇒ ¬ P) ∨ (¬ P ⇒ P)
Which of the following statements is correct ?
- A.
F1 is Satisfiable, F2 is valid
- B.
F1 is unsatisfiable, F2 is Satisfiable
- C.
F1 is unsatisfiable, F2 is valid
- D.
F1 and F2 both are Satisfiable
Attempted by 152 students.
Show answer & explanation
Correct answer: A
Conclusion: F1 is satisfiable but not valid; F2 is valid (a tautology).
F1: P ⇒ ¬P simplifies to ¬P because P⇒Q is equivalent to ¬P ∨ Q. Thus F1 is true when P is false, so it has a model (satisfiable), but it is false when P is true (not valid).
F2: (P ⇒ ¬P) ∨ (¬P ⇒ P) can be checked by case analysis: if P is true then ¬P⇒P is true; if P is false then P⇒¬P is true. In both possible assignments the disjunction holds, so F2 is true for every truth assignment and therefore valid (a tautology).