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 ≤ c2
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, c2 = 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.

Feedback?
0
0