Discrete Math Laws

DeMorgan's Laws

¬(p ∧ q) ⇔ ¬p ∨ ¬q

¬(p ∨ q) ⇔ ¬p ∧ ¬q

Double Negation Law

¬[¬p] ⇔ p

Implication Law

p → q ⇔ ¬p ∨ q

Contrapositive

p → q ⇔ ¬q → ¬p

Negation of Implication

¬(p → q) ⇔ p ∧ ¬q

Identity Laws

p ∨ F ⇔ p

p ∧ T ⇔ p

Commutative Laws

p ∨ q ⇔ q ∨ p

p ∧ q ⇔ q ∧ p

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)

Domination Laws

p ∨ T ⇔ T

p ∧ F ⇔ F

Idempotent Laws

p ∨ p ⇔ p

p ∧ p ⇔ p

Absorption Laws

p ∧ (p ∨ q) ⇔ p

p ∨ (p ∧ q) ⇔ p

Tautology

p ∨ ¬p ⇔ T

Contradiction

p ∧ ¬p ⇔ F

Equivalence

(p → q) ∧ (q → p) ⇔ (p ↔ q)

Modus Ponens

p

p → q

------------

q

Disjunction Introduction

p

------------

p ∨ q

Conjunction Elimination

p ∧ q

------------

p

Conjunction Elimination

p ∧ q

------------

q

Modus Tollens

¬q

p → q

------------

¬p

Hypothetical Syllogism

p → q

q → r

------------

p → r

Disjunctive Syllogism

p ∨ q

¬p

------------

q

Disjunctive Syllogism

p ∨ q

¬q

------------

p

Conjunction Introduction

p

q

------------

p ∧ q

Constructive Dilemma

(p → q) ∧ (r → s)

p ∨ r

------------

q ∨ s

Universal Instantiation

∀xP(x)

------------

P(c)

Universal Generalization

P(c) for arbitrary member, c, of the universe

------------

∀xP(x)

Existential Generalization

P(c) for some member, c, of the universe

------------

∃xP(x)

Existential Instantiation

∃xP(x)

------------

P(c)

Fallacy of the converse

p → q

q

------------

p

Fallacy of the inverse

p → q

¬p

------------

¬q

Disjunctive Fallacies

p ∨ q

p

------------

¬q

Disjunctive Fallacies

p ∨ q

q

------------

¬p

False Chains

p → q

p → r

------------

q → r

False Chains

p → q

r → q

------------

p → r