Subjects logic

Resolution Unsatisfiable 4A16Eb

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Resolution Unsatisfiable 4A16Eb


1. **State the problem:** We want to show that the compound proposition $ (p \lor q) \land (\neg p \lor q) \land (p \lor \neg q) \land (\neg p \lor \neg q) $ is not satisfiable using resolution. 2. **Recall the resolution rule:** Given two clauses $A \lor p$ and $B \lor \neg p$, we can infer the clause $A \lor B$ by resolving on $p$. 3. **List the clauses:** - $C_1: p \lor q$ - $C_2: \neg p \lor q$ - $C_3: p \lor \neg q$ - $C_4: \neg p \lor \neg q$ 4. **Apply resolution between $C_1$ and $C_4$ on $p$:** - From $p \lor q$ and $\neg p \lor \neg q$, resolving on $p$ gives $q \lor \neg q$. - Since $q \lor \neg q$ is a tautology, it does not help us derive a contradiction. 5. **Apply resolution between $C_2$ and $C_3$ on $p$:** - From $\neg p \lor q$ and $p \lor \neg q$, resolving on $p$ gives $q \lor \neg q$ again, a tautology. 6. **Apply resolution between $C_1$ and $C_2$ on $p$:** - From $p \lor q$ and $\neg p \lor q$, resolving on $p$ gives $q$. 7. **Apply resolution between $C_3$ and $C_4$ on $p$:** - From $p \lor \neg q$ and $\neg p \lor \neg q$, resolving on $p$ gives $\neg q$. 8. **Now resolve $q$ and $\neg q$:** - From $q$ and $\neg q$, resolving on $q$ gives the empty clause $\square$, which represents a contradiction. 9. **Conclusion:** Since resolution leads to a contradiction (empty clause), the original compound proposition is unsatisfiable. This means there is no assignment of truth values to $p$ and $q$ that makes the entire formula true.