Intelligence 2E

foundations of computational agents

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

Reasoning from contradictions is a very useful tool. For many activities it is useful to know that some combination of assumptions is incompatible. For example, it is useful in planning to know that some combination of actions an agent is contemplating is impossible. When designing a new artifact, it us useful to know that some combination of components cannot work together.

In a diagnostic application it is useful to be able to prove that some components working normally is inconsistent with the observations of the system. Consider a system that has a description of how it is supposed to work and some observations. If the system does not work according to its specification, a diagnostic agent should identify which components could be faulty.

To carry out these tasks it is useful to be able to make assumptions that can be proven to be false.

An assumable is an atom that can be assumed in a proof by contradiction. A proof by contradiction derives a disjunction of the negation of assumables.

With a Horn clause knowledge base and explicit assumables, if the system can prove a contradiction from some assumptions, it can extract those combinations of assumptions that cannot all be true. Instead of proving a query, the system tries to prove false, and collects the assumables that are used in a proof.

If KB is a set of Horn clauses, a conflict of KB is a set of assumables that, given KB, implies false. That is, $C=\{{c}_{1},\mathrm{\dots},{c}_{r}\}$ is a conflict of KB if

$$\text{KB}\cup \{{c}_{1},\mathrm{\dots},{c}_{r}\}\vDash \text{false}.$$ |

In this case, an answer is

$$\text{KB}\vDash \mathrm{\neg}{c}_{1}\vee \mathrm{\dots}\vee \mathrm{\neg}{c}_{r}.$$ |

A minimal conflict is a conflict such that no strict subset is also a conflict.

In Example 5.20, if ${\mathrm{\{}}{c}{\mathrm{,}}{d}{\mathrm{,}}{e}{\mathrm{,}}{f}{\mathrm{,}}{g}{\mathrm{,}}{h}{\mathrm{\}}}$ is the set of assumables, then ${\mathrm{\{}}{c}{\mathrm{,}}{d}{\mathrm{\}}}$ and ${\mathrm{\{}}{c}{\mathrm{,}}{e}{\mathrm{\}}}$ are minimal conflicts of ${{\text{\mathit{K}\mathit{B}}}}_{{\mathrm{2}}}$; ${\mathrm{\{}}{c}{\mathrm{,}}{d}{\mathrm{,}}{e}{\mathrm{,}}{h}{\mathrm{\}}}$ is also a conflict, but not a minimal conflict.

In the examples that follow, assumables are specified using the assumable keyword followed by one or more assumable atoms separated by commas.