Proposed by Francisco Azevedo

Model-based diagnosis can be seen as taking as input a partially parameterized structural description of a system and a set of observations about that system. Its output is a set of assumptions which, together with the structural description, logically imply the observations, or that are consistent with the observations.

Diagnosis is usually applied to combinational digital circuits, seen as black-boxes where there is a set of controllable input bits but only a set of primary outputs is visible.

The problem is to find the set *S* of all (minimal) internal faults that
explain an incorrect output vector *F* (different than the modelled, predicted,
output vector *N*), given some input vector *I*.

The possible faults consider the usual *stuck-at *fault model, where faulty
circuit gates can be either *stuck-at-0* or *stuck-at-1*, respectively outputting
value 0 or 1 independently of the input.

In the example full-adder circuit below, the single faults that explain the
incorrect output (instead of the expected <00>) are *Gate1 stuck-at-1* or
*Gate3
stuck-at-1*.

`
`
For

The diagnosis problem becomes more complex when the minimal internal malfunction is not a single fault, but rather a set of faulty gates (double faults, triple faults, and so on), with complexity increasing with the cardinality of such set. We may also want to explicitly find (e.g.) double faults instead of single faults to make a problem harder.