=Paper=
{{Paper
|id=Vol-1212/paper4
|storemode=property
|title=Proportional Reasoning in a Boolean Setting
|pdfUrl=https://ceur-ws.org/Vol-1212/DARe-14-paper-4.pdf
|volume=Vol-1212
|dblpUrl=https://dblp.org/rec/conf/ecai/PradeR14
}}
==Proportional Reasoning in a Boolean Setting==
https://ceur-ws.org/Vol-1212/DARe-14-paper-4.pdf
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)