Non-monotonic Search

In monotonic logic, the following implication always holds true:

(1)	if A Þ B, then A Ù C Þ B

That is, no additional information can invalidate an already established conclusion.

In non-monotonic logic, of which monotonic logic is a special case, implication (1) does not necessarily hold true.

Consider an example: most apples that you know about are red, so if your always reliable friend Bill tells you that he has an apple, you will assume that it is a red apple, that is

(2)	Bill has an apple Þ Bill has a red apple

Now, Bill tells you that it is a yellow apple, so you readjust your conclusion from this additional information. That is you get:

(3)	Bill has an apple Ù Bill has a yellow apple Þ Bill has a yellow apple

Let us consider a more complicated example. You are driving towards town C, when you come to a crossroad, where the road splits into three, one road leading to town A, the second road leading to town B, and the third road leading to town C. You are running low on gas, and you can't reach town C without refueling. Luckily, you have been told that there is a gas station in one of the towns A and B, and you have enough gas left to reach at least one of these towns. You just can't remember, which of A and B has a gas station.

That is, we have

(4)	There is a gas station in town A or in town B, but not in both

Your problem is to pick one of the towns to drive to.

Scenario 1:

You have enough gas to drive to either of the towns, back to the crossroad, and then to the other town. That is, no reason to panic, just pick either of towns A and B. When you arrive there, you'll have the answer to which town has a gas station.

We can formulate this as that your current information allows for two possible worlds: one in which town A, but not town B, has a gas station, and one in which town B, but not town A, has a gas station. Since town A is the nearest, and you want to minimize the minimal distance you have to drive, you pick town A. That is, you apply some rule to prefer one of the possible worlds as the real world.

That is, we have

(5)	(4) Ù A is the nearest town Þ there is a gas station in A

However, when you arrive at town A, you find that it does not have a gas station. From this you can safely conclude that there is a gas station in town B. That is, even though you made a wrong guess, you anyway ended up gaining information, which you wouldn't have done, if you hadn't made any guess at all.

We now have

(6)	((4) Ù A is the nearest town) Ù there is not a gas station in A Þ there is a gas station in B

Luckily, a premise for this scenario was that you have gas enough to drive back to the crossroad and then to town B for your refueling.

Scenario 2:

As above, except that you do not have enough gas left to drive to both towns; you need to pick either, and if it's the wrong one, you're stuck. However, notice that even in this case, assuming you go through the same reasonings and actions as above, implication (6) still holds. You cannot get a refuel, but you have gained information through at least making a choice and acting accordingly. Assume you have enough gas left after reaching town A to drive back to the crossroad - though you cannot continue to town B. Then you can draw a gas station symbol on the road sign to town B and thereby make you information available to other drivers that then will not have to go through what you have been through.

The main point here is that in case of a disjunction, monotonic logic is a show-stopper, while non-monotonic logic at least allows you to proceed by making a choice and acting according to that choice, and by that you may gain information to dissolve the disjunction.