5 Semantics

The role of a semantics for propositional logic is to explain how to interpret the formal language in order to provide fruitful definitions of validity and logical consequence. We do this by means of assignments of truth values to atomic formulas of the language.

Definition 5.1 (Assignment) An assignment for the language of propositional logic $L$ is a function $v$ , which assigns either 1 or 0 to each propositional variable.

Definition 5.2 (Valuation) Given an assignment $v$ for $L$ , we define a valuation $V$ based on $v$ inductively: $\begin{array}{lll} V (p_{n}) & = & v (p_{n}); \\ V (\neg φ) & = & {\begin{cases} 1 if V (φ) = 0 \\ 0 if V (φ) = 1 \end{cases} \\ V (φ \to ψ) & = & {\begin{cases} 1 if V (φ) = 0 or V (ψ) = 1 \\ 0 if V (φ) = 1 and V (ψ) = 0 \end{cases} \end{array}$

Definition 5.3 (Satisfaction) A valuation $V$ satisfies a formula $φ$ if, and only if, $V (φ) = 1$ .

That is, a valuation satisfies a formula if the latter is true relative to the relevant evaluation function.

Definition 5.4 (satisfiability) A set of formulas $Γ$ is satisfiable if, and only if, some valuation $V$ satisfies every element of $Γ$ .

We will often write that a formula $φ$ is satisfiable as shorthand for the claim that ${φ}$ is satisfiable. We will write that a set $Γ$ is unsatisfiable if $Γ$ is not satisfiable.

Definition 5.5 (Validity) A sentence $φ$ is propositionally valid, $⊨ φ$ , if, and only if, every valuation satisfies $φ$ .

Definition 5.6 (Logical Consequence) If $Γ$ is a set of formulas, a formula $φ$ is a logical consequence of $Γ$ , $Γ ⊨ φ$ , if, and only if, every valuation satisfying every element of $Γ$ satisfies $φ$ .

Exercise 5.1 True or false?

A formula $φ$ is unsatisfiable if, and only if, $\neg φ$ is valid.
A conjunction $φ \land ψ$ is unsatisfiable if, and only if, $\neg φ$ is valid or $\neg ψ$ is valid.
$Γ ⊨ φ$ if, and only if, $Γ \cup {φ}$ is satisfiable.
$Γ ⊨ φ$ if, and only if, $Γ \cup {\neg φ}$ is unsatisfiable.