5.2 Propositional Definite Clauses

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 body is an atom or a conjunction of atoms. Defined recursively, a body is either an atom or of the form a∧b, where a is an atom and b is a body.
  • A definite clause is either an atom a, called an atomic clause, or of the form a←b, called a rule, where a, the head, is an atom and b is a body.
  • A knowledge base is a set of definite clauses.
Example 5.4: The elements of the knowledge base in Example 5.2 are all definite clauses.

The following are not definite clauses:

apple_is_eaten ∧bird_eats_apple.
sam_is_in_room ∧night_time ←switch_1_is_up .
Apple_is_eaten ←Bird_eats_apple.
happy ∨ sad ∨ ¬alive.

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

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

a ←b ∧c ∧d.

is equivalent to the clause

a ∨ ¬b ∨ ¬c ∨ ¬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∨b) or disjunctions of negated atoms (e.g., ¬c ∨¬d).

Example 5.5: 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.
Figure 5.2: An electrical environment with components named

Assume the representation will be used to determine whether lights are on or off, based on switch positions and the status of circuit breakers, and, eventually, to be able to diagnose what is wrong with wires, switches, and circuit breakers if something unexpected is observed. Assume you are 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 of detail 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 diagnostic assistant 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 up_s2 to represent whether switch s2 is up and live_l1 to represent whether light l1 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


The designer may look at part of the domain and know that light l1 is live if wire w0 is live, because they are connected together, but may not know if w0 is live. Such knowledge is expressible in terms of rules:

live_l1 ←live_w0.
live_w0 ←live_w1 ∧up_s2.
live_w0 ←live_w2 ∧down_s2.
live_w1 ←live_w3 ∧up_s1.
live_w2 ←live_w3 ∧down_s1.
live_l2 ←live_w4.
live_w4 ←live_w3 ∧up_s3.
live_p1 ←live_w3.
live_w3 ←live_w5 ∧ok_cb1.
live_p2 ←live_w6.
live_w6 ←live_w5 ∧ok_cb2.
live_w5 ←live_outside.
lit_l1 ←light_l1 ∧live_l1 ∧ok_l1.
lit_l2 ←light_l2 ∧live_l2 ∧ok_l2.

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


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