

![0_image_0.png](0_image_0.png)

(the value for the negative class is greater than the one of the positive class); each of the negative literals codes one of the sets in C ′ . The default class is "+". - Suppose now that there exists a decision committee f with at most k literals consistent with LS. Denote t 1 , t 2 , ..., t 1 f 1 each monomial of f, in no specific order, and A 1 , A 2 , ..., A I/I
their associated values for ∆ . The monomials of f can belong to three types of subsets of monomials:
- monotonous monomials (without negative literals),
- monomials containing only negative literals,
- monomials containing positive and negative literals.

Let us call respectively M , N , M N these three classes. Given that each monomial of f can be associated to a positive or a negative ∆ , there exists on the whole six classes of rules, presented in Figure 5.

Any monomial of f containing at least one positive literal can only be satisfied by positive examples. Therefore, if there exists rules belonging to class II or VI, we can remove them without losing consistency. Furthermore, since e¯ contains only negative literals, if we remove their negative literals from all rules belonging to class V (making them go to class I), we do not lose consistency. As a consequence, we can suppose without loss of generality that all rules of f are in class I, III, or IV.

We now treat independently two cases, depending on whether the default class of f is
"+" or "-"

1. The default class is "-". Any positive example satisfies therefore a monomial in f .

There can exist two types of positive examples: those satisfying at least one rule of class I, and those not satisfying any class I rule (therefore satisfying at least one rule of class III). e¯ satisfies all class III and IV rules. Therefore,

$$\sum_{(t_{i},\vec{v}_{i})\in f\cap(\mathrm{\boldmath~\class~III~}\cup\mathrm{\boldmath~\class~IV~})}\Delta_{i}\,\leq0\;\;.$$
$$\left(\,1\,1\,\right)$$

This shows that, if a positive example not satisfying any class I rules would satisfy all class IV rules, then it would be misclassified, which is impossible by the consistency hypothesis. This gives an important property, namely that any positive example not