CSCE 222 Chapter 1.2

« previous | Thursday, February 10, 2011 | next »

Propositional Equivalences

Tautology

a compound proposition that is always true, regardless of the truth values of the propositions that occur in it

Contradiction

a compound proposition that is always false (opposite of a tautology)

Contingency

a compound proposition that is neither a tautology or a contradiction

Logical Equivalence

Propositions are equivalent iff they have identical truth tables

Common Logical Equivalences

Equivalence	Name
$p\wedge \mathbf {T} \equiv p$ $p\vee \mathbf {F} \equiv p$	Identity laws
$p\vee \mathbf {T} \equiv \mathbf {T}$ $p\wedge \mathbf {F} \equiv F$	Domination laws
$p\vee p\equiv p$ $p\wedge p\equiv p$	Idempotent laws
$\neg (\neg p)\equiv p$	Double negation law
$p\vee q\equiv q\vee p$ $p\wedge q\equiv q\wedge p$	Commutative laws
$(p\vee q)\vee r\equiv p\vee (q\vee r)$ $(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$	Associative laws
$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$ $p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$	Distributive laws
$\neg (p\wedge q)\equiv \neg p\vee \neg q$ $\neg (p\vee q)\equiv \neg p\wedge \neg q$	De Morgan's laws
$p\vee (p\wedge q)\equiv p$ $p\wedge (p\vee q)\equiv p$	Absorption laws
$p\vee \neg p\equiv \mathbf {T}$ $p\wedge \neg p\equiv \mathbf {F}$	Negation laws

Conditional Equivalences

$p\rightarrow q\equiv \neg p\vee q$

$p\rightarrow q\equiv \neg q\rightarrow \neg p$

$p\vee q\equiv \neg p\rightarrow q$

$p\wedge q\equiv \neg (p\rightarrow \neg q)$

$\neg (p\rightarrow q)\equiv p\wedge \neg q$

$(p\rightarrow q)\wedge (p\rightarrow r)\equiv p\rightarrow (q\wedge r)$

$(p\rightarrow r)\wedge (q\rightarrow r)\equiv (p\vee q)\rightarrow r$

$(p\rightarrow q)\vee (p\rightarrow r)\equiv p\rightarrow (q\vee r)$

$(p\rightarrow r)\vee (q\rightarrow r)\equiv (p\wedge q)\rightarrow r$

Biconditional Equivalences

$p\leftrightarrow q\equiv (p\rightarrow q)\wedge (q\rightarrow p)$

$p\leftrightarrow q\equiv \neg p\leftrightarrow \neg q$

$p\leftrightarrow q\equiv (p\wedge q)\vee (\neg p\wedge \neg q)$

$\neg (p\leftrightarrow q)\equiv p\leftrightarrow \neg q$

Constructing New Logical Equivalences

Use the equivalences above to reduce/decompose one compound proposition into the other

To show that a statement is a tautology, use the equivalences above to reduce/decompose the function into a single, final T value.