Question

Use resolution to show that the compound proposition\((p \vee q) \wedge (\neg p \vee q) \wedge (p \vee \neg q) \wedge (\neg p \vee \neg q)\) is not satisfiable.

Short answer

It can be proved by Resolution Law that the proposition \((p \vee q) \wedge (\neg p \vee q) \wedge (p \vee \neg q) \wedge (\neg p \vee \neg q)\) is not satisfiable.

Step-by-step solution

Resolution Law and Idempotent Law

Resolution law:Let p, q and r be 3 propositions, it states that \(((p \vee q) \wedge (\neg p \vee r)) \to (q \vee r)\).

Idempotent Law: \((p \vee p) \to p\)

Proof

\((p \vee q) \wedge (\neg p \vee q) \to (q \vee q)\) (by Resolution Law)

\((p \vee q) \wedge (\neg p \vee q) \to q\) (by Idempotent Law) (1)

And

\((p \vee \neg q) \wedge (\neg p \vee \neg q) \to (\neg q \vee \neg q)\) (by Resolution Law)

\((p \vee \neg q) \wedge (\neg p \vee \neg q) \to \neg q\) (by Idempotent Law) (2)

Combining (1) and (2)

\((p \vee q) \wedge (\neg p \vee q) \wedge (p \vee \neg q) \wedge (\neg p \vee \neg q) \to (q \wedge \neg q)\)

\((q \wedge \neg q) \equiv F\)

The hypothesis as well as the conclusion are false in the above equation, so this proposition is not satisfiable.