Mathematical Logic – Comprehensive Formula Sheet

1. Propositional Logic

Syntax

Atoms: Atomic propositions $p, q, r, \ldots$

Connectives:

$\neg p$ (negation)

$p \land q$ (conjunction)

$p \lor q$ (disjunction)

$p \to q$ (implication)

$p \leftrightarrow q$ (biconditional)

Key Formula

$(p \to q) \equiv (\neg p \lor q)$

$(p \leftrightarrow q) \equiv ((p \to q) \land (q \to p))$

Properties

Precedence: $\neg > \land > \lor > \to > \leftrightarrow$

Associativity: $\land, \lor$ are associative

2. Truth Tables

Basic Connectives

$p$	$q$	$\neg p$	$p \land q$	$p \lor q$
T	T	F	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	F

Implication & Biconditional

$p$	$q$	$p \to q$	$p \leftrightarrow q$
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

3. Logical Equivalences

Tautology

Formula true in all interpretations. Ex: $p \lor \neg p$

Contradiction

Formula false in all interpretations. Ex: $p \land \neg p$

Contingency

Formula true in some, false in others. Ex: $p \to q$

Key Laws

De Morgan: $\neg(p \land q) \equiv \neg p \lor \neg q$

Idempotent: $p \land p \equiv p$

Absorption: $p \lor (p \land q) \equiv p$

4. Normal Forms

CNF (Conjunctive)

Conjunction of disjunctions:

$(p \lor q) \land (r \lor s)$

DNF (Disjunctive)

Disjunction of conjunctions:

$(p \land q) \lor (r \land s)$

Conversion

Expand using distributive laws

Apply De Morgan's laws

Remove double negations

Both CNF and DNF are unique canonical forms

5. Proof Systems

Natural Deduction

Modus Ponens: $\phi, \phi \to \psi \vdash \psi$

Modus Tollens: $\phi \to \psi, \neg \psi \vdash \neg \phi$

Hypothetical Syllogism: $\phi \to \psi, \psi \to \chi \vdash \phi \to \chi$

Rules

$\land$-Intro: $\phi, \psi \vdash \phi \land \psi$

$\lor$-Intro: $\phi \vdash \phi \lor \psi$

$\neg$-Intro: $\phi \vdash \bot \Rightarrow \neg \phi$

Symbols

$\vdash$ (provable/derives)

$\bot$ (contradiction/false)

6. Predicate Logic

Components

Predicates: $P(x), Q(x,y)$

Variables: $x, y, z$

Constants: $a, b, c$

Functions: $f(x), g(x,y)$

Quantifiers

$\forall x \, P(x)$ (universal)

$\exists x \, P(x)$ (existential)

Examples

$\forall x(Human(x) \to Mortal(x))$

$\exists x(Prime(x) \land x > 100)$

7. Quantifier Rules

Universal Rules

UI: $\forall x \, \phi(x) \vdash \phi(t)$

UG: $\phi(x) \vdash \forall x \, \phi(x)$

Existential Rules

EI: $\exists x \, \phi(x) \vdash \phi(a)$

EG: $\phi(t) \vdash \exists x \, \phi(x)$

Equivalences

$\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$

$\neg \exists x \, P(x) \equiv \forall x \, \neg P(x)$

8. Bound & Free Variables

Definitions

Bound: Variable within scope of quantifier

Free: Variable not bound by quantifier

Examples

$\forall x \, P(x,y)$ → $x$ bound, $y$ free

$\exists x(Q(x) \land R(x,y))$ → $x$ bound, $y$ free

Closed Formula

No free variables (sentence)

Open Formula

Contains free variables

9. Models & Interpretations

Interpretation

Maps propositions/predicates to truth values in a structure

Structure/Model

Pair $\mathcal{M} = (D, I)$ where:

$D$ = domain (universe of objects)

$I$ = interpretation function

Satisfiability

$\mathcal{M} \models \phi$ (model satisfies $\phi$)

Key Concept

Formula is valid if true in all models

10. Validity & Satisfiability

Valid Formula

True in every interpretation $(\models \phi)$. Same as tautology in propositional logic.

Satisfiable Formula

True in at least one interpretation

Unsatisfiable Formula

False in all interpretations (contradiction)

Logical Consequence

$\Phi \models \psi$ iff every model of $\Phi$ is model of $\psi$

Validity is semantic, provability is syntactic

11. First-Order Theories

Theory

Set $T$ of closed formulas (sentences) in FOL

Examples

PA: Peano Arithmetic

ZFC: Set theory

Group Theory: Axioms of groups

Properties

Consistent: Cannot prove contradiction

Complete: For all $\phi$, either $T \vdash \phi$ or $T \vdash \neg \phi$

Decidable: Algorithm determines if $\phi \in T$

12. Soundness & Completeness

Soundness Theorem

If $T \vdash \phi$, then $T \models \phi$

Proofs only derive true statements

Completeness Theorem

If $T \models \phi$, then $T \vdash \phi$

All true statements are provable

Key Result

$\models \phi \iff \vdash \phi$ (in FOL)

Gödel's completeness theorem (1930)

13. Gödel's Incompleteness

1st Incompleteness

Any consistent formal system $F$ containing arithmetic is incomplete: $\exists \phi$ such that $F \not\vdash \phi$ and $F \not\vdash \neg \phi$

2nd Incompleteness

Consistent system $F$ cannot prove its own consistency $\text{Con}(F)$

Gödel Sentence

Encodes: "This statement is unprovable"

Limits of formal proof systems

14. Compactness Theorem

Statement

If every finite subset of $\Phi$ is satisfiable, then $\Phi$ is satisfiable

Contrapositive

If $\Phi$ is unsatisfiable, some finite subset is unsatisfiable

Application

Relates infinite to finite satisfiability

Consequence

FOL over infinite domains behaves like finite case

Fundamental in model theory

15. Löwenheim-Skolem

Downward Version

If $\Phi$ has infinite model, it has countable model

Upward Version

If $\Phi$ has infinite model, it has models of every infinite cardinality

Key Implication

FOL cannot characterize uncountable structures uniquely

Limitation

FOL is not categorical for infinite domains

16. Proof by Resolution

Clause Form

Disjunction of literals: $p \lor \neg q \lor r$

Resolution Rule

$\frac{p \lor \alpha \quad \neg p \lor \beta}{\alpha \lor \beta}$

Proof by Contradiction

Refute $\neg \phi$ using resolution. If $\bot$ derived, $\phi$ is valid

Completeness

Resolution is refutation complete

Quick Reference: Relationships Between Concepts

Propositional Logic

Atoms + Connectives → Formulas

Truth Tables determine semantics

Equivalences reduce formulas

Normal Forms (CNF, DNF) are canonical

Predicate Logic

Extends propositional with predicates

Quantifiers bind variables

Bound vs free variable distinction

Models interpret predicates over domains

Metatheory

Soundness: Proof → Truth

Completeness: Truth → Proof

Compactness: Infinite ↔ Finite satisfiability

Löwenheim-Skolem: Domain cardinality variations

Limitations

Gödel Incompleteness: Arithmetic incompleteness

Undecidability: No algorithm for all formulas

Non-categoricity: Can't pin down infinite structures

Resolution: Efficient proof search method

MATHEMATICAL LOGIC Comprehensive Formula Sheet