Logical Equivalences

Fundamental Equivalences

Identity Laws

$p \land T \equiv p$ $p \lor F \equiv p$

Domination Laws

$p \lor T \equiv T$ $p \land F \equiv F$

Idempotent Laws

$p \lor p \equiv p$ $p \land p \equiv p$

Double Negation Law

$\neg(\neg p) \equiv p$

Commutative Laws

$p \lor q \equiv q \lor p$ $p \land q \equiv q \land p$

Associative Laws

$(p \lor q) \lor r \equiv p \lor (q \lor r)$ $(p \land q) \land r \equiv p \land (q \land r)$

Distributive Laws

$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

De Morgan's Laws

$\neg(p \land q) \equiv \neg p \lor \neg q$ $\neg(p \lor q) \equiv \neg p \land \neg q$

Generalized De Morgan's Laws

$\neg(p_1 \land p_2 \land \cdots \land p_n) \equiv \neg p_1 \lor \neg p_2 \lor \cdots \lor \neg p_n$ $\neg(p_1 \lor p_2 \lor \cdots \lor p_n) \equiv \neg p_1 \land \neg p_2 \land \cdots \land \neg p_n$

Absorption Laws

$p \lor (p \land q) \equiv p$ $p \land (p \lor q) \equiv p$

Negation Laws

$p \lor \neg p \equiv T$ $p \land \neg p \equiv F$

Implication Equivalences

$p \rightarrow q \equiv \neg p \lor q$ $p \rightarrow q \equiv \neg q \rightarrow \neg p \text{ (contrapositive)}$ $\neg(p \rightarrow q) \equiv p \land \neg q$

Biconditional Equivalences

$p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$ $p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)$ $p \leftrightarrow q \equiv \neg(p \oplus q)$

Exclusive OR Equivalences

$p \oplus q \equiv (p \lor q) \land \neg(p \land q)$ $p \oplus q \equiv (p \land \neg q) \lor (\neg p \land q)$

Proving Equivalences

Method 1: Truth Tables

Show both sides have identical truth values for all inputs.

Method 2: Chain of Equivalences

Transform one side to the other using known equivalences.

Example: Prove $\neg(p \rightarrow q) \equiv p \land \neg q$

$\neg(p \rightarrow q)$ $\equiv \neg(\neg p \lor q) \text{ (implication equivalence)}$ $\equiv \neg(\neg p) \land \neg q \text{ (De Morgan's law)}$ $\equiv p \land \neg q \text{ (double negation)}$

Simplification Examples

Example 1

Simplify: $(p \land q) \lor (p \land \neg q)$

$= p \land (q \lor \neg q) \text{ (distributive law)}$ $= p \land T \text{ (negation law)}$ $= p \text{ (identity law)}$

Example 2

Simplify: $\neg(p \lor (\neg p \land q))$

$= \neg p \land \neg(\neg p \land q) \text{ (De Morgan's)}$ $= \neg p \land (p \lor \neg q) \text{ (De Morgan's)}$ $= (\neg p \land p) \lor (\neg p \land \neg q) \text{ (distributive)}$ $= F \lor (\neg p \land \neg q) \text{ (negation law)}$ $= \neg p \land \neg q \text{ (identity law)}$

Normal Forms

Disjunctive Normal Form (DNF)

A disjunction of conjunctions of literals: $(p \land q) \lor (\neg p \land r) \lor (p \land \neg q \land r)$

Conjunctive Normal Form (CNF)

A conjunction of disjunctions of literals: $(p \lor q) \land (\neg p \lor r) \land (p \lor \neg q \lor r)$

Every proposition can be converted to both DNF and CNF.