CSCE 222 Lecture 6

« previous | Monday, January 31, 2011 | next »

Tautology

A proposition $p$ is called a tautology iff v[[p]] = T for all evalaluations

Example

Show that (a → b) ↔ (¬a ∨ b) is a tautology:

a	b	a → b	¬a ∨ b	(a → b) ↔ (¬a ∨ b)
F	F	T	T	T
F	T	T	T	T
T	F	F	F	T
T	T	T	T	T

Since all cells under (a → b) &harr (¬a ∨ b) are true, it is a tautology

Satisfiability

Satisfiable

at least one valuation is true

Unsatisfiable

not satisfiable; none evaluate to true'

Example

We claim that (a ⊕ b) → ¬(a ∨ b) is satisfiable:

(a ⊕ b) is false when both are the same, and when the left side of a conditional is false, it evaluates to true

Logical Equivalence

Two formulas are logically equivalent iff they return the same value for all input valuations

We write $p\equiv q$ iff the propositions are logically equivalent

Study Tables 6-8:

Table 6: 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 \mathbf{𝐅}$	Domination laws
$p\vee p\equiv p$ $p\wedge p\equiv p$	Idempotent laws
$\mathrm{\neg }(\mathrm{\neg }p)\equiv p$	Double negation laws
$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

Table 7: Logical Equivalences Involving Conditional Statements

$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 r)\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$

Table 8: Logical Equivalences Involving Biconditionals

$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$