Page 140 - Intelligent Communication Systems

CHAPTER 10 / BASIC TECHNOLOGY OF THE INTELLIGENT COMMUNICATION SYSTEM I I 9

FIGURE 10.9 Semantic tree.

in a Herbrand base does not have any variables, it is possible to assign a value, T
or F, to the atomic formula. If a Herbrand base is composed of n variables, then 2"
interpretations are possible.
Example 3: The Herbrand base of Example 1 is (P(a), Q(a)}. The Herbrand
base of Example 2 is {P(a\ <2(/(a)), R(a), fi(/(/(a))), R(f(a)), ...}. When a
Herbrand base (P(d), Q(a)} of a clause set C is given, the interpretation is as shown
in Figure 10.9. If C is a contradiction, there exists a node whose value is F on every
branch of a semantic tree. The node whose value is F and appears first is called a
failure node. If a clause set C is unsatisfactory, there exists a clause set C l that is
composed of nodes whose values are false for all branches on a semantic tree. On
the other hand, if there exists a clause set C that is unsatisfactory, then C is unsat-
isfactory. This is the Herbrand theorem.
Example 4: A given clause set C= (~F(a) v Q(b\ ~Q(x) v R(y), P(z), ~R(w)}
has a Herbrand universe H(C) = {a,b} and Herbrand base HB(C) = (P(a), P(b),
Q(b), Q(d), R(a), R(b)}. Using the ground instance, the semantic tree in Figure 10.10
is generated. If there is a failure node at every branch of a semantic tree, then the
clause set is unsatisfactory. That a clause set C\ is unsatisfactory is proven by the
following operations.