Semantics: interpretation, model, satisfiable, valid

Giving symbols meaning

Syntax says which strings are legal; semantics says what they *mean* and whether they are *true*. A predicate calculus interpretation over a nonempty domain $D$ assigns:

- each constant to an element of $D$; - each function of arity $m$ to a mapping $D^m \to D$; - each predicate of arity $n$ to a mapping $D^n \to \{T, F\}$; - each variable to a nonempty subset of $D$ (its allowable substitutions).

Given an interpretation, the truth value of any sentence is fixed by applying these mappings. Many *different* domains can satisfy the same set of sentences — a knowledge base is not tied to one world.

Four properties of a sentence (or set)

- Satisfiable — there *exists* some interpretation (and variable assignment) that makes it true. Otherwise it is unsatisfiable. - Model — an interpretation that *does* make a sentence (or every sentence in a set $S$) true is a model of it. Formally, $S$ is a model of $X$ when every interpretation satisfying $S$ also satisfies $X$ — and then we say $X$ logically follows from $S$. - Valid — true under *every* interpretation. A valid sentence is a tautology, e.g. $\forall X\,(p(X) \vee \neg p(X))$. Validity is the predicate-calculus analogue of an all-true truth-table column. - Inconsistent — a set is inconsistent when *no* interpretation satisfies all of its members at once. It has no model.

These form a ladder of strength: valid $\Rightarrow$ satisfiable (a sentence true everywhere is certainly true somewhere), but not the reverse. p(a) is satisfiable (true in some worlds) yet not valid (false in others).

Worked example: classifying three sentences

Let the domain be people. (1) $\forall X\,(p(X) \vee \neg p(X))$ — *valid*: in every interpretation, each object either has property $p$ or does not, so the disjunction is always true. (2) $\exists X\,likes(X, icecream)$ — *satisfiable but not valid*: true in a world where someone likes ice cream, false in a world where no one does. (3) $p(a) \wedge \neg p(a)$ — *unsatisfiable* (inconsistent): no interpretation can make a both have and not have $p$, so the set $\{p(a), \neg p(a)\}$ has no model. Property (3) is the engine behind resolution refutation in Module 9: prove a goal by showing that *negating* it produces an inconsistent set.

Quantifier-negation equivalences

Pushing a negation across a quantifier flips the quantifier:

$$\neg \forall X\, P(X) \equiv \exists X\, \neg P(X) \qquad \neg \exists X\, P(X) \equiv \forall X\, \neg P(X)$$

In words: "not everyone likes ice cream" ($\neg\forall X\,likes(X,ic)$) means "someone does not like ice cream" ($\exists X\,\neg likes(X,ic)$). These are the quantifier analogue of De Morgan's laws and are needed when converting sentences toward clause form (Lesson 7).