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{𝐓}\equiv p$ $p\vee \mathbf{𝐅}\equiv p$	Identity laws
$p\vee \mathbf{𝐓}\equiv \mathbf{𝐓}$ $p\wedge \mathbf{𝐅}\equiv F$	Domination laws
$p\vee p\equiv p$ $p\wedge p\equiv p$	Idempotent laws
$\mathrm{\neg }(\mathrm{\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
$\mathrm{\neg }(p\wedge q)\equiv \mathrm{\neg }p\vee \mathrm{\neg }q$ $\mathrm{\neg }(p\vee q)\equiv \mathrm{\neg }p\wedge \mathrm{\neg }q$	De Morgan's laws
$p\vee (p\wedge q)\equiv p$ $p\wedge (p\vee q)\equiv p$	Absorption laws
$p\vee \mathrm{\neg }p\equiv \mathbf{𝐓}$ $p\wedge \mathrm{\neg }p\equiv \mathbf{𝐅}$	Negation laws

Conditional Equivalences

$p\to q\equiv \mathrm{\neg }p\vee q$

$p\to q\equiv \mathrm{\neg }q\to \mathrm{\neg }p$

$p\vee q\equiv \mathrm{\neg }p\to q$

$p\wedge q\equiv \mathrm{\neg }(p\to \mathrm{\neg }q)$

$\mathrm{\neg }(p\to q)\equiv p\wedge \mathrm{\neg }q$

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

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

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

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

Biconditional Equivalences

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

$p\leftrightarrow q\equiv \mathrm{\neg }p\leftrightarrow \mathrm{\neg }q$

$p\leftrightarrow q\equiv (p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)$

$\mathrm{\neg }(p\leftrightarrow q)\equiv p\leftrightarrow \mathrm{\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.