5.3 Propositional Definite Clauses

The rest of this chapter considers some restricted languages and reasoning tasks that are useful and can be efficiently implemented.

The language of propositional definite clauses is a sublanguage of propositional calculus that does not allow uncertainty or ambiguity. In this language, propositions have the same meaning as in propositional calculus, but not all compound propositions are allowed in a knowledge base.

The syntax of propositional definite clauses is defined as follows:

• An atomic proposition or atom is the same as in propositional calculus.

• A definite clause is of the form

 $h\leftarrow\mbox{}a_{1}\wedge\mbox{}\ldots\wedge\mbox{}a_{m}.$

where $h$ is an atom, the head of the clause, and each $a_{i}$ is an atom. It can be read “$h$ if $a_{1}$ and …and $a_{m}$”.

If $m>0$, the clause is called a rule, where $a_{1}\wedge\mbox{}\ldots\wedge\mbox{}a_{m}$ is the body of the clause.

If $m=0$ the arrow can be omitted and the clause is called an atomic clause or fact. The clause has an empty body.

• A knowledge base is a set of definite clauses.

Example 5.6.

The elements of the knowledge base in Example 5.2 are all definite clauses.

The following are not definite clauses:

 $\displaystyle{\neg\mbox{apple\_is\_eaten}.}$ $\displaystyle{\mbox{apple\_is\_eaten}\wedge\mbox{}\mbox{bird\_eats\_apple}.}$ $\displaystyle{\mbox{sam\_is\_in\_room}\wedge\mbox{}\mbox{night\_time}% \leftarrow\mbox{}\mbox{switch\_1\_is\_up}.}$ $\displaystyle{\mbox{Apple\_is\_eaten}\leftarrow\mbox{}\mbox{Bird\_eats\_apple}.}$ $\displaystyle{\mbox{happy}\vee\mbox{sad}\vee\neg\mbox{alive}.}$

The fourth statement is not a definite clause because an atom must start with a lower-case letter.

A definite clause $h\leftarrow\mbox{}a_{1}\wedge\mbox{}\ldots\wedge\mbox{}a_{m}$ is false in interpretation $I$ if $a_{1}\dots a_{m}$ are all true in $I$ and $h$ is false in $I$; otherwise the definite clause is true in $I$.

Note that a definite clause is a restricted form of a clause. For example, the definite clause

 $a\leftarrow\mbox{}b\wedge\mbox{}c\wedge\mbox{}d.$

is equivalent to the clause

 $a\vee\neg b\vee\neg c\vee\neg d.$

In general, a definite clause is equivalent to a clause with exactly one positive literal (non-negated atom). Propositional definite clauses cannot represent disjunctions of atoms (e.g., $a\vee\mbox{}b$) or disjunctions of negated atoms (e.g., $\neg c\vee\mbox{}\neg d$).

Example 5.7.

Consider how to axiomatize the electrical environment of Figure 5.2 following the methodology for the user’s view of semantics. This axiomatization will allow us to simulate the electrical system. It will be expanded in later sections to let us diagnose faults based on observed symptoms.

The representation will be used to determine whether lights are on or off, based on switch positions and the status of circuit breakers. The agent is not concerned here with the color of the wires, the design of the switches, the length or weight of the wire, the date of manufacture of the lights and the wires, or any of the other myriad details one could imagine about the domain.

We must choose a level of abstraction. The aim is to represent the domain at the most general level that will enable the agent to solve the problems it must solve. We also want to represent the domain at a level that the agent will have information about. For example, we could represent the actual voltages and currents, but exactly the same reasoning would be done if this were a 12-volt DC system or a 120-volt AC system; the voltages and frequencies are irrelevant for questions about how switches affect whether lights are on. Instead, we represent this domain at a commonsense level that non-electricians may use to describe the domain, in terms of wires being live and currents flowing from the outside through wires to the lights, and that circuit breakers and light switches connect wires if they are turned on and working.

We have to choose what to represent. Suppose we want to represent propositions about whether lights are lit, whether wires are live, whether switches are up or down, and whether components are broken.

We then choose atoms with a specific meaning in the world. We can use descriptive names for these, such as $\mbox{up\_s}_{2}$ to represent whether switch $s_{2}$ is up and $\mbox{live\_l}_{1}$ to represent whether light $l_{1}$ is live (i.e., has power coming into it). The computer does not know the meaning of these names and does not have access to the components of the atom’s name.

At this stage, we have not told the computer anything. It does not know what the atoms are, let alone what they mean.

Once we have decided which symbols to use and what they mean, we tell the system, using definite clauses, background knowledge about what is true in the world. The simplest forms of definite clauses are those without bodies – the atomic clauses – such as

 $\displaystyle{\mbox{light\_l}_{1}.}$ $\displaystyle{\mbox{light\_l}_{2}.}$ $\displaystyle{\mbox{ok\_l}_{1}.}$ $\displaystyle{\mbox{ok\_l}_{2}.}$ $\displaystyle{\mbox{ok\_cb}_{1}.}$ $\displaystyle{\mbox{ok\_cb}_{2}.}$ $\displaystyle{\mbox{live\_outside}.}$

The designer may look at part of the domain and know that light $l_{1}$ is live if wire $w_{0}$ is live, because they are connected together, but may not know whether $w_{0}$ is live. Such knowledge is expressible in terms of rules:

 $\displaystyle{\mbox{live\_l}_{1}\leftarrow\mbox{}\mbox{live\_w}_{0}.}$ $\displaystyle{\mbox{live\_w}_{0}\leftarrow\mbox{}\mbox{live\_w}_{1}\wedge\mbox% {}\mbox{up\_s}_{2}.}$ $\displaystyle{\mbox{live\_w}_{0}\leftarrow\mbox{}\mbox{live\_w}_{2}\wedge\mbox% {}\mbox{down\_s}_{2}.}$ $\displaystyle{\mbox{live\_w}_{1}\leftarrow\mbox{}\mbox{live\_w}_{3}\wedge\mbox% {}\mbox{up\_s}_{1}.}$ $\displaystyle{\mbox{live\_w}_{2}\leftarrow\mbox{}\mbox{live\_w}_{3}\wedge\mbox% {}\mbox{down\_s}_{1}.}$ $\displaystyle{\mbox{live\_l}_{2}\leftarrow\mbox{}\mbox{live\_w}_{4}.}$ $\displaystyle{\mbox{live\_w}_{4}\leftarrow\mbox{}\mbox{live\_w}_{3}\wedge\mbox% {}\mbox{up\_s}_{3}.}$ $\displaystyle{\mbox{live\_p}_{1}\leftarrow\mbox{}\mbox{live\_w}_{3}.}$ $\displaystyle{\mbox{live\_w}_{3}\leftarrow\mbox{}\mbox{live\_w}_{5}\wedge\mbox% {}\mbox{ok\_cb}_{1}.}$ $\displaystyle{\mbox{live\_p}_{2}\leftarrow\mbox{}\mbox{live\_w}_{6}.}$ $\displaystyle{\mbox{live\_w}_{6}\leftarrow\mbox{}\mbox{live\_w}_{5}\wedge\mbox% {}\mbox{ok\_cb}_{2}.}$ $\displaystyle{\mbox{live\_w}_{5}\leftarrow\mbox{}\mbox{live\_outside}.}$ $\displaystyle{\mbox{lit\_l}_{1}\leftarrow\mbox{}\mbox{light\_l}_{1}\wedge\mbox% {}\mbox{live\_l}_{1}\wedge\mbox{}\mbox{ok\_l}_{1}.}$ $\displaystyle{\mbox{lit\_l}_{2}\leftarrow\mbox{}\mbox{light\_l}_{2}\wedge\mbox% {}\mbox{live\_l}_{2}\wedge\mbox{}\mbox{ok\_l}_{2}.}$

At run time, the user is able to input the observations of the current switch positions, such as

 $\displaystyle{\mbox{down\_s}_{1}.}$ $\displaystyle{\mbox{up\_s}_{2}.}$ $\displaystyle{\mbox{up\_s}_{3}.}$

The knowledge base consists of all of the definite clauses, whether specified as background knowledge or as observations.