Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 7.6.2 Nonmonotonic Reasoning

So far, the reasoning system that we’ve been studying has the following key property:

• As we add premises, it is possible (in fact, likely) that new statements will become theorems.

• As we add premises, no old theorems get eliminated. In other words, if it was possible to prove P before adding the new premise(s), it is still possible to prove it.

Thus we’ll say that our reasoning system is monotonic. The set of provable claims can change in only one (thus the prefix “mono-”) direction as we add premises (in this case, it can only grow).

But not all everyday reasoning has that property. In particular, whenever we make do with incomplete information by exploiting some kind of default fact (for example, assume it’s not raining in Austin unless you know otherwise), we must be prepared to undo some conclusions if new information (for example, that it is actually raining in Austin) comes in.

In default reasoning, we conclude some fact in the absence of some indication that we should do otherwise.

In the system we already have, we can write:

[3] ∀x ((P(x) ∧ ¬Q(x)) → C(x))

But, to use [3] to conclude C(x), we must actually be able to prove ¬Q(x). What if we simply don’t know anything about ¬Q(x)? We’re stuck.

But suppose we could write:

[4] ∀x (P(x) → C(x) UNLESS Q(x))

We w ant to interpret this to mean that we can conclude C(x) unless we have explicit information that Q(x) is true. Of course, if new information about Q(x) shows up, we’ll have to add it to our system. We’ll also have to eliminate any conclusions that we derived based on its absence.

Consider the following claim that might be useful in trying to solve the problem of getting to the airport:

CanDriveToAirport UNLESS (\(\neg\)CarWillStart \(\vee\)

FlatTire \(\vee\)

FireTrucksBlockingDirveway \(\vee\)

StreetsCoveredInIce \(\vee\)

CityLockedDownInEmergency )

Notice that, in everyday planning, we are rarely even conscious of all the terms in the UNLESS clause. If we wanted to build a problem-solving robot (perhaps even a self-driving car), we’d need it also to plan an action without having to stop first and verify that all of the UNLESS terms are in fact false.

Our inference system can’t do this. But there exist formal systems that can. And, of course, people do it all the time.

Big Idea

We use default reasoning to enable us to reason about typical situations without getting completely bogged down worrying about all the unlikely things that might occur. People do this all the time. Intelligent agents and robots will also have to be able to do it.

Inheritance

Recall that we’ve already considered the issue of the flying capabilities of birds. We might be tempted to say:

[1] x (Bird(x)  CanFly(x))

And, if we did that, we’d be right most of the time. But emus and penguins can’t fly. Neither can birds that have just been born or ones with crude oil on their wings or ones with broken wings. What we really want to say here is something like:

[2] x (Bird(x)  CanFly(x) UNLESS (Emu(x)  Penguin(x)  Baby(x)  WingBroken(x)  … ) )

But we want [2] to function like [1] most of the time. If I know that x is a bird and I know nothing else, I want to assume that it can fly.

The flying birds situation is an example of a very common sort of default reasoning in which individuals are assumed to inherit (take on) the properties of a typical member of some class to which they belong. Birds typically fly. Dogs typically have tails. Houses typically have kitchens. People typically can talk.

As with any sort of nonmonotonic reasoning, we must be prepared to undo conclusions if new information (such as the fact that our bird has a broken wing) comes in.