Tip:
Highlight text to annotate it
X
The Herbrand Base for a relational signature is the set of all ground
relational sentences that can be formed from the vocabulary of the language.
Let's look at a, some examples. For a signature with object constants a
and b, no function constants, and relation constants p and q, where p has arity one
and q has arity two, the Herbrand base is shown here.
We have one p sentence for each object constant, and we have one q sentence for
each of the four possible pairs of object constants.
It's worthwhile to note that for a given relation constant and a finite set of
terms, it's an upper bound in the number of possible relational sentences that
could be formed using that relation constant.
In particular, for a set of terms of size b, there are b to the n distinct n tuples
of terms. And hence, there are b to the n ground
relational sentences for each entry relation constant.
Since the number of relation constants in a signature is finite, this means that the
Herbrand base is also finite. Of course, not all Herbrand bases are
finite. In the presence of function constants, the
number of ground terms is infinite and so the Herbrand base is infinite.
For example, in language with a single logic constant, a, and a single unit
re-function constant f, and a single re-relation constant p, the Herbrand base
consists of the sentences, p of a, p of f of a, p of f of f of a, and so forth.
A truth assignment for a relational logic language is a function that maps each
relational ground sentence in the Herbrand base to a truth value.
As an propositional logic, we use the digit one as a synonym for true, and zero
as a synonym for false. And we will refer to the value assigned to
a sentence by writing the atom with the name of the truth assignment as a super
script. The truth assignment I defined here is an example for the case of the
language we just mentioned. This exercise tests your understanding of
these concepts by asking you to answer some simple counting questions.
As with propositional logic, once we have a truth assignment for the ground
relational sentences of the language, the semantics of our language prescribes a
unique extension of that assignment to the other sentences of the language.
The rules for logical sentences in relational logic are the same as those for
logical sentences in propositional logic. A truth assignment satisfies a negation if
and only if it does not satisfy the target of the negation.
A truth assignment satisfies a conjunction if and only if it satisfies both of the
conjuncts. The truth value of the disjunction is true
if and only if the truth value of at least one of it's disjuncts is true, otherwise
the value is false. Truth value satis, truth assignment
satisfies the implication if and only if it does not satisfy the antecedent,
Or if it does satisfy the consequent. Truth assignment satisfies an equivalence
if and only if the truth values of the component sentences are the same.
In order to define truth assignments for quantified sentences, we need the notion
of instances. An instance of an expression, as it says
here, is an expression in which all variables have been conistently replaced
by ground terms.. Consistent replacement here means that, if
one occurrence of a variable is replaced by a ground term, then all occurrences of
that variable are replaced by the same ground term.
Universally quantified sentence is true, for a truth assignment, if and only if
every instance of the scope of the quantified sentence is true for that
assignment. An existentially quantified sentence is
true for a truth assignment if and only if some instance of the scope of the
quantified sentence is true for that sentence, for that assignment.
As an example of these definitions, consider the sentence, for all x p of x
implies q of x, x. What is the truth value under the
assignment shown here? According to our definition, a universally
quantified sentence is true if and only if every instance of it's scope is true.
For this language, there are just two instances that's shown here.
We know that p of a is true, and q of a is true, so the first instance is true.
We know that q of b, b is false, but so is p of b, so the second is true as well.
Since both instances are true, the quantified sentence as a whole is true.
Now, let's consider a case with nested quantifiers.
It's for all x there exist y, q of x y true or false for the truth assignment
shown here. That's before we know that this sentence
is true if every instance of it's scope is true.
The two possible instances are shown here. To determine the truth of the first of
these existential sentences, we must find at least one instance of its scope that is
true. The possibilities are shown here on, for
the first sentence, existential sentence are shown on the left.
Of these, the first is true. And so, the first existential sentence is
true as well. Now, we do the same for the sexinite, second existentially quantified
sentence. Of these, again, the first instance is
true. And so, the second existential sentence is
true as well. Since both existential sentences are true,
the original quantified sentence must be true.
A truth assignment satisfies the sentence with free variables if and only if it
satisfies every instance of that sentence. In other words, we can think of all free
variables as being universally quantified. Finally, a truth assignment satisfies a
set of sentences if and only if it satisfied every sentence in the set.
This exercise tests your grasp of semantics by asking you to evaluate some
relational logic sentences.