Analysis and Self-Assessment

94 Programming Question

The conditions in the question can be described more abstractly as follows. You are given:

With these abstractions, we can describe the two functions asked for as follows:

Assess Your Comments

Self-check Did you specify in your documentation what should happen if more than one rule for a test applies in a scenario? Just implementing one possibility is not enough. A clarification of the original specification should be given. It might be "all results implied by a scenario will be returned," "the rules are checked in order and the first result is returned," or "only one result should be possible." The latter implies that the implementation should signal an error to the implementors if it finds more than one possible result.

Self-check Did you specify whether a fact could appear in more than one fact set? Either way might make sense. If fact sets are intended to represent values of an attribute, which is what they sort of look like in the given example, then a particular fact should appear in only one fact set. If fact sets are intended to represent propositions of the form "one and only one of the following must be true," then a particular fact could appear in many fact sets. Again, an implementation could support either interpretation. It's the specification that needs fixing.

AI Issues

This problem was inspired by work that was being done with the GBS-Lite Tool. That tool is intended to make it simple for course authors to create goal-based scenarios where, among other things, students run experiments and deriving a valid conclusion from the results.

More generally, this problem has the typical elements of an AI diagnosis system. There are hidden internal states, e.g., diseases, and visible external results, e.g., symptoms. The system under consideration is model-based, because the causal rules go from states to symptoms, not about from symptoms to states.

It should be obvious from the summary that propositional logic is a central issue here. One direct approach to the problem is to build a propositional theorem prover. There are significant limits in the "theorems" that are actually needed. For example, there is no chaining of inferences. Each "theorem" is one inference long. Hence, simpler solutions should exist. One of them is to build a table.

Assess Your Solution


Self-check Did you get a working implementation of do-probe? It's a very straightforward search for an element or elements of a list.

Self-check Did you use the right rule for picking a result? The right rule is that the set of facts in the rule is a subset of the set of facts in the scenario? Possible mistakes: using intersection instead of subset, requiring only one fact to be true, failing to check for more than one fact in a rule.

Self-check Was your loop consistent with your explicit or implicit resolution to the multiple results issue? Several people wrote loops for do-probe that could easily return more than one result, but only two people noted that this was an issue.


As should be clear from the above discussion, consistent-p is hard. No one got a correct working solution, but I didn't expect one. I was hoping for an outline of a simple propositional reasoner. I didn't get that either.

Self-check Did your code work by seeing if the fact in question causes the results seen so far? This doesn't work. A result that's been seen might depend on other facts in the scenario.

Self-check Did your code work by deleting facts from a list of possible facts, when the results they implied failed to occur? This is wrong. It only works for test results that are caused by only one fact. The question explicitly said this was not always the case. In general, if a test result is false, then all you know is that at least of the facts that can cause it is false, but not which one. It's the accumulation of these disjunctions that makes the problem tricky.

In fact, even if you assume that all rules only have one fact in them, this approach doesn't work. Gregg Collins generated a simple example showing that this approach will fail to notice some facts are inconsistent.

Self-check Did you note the logical deficiencies of your solution? I would have awarded full, or almost full credit, to anyone who wrote the "delete facts" code, had they included a decent description of the many things it didn't handle.