Home / logic

Formal Logic Cheatsheet

A common misconception is that an ad hominem attack is synonymous with an insult

What is Formal Logic?

Core Concepts You Must‑Know

Concept Key Points Why It Matters
Propositional (Boolean) Logic • Sentences → propositions (true/false).
• Built with connectives (∧, ∨, ¬, →, ↔).
• Truth tables show the truth‑value of compound statements.		 Basis for circuit design, programming conditions, and basic proofs.
Predicate (First‑Order) Logic • Extends propositional logic with quantifiers (∀, ∃) and predicates that take variables.
• Allows statements about objects and their properties.		 Captures richer mathematical statements and specifications of algorithms.
Syntax vs. Semantics • Syntax: formal symbols and formation rules (how formulas are built).
• Semantics: interpretation of symbols (truth‑values, domains).		 Distinguishes well‑formed formulas from meaningful statements【1】.
Logical Consequence (⊨) A formula φ is a logical consequence of a set Γ if every model that makes all members of Γ true also makes φ true. Central notion of valid inference and proof.
Proof Systems • Natural deduction, sequent calculus, Hilbert systems.
• Provide rules of inference (e.g., Modus Ponens, ∀‑Elimination).		 Frameworks for constructing formal proofs.
Common Inference Rules - Modus Ponens: (P → Q,\;P \;\vdash\; Q)
- Modus Tollens: (P → Q,\;\lnot Q \;\vdash\; \lnot P)
- Universal Instantiation: (∀x\,P(x) \;\vdash\; P(c))
- Existential Generalization: (P(c) \;\vdash\; ∃x\,P(x))		 Enables step‑by‑step derivations in proofs.
Logical Equivalences • De Morgan’s Laws: (\lnot(P ∧ Q) \equiv (\lnot P) ∨ (\lnot Q))
• Implication Law: (P → Q \equiv \lnot P ∨ Q)
• Double Negation: (\lnot\lnot P \equiv P)		 Used to simplify formulas and prove equivalence.
Validity vs. Soundness • Validity: every interpretation that makes premises true also makes the conclusion true.
• Soundness: the proof system derives only valid arguments.		 Guarantees that derived conclusions are trustworthy.
Common Fallacies (to avoid) • Affirming the consequent (invalid form of Modus Ponens).
• Denying the antecedent (invalid form of Modus Tollens).		 Recognizing these prevents erroneous reasoning.

Essential Symbols

Symbol Name Meaning / Usage Example
∧ Conjunction “and”; both operands true (P ∧ Q)
∨ Disjunction “or”; at least one operand true (P ∨ Q)
¬ Negation “not”; opposite truth‑value (\lnot P)
→ Conditional “if…then”; material implication (P → Q)
↔ Biconditional “if and only if”; both directions true (P ↔ Q)
⊥ Falsum Contradiction / always false —
⊤ Verum Tautology / always true —
∀ Universal quantifier “for all” (∀x\,P(x))
∃ Existential quantifier “there exists” (∃x\,P(x))
⊨ Logical consequence Semantic entailment (Γ ⊨ φ)
⊢ Syntactic entailment Proof‑theoretic derivation (Γ ⊢ φ)
≡ Logical equivalence Same truth‑value in all models (P ∧ Q ≡ Q ∧ P)
∴ Therefore Introduces conclusion (P, P → Q ∴ Q)
∵ Because Introduces premise (Q ∵ P, P → Q)
⊂ Subset Every element of A is in B (A ⊂ B)
∈ Element of Membership relation (x ∈ A)
≠ Not equal Inequality (a ≠ b)
∅ Empty set Set with no elements —
⊢ Turnstile Derivation in a proof system【2】
∴ Therefore Indicates conclusion【2】
∵ Because Indicates premise【2】

All symbols and their conventional meanings are drawn from standard logical notation tables【2】.

Quick Reference: Truth Tables (Propositional Connectives)

(P) (Q) (P ∧ Q) (P ∨ Q) (\lnot P) (P → Q) (P ↔ Q)
T T T T F T T
T F F T F F F
F T F T T T F
F F F F T T T

Study Tips