Home / logic

Formal Logic — Cheatsheet

Propositional Logic

Connectives & Truth Table

P	Q	¬P	P∧Q	P∨Q	P⊕Q	P→Q	P↔Q	P↑Q (NAND)	P↓Q (NOR)
T	T	F	T	T	F	T	T	F	F
T	F	F	F	T	T	F	F	T	F
F	T	T	F	T	T	T	F	T	F
F	F	T	F	F	F	T	T	T	T

NAND and NOR are each functionally complete — every other connective can be built from just one of them (why CMOS gates exist).

Operator Precedence

¬ > ∧ > ∨ > → > ↔

→ is right-associative: P → Q → R is P → (Q → R)
All others left-associative
When in doubt, parenthesize

Symbols

Symbol	Meaning	Notes
¬, ∼, P̄	Negation	All equivalent
∧	Conjunction (AND)
∨	Disjunction (inclusive OR)
⊕	Exclusive OR (XOR)
↑ / ↓	NAND / NOR	Sheffer / Peirce
→ , ⇒	Material implication	→ object lang.; ⇒ often metalang.
↔	Biconditional	Object language
≡	Logical equivalence	Metalanguage; same truth table
⊢	Syntactic entailment	"is provable from"
⊨ , ⊧	Semantic entailment	"models / satisfies"
∴	Therefore
∵	Because
⊤ , ⊥	Tautology / Contradiction
□ , ◇	Necessarily / Possibly	Modal logic

Logical Equivalences

Name	Equivalence
Double negation	¬¬P ≡ P
De Morgan (∧)	¬(P ∧ Q) ≡ ¬P ∨ ¬Q
De Morgan (∨)	¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Implication	P → Q ≡ ¬P ∨ Q
Contrapositive	P → Q ≡ ¬Q → ¬P
Biconditional	P ↔ Q ≡ (P → Q) ∧ (Q → P)
Commutative	P ∧ Q ≡ Q ∧ P ; P ∨ Q ≡ Q ∨ P
Associative	(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
Distributive	P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
Idempotence	P ∧ P ≡ P ; P ∨ P ≡ P
Absorption	P ∨ (P ∧ Q) ≡ P
Identity	P ∧ ⊤ ≡ P ; P ∨ ⊥ ≡ P
Domination	P ∨ ⊤ ≡ ⊤ ; P ∧ ⊥ ≡ ⊥
Negation	P ∨ ¬P ≡ ⊤ ; P ∧ ¬P ≡ ⊥
Vacuous truth	P → Q is true whenever P is false

Inference Rules

Rule	Form
Modus Ponens (MP)	P → Q, P ⊢ Q
Modus Tollens (MT)	P → Q, ¬Q ⊢ ¬P
Hypothetical Syllogism (HS)	P → Q, Q → R ⊢ P → R
Disjunctive Syllogism (DS)	P ∨ Q, ¬P ⊢ Q
Conjunction Intro (∧I)	P, Q ⊢ P ∧ Q
Conjunction Elim (∧E)	P ∧ Q ⊢ P
Disjunction Intro (∨I)	P ⊢ P ∨ Q
Constructive Dilemma	(P → Q) ∧ (R → S), P ∨ R ⊢ Q ∨ S
Reductio (RAA)	Assume P, derive ⊥, conclude ¬P

Normal Forms

CNF (Conjunctive): conjunction of disjunctions of literals — input form for SAT solvers.
DNF (Disjunctive): disjunction of conjunctions of literals — used in circuit minimization (sum-of-products).

Formal Fallacies (invalid forms)

Fallacy	Form
Affirming the consequent	P → Q, Q ⊬ P
Denying the antecedent	P → Q, ¬P ⊬ ¬Q
Undistributed middle	Syllogism where middle term isn't distributed in either premise
Existential fallacy	Drawing existential conclusion from purely universal premises

Informal fallacies (ad hominem, straw man, appeal to authority, etc.) concern content not form — out of scope for formal logic.

Predicate Logic

Quantifiers

Symbol	Meaning
∀x P(x)	For all x, P(x) holds
∃x P(x)	There exists an x such that P(x)
∃!x P(x)	Exactly one x such that P(x)

Bound variable: in scope of a quantifier.
Free variable: not bound — formula isn't a closed statement until bound or assigned.
Scope of quantifier extends as far right as parentheses allow.

Quantifier Equivalences

¬∀x P(x)            ≡  ∃x ¬P(x)
¬∃x P(x)            ≡  ∀x ¬P(x)
∀x (P(x) ∧ Q(x))    ≡  ∀x P(x) ∧ ∀x Q(x)
∃x (P(x) ∨ Q(x))    ≡  ∃x P(x) ∨ ∃x Q(x)

Note: ∀ does not distribute over ∨, and ∃ does not distribute over ∧.

Quantifier Inference Rules

Rule	Form
Universal Instantiation (∀E / UI)	∀x P(x) ⊢ P(c) for any c
Universal Generalization (∀I / UG)	P(c) for arbitrary c ⊢ ∀x P(x)
Existential Instantiation (∃E / EI)	∃x P(x) ⊢ P(c) for some new c
Existential Generalization (∃I / EG)	P(c) ⊢ ∃x P(x)

Symbol	Meaning
∈ , ∉	Element of / not
⊆	Subset (possibly equal)
⊂	Proper subset (strictly smaller) — ambiguous in older texts; some use ⊊
∪ , ∩	Union, Intersection
∅	Empty set
𝒫(S)	Power set

Meta-Theory

Validity vs Soundness

Argument-level:
- Valid: form preserves truth — if premises are true, conclusion must be.
- Sound: valid and all premises are actually true.
Proof-system-level:
- Sound: only proves things that are semantically valid: Γ ⊢ φ ⇒ Γ ⊨ φ
- Complete: proves everything semantically valid: Γ ⊨ φ ⇒ Γ ⊢ φ

Key Theorems (First-Order Logic)

Gödel's Completeness Theorem: Γ ⊢ φ ⇔ Γ ⊨ φ
Compactness: Γ ⊨ φ iff some finite subset of Γ does.
Gödel's Incompleteness (arithmetic): any consistent system rich enough for arithmetic has true statements it cannot prove.

Notation Gotchas

Confusion	Distinction
⊢ vs ⊨	Syntactic (provable) vs semantic (true in every model)
≡ vs ↔	Metalanguage equivalence vs object-language biconditional
→ vs ⇒	Often used interchangeably; some texts reserve ⇒ for metalanguage
⊂ vs ⊆	Proper vs non-strict subset (check author's convention)
¬ scope	Binds tightest: ¬P ∧ Q means (¬P) ∧ Q, not ¬(P ∧ Q)

Worked Mini-Example

"All cameras with PoE need a switch. Camera A has PoE. Therefore camera A needs a switch."

Predicate form:

P(x): x has PoE
S(x): x needs a switch
Premises: ∀x (P(x) → S(x)) ; P(a)
Goal: S(a)

Proof:

∀x (P(x) → S(x)) — premise
P(a) → S(a) — UI on (1)
P(a) — premise
S(a) — MP on (2),(3) ∎