Quiz. Evaluating sat/unsat/valid [000a]
- November 22, 2025
Are the following formulas sat., unsat., or valid?Quiz. Evaluating sat/unsat/valid [000a]
- November 22, 2025
- \((p\land q) \to \neg p\)
- \((p \land q) \to (p \lor \neg q)\)
- \((p \to (q \to r)) \land \neg ((p \land q) \to r)\)
Solution.
- November 22, 2025
As a reminder lets recap the definitions:
Solution.
- November 22, 2025
- A formula is satisfiable if there exists at least one combination of true/false assignments to its variables that makes the formula true.
- A formula is unsatisfiable if there is no combination of true/false assignments to its variables that makes the formula true (i.e., it is always false).
- A formula is valid (or a tautology) if it is true under all possible combinations of true/false assignments to its variables.
Now we can analyze each formula:
- For the lhs to be true both p and q must be true. However, if p is true then \(\neg p\) is false, making the implication false. If p is false then the implication is vacuously true regardless of what we set q to. Thus, this formula is satisfiable (e.g., when p is false) but not valid (e.g., when p and q are true).
- If both p and q are true then the lhs is true and so is the rhs by virtue of p being true. If p is false then the implication is vacuously true regardless of q. If q is false then the rhs is true regardless of p. Thus, this formula is valid as it is true for all combinations of truth values for p and q.
- The first part \((p \to (q \to r))\) is true unless p is true and either q or r is false. The second part \(\neg ((p \land q) \to r)\) is true when p and q are true but r is false. Thus we can satisfy the entire formula by setting p and q to true and r to false. However, if we set p to false then the first part is vacuously true, but the second part becomes false. Thus, this formula is falsifiable (e.g., when p and q are true and r is false) but not valid (e.g., when p is false).