Tautologies, Contradictions, and Logical Equivalence Laws

Logical Equivalence

Two statements are logically equivalent if and only if they have identical truth values for each possisble substitution of statements for their statement variable.

 

 

Tautologies and Contradictions

$\begin{matrix} p & \neg p & p \lor \neg p \\ T & F & T\\ F & T & T\\ \end{matrix}$

Tautology is a compound statement that is always true regardless of the truth values of individual statements

 

$\begin{matrix} p & \neg p & p \land \neg p \\ T & F & F\\ F & T & F\\ \end{matrix}$

Contradiction is a compound statement that is always false regardless of the truth values of individual statements

 

$e.g.\ (p \land \neg q) \land (\neg p \lor q)\\ \begin{matrix} p & q & \neg p & \neg q & p \land \neg q & \neg p \lor q & (p \land \neg q) \land (\neg p \lor q) \\ T & T & F & F & F & T & F\\ T & F & F & T & T & F & F\\ F & T & T & F & F & T & F\\ F & F & T & T & F & T & F \end{matrix}\\ so, (p \land \neg q) \land (\neg p \lor q)\ is\ a\ contradiction$

 

 

De Morgan's Laws in logic

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

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

$proof\ for\ \neg (p \land q) \equiv \neg p \lor \neg q\\ \begin{matrix} p & q & \neg p & \neg q & p \land q & \neg (p \land q) & \neg p \lor \neg q\\ T & T & F & F & T & F & F\\ T & F & F & T & F & T & T\\ F & T & T & F & F & T & T\\ F & F & T & T & F & T & T \end{matrix}\\$

$proof\ for\ \neg (p \lor q) \equiv \neg p \land \neg q\\ \begin{matrix} p & q & \neg p & \neg q & p \lor q & \neg (p \lor q) & \neg p \land \neg q\\ T & T & F & F & T & F & F\\ T & F & F & T & T & F & F\\ F & T & T & F & T & F & F\\ F & F & T & T & F & T & T \end{matrix}\\$

 

 

Logical Equivalence Laws

Commutative laws : $p \land q \equiv q \land p,\ p \lor q \equiv q \lor p$

Associative laws : $(p \land q) \land r \equiv p \land (q \land r),\ (p \lor q) \lor r \equiv p \lor (q \lor r)$

Distributive laws : $p \land (q \lor r) \equiv (p \land q) \lor (p \land r),\ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

Identity laws : $p \land \bold{t} \equiv p,\ p \lor \bold{c} \equiv p$

Negation laws : $p \lor \neg p \equiv \bold{t},\ p \land \neg p \equiv \bold{c}$

Double negative law : $\neg(\neg p) \equiv p$

Idempotent laws : $p \land p \equiv p,\ p \lor p \equiv p$

Universal bound laws : $p \lor \bold{t} \equiv \bold{t},\ p \land \bold{c} \equiv \bold{c}$

De Morgan's laws : $\neg (p \land q) \equiv \neg p \lor \neg q,\ \neg (p \lor q) \equiv \neg p \land \neg q$

Absorption laws : $p \lor (p \land q) \equiv p,\ p \land (p \lor q) \equiv p$

Negations of t(autology) and c(ontradiction) : $\neg \bold{t} \equiv \bold{c},\ \neg \bold{c} \equiv \bold{t}$