Symbolic Reasoning with Relative Orders of Magnitude
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Qualitative Reasoning and Naive Physics. Pages 1509-1514.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
Reasoning with relative orders of magnitude is particularly appropriate when it is necessary to capture commonsense reasoning and tackle engineering tasks involving complex physical systems. The ftrst systems to be proposed, FOG [Raiman, 1986] and O(M) [Mavrovouniotis and Stephanopoulos, 1987], are however limited and thus not widely used. In this ftrst paper, only symbolic reasoning is considered, and the limitation due to the impossibility of expressing a gradual change in order of magmtude is tackled. A new relation "to be distant from" is introduced, followed by the 15 axioms of the ROM(K) system and 45 or so properties which have a clear qualitative meaning. A simple algebraic formalization of this perfectly symmetric framework with two degrees of freedom and a set structure overlap is then given, its consistency being proved by building a family of models in the fteld of real numbers of non standard analysis. The result is 15 primitive relations which, thanks to their overlapping, allow gradual transitions in order of magnitude to be expressed smoothly. The conclusion leads into the second paper [Dague, 1993] which concerns the sound transposition of the rules of O(M) in ~ for connection with the numeric world and control of the inferences.
- D. Bobrow, Qualitative Reasoning about Physical Systems, MIT Press, Cambridge, 1985.
- P. Dague, "Model-based diagnosis of analog electronic circuits," Annals of Mathematics and Artificial Intelligence, forthcoming.
- P. Dague, "Order of magnitude revisited," 2nd Interna- tional Workshop on Qualitative Physics, Paris, July 1988.
- P. Dague, " Numeric reasoning with relative orders of magnitude," Proceedings of AAAI Conference , Washington, July 1993.
- P. Dague, P. Deves, and 0. Raiman, "Trouble- shooting: when Modeling is the Trouble," Proceedings of AAAI Conference, Seattle, July 1987 . .
- J. de Kleer and J.S. Brown, "A qualitative physics based on confluences," Artificial Intelligence 24, 1984.
- J .-L. Dormoy and 0 . Raiman, "Assembling a device, " Proceedings of AAAI Conference, St. Paul, August 1988.
- K .D . Forbus, "Qualitative process theory," Artificial Intelligence 24, 1984.
- B.J . Kuipers, "Qualitative simulation," Artificial Intel- ligence 29, 1986.
- M .L. Mavrovouniotis and G. Stephanopoulos, "Rea- soning with orders of magnitude and approxi- mate relations," Proceedings of AAAI Conference, Seattle, July 1987.
- S.S. Murthy, "Qualitative reasoning at multiple resolution," Proceedings of AAAI Conference , St. Paul, August 1988.
- Raiman, "Order of magnitude reasoning," Proceedings of AAAI Conference, Philadelphia, August 1986.
- Raiman, "Order of magnitude reasoning," Artificial Intelligence 51, 1991.
- P. Struss, "Mathematical aspects of qualitative reasoning," AI in Engineering 3-3, 1988.
- L. Trave-Massuyes and N. Piera, "The orders of mag- nitude models as qualitative algebras," Proceedings of the Eleventh /JCAI, Detroit, August 1989. IJCAI
- B.C. Williams, "MINIMA: a symbolic approach to qualitative algebraic reasoning," Proceedings of AAAI Conference, St. Paul, August 1988.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
The use of qualitative reasoning has expanded consid erably since the eighties [Bobrow, 1985], the principal fteld of application being the behavioral modeling of physical systems when purely numeric models are too complex or when available knowledge is imprecise or uncertain. For these intelligent engineering tasks, qual itative reasoning methods are required that are suffi ciently flexible and subtle to be able to incorporate numeric processing and be implemented efficiently.
The ftrst qualitative models used only signs of quan tities and associated equations, called confluences [de Kleer and Brown, 1984, Dormoy and Raiman, 1988]. This structure of signs { -,0, + ,?}, even coupled with the structure of real numbers and using computer algebra as in MINIMA [Williams, 1988], is in general insufficient. lmpro\'cments allowed qualitative classes to be expressed from an ordered set of landmarks [Forbus, 1984, Kuipers, 1986], but this sometimes led to interval calculus which raises some difficulties at the qualitative level [Struss, 1988]. This can also be seen as reasoning about absolute orders of magnitude represented by a partition of ~- A general algebraic structure, called Q-algebra, has been defmed in this framework [Trave-Massuyes and Piera, 1989], but many problems still need to be overcome if an efficient tool is to be built from this axiomatics. Some attempts to unify the various quantity spaces have also been made [Murthy, 1988].
Another approach is to take relative orders of magni tude, represented by binary relations expressing respec tive orders of magnitude between two quantities, in order to capture a type of commonsense reasoning used by experts ("close to", "negligible w.r.t.") when simplifying problems. It is this type of relative order of magnitude reasoning that concerns us here, more pre cisely when relations r are invariant by homothety (A r B depends only on A/B). The frrst attempt to for malize such reasoning appeared with the formal system FOG [Raiman, 1986], based on 3 basic relations and described by 32 inference rules. It has been used suc cessfully in the DEDALE system of analog circuit diagnosis [Dague et al., 1987] for reasoning about the current intensities, which are not directly observable. Nevertheless, FOG has several limitations and carmot really be used in engineering. The two most obvious ones are the difficulty to incorporate quantitative infor mation when available and the difficulty to control the inference process, in order to obtain valid results in the real world. These problems were pointed out in [Mavrovouniotis and Stephanopoulos, 1987] but the proposed system O(M), made up of 28 relations, does not really solve them (the validity in ~ is not guaran teed any more than in FOG when chaining rules).
In fact, trouble arises already at the formal level both in FOG and O(M) when wanting to express a gradual change from one order of magnitude to another: only a steep change is possible, due to the non overlapping of the orders of magnitude. In this paper, the tdeas of which were sketched in [Dague, 1988], a solution to this problem, in the shape of a formal system, is given that is based on sound principles. The second paper [Da~e, 1993] shows how to transpose this system to ~ wtth a guarantee of soundness, solving the two other problems mentioned above.
The present paper is organized as follows. Section 2 explains why FOG is unable to express changes in order of magnitude smoothly. Section 3 contains the 15 axioms of our system ROM(K) and their qualita tive meaning, with in particular the introduction of a new relation "to be distant from". Section 4 gives a series of properties that can be derived from the axioms. These properties have an obvious and intuitive interpretation in qualitative terms and will be used together with the axioms as inference rules. In section 5 a very simple algebraic formalization of ROM(K) is given, which provides a set overlap. Section 6 is a pres entation of models of ROM(K) in non standard anal ysis, ensuring the consistency of the axioms. In section 7 the objective of allowing smooth changes in order of magnitude is shown to have been attained. Section 8 lists a series of 15 primitive relations allowing the building of 47 compound ones. Section 9, the conclu sion, introduces the second paper [Dague, 1993] con cerning the translation of the results in IR.
2 The problem of smoothly expressing changes in order of magnitude
The formal system FOG introduced three relations Vo ("close to"), Co ("comparable to") and Ne ("negligible w.r.t."), the a:xiomatics of which was described by 32 rules. This set of rules was not minimal, a lot of rules being redundant or consequences of other ones. It was proved to be consistent by giving an interpretation of the relations in the field of real numbers R of N.S.A. (Non Standard Analysis), such that all rules were true in this interpretation.
When usmg FOG for symbolic representation and reasoning, a lack of expressivity arises. For example, in order to describe the relative orders of magnitude of two positive quantities A<B that gradually move apart, only the following exclusive relations can be expressed: AVo B, -,(AVo B) "A CoB, A NeB.
Having such exclusive relations as primitives is not satisfactory for knowledge representation. In this example, it does not capture the gradually increasing "distance" between A and B. When modeling the behavior of a device, or a process, it is in general impossible to use such an abrupt discontinuity: how can one say that one suddenly passes from A Vo B to -,(A Vo B) " A Co B ? An answer is generally to drop the principle of the excluded middle and to use compound relations built as disjunctions of successive primitive ones in order to obtain overlapping relations. This gives in our case: A Vo B, A Co B, -,(A Vo B) "A CoB, -,(AVo B), A NeB.
The problem is that the two new relations thus created are too coarse to express the transition between the adjacent relations and therefore carry very little information. This lack of flexibility comes from the fact that in some sense FOG has only "one degree of freedom". Indeed, it results from the rules of FOG that Ne is defmed in terms of Vo and from the interpreta tion ~ven in N.S.A that Co is nothing else than the negation of Ne, i.e. for positive quantities A and B one has: A Co B <=> -,(A Ne B) " -, (B Ne A).
Thus, everything can be expressed with only one relation. It can be objected that the above property of Co comes from the given interpretation but is not expressed in the rules: one of the rules just says that Co implies -, Ne, but not the converse. But, firstly, it would still have to be shown that the converse is not a logical consequence of all the rules (we will actually prove this result by producing an interpretation in which the converse does not hold) and secondly, admitting this result does not give a satisfactory answer to the problem. In fact, not only does the problem of the transition between Vo and -, Vo remains unsolved, but the rules of FOG do not provide any direct infor mation about the new exclusive relation -,(A Co B) " -,(A Ne ·B) that would be introduced "between" Co and Ne.
In terms of sets (since the relations are invariant by homothety they can equally be represented by the sets of elements which are related to 1), the problem comes from that the sets do not overlap. The idea is thus to introduce a fourth set to make the structure overlap. This is done by introducing a fourth relation which captures the intuitive notion "to be distan.t from" and solves the problem of transition between orders of magnitude at the symbolic level, by giving means to defme and use overlapping relations. In addition this gives an elegant and completely symmetric axiomatic framework with "two degrees of freedom" (constrained by a dependency relation) .
3 Axioms of ROM(K)
Quantities are taken in a totally ordered commutative field K (K is thus characteristic zero, i.e. it contains the field of rationals 0! as a subfield) and the formal system ROM(K) is defmed by 15 axioms noted (Ai) , in which four binary relations ~. "'· ~ and t are involved. The intuitive meanings of these relations are the following: ~ stands for "close to", "' for "compa rable to" (same order of magnitude), ~ for "negligible w.r.t." and t for "distant from". The first three are thus analogous to Vo, Co and Ne of FOG respectively; the last one is a new defmed relation. In the following, [A] stands for the sign of A induced by the total order of K and I A I stands for the absolute value of A. The 15 axioms are as follows:
(Al) A~A
(A2) A~B ~ B~A
(A3) A ~ B, B ~ C ~ A ~ C
(A4) A"'B ~ B"'A
(AS) A "' B, B "' C ~ A "' C
(A6) A~B~A"'B
(A7) A ~ B ~ C.A ~ C.B
(A8) A "' B ~ C.A "' C.B
(A9) A "' 1 ~ [A] = +
(AlO) A ~ B _... B ~ (B +A)
(All) A ~ B, B "' C ~ A ~ C
(Al2) A~ B, [C] = [A] ~ (A+C) ~ (B+C)
(Al3) A "' B, [C] = [A] ~ (A+ C) "' (B +C)
(Al4) A"' (A+ A)
(Al5) At B _... (A-B)"' A or (B-A)"' B
This set of axioms will later be shown to be con sistent and is assumed to be minimal, i.e. no axiom is a logical consequence of the others. This will appear as a reasonable conjecture with the algebraic formulation of the axioms given later. Note that ihe first 12 axioms are present (in the same form or as particular cases) in the rules of FOG (see rules AI, RO, R3, Rl, RS, R2, R22, R21, RIO, R23 and R24, R8, Rl7 respectively) and that the last 3 do not appear in FOG.
Let us now look at these axioms in more detail. Two axioms are equivalences that can be seen as defi nitions: (AIO) defmes the relation ~ in terms of ~ (a quantity is negligible w.r.t. another iff the quantity obtained by adding it to the second one remains close to this second one) and (AlS) defmes the new relation t. in terms of "' (two quantities are distant iff their dif ference is comparable to one of them) . Thus, there are only two basic relations ~ and "', the properties of which are given by the other 13 axioms: note that axiom (All) has been written using ~ only for con venience but, taking into account defmition (AIO), it could equally well have been written as:
(All ') B "'C, B ~ (B+A) ~ C ~ (C+A).
Axioms (AI) to (A3) state that ~ is an equivalence relation (reflexive, symmetric and transitive) and axioms (A4) to (A6) state that "' is also an equivalence relation, which is coarser than ~ (see (A6)).
The two axioms (A 7) and (A8) state that both ~ and "' are stable by homothety (relation between A and B depends only on the ratio A/B). It follows that the two relations ~ and "' are entirely determined by the class of 1 for ~ and the class of 1 for "'.
Axiom (A9) introduces a coupling between these relations and signs: any element in the class of 1 for "' is positive. In fact, it can easily be deduced from (A8,A4,A9) that two elements which are comparable (ar1d a fortiori (by A6) which are close) have the same sign (see property (Pl) below). Unlike [Mavrovouniotis and Stephanopoulos, 1987], it is con sidered important to incorporate the sign in the notions of close and comparable, i.e. to consider these relations as applying to algebraic quantities with their sign and not to absolute values of quantities. In tlus way it is possible, for example, to derive [A]= -[B] from A+ B + C = 0 and C~A: if we have 3 currents at a node with one negligible w.r.t . another, then one of the two main ones is flowing in and the other is flowing out. It follows in particular that the only quantity comparable to 0 is 0 ttself.
Axiom (All) expresses the intuitive relation between the two notions "negligible" and "comparable": if two quantities are comparable, any quantity which is negli gible w.r.t. the first one is also negligible w.r.t. the second one. As mentioned above, it expresses in fact a coupling between the two basic relations ~ and "' (see (All')): if two quantities are comparable and if adding a third quantity to the first one gives a close quantity, then adding the same quantity to the second one will also ~ve a close quantity.
Axtoms (Al2) and (A13) state that both relations ~ and "' between two quantities (necessarily having the same sign by (PI)) are preserved by adding a quantity of the same sign, i.e. when moving the two quantities away from 0 by the same amount. It is easy to prove that, using invariance by homothety (A 7) (resp. (A8)), the axiom (Al2) (resp. (A13)) is equivalent to saying that if two quantities are close (resp. comparable) then any quantity between them (for the order of K) is close (resp. comparable) to them (see properties (P21), resp. (P22) below). Considering the second formu lation of (A13), more precisely using (Al3,A8,A4,A5), it is clear that the axiom (A9) expressmg the coupling of "' with signs could be replaced by the weaker axiom that simply says that the relation "' is not the universal relation: 3 A,B -,(A "' B).
Axiom (Al4) states that, by adding a quantity to itself, one obtains a comparable quantity, i.e. that I and 2 are comparable. In fact, assuming the axioms (A4) to (A8), (AlO) and (A13), it is possible to show that this new axiom (A14) is simply equivalent to:
3 A:;<:B e Q~ (A ,...., B or A ~ B) i.e. there exist at least two different standard positive rational numbers that can be compared by the relation (A ,...., B or A ~ B). Adding this new axiom to the others is thus not very restrictive, and would seem to be the very least that we could demand if we want enough, though not all, positive quantities to be com parable by this relation (remember that in the N.S.A. mterpretation of FOG, any two positive quantities were comparable by this relation).
4 Properties of ROM(K)
Here are some properties (Pi) of ROM(K), i.e. theo rems that can be demonstrated from the axioms (Ai). Only those properties that have a clear intuitive qual itative meanmg and illustrate the qualitative dependen cies between the four relations are given. Along with axioms, they will constitute production rules of a sym bolic deduction system ROM. Some of these proper ties are similar to rules of FOG (in fact all rules of FOG can easily be proved to be true in ROM) and a lot of them are original: it is particularly the case of the 19 properties (P26) to (P44) which concern the new relation *· Proof comes down to simple algebraic cal culus and properties are given in a logical order which makes it easier to demonstrate a new property by using previously demonstrated properties and axioms, which are indicated between parentheses.
- (PO) A,...., A (Al,A6)
- (Pl) A,...., B ~ [A] = [B] (A8,A4,A9)
- (P2) 0 ~A (AIO,Al)
- (P3) A~ B ~ C.A ~ C.B (AlO,A7)
- (P4) A ~ B, A ,...., C ~ C ~ B (A8,P3,A4,A 11 ,P 1 ,P2)
- (PS) A~ B ~ -A~ B (AlO,A2,A6,All)
- (P6) A ~ C, B ~ C ~ (A+ B) ~ C (PS,AlO,A2,A3,A6,All)
- (P7) A~ (A+ B) ~ A~ (A-B) (AlO,PS)
- (P8) A~ B ~ A~ -B (P5,P3)
- (P9) A ~ B, C ~ B ~ A ~ (B +C), A ~ (B-C) (AlO,A6,All,P5)
- (PlO) A~ B ~ A~ (B+A), A~ (B-A) (P9)
- (Pll) A~ B, B ~ C ~ A~ C (A 1 O,A6,P4,PS,P6)
- (Pl2) A ~ 0 +--+ A ,...., 0 +--+ A ~ 0 +--+ A ~ A
- +--+ A=O (A6,A4,P2,P4,P5,Al0,A2,Al,Pl)
- (Pl3) A~ B ~ IAI < IBI or (A=B=O) (AIO,A6,Pl,P5)
- (Pl4) two from (A "' B, A "' -B, A ~ B, B ~ A) ~ A=B=O (Pl,A4,All,Pl2,P8,Pll)
- (PIS) C"' (A+ B), C ~A ~ [A] = -[B] (P4,P5,AIO,A6,P I)
- (Pl6) A~ B, [C] = [B] ~ A~ (B+C) (AlO,Al2)
- (Pl7) A~ B, C ~ D, [C] = [A] ~ (A+C) ~
- (B+ D) (Al2,A6,Pl,A3)
- (Pl8) A"' B, C "' D, [C] = [A] ~ (A+ C) "' (B +D) (Al3,Pl,A5)
(Pl9) A <{ B, C <{ D, [B] = [D] f-+ (A+ C) <{ (B+D) (AIO,Pl7)
- (P20) (A+ C) <{ (B +C), [C] = [A] f-+ A <{ B (P3,Pl3,Pl6)
- (P21) A~ B, A~ C ~ B f-+ C ~A, C ~ B (A7,Al2,Al,A2)
- (P22) A "' B, A ~ C ~ B f-+ C "' A, C "' B (A8,A 13,PO,A4)
- (P23) (B +C) <{ A, [B] = [C] f-+ B ~ A (AIO,A7,Al2)
- (P24) A <{ B, I c I ~ I A I, I D I z I B I f-+ c <{ D (Pl6,P23,P5,P8,P2,Pl2)
- (P25) A"' B f-+ A"' (A+ B) (Al3,Al4,A5)
- (P26) At. B f-+ B t. A (Al5)
- (P27) 0 t. A (Al5,PO)
- (P28) At. A f-+ A = 0 (Al5,Pl)
- (P29) A t. (A+ A) (A15,Al4)
- (P30) At. -A (Al5,Al4,A4)
- (P31) A<{ B or B <{A or A"' -B f-+ At. B (Al5,P5,AIO,A6,A4,P25)
- (P32) A <{ B or A "' B or A "' -B f-+ A t. (A+ B), At. (A-B) (Al5,AIO,A6,P8,A4,P25)
- (P33) At. (A-B), B t. (B-A) -.+ A"' B or A "' -B (Al5,A4,A8,A5,P25)
- (P34) A ~ B, A t. B f-+ A= B = 0 (Al5,AIO,P5,P4,Pl2,A2)
- (P35) A t. B f-+ C.A t. C.B (A 15,A8)
- (P36) At. B, C <{A f-+ C <{ (A-B) (Al5,A4,All,Pl6,Pl2,P2,Al3,A5,P8)
- (P37) A~ B, Ct. A f-+ (C-A) ~(C-D) (P36,AIO,P26,A 7)
- (P38) A t. B, C ~ A, D ~ B f-+ C t. D (P26,A2,P37,A6,Al5,A4,A5,A8)
- (P39) A t. B, (A+ C) "' A, (B +C) "' B f-+ (A+ C) t. (B +C) (Al5,A4,A5)
(P40) A t. B, C ~ A ~ B ~ D f-+ C t. D
(P26,P35,P28,P27 ,A 15,A 13,P 1 ,A 14,A5,A8,A4,P25,P22)
(P41) [A] i= [B] f-+ At. B (P27,P40,P26)
- (P42) (A+ C) t. (B+ C), [C] = [A] f-+ At. B (P35,P40,P26)
- (P43) At. (A+ B) f-+ At. (A-B)
(A 15,P25,P27 ,A 13,A8,A4,P26,P42)
- (P44) A "' B or A t. B (P41 ,PO,A8,P35,A4,P26,A 14,P22,P29 ,P40)
Let us now look at some of these properties in more detail.
(P3) states that <{ is stable by homothety.
(All) and (P4) state that <{ is compatible with "' and thus defmes a relation between equivalence classes for "'·
(Pll) proves the transitivity of<{. We can conclude from all this that the relation (A "' B or A <{ B) is a partial preorder, that "' is the associated equivalence relation and that ~ is the induced strict order between equivalence classes for"' (other than the class {0}).
(Pl4) proves that the four relations A"' B, A"' -B, A <{ B, B <{ A are two by two exclusive, except when A= B = 0. Notice that it is not assumed that, given any A and B, one of these relations always holds. In fact, (A4,A8,P3,P5,P8,P2,Pl) are used to demonstrate that this would be equivalent to assuming that (A "' B or A <{ B) is a total preorder on positive elements.
Using the above properties about ~ and <{, it is easy to show that if the relation ~ is not trivial, i.e. does not coincide with equality (which is equivalent by
(A6,Pl,A7,Al0) to saying that there exists I i= 0 such that I <{ 1), then the field K is non archimedean (by using standard integers).
From (Al4,P25,A4,A5,A8) any positive standard rational number and more generally by (P22) any element between two positive standard rational numbers is in the class of 1 for"'· Thus, by (All,P13), any positive element I such that I <{ 1 is smaller than all positive standard rational numbers.
(P34) proves that the two relations ~ and t. are exclusive, except for A= B = 0. But it is not assumed that for any given A and B we have (A ~ B or A t. B), which would mean that t. is nothing else, on non zero elements, than the negation of~. In fact, using (P32,AIO,P33,P5), it is shown that it would be equiv alent to assuming that for any given A and B we have (A"' B or A"' -B or A~ B or B ~A).
(P38) shows that t. defmes a relation between equiv alence classes for ~: if two quantities are close, then any quantity which is distant from one is distant from the other. From (P37), the two distances are close.
In (P39) the conditions about C are in particular sat isfied when both (C <{ A or C "' A) and (C <{ B or C "' B) are true, by (AIO,A6,A4,P25) .
(P44) proves in some sense a completeness result: any given two elements are always related by "' or by t. (not exclusively cf. (Al4) and (P29)).
5 Algebraic formalization of ROM(K)
This is in fact a very simple algebraic characterization of the axioms of ROM(K). Taking into account the invariance by homothety of the four relations (A 7, A8, P3, P35), it is just as possible to work with the sets of elements that are related to 1 as with the relations themselves. More precisely, let the 4 sets be:
V = {AlA~ 1}, C = {AlA"' 1},
N= {AlA~ l},D = {AIAt. 1}.
The 4 relations are recovered from these sets by: A~ B -.+ A/Be Vor A=B=O, A"' B -.+ A/B e Cor A=B=O, A<{ B -.+ A/BeN or A= B = 0, A t. B -.+ A/B e D or B = 0.
Axioms (AlO, Al5) express the defmitions of N in terms of V and of D in terms of C by:
(i) N = V -1 and (ii) D = ( 1 - C) U 1 I ( 1 - C)'. The axioms (AI to A3) (resp. A4 to A6) saying that ~ (resp. "') are equivalence relations state that V (resp. C) is a multiplicative subgroup of K', and in fact of K~ from the sign condition (A9). Moreover Vis a sub group of C from (A6). Axioms (Al2, A13), or more explicitly their equivalent forms ( P21, P22), state that V and Care convex subsets of K. We thus have:
(iii) V £ C are multiplicative convex subgroups of K~.
Finally, (All) and (Al4) are expressed by:
- (iv) N is stable by product by C and
(v) Cis stable by addition.
(i) to (v) thus give a concise algebraic axiomatics of ROM(K). What is interested is a non trivial model, i.e. such that N i= {0}, which is equivalent to Vi= {1}. Note that, in the more recent set-based general frame work for order of magnitude reasoning presented in [Raiman, 1991], the above sets Nand C correspond to the sets Small and Rough respectively (see Fig. 1).
From (i) to (v), and by using simple algebraic com putation, the following results can be proved directly, the counterparts of which can easily be found in some of the properties (Pi):
where C - C is a subring of K and N is an ideal of C - C. But note that the set -C U N U C, which is closed by opposite and product, is not closed in general by addition (the difference between two ele ments in C does not necessarily belong to this set) . More precisely, the following equivalences hold:
K = C U -C U N U 1 I N <=> K = V U D <=> -C U N U Cis a ring <=> -C U N U C = C - C All these are the same, in terms of relations, as sayin~ that, in some sense, ""' is nothing else than the negatlon of <{ on positive elements:
A""' B .....-.. -.(A<{ B)" -.(B <{A)" [A]=[B] for non zero A,B. This is also equivalent to saying that t is nothing else than the negation of :::::: on non zero elements:
At B .....-.. -.(A:::::: B) for non zero A,B. Let us call these equivalences property F.
This clarifies the links between ROM(K) and FOG, because the model proposed for POG is exactly the same as the particular case of ROM(K) satisfying property F. But this leads to the removal of the "gap" between Nand C (or between V and D) and to having only one degree of freedom instead of two.

6 Models of ROM(K) in Non Standard Analysis
Having seen the axioms and properties of the formal system ROM(K), what is now required is a model in order to prove that axioms are consistent. This model must not possess the property F, so as to show that it is a richer system than FOG. We already know that there is no model in the field IR of standard real numbers because, when using standard integers, K does not satisfy the archimcdean property. Models will be in the field K = R of real numbers of N.S.A., ' but will be different from that of FOG.

Let I be the infmitesirnals of R, and A+ the appreciable positive real numbers, i.e. those which are limited (not infmitely large) and not equal to an infmitesirnal. A+ is made up of all real numbers that are equal to a standard positive real plus an infmitesirnal. The sets C = A+ and D = (1 - C) U 1 I (1 - C)' are now defmed. D is thus exactly the complementary in R of the halo of 1 (halo(l) = 1 + halo(O) = 1 + 1). Then a positive infmitesirnal e is chosen arbitrarily (a family of models, depending of one degree of freedom, is thus obtained, in contrast to the model of FOG which was fixed) and the sets N = e-halo(O) = {a e Riale e halo(O)} = {exili e I} = ex/ and V = 1 + N = e-halo(l) = l + ex/ are defmed (see Fig. 2).
It is now easy to prove that properties (i) to (v) expressing the axiomatics of ROM(K) are satisfied by the four sets just defmed. Moreover, as e does not belong to C or to N, or equivalently as 1 + e does not belong to D or to V, the property F is not satisfied, and the present models are thus different from the trivial model of FOG: there is a "gap" between C and N (where e is) and between D and V (where 1 + e is). In fact, in each particular model we have an e e ]0,1[, with e f C and e f N, such that the following two properties hold for any positive A and B (with an exclusive disjunction):
(A ""' B) v (exA <{ B) v (exB <{ A)
(At B) v (ex(A-B) <{ B)
Remark that if e had been chosen from A+, the exact model of FOG with N = I and V = halo( 1) = com plementary of D would have been obtained. Neverthe less, the archimedean and continuity axioms required in [Rairnan, 1991] are satisfied in these models (using respectively infmitely large integers and infmitesirnals).
7 Smooth changes in order of magnitude
Coming back to the formal system ROM(K), it is now possible to show how it solves the initial problem of smoothly expressing the changes in order of magni tude. This is achieved thanks to the overlapping of the relations that can be defmed. Starting w1th the four relations of ROM(K), and tryin~ to describe the suc cessive relative orders of magrutude of two positive quantities A < B that gradually move apart, the fol lowing would be obtained, in a strict two-valued logic without uncertainty:
A :::::: B, -,(A :::::: B) " -,(A t B), A t B " A ""' B, -.(A""' B) " -.(A<{ B), A<{ B.
But in fact the existence of the two relations -,(A :::::: B) " -,(A t B) and -,(A ""' B) " ..., (A <{ B), which were void in the case of FOG and which correspond to the gaps created in our theory, is not allowed. Instead these gaps will be used as "fuzzy" transition zones. Introducmg uncertainty now by dropping the principle of the excluded middle, the following "scale" of relations for expressing the increasing space between A and B is obtained:
A :::::: B, ..., (A t B), -,(A :::::: B) " A ""' B, A t B " A "'B, At B " -,(A<{ B), -.(A"' B), A<{ B.
The result is 7 basic relations that now overlap, instead of the 3 non overlapping ones ::::::, -,:::::: " -, <{ which would result from the property F (case of FOG).
8 Primitive and compound relations
Taking into account signs and identity, the 7 basic relations above give 15 primitive relations, noted as follows:

These relations overlap (see Fig. 3) and permit a smooth transition between different orders of magni tude. They have to be compared with the 7 non over lapping relations of O(M) coming from the 3 basic ones of FOG. As said previously, it is important to notice that ~-1\ ~ , ~+A~ , -<A ..cE< , >-A»-- are not existing relations in our system. Rules of inference of the formal system ROM, coming from axioms (Ai) and properties (Pi), can be expressed for these 15 relations (it is just necessary to consider the signs of the quantities and split the different cases into prem ises, which may improve the conclusion thanks to this new knowledge).
Adding the 47 compound relations obtained by dis junction of successive primitive relations gives a total of 62 legitimate relations, to be compared to the 28 relations of O(M).
9 Towards numeric reasoning with relative orders of magnitude
We now have a clear, sound and rich system to formally reason about relative orders of magnitude and help guide intuition. It allows in particular the evolu tion of behavior when modeling physical systems to be qualitatively described. Gradual changes in order of magnitude are useful for the expert to defme the models and more information can be deduced by infer ence than with FOG or O(M) . This clearly appears in DEDALE when modeling a transistor and looking for the actual behavior of a circuit ~Dague, forthcoming].
Nevertheless, the two other limitations mentioned in the introduction, i.e. the lack of a numeric-symbolic interface and the difficulty to control the symbolic inference process, remain present in ROM as in FOG. This restricts the use of ROM to cases where addi tional information is available, such as the fact that inference paths can be controlled from the circuit design, or when the expert guides the inferences, which can easily be understood because of their obvious qual itative meaning. But the fact that, as for FOG, there is no model of ROM in IR, since rules such as transitivity of ~ and "' (A3,A5) or (Al4) are obviously being infringed when recursively applied, limits its use in general engineering tasks. It is thus necessary to sup plement the formal system by a sound order of magni tude calculus in IR. All the theoretical framework presented above is a source of inspiration for this task and all the rules of ROM, since they capture pertinent qualitative information, will serve as guidelines for inferences in IR. The second paper [Dague, 1993] demonstrates the exact counterpart in IR of all axioms and properties of ROM, leading to a powerful tool combining qualitative/symbolic and quantitative/numeric reasoning.
Acknowledgments
My thanks go to the people of the Paris IBM Scientific Center, where this research was done. I would also like to thank Francine Diener for discussion on Non Standard Analysis, Emmanuel Goldberger for research into the application of ROM to chemical processes, Rosalind Greenstein for the English version of this paper and Gilles Dague for the figures .
@inproceedings{ijcai1993p209,
title = {Symbolic Reasoning with Relative Orders of Magnitude},
author = {Dague, Philippe},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {1509--1514},
year = {1993},
note = {Qualitative Reasoning and Naive Physics},
url = {https://ijcai.org/proceedings/1993/209},
}
TY - CPAPER TI - Symbolic Reasoning with Relative Orders of Magnitude AU - Dague, Philippe T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 1509 EP - 1514 UR - https://ijcai.org/proceedings/1993/209 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: