Mathematical Logic

Logical Equivalence

E₁: Idempotence

P∨P ⇔ P

P∧P ⇔ P

E₂: Double negative elimination

¬¬P ⇔ P

E₃: Commutativity

P∧Q ⇔ Q∧P

P∨Q ⇔ Q∨P

E₄: Associativity

(P∧Q)∧R ⇔ P∧(Q∧R)

(P∨Q)∨R ⇔ P∨(Q∨R)

E₅: Distributivity

P∧(Q∨R) ⇔ (P∧R)∨(Q∧R)

P∨(Q∧R) ⇔ (P∨R)∧(Q∨R)

E₆: Reflexivity

P∧T ⇔ P

P∨F ⇔ P

E₇:  

P∧F ⇔ F

P∨T ⇔ T

E₈:  

P∧¬P ⇔ F

P∨¬P ⇔ T

E₉: De Morgan’s law

¬(P∧Q) ⇔ ¬P∨¬Q

¬(P∨Q) ⇔ ¬P∧¬Q

E₁₀:  

P∨(P∧Q) ⇔ P

P∧(P∨Q) ⇔ P

E₁₁

P→Q ⇔ ¬P∨Q

¬(P→Q) ⇔ P∧¬Q

E₁₂

P→Q ⇔ ¬Q→¬P

E₁₃

P→(Q→R) ⇔ (P∧Q)→R

E₁₄

(P→Q)∧(P→R) ⇔ P→(Q∧R)

E₁₅

¬(P⇌Q) ⇔ P⇌¬Q

E₁₆

P⇌Q ⇔ (P→Q)∧(Q→P)

P⇌Q ⇔ (P∧Q)∨(¬P∧¬Q)

E₁₇:  

∃x:(A(x)∨B(x)) ⇔ (∃x:A(x))∨(∃x:B(x))

∀x:(A(x)∧B(x)) ⇔ (∀x:A(x))∧(∀x:B(x))

E₁₈:  

¬∃x:A(x) ⇔ ∀x:¬A(x)

¬∀x:A(x) ⇔ ∃x:¬A(x)

E₁₉:  

∀x:(A∧B(x)) ⇔ A∧(∀x:B(x))

∀x:(A∨B(x)) ⇔ A∨(∀x:B(x))

∃x:(A∧B(x)) ⇔ A∧(∃x:B(x))

∃x:(A∨B(x)) ⇔ A∨(∃x:B(x))

E₂₀

(∀x:A(x))→B ⇔ ∃x:(A(x)→B)

(∃x:A(x))→B ⇔ ∀x:(A(x)→B)

A→(∀x:B(x)) ⇔ ∀x:(A→B(x))

A→(∃x:B(x)) ⇔ ∃x:(A→B(x))

EE₁

∀x∀y:P(x,y) ⇔ ∀y∀x:P(x,y)

∃x∃y:P(x,y) ⇔ ∃y∃x:P(x,y)