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 ?
Answer: A. F1 is Satisfiable, F2 is valid — 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…
- 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 182 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).
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2