Mathematical Logic

Introduction to Mathematical Logic Section

Mathematical logic studies the principles of reasoning and provides a rigorous framework to analyze the structure of statements and arguments. It begins with the basics of propositional logic, where statements are combined using logical operators like and, or, and not, to form compound statements and evaluate their truth.

A deeper layer is predicate logic, which extends propositional logic by introducing quantifiers like for all and there exists, allowing reasoning about objects and their properties. Central to this is the concept of logical validity, which examines whether conclusions follow from premises regardless of specific interpretations.

Mathematical logic also explores formal systems, which consist of axioms, rules of inference, and symbols for constructing proofs. Key topics include set theory, the foundation of mathematics, and model theory, which studies the relationship between formal languages and their interpretations.

Another significant area is computability theory, which asks fundamental questions about what problems can be solved by algorithms, and proof theory, which investigates the nature and structure of mathematical proofs.

Applications of mathematical logic are vast, influencing fields like computer science, where it underpins algorithms and programming languages, and philosophy, where it sharpens reasoning. It develops skills in abstraction, critical thinking, and formal reasoning, making it a cornerstone of mathematical rigor.

Mathematical Logic Formulas

The Mathematical Logic Formulas page presents essential logical laws, rules, and principles organized in five main categories: Logical Equivalences, De Morgans Laws, Logical Laws, Quantifier Rules, and Inference Rules. It covers fundamental concepts from basic logical operations like conjunction and disjunction to advanced topics like quantifiers and inference rules. Each formula includes detailed explanations, symbolic notation, real-world examples, and practical applications.

Idempotent Law for Conjunction

P \land P \equiv P

Idempotent Law for Disjunction

P \lor P \equiv P

Commutative Law for Conjunction

P \land Q \equiv Q \land P

Commutative Law for Disjunction

P \lor Q \equiv Q \lor P

Associative Law for Conjunction

(P \land Q) \land R \equiv P \land (Q \land R)

Associative Law for Disjunction

(P \lor Q) \lor R \equiv P \lor (Q \lor R)

Distributive Law of Conjunction over Disjunction

P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)

Distributive Law of Disjunction over Conjunction

P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)

Identity Law for Conjunction

P \land \top \equiv P

Identity Law for Disjunction

P \lor \bot \equiv P

Domination Law for Conjunction

P \land \bot \equiv \bot

Domination Law for Disjunction

P \lor \top \equiv \top

Law of Excluded Middle

P \lor \neg P \equiv \top

Law of Non Contradiction

P \land \neg P \equiv \bot

Double Negation Law

\neg(\neg P) \equiv P

De Morgan Law for Conjunction

\neg(P \land Q) \equiv \neg P \lor \neg Q

De Morgan Law for Disjunction

\neg(P \lor Q) \equiv \neg P \land \neg Q

Absorption Conjunction Form

P \land (P \lor Q) \equiv P

Absorption Disjunction Form

P \lor (P \land Q) \equiv P

Redundancy Law for Disjunction

P \lor (Q \lor P) \equiv P \lor Q

Redundancy Law for Conjunction

P \land (Q \land P) \equiv P \land Q

Disjunction Introduction

P \to (P \lor Q)

Conjunction Elimination

(P \land Q) \to P

Material Implication

P \to Q \equiv \neg P \lor Q

Contrapositive Equivalence

P \to Q \equiv \neg Q \to \neg P

Negation of a Conditional

\neg(P \to Q) \equiv P \land \neg Q

Exportation

(P \land Q) \to R \equiv P \to (Q \to R)

Biconditional as Two Conditionals

P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)

Biconditional as Disjunction of Conjunctions

P \leftrightarrow Q \equiv (P \land Q) \lor (\neg P \land \neg Q)

Negation of a Biconditional

\neg(P \leftrightarrow Q) \equiv (P \land \neg Q) \lor (\neg P \land Q)

Negation of Tautology

\neg \top \equiv \bot

Negation of Contradiction

\neg \bot \equiv \top

Idempotent Law for Conjunction

P \land P \equiv P

Idempotent Law for Disjunction

P \lor P \equiv P

Commutative Law for Conjunction

P \land Q \equiv Q \land P

Commutative Law for Disjunction

P \lor Q \equiv Q \lor P

Associative Law for Conjunction

(P \land Q) \land R \equiv P \land (Q \land R)

Associative Law for Disjunction

(P \lor Q) \lor R \equiv P \lor (Q \lor R)

Distributive Law of Conjunction over Disjunction

P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)

Distributive Law of Disjunction over Conjunction

P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)

Identity Law for Conjunction

P \land \top \equiv P

Identity Law for Disjunction

P \lor \bot \equiv P

Domination Law for Conjunction

P \land \bot \equiv \bot

Domination Law for Disjunction

P \lor \top \equiv \top

Law of Excluded Middle

P \lor \neg P \equiv \top

Law of Non Contradiction

P \land \neg P \equiv \bot

Double Negation Law

\neg(\neg P) \equiv P

De Morgan Law for Conjunction

\neg(P \land Q) \equiv \neg P \lor \neg Q

De Morgan Law for Disjunction

\neg(P \lor Q) \equiv \neg P \land \neg Q

Absorption Conjunction Form

P \land (P \lor Q) \equiv P

Absorption Disjunction Form

P \lor (P \land Q) \equiv P

Redundancy Law for Disjunction

P \lor (Q \lor P) \equiv P \lor Q

Redundancy Law for Conjunction

P \land (Q \land P) \equiv P \land Q

Disjunction Introduction

P \to (P \lor Q)

Conjunction Elimination

(P \land Q) \to P

Material Implication

P \to Q \equiv \neg P \lor Q

Contrapositive Equivalence

P \to Q \equiv \neg Q \to \neg P

Negation of a Conditional

\neg(P \to Q) \equiv P \land \neg Q

Exportation

(P \land Q) \to R \equiv P \to (Q \to R)

Biconditional as Two Conditionals

P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)

Biconditional as Disjunction of Conjunctions

P \leftrightarrow Q \equiv (P \land Q) \lor (\neg P \land \neg Q)

Negation of a Biconditional

\neg(P \leftrightarrow Q) \equiv (P \land \neg Q) \lor (\neg P \land Q)

Negation of Tautology

\neg \top \equiv \bot

Negation of Contradiction

\neg \bot \equiv \top

See All Formulas

Learn More

Logic Terms and Definitions

Proposition

A declarative statement that carries exactly one truth value: true or false, but not both

Elementary Proposition

An atomic, indivisible statement $P$ that cannot be broken into simpler logical components

Compound Proposition

A proposition built by combining simpler propositions using logical connectives: $\varphi := P \circ Q$ where $\circ \in \{\land, \lor, \to, \leftrightarrow, \neg\}$

Well-Formed Formula (WFF)

An expression constructed according to the formation rules of propositional logic, ensuring unambiguous syntactic structure

Literal

An atomic proposition or its negation: $P$ (positive literal) or $\neg P$ (negative literal)

Logical Connective

An operator that combines or modifies propositions to form compound propositions: $\neg$, $\land$, $\lor$, $\to$, $\leftrightarrow$

Negation

A unary connective $\neg P$ that reverses the truth value of $P$

Conjunction

A binary connective $P \land Q$ that is true only when both $P$ and $Q$ are true

Disjunction

A binary connective $P \lor Q$ that is true when at least one of $P$ or $Q$ is true

Disjunctive Normal Form (DNF)

A formula expressed as a disjunction of conjunctions of literals: $(L_1 \land L_2) \lor (L_3 \land L_4) \lor \ldots$

Conjunctive Normal Form (CNF)

A formula expressed as a conjunction of disjunctions of literals: $(L_1 \lor L_2) \land (L_3 \lor L_4) \land \ldots$

Conditional (Implication)

$P \to Q$: false only when $P$ is true and $Q$ is false; true in all other cases

Biconditional

$P \leftrightarrow Q$: true when $P$ and $Q$ share the same truth value, equivalent to $(P \to Q) \land (Q \to P)$

Antecedent

In a conditional $P \to Q$, the antecedent is $P$ — the hypothesis or "if" part

Consequent

In a conditional $P \to Q$, the consequent is $Q$ — the conclusion or "then" part

Converse

The converse of $P \to Q$ is $Q \to P$ — the conditional with antecedent and consequent swapped

Contrapositive

The contrapositive of $P \to Q$ is $\neg Q \to \neg P$ — always logically equivalent to the original

Inverse (of Conditional)

The inverse of $P \to Q$ is $\neg P \to \neg Q$ — not logically equivalent to the original

Logical Equivalence

Two formulas $\varphi$ and $\psi$ are logically equivalent ($\varphi \equiv \psi$) if they have identical truth values under every possible assignment

Tautology

A formula $\varphi$ that evaluates to true under every possible truth assignment. Notation: $\models \varphi$ or $\varphi \equiv \top$

Contradiction

A formula $\varphi$ that evaluates to false under every possible truth assignment. Notation: $\varphi \equiv \bot$

Contingency

A formula that is neither a tautology nor a contradiction — it is true under some assignments and false under others

Satisfiability

A formula $\varphi$ is satisfiable if there exists at least one truth assignment under which $\varphi$ evaluates to true

Truth Table

A tabular listing of all possible truth value combinations for a formula's variables and the resulting truth value of the formula

Assignment (Valuation)

A function $v$ that maps each propositional variable to a truth value: $v: \{P, Q, R, \ldots\} \to \{T, F\}$

Absorption

$P \land (P \lor Q) \equiv P$ and $P \lor (P \land Q) \equiv P$

Law of Excluded Middle

$P \lor \neg P$ is always true — every proposition is either true or false, with no third option

Non-contradiction

$\neg(P \land \neg P)$ is always true — no proposition can be simultaneously true and false

Proposition

A declarative statement that carries exactly one truth value: true or false, but not both

Elementary Proposition

An atomic, indivisible statement $P$ that cannot be broken into simpler logical components

Compound Proposition

A proposition built by combining simpler propositions using logical connectives: $\varphi := P \circ Q$ where $\circ \in \{\land, \lor, \to, \leftrightarrow, \neg\}$

Well-Formed Formula (WFF)

An expression constructed according to the formation rules of propositional logic, ensuring unambiguous syntactic structure

Literal

An atomic proposition or its negation: $P$ (positive literal) or $\neg P$ (negative literal)

Logical Connective

An operator that combines or modifies propositions to form compound propositions: $\neg$, $\land$, $\lor$, $\to$, $\leftrightarrow$

Negation

A unary connective $\neg P$ that reverses the truth value of $P$

Conjunction

A binary connective $P \land Q$ that is true only when both $P$ and $Q$ are true

Disjunction

A binary connective $P \lor Q$ that is true when at least one of $P$ or $Q$ is true

Disjunctive Normal Form (DNF)

A formula expressed as a disjunction of conjunctions of literals: $(L_1 \land L_2) \lor (L_3 \land L_4) \lor \ldots$

Conjunctive Normal Form (CNF)

A formula expressed as a conjunction of disjunctions of literals: $(L_1 \lor L_2) \land (L_3 \lor L_4) \land \ldots$

Conditional (Implication)

$P \to Q$: false only when $P$ is true and $Q$ is false; true in all other cases

Biconditional

$P \leftrightarrow Q$: true when $P$ and $Q$ share the same truth value, equivalent to $(P \to Q) \land (Q \to P)$

Antecedent

In a conditional $P \to Q$, the antecedent is $P$ — the hypothesis or "if" part

Consequent

In a conditional $P \to Q$, the consequent is $Q$ — the conclusion or "then" part

Converse

The converse of $P \to Q$ is $Q \to P$ — the conditional with antecedent and consequent swapped

Contrapositive

The contrapositive of $P \to Q$ is $\neg Q \to \neg P$ — always logically equivalent to the original

Inverse (of Conditional)

The inverse of $P \to Q$ is $\neg P \to \neg Q$ — not logically equivalent to the original

Logical Equivalence

Two formulas $\varphi$ and $\psi$ are logically equivalent ($\varphi \equiv \psi$) if they have identical truth values under every possible assignment

Tautology

A formula $\varphi$ that evaluates to true under every possible truth assignment. Notation: $\models \varphi$ or $\varphi \equiv \top$

Contradiction

A formula $\varphi$ that evaluates to false under every possible truth assignment. Notation: $\varphi \equiv \bot$

Contingency

A formula that is neither a tautology nor a contradiction — it is true under some assignments and false under others

Satisfiability

A formula $\varphi$ is satisfiable if there exists at least one truth assignment under which $\varphi$ evaluates to true

Truth Table

A tabular listing of all possible truth value combinations for a formula's variables and the resulting truth value of the formula

Assignment (Valuation)

A function $v$ that maps each propositional variable to a truth value: $v: \{P, Q, R, \ldots\} \to \{T, F\}$

Absorption

$P \land (P \lor Q) \equiv P$ and $P \lor (P \land Q) \equiv P$

Law of Excluded Middle

$P \lor \neg P$ is always true — every proposition is either true or false, with no third option

Non-contradiction

$\neg(P \land \neg P)$ is always true — no proposition can be simultaneously true and false

See All Definitions

The Logic Terms and Definitions page presents key concepts and terminology organized in multiple categories including Logic Basics, Reasoning, Formal Logic, Proof Methods, Logical Principles, and Structures. It covers fundamental concepts like propositions and predicates, reasoning methods, formal systems, and proof techniques. Each term is clearly defined to help understand the building blocks of mathematical logic and logical reasoning.

Learn More

Propositional Logic

Propositional logic, also known as propositional calculus or sentential logic, forms a foundational sub-field of mathematical logic along with other sub-fields such as first-order logic, higher-order logic, modal logic, intuitionistic logic, temporal logic, set theory, model theory, proof theory, and recursion theory.
Propositional logic provides a formal system for representing and analyzing statements that are either true or false.

It includes:

•
Syntax:
The formal structure including propositions (typically represented by variables like p, q, r) and logical connectives (AND, OR, NOT, implies, etc.)
•
Semantics:
How we determine truth values using truth tables, and identifying tautologies (always true) and contradictions (always false)
•
Equivalences:
Laws like De Morgan's laws, distributive laws, and other equivalences that allow for simplification.
However, not all logical equivalences are laws. Some are specific derivations that are still true but are not considered "fundamental" enough to be named as laws.
All laws are logical equivalences, but not all logical equivalences are laws.
Laws are fundamental, while other equivalences may be derived, conditional, or context-dependent.
Learn more about basic laws of propositional logic and other equivalences.
•
Inference Rules:
Formal rules such as modus ponens, modus tollens, and others that allow for step-by-step proofs
•
Normal Forms:
Standard ways to represent logical formulas, like conjunctive normal form (CNF) and disjunctive normal form (DNF)
•
Proof Techniques:
Methods like proof by contradiction, direct proof, and truth tables to establish the validity of arguments
•
Truth tables:
Truth tables are primarily used in sentential logic to determine the truth values of logical expressions based on their components.
•
Applications:
Propositional logic is indeed widely used in computer science (for circuit design, program verification), artificial intelligence (knowledge representation, automated reasoning), philosophy (formal analysis of arguments), and many other fields

The study of propositional logic establishes the foundation for more complex logical systems while providing essential tools for formal reasoning across numerous disciplines.

Learn More

Tools

Truth Tables Generator

Build custom truth tables for any logical expression. Enter your own propositions and operators to dynamically generate complete truth tables with step-by-step evaluation.

Try it

Logic Symbols Reference

Our Mathematical Logic Symbols page provides a comprehensive collection of symbols essential for working with formal logic systems. This reference includes detailed categorization of symbols across multiple domains of mathematical logic.
Explore symbols organized by functional categories including logical operations (¬, ∧, ∨), quantifiers (∀, ∃), set operations (∈, ⊆, ∩), relation symbols (=, ≠, ≤), and specialized notation systems. The page features both basic symbols like implication (→) and biconditional (↔), as well as advanced concepts from temporal modal logic (□, ◇), type theory and lambda calculus (λ, ≡).
Each symbol is presented with its corresponding LaTeX code and a brief explanation of its meaning and usage, making this an invaluable resource for students, educators, and professionals working with mathematical proofs, set theory, or formal logic systems.

Learn More