Sentential (Propositional) Logic

Sentential logic (also called propositional logic) treats whole declarative statements as atomic and studies how they combine under the truth-functional connectives. It is the natural starting point for classical logic; First-Order Logic is built on top of it by adding terms, variables, and quantifiers.

The presentation separates syntax (what counts as a well-formed formula), semantics (what the formulas mean and when they are true), and proof theory (which formulas can be derived by purely symbolic rules). The central metatheorems — soundness, completeness, and compactness — say precisely how these three layers fit together.

Syntax

Fix a countable set of propositional variables (atoms) $\mathsf{Prop}=\{p_0,p_1,p_2,\dots \}$, intended to stand for whole declarative sentences whose internal structure we ignore. The logical connectives are

$$\neg (\text{negation}),\wedge (\text{conjunction}),\vee (\text{disjunction}),\to (\text{implication}),\leftrightarrow (\text{biconditional}).$$

The set of well-formed formulas (wffs) is the smallest set such that:

• (F1) every atom $p_i\in \mathsf{Prop}$ is a formula;
• (F2) if $\phi$ is a formula, so is $\neg \phi$;
• (F3) if $\phi$ and $\psi$ are formulas, so are $(\phi \wedge \psi )$, $(\phi \vee \psi )$, $(\phi \to \psi )$, and $(\phi \leftrightarrow \psi )$.

This is a definition by structural recursion: every formula is built up from atoms in finitely many steps, which justifies proof by induction on the structure of formulas — to prove a property holds of all wffs, prove it for atoms and show it is preserved by each connective.

A connective set is functionally complete if every truth function is expressible using only its members. The set $\{\neg ,\wedge ,\vee \}$ is functionally complete, and so is each of $\{\neg ,\wedge \}$, $\{\neg ,\vee \}$, $\{\neg ,\to \}$. Indeed the single connectives NAND ($\uparrow$) and NOR ($\downarrow$) are each functionally complete on their own.

Semantics

A truth assignment (or valuation) is a function $v:\mathsf{Prop}\to \{\mathsf{T},\mathsf{F}\}$. Such a $v$ is the sentential analogue of a structure (model) in first-order logic: where a first-order structure interprets the symbols of a signature in a domain, a truth assignment interprets each atom as one of the two truth values $\mathsf{T}$ ("true") and $\mathsf{F}$ ("false"). One can think of $v$ as a model with a fixed two-element domain $\{\mathsf{T},\mathsf{F}\}$ in which every atom names one of those two values. A truth assignment extends uniquely to a function $\bar{v}$ on all formulas by the truth tables of the connectives:

We write $v\models \phi$ ("$v$ satisfies $\phi$", equivalently "$v$ is a model of $\phi$") when $\bar{v}(\phi )=\mathsf{T}$. Note that material implication $\phi \to \psi$ is false in exactly one row — when the antecedent is true and the consequent false — so a false antecedent makes the implication vacuously true.

Key semantic notions, stated uniformly in model terminology:

• $\phi$ is a tautology (valid), written $\models \phi$, if every truth assignment is a model of $\phi$. Example: $p\vee \neg p$ (excluded middle).
• $\phi$ is a contradiction (unsatisfiable) if it has no model. Example: $p\wedge \neg p$.
• $\phi$ is satisfiable if it has some model.
• A set $\Gamma$ of formulas semantically entails $\phi$, written $\Gamma \models \phi$, if every model of $\Gamma$ (every assignment that satisfies all of $\Gamma$) is also a model of $\phi$.

Two formulas are logically equivalent ($\phi \equiv \psi$) when they have the same models — i.e. they agree on every assignment. Standard equivalences include the De Morgan laws $\neg (\phi \wedge \psi )\equiv \neg \phi \vee \neg \psi$ and $\neg (\phi \vee \psi )\equiv \neg \phi \wedge \neg \psi$, distributivity, double negation $\neg \neg \phi \equiv \phi$, and the definitional equivalences $\phi \to \psi \equiv \neg \phi \vee \psi$ and $\phi \leftrightarrow \psi \equiv (\phi \to \psi )\wedge (\psi \to \phi )$. Every formula can be put into conjunctive normal form (CNF, a conjunction of clauses) and into disjunctive normal form (DNF, a disjunction of conjunctions).

Proof theory

Semantics answers which formulas are valid; proof theory provides a syntactic mechanism for deriving them. Several equivalent presentations exist.

• Hilbert systems use a few axiom schemas plus a single inference rule, modus ponens (from $\phi$ and $\phi \to \psi$ infer $\psi$). A typical schema set over $\{\neg ,\to \}$ is $$\phi \to (\psi \to \phi ),(\phi \to (\psi \to \chi ))\to ((\phi \to \psi )\to (\phi \to \chi )),(\neg \phi \to \neg \psi )\to (\psi \to \phi ).$$
• Natural deduction replaces axioms with introduction and elimination rules for each connective and reasons under temporary assumptions that are later discharged (e.g. $\to$-introduction discharges the antecedent).
• Sequent calculus manipulates sequents $\Gamma ⊢\Delta$ and enjoys cut elimination.

Write $\Gamma ⊢\phi$ when $\phi$ is derivable from the assumptions $\Gamma$ in the chosen system. A useful bridge between syntax and the connectives is the Deduction Theorem: $\Gamma \cup \{\phi \}⊢\psi$ iff $\Gamma ⊢\phi \to \psi$.

Metatheorems

The two halves — $⊢$ (provability) and $\models$ (truth) — coincide:

• Soundness: if $\Gamma ⊢\phi$ then $\Gamma \models \phi$. (Everything provable is true; the rules never lead from truths to a falsehood.)
• Completeness (Post): if $\Gamma \models \phi$ then $\Gamma ⊢\phi$. (Every semantic consequence has a proof.)

Together: $\Gamma ⊢\phi ⟺\Gamma \models \phi$. A consequence is the Compactness Theorem: a set $\Gamma$ of formulas has a model iff every finite subset of $\Gamma$ has a model. Sentential validity is also decidable — the truth-table method enumerates all assignments and terminates — though deciding satisfiability (SAT, the existence of a model) is $\mathsf{NP}$-complete (see Computational Complexity Theory).

Where sentential logic stops is at the internal structure of statements: it cannot express that "every prime greater than $2$ is odd" follows from facts about individual numbers. Capturing that requires objects, predicates, and quantifiers — the subject of First-Order Logic.