Updated 2 years ago • 2 min read

Discrete Math Rules—For Your Reference

Below you will find the laws of propositional logic, the rules of inference, and the quantified statements rules of inference presented in a table format.

Laws of Propositional Logic Table
Law Name	Law
De Morgan’s laws:	¬( p ∨ q ) ≡ ¬p ∧ ¬q	¬( p ∧ q ) ≡ ¬p ∨ ¬q
Idempotent laws:	p ∨ p ≡ p	p ∧ p ≡ p
Associative laws:	( p ∨ q ) ∨ r ≡ p ∨ ( q ∨ r )	( p ∧ q ) ∧ r ≡ p ∧ ( q ∧ r )
Commutative laws:	p ∨ q ≡ q ∨ p	p ∧ q ≡ q ∧ p
Distributive laws:	p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r )	p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )
Identity laws:	p ∨ F ≡ p	p ∧ T ≡ p
Domination laws:	p ∧ F ≡ F	p ∨ T ≡ T
Double negation law:	¬¬p ≡ p
Complement laws:	p ∧ ¬p ≡ F ¬T ≡ F	p ∨ ¬p ≡ T ¬F ≡ T
Absorption laws:	p ∨ (p ∧ q) ≡ p	p ∧ (p ∨ q) ≡ p
Conditional identities:	p → q ≡ ¬p ∨ q	p ↔ q ≡ ( p → q ) ∧ ( q → p )

Rules of Inference Table
Rule of inference	Name
p p → q ∴ q	Modus ponens
¬q p → q ∴ ¬p	Modus tollens
p ∴ p ∨ q	Addition
p ∧ q ∴ p	Simplification
p q ∴ p ∧ q	Conjunction
p → q q → r ∴ p → r	Hypothetical syllogism
p ∨ q ¬p ∴ q	Disjunctive syllogism
p ∨ q ¬p ∨ r ∴ q ∨ r	Resolution

Quantified Statements Rules of Inference Table
Rule of Inference	Name	Example
c is an element (arbitrary or particular ∀x P(x) ∴ P(c)	Universal instantiation	Sam is a student in the class. Every student in the class completed the assignment. Therefore, Sam completed his assignment.
c is an arbitrary element P(c) ∴ ∀x P(x)	Universal generalization	Let c be an arbitrary integer. c ≤ c² Therefore, every integer is less than or equal to its square.
∃x P(x) ∴ (c is a particular element) ∧ P(c)	Existential instantiation	There is an integer that is equal to its square. Therefore, c² = c, for some integer c.
c is an element (arbitrary or particular) P(c) ∴ ∃x P(x)	Existential generalization	Sam is a particular student in the class. Sam completed the assignment. Therefore, there is a student in the class who completed the assignment.

30