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 {T} \equiv p$ $p\vee \mathbf {F} \equiv p$	Identity laws
$p\vee \mathbf {T} \equiv \mathbf {T}$ $p\wedge \mathbf {F} \equiv \mathbf {F}$	Domination laws
$p\vee p\equiv p$ $p\wedge p\equiv p$	Idempotent laws
$\neg (\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
$\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

Table 7: Logical Equivalences Involving Conditional Statements

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

Table 8: Logical Equivalences Involving Biconditionals

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