Logic Fundamentals: Syntax, Semantics, and Entailment

Introduction

Three foundational pillars underlie every logic: 1. Syntax: What sentences are grammatically legal? 2. Semantics: When are sentences true? 3. Entailment: When does one set of sentences guarantee another is true?

Syntax

Purely structural: defines which strings of symbols are legal sentences, independent of meaning.

Semantics

Defines the truth value of sentences relative to a model (possible world).

Models

A model m is a complete truth-value assignment to all propositional symbols. For n symbols there are 2^n possible models.

Truth in a Model (Recursive Definition)

Sentence	True in m iff…
`P` (atom)	`m(P) = true`
`¬α`	`m ⊭ α`
`α ∧ β`	`m ⊨ α` and `m ⊨ β`
`α ∨ β`	`m ⊨ α` or `m ⊨ β`
`α → β`	`m ⊭ α` or `m ⊨ β`
`α ↔︎ β`	`(m ⊨ α)` iff `(m ⊨ β)`

Entailment

Definition: KB ⊨ α (KB entails α) iff in every model where KB is true, α is also true.

Equivalently: M(KB) ⊆ M(α) where M(X) is the set of models satisfying X.

Example

KB = {A → B, A}. Does KB ⊨ B?

A	B	A→B	KB satisfied?	B?
T	T	T	Yes	Yes
T	F	F	No	—
F	T	T	No	—
F	F	T	No	—

Only model satisfying KB: A=T, B=T. B is true there. So KB ⊨ B. ✓

TT-ENTAILS? (Model Checking)

function TT-ENTAILS?(KB, α) returns true or false
    symbols ← all propositional symbols in KB and α
    return TT-CHECK-ALL(KB, α, symbols, {})

function TT-CHECK-ALL(KB, α, symbols, model) returns true or false
    if symbols is empty then
        if PL-TRUE?(KB, model) then return PL-TRUE?(α, model)
        else return true          -- vacuously true: KB is false in this model
    else
        P ← FIRST(symbols); rest ← REST(symbols)
        return TT-CHECK-ALL(KB, α, rest, model ∪ {P=true})
            AND TT-CHECK-ALL(KB, α, rest, model ∪ {P=false})

Complexity: Time O(2^n), Space O(n). Correct but exponential — motivates better algorithms.

Inference: Soundness and Completeness

Inference KB ⊢_i α: syntactic derivation of α from KB using rules.

Sound: KB ⊢_i α implies KB ⊨ α — never derives false conclusions from true premises.
Complete: KB ⊨ α implies KB ⊢_i α — derives every entailed conclusion.

KB ⊨ α   (semantic — about possible worlds)
   ↑ soundness guarantees this from ↓
KB ⊢_i α  (syntactic — about symbol manipulation)
   ↑ completeness guarantees this from ↑

Sound + complete: ⊢ and ⊨ coincide perfectly.

Key Distinctions

Material implication (→): a connective inside sentences. P → Q is a sentence.
Entailment (⊨): a meta-level relation between KB and a conclusion.

KB ⊨ α iff the sentence (KB₁ ∧ KB₂ ∧ ... ∧ KBn) → α is a tautology.