∗ When does Q**(arg) entail some description built with some other constructor?**
all(p, nothing) ≡ at-most(0, p)
- Reasoning with conjunctions of descriptions built with Q only. **This usually**
results in a normal-form that either combines the arguments **into a single one,**
or keeps the arguments as a list, set or multi-set.

## And(All(P, C), All(P, D)) ≡ All(P, And(**C, D**))

- Rules of inference dealing with combinations of several concept constructors. **These**
rules can be grouped into similar families as above, except that they will involve two or more kinds of constructors.
Since there is no such rule involving all**, we offer an alternative example:**
and(at-most(n, p), at-least(m, p)) ≡ nothing if n<m The augmented set of inference rules should be proven sound and complete with respect to the semantics specified earlier. As with any logic, soundness is relatively easy to show, but completeness is much harder. Royer and Quantz propose one approach (Royer & Quantz, 1992) for generating inference rules that are complete, based on translation to First Order Logic, but the technique is not easy to apply.

(3) Extend the implementation. **This requires first determining an appropriate normal**
form for the argument of constructor Q**, declaring a data structure to hold the information,** and completing the put Q and get Q **procedures to access them from a normalized concept.**
For simplicity, we will not address detailed data structure **issues here; instead, we use a** simple notation based on terms in the style of Prolog to represent data structures. In the case of all, the representation is just a pair all(<Role>,<NormalizedConcept>)**. We**
note that if we wanted to keep track of the original form of the **concept (so it can be printed**
out to users as entered), this could be added as an extra field of the data structure. We emphasize that the normalized form of the description (e.g., a finite automaton) might not even resemble the original syntax (e.g., a regular expression), though in our examples this will not be the case.

Next, we need to implement the three procedures: Q::Normalize,Q::Conjoin**, and**
Q::Subsumes?**, whose invocation is orchestrated by the corresponding functions for the**
and **constructor.**
By analyzing the normalization algorithms for numerous constructors, we have arrived at a more refined understanding of the prototypical Q::Conjoin **procedure. This is presented** in the Appendix A as Figure 3, and uses the following other, smaller functions Q::Universal? , Q::Incoherent? , Q::SubsumesSame? , Q**::ConjoinToSame** , Q::IncoherentWDifferent? , Q::SubsumesDifferent? , Q**::ConjoinToDifferent** , Q**::FindOtherImplications** .

These functions correspond to the categories of inference rules we have mentioned above. When this decomposition can be applied, it provides two advantages: improved chances of correct implementation by making smaller, specialized modules; and independent reuse, as in