Logic law

A logic law, or law of propositional logic, is a known logical equivalence. Since propositions can be substituted for one another if they are logically equivalent, logic laws come in handy when making logical proofs. Here's a list of logic laws for your reference:

De Morgan's laws	$\lnot (p \lor q) \equiv \lnot p \land \lnot q$ $\lnot \forall x P(x) \equiv \exists x \lnot P(x)$	$\lnot (p \land q) \equiv \lnot p \lor \lnot q$ $\lnot \exists x P(x) \equiv \forall x \lnot P(x)$
Idempotent laws	$p \lor p \equiv p$	$p \land p \equiv p$
Associative laws	$(p \lor q) \lor r \equiv p \lor (q \lor r)$	$(p \land q) \land r \equiv p \land (q \land r)$
Commutative laws	$p \lor q \equiv q \lor p$	$p \land q \equiv q \land p$
Distributive laws	$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
Identity laws	$p \lor 0 \equiv p$	$p \land 1 \equiv p$
Domination laws	$p \land 0 \equiv 0$	$p \lor 1 \equiv 1$
Double negation law	$\lnot \lnot p \equiv p$
Complement laws	$p \land \lnot p \equiv 0$ $\lnot 1 \equiv 0$	$p \lor \lnot p \equiv 1$ $\lnot 0 \equiv 1$
Absorption laws	$p \lor (p \land q) \equiv p$	$p \land (p \lor q) \equiv p$
Conditional identities	$p \rightarrow q \equiv \lnot p \lor q$	$p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$

⚠ In the table, $p$ and $q$ represent any compound proposition, so don't assume that you must be working with individual propositions in order to use the logic laws! Just keep an eye out for the distinct patterns of surrounding logical operations that match a logic law.

Contents

De Morgan's laws

De Morgan's laws state that the negation of a disjunction is the conjunction of the negations, and the negation of a conjunction is the disjunction of the negations.

$$\lnot (p \lor q) \equiv \lnot p \land \lnot q$$ $$\lnot (p \land q) \equiv \lnot p \lor \lnot q$$

For quantified statements, the negation of a universal statement is its existentially quantified negation, and the negation of an existential statement is its universally quantified negation.

$$\lnot \forall x P(x) \equiv \exists x \lnot P(x)$$ $$\lnot \exists x P(x) \equiv \forall x \lnot P(x)$$

If you need more convincing, first assume the domain of $x$ is finite. Then, quantified statements can be written as:

$$\forall x P(x) \equiv P(a_1) \land ... \land P(a_n)$$ $$\exists x P(x) \equiv P(a_1) \lor ... \lor P(a_n)$$

Negating both of these logical equivalences gives:

$$\lnot \forall x P(x) \equiv \lnot P(a_1) \lor ... \lor \lnot P(a_n)$$ $$\lnot \exists x P(x) \equiv \lnot P(a_1) \land ... \land \lnot P(a_n)$$

Finally, by recognizing the pattern and recalling the logical equivalences from the first step:

$$\lnot \forall x P(x) \equiv \exists x \lnot P(x)$$ $$\lnot \exists x P(x) \equiv \forall x \lnot P(x)$$

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort

De Morgan's laws	\(\lnot (p \lor q) \equiv \lnot p \land \lnot q\) \(\lnot \forall x P(x) \equiv \exists x \lnot P(x)\)	\(\lnot (p \land q) \equiv \lnot p \lor \lnot q\) \(\lnot \exists x P(x) \equiv \forall x \lnot P(x)\)
Idempotent laws	\(p \lor p \equiv p\)	\(p \land p \equiv p\)
Associative laws	\((p \lor q) \lor r \equiv p \lor (q \lor r)\)	\((p \land q) \land r \equiv p \land (q \land r)\)
Commutative laws	\(p \lor q \equiv q \lor p\)	\(p \land q \equiv q \land p\)
Distributive laws	\(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)	\(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
Identity laws	\(p \lor 0 \equiv p\)	\(p \land 1 \equiv p\)
Domination laws	\(p \land 0 \equiv 0\)	\(p \lor 1 \equiv 1\)
Double negation law	\(\lnot \lnot p \equiv p\)
Complement laws	\(p \land \lnot p \equiv 0\) \(\lnot 1 \equiv 0\)	\(p \lor \lnot p \equiv 1\) \(\lnot 0 \equiv 1\)
Absorption laws	\(p \lor (p \land q) \equiv p\)	\(p \land (p \lor q) \equiv p\)
Conditional identities	\(p \rightarrow q \equiv \lnot p \lor q\)	\(p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)\)