Question

Prove that P (P) = (QA ~ Q)] is a tautology.

Answer 1

The statement
`P \leftrightarrow [(\lnot P) \rightarrow (Q \land \lnot Q)]` is a tautology.

Explanation:

A tautology is a formula which is "always true" that is, it is true for every assignment of truth values to its simple components.

To show that this statement is a tautology we are going to use a table of logical equivalences:

`P \leftrightarrow [(\lnot P) \rightarrow (Q \land \lnot Q)] \equiv`

`\equiv (P \land [(\lnot P)\rightarrow (Q \land \lnot Q)]) \lor(\lnot P \land \lnot [(\lnot P)\rightarrow (Q \land \lnot Q)])` by the logical equivalences involving bi-conditional statements

`\equiv (P \land [\lnot(\lnot P)\lor (Q \land \lnot Q)]) \lor(\lnot P \land \lnot [\lnot(\lnot P)\lor (Q \land \lnot Q)])` by the logical equivalences involving conditional statements

`\equiv (P \land [P\lor (Q \land \lnot Q)]) \lor(\lnot P \land \lnot [ P\lor (Q \land \lnot Q)])` by the Double negation law

`\equiv (P \land [P\lor (Q \land \lnot Q)]) \lor(\lnot P \land \lnot P\land \lnot(Q \land \lnot Q))` by De Morgan's law

`\equiv (P \land [P\lor F]) \lor(\lnot P \land \lnot P\land \lnot(Q \land \lnot Q))` by the Negation law

`\equiv (P \land [P\lor F]) \lor(\lnot P \land \lnot P\land \lnot Q \lor \lnot(\lnot Q))` by De Morgan's law

`\equiv (P \land [P\lor F]) \lor(\lnot P \land \lnot P\land \lnot Q \lor  Q)` by the Double negation law

`\equiv (P \land P) \lor(\lnot P \land \lnot P\land \lnot Q \lor  Q)` by the Identity law

`\equiv (P) \lor(\lnot P \land \lnot P\land \lnot Q \lor  Q)` by the Idempotent law

`\equiv (P) \lor(\lnot P \land \lnot P\land  (Q\lor \lnot Q))` by the Commutative law

`\equiv (P) \lor(\lnot P \land \lnot P\land T)` by the Negation law

`\equiv (P) \lor(\lnot (P \lor P)\land T)` by De Morgan's law

`\equiv (P) \lor(\lnot (P)\land T)` by the Idempotent law

`\equiv (P \lor\lnot P) \land(P \lor T)` by the Distributive law

`\equiv (T) \land(P \lor T)` by the Negation law

`\equiv (T) \land(T)` by the Domination law

`\equiv T`