Propositional Equivalences

Tautology

A compound proposition that is always true.

Contradiction

A compound proposition that is always false

Contingency

A compound proposition that is neither a tautology nor a contradiction.

Logical Equivalences

Compound proposition that have the same truth values in all possible cases. Means, compound propositions p and q are called logically equivalent if p ↔ q is a tautology.

Example of Tautology and Contradiction

p	q	p∨ -p	p ∧ -p
T	T	T	F
F	F	T	F

*p ∨-q is always true

*p ∧-q is always false

Logical equivalences tables

Name	Equivalence
Identity Laws	p ∧ T ≡ p p ∨ F ≡ p
Domination Laws	p ∨ T ≡ T p ∧ F ≡ F
Idempotent Laws	p ∨ p ≡ p p ∧ p ≡ p
Negation Laws	p ∨¬p ≡ T p ∧¬p ≡ F
Double Negation Law	¬(¬p) ≡ p
Commutative Law	p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p
Absorption Law	p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
De Morgan’s Laws	¬(p ∧ q) ≡¬p ∨¬q ¬(p ∨ q) ≡¬p ∧¬q
Associative Laws	(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributive laws	p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

*T = Compound proposition is always true

*F = Compound proposition is always false

Logical Equivalences involving Conditional Statements

p → q ≡ ¬p ∨ q

p → q ≡ ¬q →¬p

p ∨ q ≡¬p → q

p ∧ q ≡¬(p →¬q)

¬(p → q) ≡ p ∧¬q

(p → q) ∧ (p → r) ≡ p → (q ∧ r)

(p → r) ∨ (q → r) ≡ (p ∧ q) → r

(p → q) ∨ (p → r) ≡ p → (q ∨ r)

(p → q) ∧ (p → r) ≡ p → (q ∧ r)

  

Logical Equivalences involving Biconditional Statements

p ↔ q ≡ ¬p ↔¬q

¬(p ↔ q) ≡ p ↔¬q

p ↔ q ≡ (p ∧ q) ∨ (¬p ∧¬q)

p ↔ q ≡ (p → q) ∧ (q → p)

Example Logical Equivalent.

Shows that are logical equivalents.

Double Negation Law ¬(¬p) ≡ p

p	-p	-(-p)
T	F	T
F	T	F

Commutative Law p ∨ q ≡ q ∨ p

p	q	p ∨ q	q ∨ p
T	T	T	T
T	F	T	T
F	T	T	T
F	F	F	F

Associative Law (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

p	q	r	(p ∨ q)	(p ∨ q) ∨ r	(q ∨ r)	p ∨ (q ∨ r)
T	T	T	T	T	T	T
T	T	F	T	T	T	T
T	T	T	T	T	T	T
T	T	F	T	T	F	T
F	F	T	T	T	T	T
F	F	F	T	T	T	T
F	F	T	F	T	T	T
F	F	F	F	F	F	F

Example Logical Equivalent involving Conditional Statement

Shows that are logical equivalents.

¬(p → q) ≡ p ∧¬q

p	q	¬(p → q)	¬q	p ∧¬q
T	T	F	F	F
T	F	T	T	T
F	T	F	F	F
F	F	F	T	F

(p → q) ∨ (p → r) ≡ p → (q ∨ r)

p	q	r	(p → q)	(p → r)	(p → q) ∨ (p → r)	(q ∨ r)	p → (q ∨ r)
T	T	T	T	T	T	T	T
T	T	F	T	F	T	T	T
T	F	T	F	T	T	T	T
T	F	F	F	F	F	F	F
F	T	T	T	T	T	T	T
F	T	F	T	T	T	T	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	F	T

Example Logical Equivalent involving Biconditional Statement

p ↔ q ≡ (p → q) ∧ (q → p)

p	q	p ↔ q	p → q	q → p	(p → q) ∧ (q → p)
T	T	T	T	T	T
T	F	F	F	T	F
F	T	F	T	F	F
F	F	T	T	T	T