Proportional reasoning in a Boolean setting Henri Prade1,2 and Gilles Richard1 1 IRIT, University of Toulouse, France, 2 QCIS, University of Technology, Sydney, Australia prade@irit.fr, richard@irit.fr Abstract. Extrapolations are often based on parallels made between two situa- tions that are thus compared. Comparative information may pertain to similarities as well as to dissimilarities. Analogical proportions, i.e., statements of the form “A is to B as C is to D”, provide a natural way for stating such a parallel. In the Boolean setting, logical proportions, a recently introduced notion that general- izes the idea of analogical proportion, relate four objects through the conjunction of two equivalences between comparison indicators expressing similarities or dis- similarities. Among the 120 existing logical proportions, we identify the ones that are suitable candidates for getting a unique D from C and comparison indicators whose values are obtained from A and B. In order to provide a new introduc- tion to the idea of logical proportion, we first investigate comparative reasoning about objects described in terms of Boolean properties. More precisely, thanks to comparative information that we may have about an object w.r.t. another known object, it is sometimes possible to complete the information we have regarding the initial object. 1 Introduction Extrapolation is often used in a numerical setting for predicting values. Extrapolation in a logical setting has not been much investigated, up to the exception of few recent works [14, 13] for completing rule bases with new rules. Analogical proportions, i.e. statements of the form “A is to B as C is to D”, provide a way of extrapolating D from A, B and C, when the analogical proportion relating the four items has been cast in a logical form [7]. The logical expression of an analogical proportion has been shown to be an important particular case of the remarkable notion of logical proportion which has been recently introduced [10–12]. The general form of a logical proportion is a con- junction of two equivalences between comparison indicators expressing similarities or dissimilarities pertaining to pairs of Boolean variables (A, B) and (C, D). Thus logical proportions appear to be of interest for comparative reasoning. Comparative thinking is pervasive in human mind. It plays a key role in our ap- praisal of situations, but also in taxonomic reasoning and extrapolative reasoning. A simple form of comparative reasoning amounts to reconstruct the description of an ob- ject from the result of comparisons with another object. It is this latter type of reasoning that we more particularly discuss in the first part of the paper in order to provide a new introduction to the idea of logical proportion, before identifying the logical proportions that have an extrapolative power. Given a collection U of Boolean properties, it is a common practice to describe an object A by a set a of properties that this object satisfies. Thus, a is a representation of A, where a is a subset of U. Note that a = ∅ or a = U are not forbidden, since A may have none of the properties in U, or all of them. Having all the characteristics of A w.r.t. the properties in U means that we have a complete knowledge of a (with respect to the conceptual space induced by U). But it may be the case that we have no direct information at our disposal about A, but only some comparative information with respect to another known object B (i.e., where b is known w.r.t. U). Obviously, if we know that A is identical to the known object B, then a = b and we are done. On the other hand, if we know that A is the exact opposite of B, then we are done again with a = U \ b = b (in the following b denotes set complementation). But, in general, we may only have information about partial match and/or partial mismatch. For instance, A shares (or does not share) some properties with another known object B: they are both red, they have both wheels, A has no engine but B has one, etc. From that perspective, there are only 4 types of comparative information between 2 objects A and B: – the properties that A and B share: a ∩ b; – the properties that A has but that B does not have: a ∩ b; – the properties that B has but that A does not have: a ∩ b; – the properties that neither A nor B have: a ∩ b. In the following, we assume that the information is complete (with respect to U) about some of the above comparison indicators. For instance, we know all the properties in U that A and B share. In a k-nearest neighbors-like approach for instance, if a ∩ b and a ∩ b are “sufficiently” large, then we infer that some unknown property of A outside U is the corresponding one for B. For instance, if we know that they are both red, they have both wheels and that B is a vehicle then we may infer that A is plausibly a vehicle as well. This approach, focusing on the similarities between A and B, is indeed quite successful in classification. But, in this paper, we want to take into account other kinds of comparative knowl- edge, not only similarities, but also dissimilarities. Our primary aim is to devise a rigor- ous method to get accurate information regarding A starting from some of the previous types of comparative information. The paper is organized as follows. In Section 2, we investigate how we can compar- atively describe an object A w.r.t. another object B with the help of the different types of comparative information, and we determine, by easy Boolean calculations, in what cases the description of an object may be recovered from the description of another ob- ject and the knowledge of two comparative indicators relating them. We also establish a strong link with logical proportions: these proportions will become the backbone of our ampliative reasoning method. In Section 3, we provide a short background on logical proportions, highlighting some of their remarkable properties. In Section 4, in relation with our initial problem, we investigate the way to solve Boolean equations involving logical proportions, and identify the proportions suitable for extrapolation. After listing and discussing problems of interest in relation with extrapolation in Section 5, we sug- gest a generic transduction / extrapolation rule in Section 6, which, when combined with the equation solving process, provides a potential basis for implementing classifiers, for performing matrix abduction, and more generally for achieving prediction tasks. 2 Indicators as comparative descriptors The 4 expressions given in the introduction provide comparative information regarding A and B and we call them set indicators or indicators for short. We have two types of indicators: - a ∩ b and a ∩ b telling us about properties that both A and B have, or that both A and B do not have: we call them similarity indicators, - a ∩ b and a ∩ b telling us about properties that only one among A and B has: we call them dissimilarity indicators. We notice that the union of the 4 indicators is just U and the intersection of any 2 indicators is empty. 2.1 Basic elements of a theory of set indicators Let us here denote s, t, u, v the four set indicators pertaining to a and b: s = a ∩ b, u = a ∩ b, v = a ∩ b, and t = a ∩ b. Considering that a set indicator can be empty or not, we have 4 × 2 = 16 configurations that we describe in Table 2.1. To each indicator i ∈ {s, t, u, v}, we can associate a Boolean variable i0 defined as: i0 = 1 if i 6= ∅ and i0 = 0 otherwise. configuration s= u= v= t= a ∩ b 6= ∅ a ∩ b 6= ∅ a ∩ b 6= ∅ a ∩ b 6= ∅ 1 a ∩ b 6= ∅, a 6⊆ b; 1 1 1 1 b 6⊆ a; a ∪ b 6= U 2 a ∩ b 6= ∅, a 6⊆ b; 1 1 1 0 b 6⊆ a; a ∪ b = U 3 b⊂a⊂U 1 1 0 1 4 b ⊂ a; a = U 1 1 0 0 5 a⊂b⊂U 1 0 1 1 6 a ⊂ b; b = U 1 0 1 0 7 a=b⊂U 1 0 0 1 8 a=b=U 1 0 0 0 9 a ∩ b = ∅; a ∪ b 6= U 0 1 1 1 10 a ∩ b = ∅; a ∪ b = U 0 1 1 0 11 a ⊂ X; b = ∅; 0 1 0 1 12 a = X; b = ∅ 0 1 0 0 13 a = ∅; b ⊂ U 0 0 1 1 14 a = ∅; b = U 0 0 1 0 15 a = b = ∅; U 6= ∅ 0 0 0 1 16 a = b = ∅ = U 0 0 0 0 Table 1. Respective configurations of two subsets Then the following properties can also be checked in Table 1. max(s0 , t0 , u0 , v 0 ) = 1. This means that the four set indicators cannot be simultaneously empty, except if the referential U is empty which corresponds to line 16 in Table 1. In logical terms we have: s0 ∨ t0 ∨ u0 ∨ v 0 ≡ >. If a 6= ∅, b 6= ∅, a 6= U, b 6= U, we have max(n(u0 ), n(v 0 )) ≤ min(s0 , t0 ). where n(x) = 1 if x = 0 and n(x) = 0 if x = 1. A counterpart of this property holds in possibility theory and have also been noticed in formal concept analysis [4]. This corresponds to lines 1, 2, 3, 5, 7, 9, 10 in Table 1. This also corresponds to the 5 possible configurations of two non-empty subsets a and b (lines 1, 3, 5, 7, 9), first identified by Gergonne [6, 5] when discussing syllogisms, plus two configurations (lines 2, 10) where a ∪ b = U (but where a 6= U, b 6= U). Is should be also noticed that a subset a can be defined from another subset b, with the help of some of its positive and negative similarities s and t with a, and its differences u and v, in many different ways: a=s∪u a=v∪t a = s ∪ (b ∩ t) a = v ∪ (b ∩ u) = u ∪ (b ∩ v) The four indicators s, t, u, v are thus jointly necessary for describing all the situations pertaining to the relative position of two subsets. 2.2 Minimal number of indicators for recovering a subset It is quite clear that, knowing b and having only one indicator cannot give us the com- plete knowledge of a. For instance, there is not a unique subset a such that s = a ∩ b is given. In order to get an accurate view of A starting from comparative information w.r.t. B, we need at least 2 of them. So our problem can now be stated as follows: what are the pairs of indicators which could lead to a complete knowledge of A? More formally, what are the pairs of indicators (i1 , i2 ) such that a is a function of b, i1 , i2 ? As we have 4 indicators, we have 4 choices for i1 and then 3 remaining choices for i2 leading to a total of 12 options. But as the problem is entirely symmetrical in i1 and i2 , we have only 6 cases to manage. 1. i1 = a ∩ b and i2 = a ∩ b: in that case, we compute a = (a ∩ b) ∪ (a ∩ b) = i1 ∪ i2 as the unique solution. 2. i1 = a ∩ b and i2 = a ∩ b: in that case, the solution is not unique for a. In other words, we do not have enough information for computing a. 3. i1 = a ∩ b and i2 = a ∩ b: we start from a = (a ∩ b) ∪ (a ∩ b) = i1 ∪ (a ∩ b), but a ∩ b = (a ∪ b) ∩ b = i2 ∩ b = i2 ∪ b leading to a unique a = i1 ∪ i2 ∪ b. 4. i1 = a ∩ b and i2 = a ∩ b: starting from a = (a ∩ b) ∪ (a ∩ b) = (a ∩ b) ∪ i1 . Since b = (a ∩ b) ∪ (a ∩ b) = (a ∩ b) ∪ i2 , we have (a ∩ b) = b \ i2 leading to the unique solution a = i1 ∪ (b \ i2 ). 5. i1 = a ∩ b and i2 = a ∩ b: this case is the dual of case 2 where b is replaced with b. Similarly, the solution is still not unique. 6. i1 = a ∩ b and i2 = a ∩ b: obviously a = i1 ∪ i2 then a = i1 ∪ i2 . As we can see, there are only 4 pairs of indicators leading to a unique a (we recognize the expressions of the previous subsection), while the 2 remaining pairs are not infor- mative enough to uniquely determine the set a. It could also happen that the given disjoint subsets i1 ⊂ U and i2 ⊂ U are them- selves indicators for other objects C and D different from A and B. A related question arises: given 2 disjoint subsets i1 and i2 , can we always find a pair of objects (C, D) such that i1 and i2 are the values of indicators for the pair (C, D)? In fact the answer to this question is positive and can be proved as follows. Consid- ering only similarity indicators, let us look for a pair (C, D) such that c ∩ d = i1 and c ∩ d = i2 , knowing that i1 ∩ i2 = ∅. The second equation is equivalent to c ∪ d = t∗ where t∗ = i2 , and the problem can be restated as a well known equivalent one: Knowing that i1 ⊆ t∗ , find 2 sets c and d such that: c ∩ d = i1 and c ∪ d = t∗ . It is well known that this problem has solutions (generally not unique). This simple property allows us to change the setting of our initial problem since it appears that having the values of 2 indicators for a pair (A, B) is equivalent to have 2 equalities between indicators for the pair (A, B) and indicators for another pair (C, D). Finally, since the power set 2U is just a Boolean lattice, it is convenient to reword the problem in a simple Boolean setting. When turning to a Boolean framework, ∩ is translated into ∧, ∪ into ∨, and = into ≡. We keep the complementation overbar, as a compact notation, for negation. Ultimately, equivalences between indicators lead to the notion of logical proportion. Let us investigate this Boolean view in the next section. 3 Brief background on logical proportions Adopting a Boolean notation, for a given pair of Boolean variables (a, b), we have 4 distinct indicators: – a ∧ b and a ∧ b that we call similarity indicators, – a ∧ b and a ∧ b that we call dissimilarity indicators. Following the set analysis, comparing a pair of variables (a, b) to another pair (c, d) is done via a pair of equivalence between indicators. 3.1 120 logical proportions As shown in the introductory discussion, it makes sense to consider at least 2 equalities to be in a position to compute d. As a consequence, it is legitimate to consider all the conjunctions of 2 equivalences between indicators: such a conjunction is called a logical 0 1 0 proportion [10, 9]. More formally, let I(a,b) and I(a,b) (resp. I(c,d) and I(c,d) ) denote 2 indicators for (a, b) (resp. (c, d)). Definition 1 A logical proportion T (a, b, c, d) is the conjunction of 2 distinct equiva- lences between indicators of the form 0 0 (I(a,b) ≡ I(c,d) ) ∧ (I(a,b) ≡ I(c,d) ) Since we have to choose 2 distinct equivalences among 4 × 4 = 16 possible ones for defining a logical proportion, we have [16 2 ] = 120 such proportions and it has been shown that they are all semantically distinct. Consequently, if two proportions are se- mantically equivalent, they have the same expression as a conjunction of two equiv- alences between indicators (up to the symmetry of the conjunction). Then a logical proportion is just a particular Boolean formula involving 4 variables and as such, has a truth table with 16 lines. It has been shown [11] that an equivalence between 2 indi- cators has exactly 10 lines leading to 1 in its truth table and any logical proportion has exactly 6 lines leading to 1 in its truth table. First of all, depending on the way the indicators are combined, different types of logical proportions are obtained [9, 11]. There are – 4 homogeneous proportions that involve only dissimilarity, or only similarity in- dicators: analogy A, reverse analogy R, paralogy P and inverse paralogy I (see definitions below). – 16 conditional proportions defined as the conjunction of an equivalence between similarity indicators and of an equivalence between dissimilarity indicators, as, e.g., ((a ∧ b) ≡ (c ∧ d)) ∧ ((a ∧ b) ≡ (c ∧ d)), which expresses that the two conditional objects2 b|a and d|c have the same examples (1st condition) and the same counter- examples (2nd condition). – 20 hybrid proportions obtained as the conjunction of two equivalences between similarity and dissimilarity indicators, as in the following example: a ∧ b = c ∧ d and a ∧ b = c ∧ d. – 32 semi-hybrid proportions for which one half of their expressions involve indica- tors of the same kind, while the other half requires equivalence between indicators of opposite kinds, as, e.g., a ∧ b = c ∧ d and a ∧ b = c ∧ d. – 48 degenerated proportions whose definition involves 3 distinct indicators only. 3.2 The 4 homogeneous logical proportions When we add the constraint of considering homogeneous equivalences only, i.e., con- sidering logical proportions that involve only dissimilarity, or only similarity indicators, 4 logical proportions remain which are listed below with their name: 1 0 Note that I(a,b) (or I(a,b) ) refers to one element in the set {a ∧ b, a ∧ b, a ∧ b, a ∧ b}, and should not be considered as a functional symbol: I(a,b) and I(c,d) may be indicators of two different kinds. Still, we use this notation for the sake of simplicity. 2 A conditional object b|a can take three truth values: true if a ∧ b is true, false if a ∧ ¬b is true, not applicable if a is false; it may be intuitively thought as representing the rule “if a then b” [3]. analogy: A(a, b, c, d), defined by ((a ∧ b) ≡ (c ∧ d)) ∧ ((a ∧ b) ≡ (c ∧ d)) reverse analogy: R(a, b, c, d), defined by ((a ∧ b) ≡ (c ∧ d)) ∧ ((a ∧ b) ≡ (c ∧ d)) paralogy: P (a, b, c, d), defined by ((a ∧ b) ≡ (c ∧ d)) ∧ ((a ∧ b) ≡ (c ∧ d)) inverse paralogy: I(a, b, c, d), defined by ((a ∧ b) ≡ (c ∧ d)) ∧ ((a ∧ b) ≡ (c ∧ d)) Reverse analogy expresses that “a differs from b as d differs from c”, and con- versely; paralogy expresses that “what a and b have in common, c and d have it also”. The inverse paralogy expresses a complete opposition between the pairs (a, b) and (c, d). The truth tables of these homogeneous proportions are recalled in Table 2, where we only show the lines leading to truth value 1. The following proposition, easily de- ducible from the definition, establishes a link between analogy, reverse analogy and paralogy (while inverse paralogy I is not related to the 3 others through a simple per- mutation): Proposition 1 A(a, b, c, d) ↔ R(a, b, d, c) and A(a, b, c, d) ↔ P (a, d, c, b). A R P I 0000 0000 0000 1100 1111 1111 1111 0011 0011 0011 1001 1001 1100 1100 0110 0110 0101 0110 0101 0101 1010 1001 1010 1010 Table 2. Analogy, Reverse analogy, Paralogy, Inverse Paralogy truth tables It is not the aim of this paper to investigate the whole set of properties of this class of Boolean formulas, nevertheless we recall in Table 3 the basic behavior which could be expected from these proportions. To conclude this section, let us note that the analogical proportion is the Boolean counterpart of the numerical proportion ab = dc . As such, it is expected that this propor- tion enjoys a property similar to the well known rule of three for numerical proportions: knowing 3 of the variables, we can compute a 4th one in order to build up a proportion. This is obviously linked to our initial problem where we want to derive some missing information. We will investigate this issue in Section 4. property definition # of proportions homogeneous full identity T (a, a, a, a) 15 A, R, P reflexivity T (a, b, a, b) 6 A, P reverse reflexivity T (a, b, b, a) 6 R, P sameness T (a, a, b, b) 6 A, R symmetry T (a, b, c, d) → T (c, d, a, b) 12 A, R, P, I central permutation T (a, b, c, d) → T (a, c, b, d) 16 A, I all permutations ∀i, j, T (a, b, c, d) → T (pi,j (a, b, c, d)) 1 I transitivity T (a, b, c, d) ∧ T (c, d, e, f ) → T (a, b, e, f ) 54 A, P code independency T (a, b, c, d) → T (a, b, c, d) 8 A, R, P, I Table 3. Properties of logical proportions n 3.3 Extension to B It is unlikely that we can represent objects in practice with only one property. In standard datasets, objects are represented by Boolean vectors, and it does make sense to extend the previous framework to Bn . The simplest way to do it is to consider a definition involving componentwise proportions as follows (where T denotes any proportion and → − → − − → − a , b ,→ c and d are in Bn ): → − − → − T (→−a , b ,→ c , d ) iff ∀i ∈ [1, n], T (ai , bi , ci , di ) where → −x = (x , · · · , x ) for x = a, b, c, and d. All the previous properties of Boolean 1 n proportions remains valid for their counterpart in Bn : For instance, if T = A, then the central permutation property (see Table 3) is still valid: → − − → − −c , → − → − T (→ − a , b ,→ c , d ) → T (→− a ,→ b, d) 4 Equation solving process As said in the introduction, the main problem we want to tackle is to compute miss- ing information starting from existing one. In the context of logical proportions, the equation solving problem can be stated as follows. Given a logical proportion T and 3 Boolean values a, b, c, does it exist a Boolean value x such that T (a, b, c, x) = 1, and in that case, is this value unique? This is what we call the equation solving problem. First of all, it is easy to see that there are always cases where the equation has no solution. Indeed, the triple a, b, c may take 23 = 8 values, while any proportion T is true only for 6 distinct valuations, leaving at least 2 cases with no solution. For instance, when we deal with analogy A, the equations A(1, 0, 0, x) and A(0, 1, 1, x) have no solution. When the equation T (a, b, c, x) = 1 is solvable, a proportion T which has a unique solution will be said univocal. The following proportion is not univocal as can be seen on its truth table (Table 4), despite the fact that it satisfies full identity, reflexivity, sym- metry and transitivity: ((a ∧ b) ≡ (c ∧ d)) ∧ ((a ∧ b) ≡ (c ∧ d)). We have the following result: Proposition 2 There are exactly 64 univocal proportions (including the homogeneous ones). They are the 4 homogeneous proportions, 8 conditional proportions, 12 hybrid proportions, 24 semi-hybrid proportions, and 16 degenerated proportions. 0000 0101 1010 1011 1110 1111 Table 4. A non univocal proportion The formal expressions of the 60 non homogeneous univocal proportions are given in the Appendix at the end of the paper. When considering only the homogeneous proportions A, R, P, I, we have a more detailed result: (already shown in [10] except for I): Proposition 3 The analogical equation A(a, b, c, x) is solvable iff (a ≡ b) ∨ (a ≡ c) holds. The reverse analogical equation R(a, b, c, x) is solvable iff (b ≡ a) ∨ (b ≡ c) holds. The paralogical equation P (a, b, c, x) is solvable iff (c ≡ b) ∨ (c ≡ a) holds. In each of the three above cases, when it exists, the unique solution is given by x = c ≡ (a ≡ b), i.e. x = a ≡ b ≡ c. The inverse paralogical equation I(a, b, c, x) is solvable iff (a 6≡ b) ∨ (b 6≡ c) holds. In that case, the unique solution is x = c 6≡ (a 6≡ b). As we can see, the first 3 homogeneous proportions A, R, P behave similarly. Still, the conditions of their solvability differ. Moreover, it can be checked that at least 2 of these proportions are always simultaneously solvable. Besides, when they are solvable, there is a common expression that yields the solution. This again points out a close relationship between A, R, and P . This contrasts with proportion I which in some sense behaves in an opposite manner. When moving to Bn , the previous result remains valid, i.e. for 64 proportions, the → − − → equation T (→ −a , b ,→c ,− x ) = 1 has at most one solution. From an inference perspective, the equation solving property is the main tool: when we have 3 known objects A, B, C and another one D whose properties are unknown, but we have the information that T (A, B, C, D) for a given univocal proportion, then we can compute D. Let us start with an example to highlight the link with our initial problem. Let us assume Bn contains 6 properties such that every object can be represented as a 6 digits Boolean vector. For instance the object C is represented by the vector c = 100110. Another object D is unknown but we have some comparative information w.r.t. C : for instance we know c ∩ d i.e. the properties that C and D share: c ∩ d = 100100. And we know c ∩ d = 000010. We are exactly in the case 2 of section 2 and we cannot recover D as 3 components are not deducible as shown in Table 5. This is coming for instance from the fact that we have no information regarding the properties which do not belong to C. c 100110 c∩d 1 0 0 1 0 0 c∩d 0 0 0 0 1 0 d 1??10? Table 5. Non computable solution But in the case where we know c ∩ d = 010000, we recover D as in Table 6 where the set d is just (c ∩ d) ∪ c ∩ d ∪ c. c 100110 c∩d 1 0 0 1 0 0 c∩d 0 1 0 0 0 0 d 101101 Table 6. Computable solution 5 Existence of a logical proportion linking 4 Boolean vectors Now we are back to our initial framework of objects represented as collection of Boolean properties. In that case, an object A is represented as a Boolean vector and then belongs to Bn where n is just the cardinal of U (the whole set of properties) We then can provide a list of relevant problems we may need to solve: 1. Given 4 objects A, B, C, D, is there a proportion T among the 120 proportions, such that T (a, b, c, d)? 2. If the answer to question 1 is “Yes”, can we exhibit such a proportion? 3. If the answer to question 1 is “Yes”, is such a proportion unique? 4. Given 3 objects A, B, C and a proportion T , can we compute an object D such that T (A, B, C, D)? (i.e. is T a univocal proportion?) Reasoning about the first problem is relatively straightforward. As soon as we have the Boolean representation a, b, c, d of A, B, C, D, we have to consider the n valuations (ai , bi , ci , di ) corresponding to the components of a, b, c and d. Among these n valua- tions, some can be identical: so let us denote m the number of distinct valuations among these n valuations. Obviously, if m > 7, there is no proportion such that T (a, b, c, d) since only 6 valuations can lead a given proportion to true. If m = 1, we have exactly 45 candidate proportions. If m = 2, we have exactly 15 candidate proportions. If m = 3, we have 3 or 6 candidate proportions. If m = 4, the landscape is a bit different. Obviously, we cannot get more than 6 proportions, but some combinations lead to 0 candidate proportion. In fact, we can have 0, 1, 3 or 6 candidate proportions. For instance: Lemma A logical proportion cannot satisfy the class of valuation {0111, 1011, 1101, 1110} or the class {1000, 0100, 0010, 0001}. Proof: It is enough to show that this is the case for an equivalence between indicators. So let us consider such an equivalence l1 ∧ l2 ≡ l3 ∧ l4 . If this equivalence is valid for {0111, 1011}, it means that its truth value does not change when we switch the truth value of the 2 first literals from 0 to 1: there are only 2 indicators for a and b satisfying this requirement: a ∧ b and a ∧ b. On top of that, if this equivalence is still valid for {1101, 1110}, it means that its truth value does not change when we switch the truth value of the 2 last literals from 0 to 1: there are only 2 indicators for c and d satisfy- ing this requirement: c ∧ d and c ∧ d. Then the equivalence l1 ∧ l2 ≡ l3 ∧ l4 is just a ∧ b ≡ c ∧ d, a ∧ b ≡ c ∧ d, a ∧ b ≡ c ∧ d or a ∧ b ≡ c ∧ d. None of these equivalences satisfies the whole class {0111, 1011, 1101, 1110}. The same reasoning applies for the other class. 2 From a practical viewpoint, as soon as we observe this class appearing as a part of the n valuations (ai , bi , ci , di ), we know that there is no suitable proportion. If m = 5 or m = 6, we get 0 or 1 candidate proportion. 6 Induction with proportions We can now adopt a viewpoint, similar in some sense to the k-nearest neighbors philos- ophy, where we infer unknown properties of a partially known object D starting from the knowledge we have about its other specified properties. This induction principle can be stated as follows (where J is a subset of [1, n]): ∀i ∈ [1, n] \ J, T (ai , bi , ci , di ) ∀i ∈ J, T (ai , bi , ci , di ) This can be seen as a continuity principle assuming that if it is known that a proportion holds for some attributes, this proportion should still holds for the other attributes. It is in some sense similar to the inference principle defined in [16, 15] in the case of the analogical proportion. Let us now explain how we can use this inference principle to predict missing infor- mation for a given object D. Suppose the known part of D are the attributes belonging to [1, n] \ J, the unknown part being the attributes belonging to J: if we are able to find a triple of known objects A, B, C and a univocal proportion T satisfying the premisses of the rule, we solve the equations T (ai , bi , ci , xi ) for every i ∈ J, and the (unique) solution is considered to be the value of di . A particular case of this inductive principle has been implemented for classifica- tion purposes, i.e., when there is only one missing information which is the class of the object. Diverse approaches have been implemented, mainly using homogeneous propor- tions, all of them relaxing the induction principle to allow some flexibility: one can cite [1] using analogical proportion only, [8] using the 4 homogeneous. In terms of accuracy, it appears that the results are similar when using A, R, P , while I exhibits a different behavior. The prediction of missing values, using A, has been recently experimented with success [2] This leads us to the question of choosing the most suitable proportion for a given dataset. We can also consider other proportions among the 60 remaining univocal ones. These proportions express different kinds of regularities, which may be more or less often encountered in datasets. Some of them could also appear as suitable candidates for classification purposes or for completing missing values. The respective roles of the univocal logical proportions is a topic for further research. Generally speaking, the pro- posed approach tends to indicate the possibility of transposing the idea of proportional reasoning from numerical settings to Boolean or nominal worlds. 7 Conclusion We have outlined a systematic discussion of the interest of logical comparison indica- tors, and of their potential value for reasoning tasks such as classification or completion of missing information. We have emphasized the role of logical proportions in these rea- soning tasks exploiting similarities and dissimilarities. In particular, we have identified the univocal logical proportions that are the basic tool in that respect. 8 Appendix The 60 univocal non-homogeneous proportions. – 8 conditional proportions: (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) – 12 hybrid proportions: (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) – 24 semi-hybrid proportions: (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) – 16 degenerated proportions: (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) ; (a ∧ b ≡ c ∧ d) ∧ (a ∧ b ≡ c ∧ d) References 1. Bayoudh, S., Miclet, L., Delhay, A.: Learning by analogy: A classification rule for binary and nominal data. Proc. Inter. Joint Conf. on Artificial Intelligence IJCAI07 pp. 678–683 (2007) 2. Beltran, W.C., Jaudoin, H., Pivert, O.: Estimating null values in relational databases us- ing analogical proportions. In: Laurent, A., Strauss, O., Bouchon-Meunier, B., Yager, R.R. (eds.) Proc. 15th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU’14), Part III, Montpellier, July 15-19. Comm. in Comp. and Inf. Sci., vol. 444, pp. 110–119. Springer (2014) 3. Dubois, D., Prade, H.: Conditional objects as nonmonotonic consequence relationships. IEEE Trans. on Systems, Man and Cybernetics 24, 1724–1740 (1994) 4. Dubois, D., Prade, H.: Possibility theory and formal concept analysis: Characterizing inde- pendent sub-contexts. Fuzzy Sets and Systems 196, 4–16 (2012) 5. Faris, J.A.: The Gergonne relations. J. of Symbolic Logic pp. 207–231 (1955) 6. Gergonne, J.D.: Essai de dialectique rationnelle. Annales de Mathématiques Pures et Ap- pliquées pp. 189–228 (1816-1817) 7. Miclet, L., Prade, H.: Handling analogical proportions in classical logic and fuzzy logics settings. In: Proc. 10th Eur. Conf. on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’09), Verona. pp. 638–650. Springer, LNCS 5590 (2009) 8. Moraes, R.M., Machado, L.S., Prade, H., Richard, G.: Classification based on homogeneous logical proportions. In: Bramer, M., Petridis, M. (eds.) Proc. of AI-2013, The Thirty-third SGAI International Conference on Innovative Techniques and Applications of Artificial In- telligence, Cambridge, England, UK,. pp. 53–60. Springer (2013) 9. Prade, H., Richard, G.: Logical proportions - Typology and roadmap. In: Hüllermeier, E., Kruse, R., Hoffmann, F. (eds.) Computational Intelligence for Knowledge-Based Systems Design: Proc. 13th Int. Conf. on Inform. Proc. and Manag. of Uncertainty (IPMU’10), Dort- mund, June 28 - July 2. LNCS, vol. 6178, pp. 757–767. Springer (2010) 10. Prade, H., Richard, G.: Reasoning with logical proportions. In: Lin, F.Z., Sattler, U., Truszczynski, M. (eds.) Proc. 12th Int. Conf. on Principles of Knowledge Representation and Reasoning, KR 2010, Toronto, May 9-13. pp. 545–555. AAAI Press (2010) 11. Prade, H., Richard, G.: From analogical proportion to logical proportions. Logica Universalis 7(4), 441–505 (2013) 12. Prade, H., Richard, G.: Homogenous and heterogeneous logical proportions. IfCoLog J. of Logics and their Applications 1(1), 1–51 (2014) 13. Schockaert, S., Prade, H.: Completing rule bases using analogical proportions. In: Prade, H., Richard, G. (eds.) Computational Approaches to Analogical Reasoning - Current Trends, pp. 195–215. Springer (2013) 14. Schockaert, S., Prade, H.: Interpolative and extrapolative reasoning in propositional theories using qualitative knowledge about conceptual spaces. Artificial Intelligence 202, 86–131 (2013) 15. Stroppa, N., Yvon, F.: An analogical learner for morphological analysis. In: Online Proc. 9th Conf. Comput. Natural Language Learning (CoNLL-2005). pp. 120–127 (2005) 16. Stroppa, N., Yvon, F.: Analogical learning and formal proportions: Definitions and method- ological issues. Tech. rep. (June 2005)