Case Study: Other Ways of Thinking - Thinking as Computation - page 258

11.4 Propositional reasoning
So far, it has been assumed that a knowledge base is made up only of atomic or
conditional sentences. This allowed the use of a thinking procedure like back-chaining
to draw all the necessary conclusions, and even to do explanation and learning.
But, of course, there are sentences of English that do not fit this pattern. Consider
the following three sentences:
At least one of Alice, Bob, or Carol is guilty.
If Alice is guilty, then so is Bob.
If Alice is not guilty, then neither is Carol.
From these sentences alone, there is no way to tell whether Alice and Carol are guilty.
However, it is not hard to see that Bob must be guilty. The reasoning is as follows. If
Alice is guilty, then Bob is also guilty. But if Alice is not guilty, then neither is Carol,
and since one of the three must be guilty, it must be Bob. So either way, Bob must be
guilty. In other words, the three sentences logically entail that Bob is guilty.
To be able to use knowledge in this sophisticated way, it is necessary to go beyond
atomic and conditional sentences to represent what is known, and to go beyond back-
chaining to calculate logical entailments. So it is useful to consider a new language
for representing knowledge, a propositional language , which allows us the expression of
negations and disjunctions in addition to the previous conjunctions and conditionals.
11.4.1 Conjunctive normal form
Perhaps the simplest representation of a propositional language in Prolog is to use
the conjunctive normal form ,or CNF . For present purposes, a CNF formula is a list
of disjunctive clauses ,or dclauses for short, where a dclause is a list of literals, and a
literal is either an atom or its negation. A dclause is interpreted as the disjunction of its
elements, and the entire CNF formula is interpreted as the conjunction of its elements.
So the dclause [p,q] is interpreted as saying that p or q is true, and the CNF formula
[[p,q],[not(r)]] is interpreted as saying that p or q is true and r is false.
Note that dclauses are interpreted differently from clauses. Previously, a list like
[p,q,r,s] represented the conditional “If q and r and s then p .” That same list as a
dclause represents the disjunction “ p or q or r or s .”
And yet there is a definite connection between the two interpretations. Consider a
conditional like this:
If q and r and s then p .