Predicate Calculus Semantics
The truth value of predicate calculus expressions depends on the
mapping of constants, variables, predicates, and functions
into objects and relations in the domain of discourse. That is,
the truth value of an expression depends on its interpretation.
Formal Definition of Interpretation
Let the domain D be a nonempty set of objects. An interpretation over
D is an assignment of the entities of D to each of the constant, variable,
predicate, and functions symbols of a predicate calculus expression, such that:
- Each constant is assigned an element of D.
- Each variable is assigned to a nonempty subset of D, which constitutes the
allowable substitutions for that variable.
- Each function f of arity m is defined on m arguments of D and defines a mapping
from Dm into D.
- Each predicate p or arity n is defined on n arguments of D and defines a mapping
from Dn into {T, F}.
Rules for Evaluating Predicate Calculus Expressions
Assume an expression E and an interpretation I for E over a
nonempty domain D. The truth value for E is determined by:
- The value of a constant is the element of D it is assigned to by I.
- The value of a variable is the set of elements of D it is assigned to by I.
- The value of a function expression is that element of D
obtained by evaluating the function for the parameter values assigned by the
interpretation.
- The value of truth symbol "true" is T and "false" is F.
- The value of an atomic sentence is either T or F, as
determined by the interpretation I.
- The value of the negation of a sentence is T if the sentence
itself is F, and is F if the sentence is T.
- The value of a conjunction, disjunction, implication, equivalence of two sentences is
determined by the truth table definitions of these predicates.
- The value of ∀X S is T if the sentence S containing
X is T for all assignments to X under I, and F otherwise.
- The value of ∃X S is T if there is an assignment to X in the
interpretation under which S is T; otherwise it is F.
Some Examples
Suppose the domain is the D is the set of nonnegative integers, {0, 1, 2, 3, ...}. Let's
also assume the normal interpretation I of the integers. This includes such facts as
2 + 3 = 5, 2 < 3, and so on. Given this domain and interpretation, let's evaluate the following expressions:
- The value of the constant five is the integer 5.
- The value of the variable X in the expression X < 5 is the set {0, 1, 2, 3, 4}.
- The value of the function expression square(two) is the integer 4.
- The value of the function expression times(two,three) is the integer 6.
- The value of the predicate expression equal(times(two,three),six) is T.
- The value of the negation expression ~equal(times(two,three),six) is F.
- The value of the conjunction expression even(six) ^ odd(eight) is F.
- The value of the disjunction expression even(six) v odd(eight) is T.
- The value of the existentially quantified expression odd(X) is T.
- The value of the universally quantified expression ∀X odd(X) is F.
Some Useful Equivalences
- ~ ∃X p(X) = ∀X ~p(X)
- ~ ∀X p(X) = ∃X ~p(X)
- ∃X p(X) = ∃Y p(Y)
- ∀X q(X) = ∀Y q(Y)
- ∀X (p(X) ^ q(X)) = ∀X p(X) ^ ∀Y p(Y)
- ∃X (p(X) v q(X)) = ∃X p(X) v ∃Y p(Y)
Inference Rules
An inference rule is a mechanical means of producing new predicate
calculus sentences from a given set of sentences. Of course, we only want
to use inference rules that are sound -- that is, rules that produce
true sentence, if the original set of sentences was true.
Some Definitions
For a predicate calculus expression S and an interpretation I:
- If S has a value of T under I and a particular variable assignment, then I is
said to satisfy S.
- If I satisfies S for all variable assignments, then I is
model of S.
- S is satisfiable if and only if there exists an
interpretation and variable assignment that satisfy it; otherwise it is unsatisfiable.
- A set of expressions is satisfiable if and only if there exists an
interpretation and variable assignment that satisfy every element of the set.
- A set of expressions that is not satisfiable is said to be inconsistent.
∃X (p(X) ^ ~p(X)) is inconsistent.
- If S has a value T for all possible interpretations, it is said to be valid.
∀X (p(X) v ~p(X)) is valid.
Proof Procedure
A proof procedure is a combination of an inference rule and an algorithm for
applying that rule to a set of logical expressions to generate new sentences.
- A predicate calculus expression X logically follows from a set S
of predicate calculus expressions if every interpretation and variable assignment
that satisfies S, also satisfies X.
- An inference rule is sound if every expression produced by the
rule from S also logically follows from S.
- An inference rule is complete if given a set S of predicate calculus
expressions, the rule can infer every expression that logically follows from S.
Some Inference Rules
- Modus Ponens: If the sentences P and P -> Q are true, then modus ponens
lets us infer Q.
- Modus Tolens: If P -> Q is true and ~Q is true, then modus tolens
lets us infer ~P.
- And Elimination: If P ^ Q is true, then infer P and infer Q.
- And Introduction: If P is true and Q is true, then infer P ^ Q.
- Universal Instantiation: If any universally quantified variable in a true sentence
is replaced by an appropriate term from the domain, then the result is a true sentence. For example,
if socrates replaces X in ∀X mortal(X), then the
result, mortal(socrates) is true.
These rules let us prove the correctness of the following famous syllogism:
All humans are mortal.
Socrates is a human.
------------------
Therefore, Socrates is mortal.
Proof:
| Line | Premise | Justification |
|---|
| 1 | ∀X ( human(X) -> mortal(X) ) | Given |
| 2 | human(socrates) | Given |
| 3 | human(socrates) -> mortal(socrates) | From 1, by UI |
| 4 | mortal(socrates) | From 2, 3 by MP |