Skip to content
Pathcue

Mathematical Logic Cheat Sheet

The core ideas of Mathematical Logic distilled into a single, scannable reference — perfect for review or quick lookup.

PiqCue — piqcue.com/mathematical-logic/cheatsheet

Quick Reference

Propositional Logic

The branch of logic that deals with propositions (statements that are either true or false) and logical connectives such as AND, OR, NOT, IMPLIES, and IF AND ONLY IF. It provides the simplest formal system for reasoning about truth values.

Predicate Logic (First-Order Logic)

An extension of propositional logic that includes quantifiers (for all, there exists) and predicates that express properties of objects and relations among them, allowing statements about all or some elements in a domain.

Goedel's Incompleteness Theorems

Two landmark theorems proved by Kurt Goedel in 1931. The first states that any consistent formal system capable of expressing basic arithmetic contains true statements that cannot be proved within the system. The second states that such a system cannot prove its own consistency.

Set Theory (ZFC)

The axiomatic framework formulated by Zermelo and Fraenkel (with the Axiom of Choice) that provides the standard foundation for virtually all of modern mathematics. It defines the rules for constructing and manipulating sets.

Model Theory

The study of the relationship between formal languages (syntax) and their interpretations or structures (semantics). It investigates which sentences are true in which structures and how different models relate to one another.

Proof Theory

The sub-field of mathematical logic that studies mathematical proofs as formal objects. It analyzes the structure, strength, and properties of proof systems, and provides tools for showing consistency and comparing the power of different axiomatic systems.

Computability Theory

The branch of mathematical logic that studies which functions on the natural numbers are computable by an algorithm and which problems are decidable. It classifies problems by their degree of unsolvability using Turing machines and recursive functions.

Completeness and Soundness

A logical system is sound if every provable statement is true in all models, and complete if every statement true in all models is provable. Goedel's Completeness Theorem (1929) establishes that first-order predicate logic is both sound and complete.

Boolean Algebra

An algebraic structure that captures the essential operations of propositional logic (AND, OR, NOT) and set operations (intersection, union, complement). It obeys laws such as commutativity, associativity, distributivity, and De Morgan's laws.

Formal Language and Syntax

A formal language is a precisely defined set of strings over a given alphabet, constructed according to explicit grammatical rules. In logic, the syntax specifies how to build well-formed formulas (wffs) from symbols, variables, connectives, and quantifiers.

Key Terms at a Glance

Axiom:A statement accepted as true without proof, serving as a starting point for deducing other statements within a formal system.
Axiom of Choice:An axiom stating that for any collection of non-empty sets, a choice function exists that selects one element from each set.
Boolean Algebra:An algebraic structure defined over a set with two binary operations (AND, OR) and one unary operation (NOT) satisfying specific laws.
Cardinality:A measure of the number of elements in a set, extended to infinite sets by Cantor using bijections.
Church-Turing Thesis:The hypothesis that any effectively computable function can be computed by a Turing machine.
Completeness:A property of a logical system meaning every semantically valid formula is provable within the system.
Compactness Theorem:A set of first-order sentences is satisfiable if and only if every finite subset is satisfiable.
Computability:The study of which problems can be solved by algorithms and the classification of unsolvable problems by degree of unsolvability.
Contradiction:A formula that is false under every possible interpretation or truth assignment.
Decidability:A decision problem is decidable if there exists an algorithm that always terminates with a correct yes-or-no answer for every input.
De Morgan's Laws:Logical equivalences: NOT(A AND B) equals (NOT A) OR (NOT B), and NOT(A OR B) equals (NOT A) AND (NOT B).
First-Order Logic:A formal logical system that extends propositional logic with quantifiers and predicates, allowing statements about objects and their properties.
Formal System:A system consisting of a formal language, a set of axioms, and inference rules used to derive theorems.
Goedel Numbering:A technique of assigning a unique natural number to each symbol, formula, and proof in a formal system, enabling self-reference.
Halting Problem:The undecidable problem of determining whether an arbitrary Turing machine halts on a given input.

Get study tips in your inbox

We'll send you evidence-based study strategies and new cheat sheets as they're published.

We'll notify you about updates. No spam, unsubscribe anytime.

Mathematical Logic Cheat Sheet - Quick Reference Guide | PiqCue