I Logic Study Guide — Propositional & Modal

Propositional Logic

Connectives, truth tables, entailment, the deduction theorem, and tableau proof rules — all in one place.

Connectives
Truth Tables
Entailment ⊨
Deduction Theorem
Tableau Rules
Laws & Equivalences

The Five Connectives

Every propositional formula is built from atomic sentences and these five operations.

¬
Negation
¬A — "not A"
Flips truth value. T→F, F→T.
∧
Conjunction
A ∧ B — "A and B"
True only when BOTH are true.
∨
Disjunction
A ∨ B — "A or B"
False only when BOTH are false.
→
Conditional
A → B — "if A then B"
False only when A=T and B=F.
↔
Biconditional
A ↔ B — "A iff B"
True when both have the same value.

Visual: What Each Connective Selects

Think of A and B as overlapping sets of "situations where the sentence is true"
¬A
¬A — outside A
A B
A ∧ B — intersection
A B
A ∨ B — union
A B
A → B — not(A and ¬B)
A B
A ↔ B — same truth value

Operator Precedence

Binding strength — higher binds tighter (like × before + in arithmetic)
¬
HIGHEST
∧
2nd
∨
3rd
→
4th
↔
LOWEST
¬ binds tightest: ¬A∧B means (¬A)∧B, not ¬(A∧B)

Truth Tables

Complete truth tables for all five connectives. Hover rows to highlight.

¬ Negation

Unary — one input
A¬A
TF
FT
Flips. Simple.

∧ Conjunction

True only when both true
ABA∧B
TTT
TFF
FTF
FFF

∨ Disjunction

False only when both false
ABA∨B
TTT
TFT
FTT
FFF

→ Conditional

False ONLY when T→F
ABA→B
TTT
TFF
FTT
FFT
The "odd" rows: F→anything = T (vacuous truth)

↔ Biconditional

True when both match
ABA↔B
TTT
TFF
FTF
FFT
Same as (A→B) ∧ (B→A)

Complex Formula: (A → B) ∧ (B → C) → (A → C)

Hypothetical Syllogism — this is a tautology (all T in final column)
ABC A→B B→C (A→B)∧(B→C) A→C Full Formula

Semantic Entailment ⊨

The central relation of propositional logic. What it means, and its key properties.

Definition

The core semantic relation
Γ ⊨ A

Every valuation v that makes all sentences in Γ true also makes A true. In other words: there is no possible assignment of truth values that satisfies Γ but falsifies A.

Key Properties of ⊨

Reflexivity
A ⊨ A
Any sentence entails itself.
Monotonicity
If Γ ⊨ A, then Γ ∪ Δ ⊨ A
Adding more premises never breaks an entailment.
Transitivity (Cut)
If Γ ⊨ A and Δ∪{A} ⊨ B, then Γ∪Δ ⊨ B
Chain entailments together. A is the bridge.
Compactness
If Γ ⊨ A, some finite Γ₀ ⊆ Γ already suffices
You never need infinitely many premises.

Transitivity Visualized

The "cut" rule — A is derived from Γ, then used to derive B
PREMISE SET
Γ
⊨
BRIDGE
A
given
PREMISE SET
Δ ∪ {A}
⊨
TARGET
B
given
∴
COMBINED
Γ ∪ Δ
⊨
CONCLUSION
B
derived
Key: A doesn't need to be in Γ — it's entailed by Γ. Γ produces A silently. Δ uses A to produce B. Pooling Γ ∪ Δ gives you B directly.

Tautology

⊨ A (empty premise set entails A)

True under every valuation. No premises needed. Examples:

A ∨ ¬A
A → A
(A → B) → ((B → C) → (A → C))

Contradiction

Unsatisfiable — false under every valuation

False under every valuation. A contradiction entails everything (ex falso):

A ∧ ¬A
¬(A ∨ ¬A)
{A, ¬A} ⊨ B (for any B)

The Deduction Theorem

The bridge between object-level → and meta-level ⊨. One of the most important results in propositional logic.

Γ ⊨ A → B
META LEVEL — entailment
The premises in Γ entail the conditional A→B as a conclusion
⟺
IF AND ONLY IF
Γ ∪ {A} ⊨ B
OBJECT LEVEL — adding assumption
Adding A as a premise to Γ entails B directly

→ Left to Right

If Γ ⊨ A→B, then Γ∪{A} ⊨ B
Assume v makes all of Γ∪{A} true. In particular, v makes Γ true. By hypothesis, v makes A→B true. Since v also makes A true, by the truth table for →, v must make B true. ✓
Uses: truth table for → (T→T = T, T→F = F)

← Right to Left

If Γ∪{A} ⊨ B, then Γ ⊨ A→B
Assume v makes all of Γ true. Either v(A)=T or v(A)=F.
Case T: Γ∪{A} all true, so v(B)=T. Then A→B is T.
Case F: A→B is vacuously T regardless of B.
The vacuous case (F→anything=T) is why → is defined this way.

Why This is "Striking"

The philosophical significance
HOW MATHEMATICIANS PROVE CONDITIONALS

To prove "if P then Q," mathematicians universally assume P and then derive Q. The deduction theorem says this strategy is logically valid — assuming A and deriving B is exactly equivalent to proving A→B outright.

WHY → IS DEFINED AS IT IS

The "odd" truth table for → (where F→anything = T) is the only definition that makes the Deduction Theorem hold perfectly. The vacuous truth cases aren't a bug — they're what makes the bridge between ⊨ and → mathematically clean.

Propositional Tableau Rules

Every connective has two rules: one for when it's marked True, one for False. Annotations cite which rule and which line.

How Tableaux Work

TO PROVE Γ ⊨ A

Assume the negation: mark every sentence in Γ as T, and mark A as F. Then apply rules to decompose. If every branch closes (contradiction), the entailment holds.

OPEN BRANCH = COUNTERMODEL

If a branch stays open with no more rules to apply, read off a countermodel directly from the T/F assignments on that branch. The entailment fails.

Rules for ¬

¬T — True Negation
1.T¬A
2.FA¬T 1
If ¬A is true, then A is false. Flip the sign.
¬F — False Negation
1.F¬A
2.TA¬F 1
If ¬A is false, then A is true. Flip the sign.

Rules for ∧

∧T — True Conjunction
1.TA ∧ B
2.TA∧T 1
3.TB∧T 1
No branching. Both conjuncts must be true.
∧F — False Conjunction BRANCHES
1.FA ∧ B
2.FA
|
2.FB
∧F 1
⑂ Creates two branches — at least one conjunct is false

Rules for ∨

∨T — True Disjunction BRANCHES
1.TA ∨ B
2.TA
|
2.TB
∨T 1
⑂ Creates two branches — at least one disjunct is true
∨F — False Disjunction
1.FA ∨ B
2.FA∨F 1
3.FB∨F 1
No branching. Both disjuncts must be false.

Rules for →

→T — True Conditional BRANCHES
1.TA → B
2.FA
|
2.TB
→T 1
⑂ Either A is false OR B is true
→F — False Conditional
1.FA → B
2.TA→F 1
3.FB→F 1
No branching. A must be true AND B false (the one failing case).

Which Rules Branch?

Memorize this — branching rules are where tableaux split into multiple paths
BRANCHING RULES ⑂
F (A ∧ B)
T (A ∨ B)
T (A → B)
LINEAR RULES (no branch)
T/F ¬A
T (A ∧ B)
F (A ∨ B)
F (A → B)
Pattern: Rules branch when there are multiple ways the formula can have that truth value. F(A∧B) branches because either A or B could be the false one.

Logical Laws & Equivalences

Key tautologies and equivalences. Two formulas are logically equivalent (A ≡ B) when A ↔ B is a tautology.

Double Negation
¬¬A ≡ A
De Morgan 1
¬(A ∧ B) ≡ ¬A ∨ ¬B
De Morgan 2
¬(A ∨ B) ≡ ¬A ∧ ¬B
Contrapositive
A → B ≡ ¬B → ¬A
Material Conditional
A → B ≡ ¬A ∨ B
Exportation
(A ∧ B) → C ≡ A → (B → C)
Commutativity ∧
A ∧ B ≡ B ∧ A
Commutativity ∨
A ∨ B ≡ B ∨ A
Associativity ∧
(A∧B)∧C ≡ A∧(B∧C)
Associativity ∨
(A∨B)∨C ≡ A∨(B∨C)
Distribution 1
A∧(B∨C) ≡ (A∧B)∨(A∧C)
Distribution 2
A∨(B∧C) ≡ (A∨B)∧(A∨C)
Absorption 1
A ∧ (A ∨ B) ≡ A
Absorption 2
A ∨ (A ∧ B) ≡ A
Excluded Middle
⊨ A ∨ ¬A
Non-Contradiction
⊨ ¬(A ∧ ¬A)
Modus Ponens
{A, A→B} ⊨ B
Modus Tollens
{¬B, A→B} ⊨ ¬A
Hyp. Syllogism
{A→B, B→C} ⊨ A→C
Disjunctive Syll.
{A∨B, ¬A} ⊨ B

The Core Inference Rules

The workhorses of propositional reasoning
MODUS PONENS
A
A → B
∴ B
MODUS TOLLENS
¬B
A → B
∴ ¬A
HYP. SYLLOGISM
A → B
B → C
∴ A → C
DISJUNCTIVE SYLL.
A ∨ B
¬A
∴ B

Modal Logic

Possible worlds, accessibility relations, and the systems K, T, B, 4, S4, and S5 — fully visualized.