Knowledge Representation Using Nonmonotonic or Nonbinary Logics

(FLIES x)

The logical sentence above is true, if and only if it does not violate the logical sentences R1 R2 . . . Rn. Where

R1: (IF (OSTRICH x) (NOT (FLIES x)))

R2: (IF (PENGUIN x) (NOT (FLIES x)))

R3: (IF (KIWI x) (NOT (FLIES x)))

R4: (IF (DEAD x) (NOT (FLIES x)))

Note that this differs from the original example (IF (BIRD x) (FLIES x)). It is weaker in that it doesn't allow one to conclude that all birds fly, only birds that are not known not to fly. It is stronger than the lengthy qualified "AND" statement in that it allows one to conclude that a particular bird flies even if there is no information about whether the bird is dead, a penguin, a kiwi, or an ostrich.

Given the above logical sentences, suppose I am also given the following:

1. (IF (MAGPIE x) (BIRD x))

2. (MAGPIE HECKLE)

Thus

(BIRD x)

(FLIES x)

implies that (FLIES HECKLE). If I add (DEAD HECKLE) to the knowledge base, this violates (FLIES HECKLE) and deduction stops -- there is a contradiction. The default rule can not be applied.

Nonmonotonic Algorithm

1. Try to prove (NOT b)

2. If not provable use (IF a b)

Note: the test for consistency must be implemented with caution. As discussed in Chapter 6, provability is usually only semi-decidable. In a semi-decidable system, when a logical sentence is not provable, an inference procedure may run forever. Since consistency of a logical sentence is equivalent to nonprovability of its negation, this means that the consistency test can run forever.

Unfortunately, if we allow nonmonotonic logic, some default rules may conflict with other default rules. For example consider the default rules below: The problem is deciding what to conclude about the color of Eli, the albino elephant.

(ELEPHANT x) (ALBINO x)

============== ===============

(COLOR x GRAY) (COLOR x WHITE)

One way to handle this dilemma is to order all of the default rules. Generally, the more specific the default, the higher the priority. Thus in this case, there are fewer white elephants than gray elephants, thus the albino rule is of higher priority. There are fewer penguins (ostriches or kiwis) than birds; hence a default rule asserting that penguins (ostriches or kiwis) don't fly should be of higher priority than one that says that all birds fly.

Examples of implemented nonmonotonic logic system are Doyle's "Truth Maintenance System (TMS)" and de Kleer's "Assumption-Based Truth Maintenance System (ATMS)". They are designed as a subsystem for insuring truth maintenance in other reasoning programs. They check for inconsistencies and initiate their own reasoning mechanisms to resolve the inconsistency and appropriately modify the knowledge-base. More detail on TMS and ATMS can be found in the following references:

Artificial Intelligence, April, 1980 (special issue on nonmonotonic reasoning)

Doyle, J., "A Glimpse of Truth Maintenance," in Artificial Intelligence: An MIT Perspective, Vol. I, MIT Press, Cambridge, Mass, 1979 (Math Library).

Doyle, J., "A Truth Maintenance System," Artificial Intelligence, Vol. 12, No. 3, 1979.

de Kleer, J., "An Assumption-Based Truth Maintenance System", Artificial Intelligence, vol. 28, No. 2, 1986.

Rich, E. , Artificial Intelligence, McGraw Hill, pp. 181-184.

Formal inference systems based on nonmonotonic logic are in general non-semidecidable. The reason is that in order to apply a default rule, the system must check for contradictions in the default conditions and consistency of the default conclusions. Thus in addition to proving that the default conditions are satisfied, it must also try to prove the negation of the conclusion to verify consistency of these conclusions. Since any first-order logic system is semi-decidable, at best, this means that it can only be guaranteed to stop in finite time if the negation is true, but might run forever if the conclusion is consistent, i.e., the negation of the conclusion can not be proven true.

Thus nonmonotonic systems suffer from the following two major problems. First, nonmonotonic systems can be excruciating slow because of the repeated need for consistency checking. Secondly, the non-decidability of nonmonotonic inference is such that any system using this logic will necessarily make mistakes from time to time (or loop indefinitely). See [Israel, 1980] or [Perlis, 1986] for more discussion on this topic.

Classical logic allows just two truth values; True or False (nil). Kleene's [1952] 3-valued logic was originally designed to accommodate undecided mathematical statements. The third truth value represents an "undecided" value ("u") to indicate a state of partial knowledge. If a component of a logical sentence is not known, its truth value is designated as "u". Three-valued logic provides the mechanism to draw conclusions when the information implies a conclusion and propagates lack of information, otherwise. For example the conjunction (AND P Q) would be assigned the value of "True" if both P and Q are true, "False" if either P or Q are false, and "Undecided" if neither P nor Q are false but either P or Q are undecided. A complete set of truth tables are provided below.

Other versions of 3-valued logic can be found in the following references.

Haack, S., Deviant Logic, Cambridge Univ. Press, 1974.

Haack, S., Philosophy of Logics, Cambridge Univ. Press, 1974.

Kleene, S., Introduction of Metamathematics, Van Nostrand, 1952.

Lukasiewicz, J, "On 3-valued Logic," in: McCall, S., Polish Logic, Oxford Univ. Press, 1967.

Lukasiewicz, J, "Many-Valued Systems of Propositional Logic," in: McCall, S., Polish Logic, Oxford Univ. Press, 1967.

Fig. 1. Three Valued Logic Table

3. Fuzzy Logic and Commonsense Reasoning (Lotfi Zadeh's papers to be put on reserve in the Engineering Library for Week 11 lecture.)

Fuzzy logic goes beyond 3-valued logic in generalizing classical logic to multiple values. In fuzzy logic the set of truth values can fall anywhere in the interval [0,1]. Zadeh advocates the use of countable subsets of these values to make the complexity manageable. He refers to these structured subsets as linguistic truth values such as {true, mostly true, more or less true, not very true, false}.

Let me provide you with a quick introduction to fuzzy sets via a simple example. The main idea in fuzzy set theory is that an element has a degree of membership in a fuzzy set. Consider the fuzzy set "thinness" for a pressure bearing cylinder. The elements are the ratios of radius to thickness of pressure bearing cylinders and their degree of membership depends on their numerical measure of the ratios as shown in the table below:

In the 1950’s the English economist Shackle [1961] proposed a nonprobabilistic framework for decision making based on the notion of "possibilities". In the 1960’s Dempster [1967] introduced the notions of upper and lower probabilities, which were not additive, for dealing with incomplete data. Shafer built on the Dempster model and interpreted these upper and lower probabilities as degrees of plausibility and belief, respectively and introduced the approach to uncertainty management sometimes referred to as "Dempster-Shafer" theory. One distinction of this theory is that it does not require a prior probability for each individual event, but a prior measure of "belief" to classes of events.

"Possibility theory" was introduced by Zadeh in 1977 based on his previous notions of fuzzy sets developed in the 1960’s. In possibility theory, the uncertainty of an event is described both by the degree of possibility of the event itself and by the degree of possibility of the contrary event, with some weak relationship between the two. The complement (normalized to 1) of the possibility of the contrary event can be interpreted as the degree of necessity (certainty) of the event itself [Dubois and Prade, 1988].

Unlike a network of computer data bases, human knowledge is dispersed and autonomous. Virtually everyone has information relevant to solving a problem if only this information can be tapped. Incorporating this human knowledge in computer systems is the goal of knowledge engineering. When problems involve failures and uncertain events, as in engineering diagnostic problems, the knowledge is seldom of a binary nature and thus classical approaches to expert systems may be inadequate. Multivariate logics using probability measures may be needed. I refer to the discipline devoted to representing and encoding probabilistic knowledge as probabilistic knowledge engineering. Probabilistic inference will be covered in the next weeks.