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 Xlikes(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 XP(X)\equiv \exists X\neg P(X)\neg \exists XP(X)\equiv \forall X\neg P(X)$$

In words: "not everyone likes ice cream" ($\neg \forall Xlikes(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).