Question

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

Answer 1

Answer:

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

Step-by-step 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$