Mathematical Logic

Master propositional logic, truth tables, Boolean algebra, and predicate calculus—the foundation of mathematics, computer science, and rational reasoning

What is Mathematical Logic?

Mathematical logic is the formal study of reasoning, inference, and proof using symbolic notation and rigorous mathematical methods—it provides the foundational framework for determining truth, validity, and logical consequence in mathematical statements, transforming intuitive reasoning into precise, verifiable arguments that can be mechanically checked for correctness.

Originating from the work of George Boole (1815-1864), Gottlob Frege (1848-1925), and Bertrand Russell (1872-1970), mathematical logic revolutionized mathematics by treating logic itself as a mathematical object—this formalization enabled the rigorous analysis of mathematical foundations, resolved paradoxes in set theory, and ultimately led to the development of computer science through Alan Turing's work on computability.

Modern mathematical logic consists of four major branches: propositional logic (dealing with compound statements), predicate logic (involving quantifiers and variables), set theory (foundational to all mathematics), and model theory (studying interpretations of formal systems)—these tools underpin everything from database queries and circuit design to artificial intelligence and automated theorem proving.

🔷 Propositional Logic (Sentential Calculus)

Propositional logic is the simplest form of formal logic, dealing with propositions (statements that are either true or false) and logical connectives that combine them—it forms the foundation for all other logical systems and provides the basic tools for mathematical reasoning.

Logical Operators (Connectives)

1. Negation (NOT) — ¬ or ~

Reverses the truth value of a proposition

¬P or ~P

If P is true, ¬P is false; if P is false, ¬P is true

2. Conjunction (AND) — ∧

True only when both propositions are true

P ∧ Q

Example: "It is raining AND it is cold"

3. Disjunction (OR) — ∨

True when at least one proposition is true

P ∨ Q

Example: "I will study math OR physics"

4. Implication (IF...THEN) — →

False only when hypothesis is true and conclusion is false

P → Q

Example: "If it rains, then the ground is wet"

5. Biconditional (IF AND ONLY IF) — ↔

True when both propositions have the same truth value

P ↔ Q

Equivalent to: (P → Q) ∧ (Q → P)

📊 Truth Tables

A truth table is a mathematical tool that systematically displays all possible truth values for a logical expression based on every combination of truth values for its component propositions—invented by Ludwig Wittgenstein and Emil Post in the 1920s, truth tables provide a mechanical method for determining the validity of logical arguments and the equivalence of logical expressions.

Truth Table Construction Rules

Number of Rows: 2ⁿ where n = number of distinct propositional variables

• 1 variable = 2¹ = 2 rows

• 2 variables = 2² = 4 rows

• 3 variables = 2³ = 8 rows

• n variables = 2ⁿ rows

Complete Truth Tables for Logical Operators

P	Q	¬P	P ∧ Q	P ∨ Q	P → Q	P ↔ Q
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

🔍 Key Observation:

The implication P → Q is false only when P is true and Q is false (the hypothesis is true but conclusion fails). This counter-intuitive behavior means "if false, then anything" is considered true in classical logic.

⚖️ Fundamental Logical Equivalences

Logical equivalences are formulas that always have the same truth value regardless of the truth values of their component propositions—these equivalences form the foundation for logical reasoning, proof techniques, and simplification of complex logical expressions.

De Morgan's Laws

¬(P ∧ Q) ≡ ¬P ∨ ¬Q

¬(P ∨ Q) ≡ ¬P ∧ ¬Q

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)

Identity Laws

P ∧ T ≡ P

P ∨ F ≡ P

(T = always true, F = always false)

Implication Equivalence

P → Q ≡ ¬P ∨ Q

Critical for converting implications to disjunctions

🔶 Predicate Logic and Quantifiers

Predicate logic extends propositional logic by introducing predicates (properties or relations), variables, and quantifiers—this powerful extension enables us to express statements about individuals and groups, reason about properties of objects, and formalize mathematical statements that propositional logic cannot handle.

Predicates and Variables

A predicate is a statement containing variables that becomes a proposition when specific values are substituted:

P(x): "x is greater than 5"

• P(7) is TRUE (7 > 5)

• P(3) is FALSE (3 is not > 5)

• P(x) itself is not a proposition—it has no truth value until x is specified

Universal Quantifier (∀)

∀x P(x)

Meaning: "For all x, P(x) is true" or "Every x has property P"

Examples:

• ∀x (x² ≥ 0) — "All real numbers squared are non-negative" (TRUE)

• ∀n (n is even) — "All integers are even" (FALSE)

• ∀x ∀y (x + y = y + x) — "Addition is commutative" (TRUE)

Negation Rule:

¬(∀x P(x)) ≡ ∃x ¬P(x)

"Not all x have property P" means "There exists an x without property P"

Existential Quantifier (∃)

∃x P(x)

Meaning: "There exists an x such that P(x) is true" or "At least one x has property P"

Examples:

• ∃x (x² = 9) — "There exists a number whose square is 9" (TRUE: x = 3 or -3)

• ∃n (n is prime and n is even) — "There exists an even prime" (TRUE: n = 2)

• ∃x (x + 5 = 0) — "There exists x where x + 5 = 0" (TRUE: x = -5)

Negation Rule:

¬(∃x P(x)) ≡ ∀x ¬P(x)

"No x has property P" means "All x lack property P"

🔢 Boolean Algebra

Boolean algebra, developed by George Boole in 1854, is the algebra of truth values where variables can only be 0 (false) or 1 (true)—this system forms the mathematical foundation of digital electronics, computer circuits, database queries, and programming logic.

Boolean Operations in Digital Form

Operation	Logic Symbol	Boolean Symbol	Example
NOT	¬A	Ā or A'	¬1 = 0, ¬0 = 1
AND	A ∧ B	A · B or AB	1 · 1 = 1, others = 0
OR	A ∨ B	A + B	0 + 0 = 0, others = 1
XOR	A ⊕ B	A ⊕ B	1 if different, 0 if same

Key Boolean Algebra Laws

Absorption Laws:

A + AB = A

A(A + B) = A

Double Negation:

¬(¬A) = A

Ā̄ = A

Complement Laws:

A + Ā = 1

A · Ā = 0

🌐 Applications of Mathematical Logic

💻

Computer Science

Logic circuits, CPU design, programming languages, algorithm correctness proofs, database query optimization, artificial intelligence reasoning systems, and compiler design all fundamentally rely on mathematical logic.

🔧

Digital Electronics

Every digital device from smartphones to supercomputers uses Boolean logic gates (AND, OR, NOT, NAND, NOR) as fundamental building blocks—billions of transistors implement these logic operations in microprocessors.

📚

Mathematics

Formal proofs, theorem proving, axiomatic systems, set theory foundations, and mathematical reasoning all depend on logical inference rules—logic ensures mathematical arguments are rigorous and verifiable.

🤖

Artificial Intelligence

Expert systems, automated reasoning, knowledge representation, natural language processing, and theorem provers use predicate logic to encode knowledge and perform logical inference to solve problems.

🗄️

Database Systems

SQL queries use predicate logic—SELECT statements with WHERE clauses are logical formulas, JOIN operations combine predicates, and query optimization applies logical equivalences to improve performance.

⚖️

Philosophy & Law

Philosophical arguments, legal reasoning, logical fallacy detection, and argument analysis all employ formal logic to evaluate validity, identify inconsistencies, and construct sound reasoning chains.

⚠️ Key Concepts to Master

🎯 Tautologies and Contradictions:

A tautology is a formula that is always true regardless of truth value assignments (e.g., P ∨ ¬P), while a contradiction is always false (e.g., P ∧ ¬P). Tautologies represent logical truths, and recognizing them is essential for proof techniques like proof by contradiction.

🔄 Logical Equivalence vs Implication:

Two formulas are logically equivalent (P ≡ Q) if they have identical truth values in all cases—this is stronger than implication. P → Q means "P implies Q" (Q is true whenever P is true), while P ≡ Q means mutual implication: (P → Q) ∧ (Q → P).

📝 Quantifier Scope and Order:

Quantifier order matters! ∀x ∃y P(x,y) means "for every x, there exists a y" (possibly different y for each x), while ∃y ∀x P(x,y) means "there exists one y that works for all x"—these statements can have completely different truth values.

🔗 Modus Ponens and Modus Tollens:

Two fundamental inference rules: Modus Ponens states that from P → Q and P, we can deduce Q. Modus Tollens states that from P → Q and ¬Q, we can deduce ¬P. These rules form the basis of formal proofs and logical reasoning in mathematics.

About the Author

Adam

Co-Founder @RevisionTown

Math Expert specializing in diverse international curricula including IB (International Baccalaureate), AP (Advanced Placement), GCSE, IGCSE, and various other educational programs worldwide.

Connect on LinkedIn