# Proportional reasoning in a Boolean setting

Henri Prade, Gilles Richard

► To cite this version:

Henri Prade, Gilles Richard. Proportional reasoning in a Boolean setting. International Workshop on Defeasible and Ampliative Reasoning (DARe-14) co-located with the 21st European Conference on Artificial Intelligence (ECAI 2014), Aug 2014, Prague, Czech Republic. pp.1-13. hal-03877772

HAL Id: hal-03877772

https://ut3-toulouseinp.hal.science/hal-03877772

Submitted on 29 Nov 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Proportional reasoning in a Boolean setting

Henri Prade¹,² and Gilles Richard¹

¹IRIT, University of Toulouse, France,

² QCIS, University of Technology, Sydney, Australia

prade@irit.fr, richard@irit.fr

**Abstract.** Extrapolations are often based on parallels made between two situations 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 generalizes the idea of analogical proportion, relate four objects through the conjunction of two equivalences between comparison indicators expressing similarities or dissimilarities. 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 introduction 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 conjunction 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 appraisal of situations, but also in taxonomic reasoning and extrapolative reasoning. A simple form of comparative reasoning amounts to reconstruct the description of an object 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 $\mathcal{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 $\mathcal{U}$. Note that $a = \emptyset$ or $a = \mathcal{U}$ are not forbidden, since $A$ may have none of the properties in $\mathcal{U}$, or all of them. Having all the characteristics of $A$ w.r.t. the properties in $\mathcal{U}$ means that we have a complete knowledge of $a$ (with respect to the conceptual space induced by $\mathcal{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. $\mathcal{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 = \mathcal{U} \setminus b = \bar{b}$ (in the following $\bar{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 \cap b$;

- the properties that $A$ has but that $B$ does not have: $a \cap \bar{b}$;

- the properties that $B$ has but that $A$ does not have: $\bar{a} \cap b$;

- the properties that neither $A$ nor $B$ have: $\bar{a} \cap \bar{b}$.

In the following, we assume that the information is complete (with respect to $\mathcal{U}$) about some of the above comparison indicators. For instance, we know all the properties in $\mathcal{U}$ that $A$ and $B$ share. In a $k$-nearest neighbors-like approach for instance, if $a \cap b$ and $\bar{a} \cap \bar{b}$ are "sufficiently" large, then we infer that some unknown property of $A$ outside $\mathcal{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 knowledge, not only similarities, but also dissimilarities. Our primary aim is to devise a rigorous 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 comparatively 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 object 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 suggest 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 \cap b$ and $\bar{a} \cap \bar{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 \cap \bar{b}$ and $\bar{a} \cap 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 $\mathcal{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 \cap b$, $u = a \cap \bar{b}$, $v = \bar{a} \cap b$, and $t = \bar{a} \cap \bar{b}$. Considering that a set indicator can be empty or not, we have $4 \times 2 = 16$ configurations that we describe in Table 2.1.

To each indicator $i \in \{s, t, u, v\}$, we can associate a Boolean variable $i'$ defined as: $i' = 1$ if $i \neq \emptyset$ and $i' = 0$ otherwise.

<table><caption>**Table 1.** Respective configurations of two subsets</caption><thead><tr><th></th><th>configuration</th><th>s =<br>a ∩ b ≠ ∅</th><th>u =<br>a ∩ b ≠ ∅</th><th>v =<br>a ∩ b ≠ ∅</th><th>t =<br>a ∩ b ≠ ∅</th></tr></thead><tbody><tr><td>1</td><td>a ∩ b ≠ ∅, a ≠ b;<br>b ≠ a; a ∪ b ≠ U</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>2</td><td>a ∩ b ≠ ∅, a ≠ b;<br>b ≠ a; a ∪ b = U</td><td>1</td><td>1</td><td>1</td><td>0</td></tr><tr><td>3</td><td>b ⊂ a ⊂ U</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><td>4</td><td>b ⊂ a; a = U</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>5</td><td>a ⊂ b ⊂ U</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><td>6</td><td>a ⊂ b; b = U</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>7</td><td>a = b ⊂ U</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><td>8</td><td>a = b = U</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>9</td><td>a ∩ b = ∅; a ∪ b ≠ U</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><td>10</td><td>a ∩ b = ∅; a ∪ b = U</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>11</td><td>a ⊂ X; b = ∅</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>12</td><td>a = X; b = ∅</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><td>13</td><td>a = ∅; b ⊂ U</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>14</td><td>a = ∅; b = U</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><td>15</td><td>a = b = ∅; U ≠ ∅</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><td>16</td><td>a = b = ∅ = U</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>
Then the following properties can also be checked in Table 1.

$$ \max(s', t', u', v') = 1. $$

This means that the four set indicators cannot be simultaneously empty, except if the referential $\mathcal{U}$ is empty which corresponds to line 16 in Table 1. In logical terms we have: $s' \lor t' \lor u' \lor v' \equiv \top$.

If $a \neq \emptyset, b \neq \emptyset, a \neq \mathcal{U}, b \neq \mathcal{U}$, we have

$$ \max(n(u'), n(v')) \leq \min(s', t'). $$

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 \cup b = \mathcal{U}$ (but where $a \neq \mathcal{U}, b \neq \mathcal{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 \cup u $$

$$ a = \overline{v \cup t} $$

$$ a = s \cup (\bar{b} \cap \bar{t}) $$

$$ a = \overline{v \cup (\bar{b} \cap \bar{u})} = u \cup (b \cap \bar{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 complete knowledge of $a$. For instance, there is not a unique subset $a$ such that $s = a \cap 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 $(i_1, i_2)$ such that $a$ is a function of $b, i_1, i_2$?

As we have 4 indicators, we have 4 choices for $i_1$ and then 3 remaining choices for $i_2$ leading to a total of 12 options. But as the problem is entirely symmetrical in $i_1$ and $i_2$, we have only 6 cases to manage.

1. $i_1 = a \cap b$ and $i_2 = a \cap \bar{b}$: in that case, we compute $a = (a \cap b) \cup (a \cap \bar{b}) = i_1 \cup i_2$ as the unique solution.

2. $i_1 = a \cap b$ and $i_2 = \bar{a} \cap b$: in that case, the solution is not unique for $a$. In other words, we do not have enough information for computing $a$.
3. $i_1 = a \cap b$ and $i_2 = \bar{a} \cap \bar{b}$; we start from $a = (a \cap b) \cup (a \cap \bar{b}) = i_1 \cup (a \cap \bar{b})$, but $a \cap \bar{b} = (a \cup b) \cap \bar{b} = \bar{i_2} \cap \bar{b} = \bar{i_2} \cup \bar{b}$ leading to a unique $a = i_1 \cup \bar{i_2} \cup \bar{b}$.

4. $i_1 = a \cap \bar{b}$ and $i_2 = \bar{a} \cap b$: starting from $a = (a \cap b) \cup (a \cap \bar{b}) = (a \cap b) \cup i_1$. Since $b = (a \cap b) \cup (\bar{a} \cap b) = (a \cap b) \cup i_2$, we have $(a \cap b) = b \setminus i_2$ leading to the unique solution $a = i_1 \cup (b \setminus i_2)$.

5. $i_1 = a \cap \bar{b}$ and $i_2 = \bar{a} \cap \bar{b}$: this case is the dual of case 2 where $b$ is replaced with $\bar{b}$. Similarly, the solution is still not unique.

6. $i_1 = \bar{a} \cap b$ and $i_2 = \bar{a} \cap \bar{b}$: obviously $\bar{a} = i_1 \cup i_2$ then $a = \overline{i_1 \cup i_2}$.

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 informative enough to uniquely determine the set $a$.

It could also happen that the given disjoint subsets $i_1 \subset U$ and $i_2 \subset U$ are themselves indicators for other objects $C$ and $D$ different from $A$ and $B$. A related question arises: given 2 disjoint subsets $i_1$ and $i_2$, can we always find a pair of objects $(C, D)$ such that $i_1$ and $i_2$ 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. Considering only similarity indicators, let us look for a pair $(C, D)$ such that $c \cap d = i_1$ and $\bar{c} \cap \bar{d} = i_2$, knowing that $i_1 \cap i_2 = \emptyset$. The second equation is equivalent to $c \cup d = t^*$ where $t^* = \overline{i_1 \cup i_2}$, and the problem can be restated as a well known equivalent one:

Knowing that $i_1 \subseteq t^*$, find 2 sets $c$ and $d$ such that: $c \cap d = i_1$ and $c \cup 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 $2^U$ is just a Boolean lattice, it is convenient to reword the problem in a simple Boolean setting. When turning to a Boolean framework, $\cap$ is translated into $\wedge$, $\cup$ into $\vee$, and $=$ into $\equiv$. 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 \wedge b$ and $\bar{a} \wedge \bar{b}$ that we call *similarity indicators*,

- $a \wedge \bar{b}$ and $\bar{a} \wedge 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 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 equivalences between indicators of the form

$$ (I_{(a,b)} \equiv I_{(c,d)}) \wedge (I'_{(a,b)} \equiv I'_{(c,d)}) $$

Since we have to choose 2 distinct equivalences among $4 \times 4 = 16$ possible ones for defining a logical proportion, we have $[2^{16}] = 120$ such proportions and it has been shown that they are all semantically distinct. Consequently, if two proportions are semantically equivalent, they have the same expression as a conjunction of two equivalences 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 indicators 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 indicators: 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 \wedge b) \equiv (c \wedge d)) \wedge ((a \wedge \bar{b}) \equiv (c \wedge \bar{d}))$, which expresses that the two conditional objects<fnref n="2" /> $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 \wedge b = \bar{c} \wedge d$ and $\bar{a} \wedge \bar{b} = c \wedge \bar{d}$.

- 32 semi-hybrid proportions for which one half of their expressions involve indicators of the same kind, while the other half requires equivalence between indicators of opposite kinds, as, e.g., $a \wedge b = c \wedge d$ and $\bar{a} \wedge \bar{b} = c \wedge \bar{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., considering logical proportions that involve only dissimilarity, or only similarity indicators, 4 logical proportions remain which are listed below with their name:

<footnote n="1">¹ Note that $I_{(a,b)}$ (or $I'_{(a,b)}$) refers to one element in the set $\{a \wedge b, \bar{a} \wedge b, a \wedge \bar{b}, \bar{a} \wedge \bar{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.</footnote>

<footnote n="2">² A conditional object $b|a$ can take three truth values: true if $a \wedge b$ is true, false if $a \wedge \neg b$ is true, not applicable if $a$ is false; it may be intuitively thought as representing the rule “if $a$ then $b$” [3].</footnote>
analogy: $A(a, b, c, d)$, defined by

$$((a \wedge \bar{b}) \equiv (c \wedge \bar{d})) \wedge ((\bar{a} \wedge b) \equiv (\bar{c} \wedge d))$$

reverse analogy: $R(a, b, c, d)$, defined by

$$((a \wedge \bar{b}) \equiv (\bar{c} \wedge d)) \wedge ((\bar{a} \wedge b) \equiv (c \wedge \bar{d}))$$

paralogy: $P(a, b, c, d)$, defined by

$$((a \wedge b) \equiv (c \wedge d)) \wedge ((\bar{a} \wedge \bar{b}) \equiv (\bar{c} \wedge \bar{d}))$$

inverse paralogy: $I(a, b, c, d)$, defined by

$$((a \wedge b) \equiv (\bar{c} \wedge \bar{d})) \wedge ((\bar{a} \wedge \bar{b}) \equiv (c \wedge d))$$

Reverse analogy expresses that “a differs from b as d differs from c”, and conversely; 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 deducible 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 permutation):

**Proposition 1** $A(a, b, c, d) \leftrightarrow R(a, b, d, c)$ and $A(a, b, c, d) \leftrightarrow P(a, d, c, b)$.

<table><caption>**Table 2.** Analogy, Reverse analogy, Paralogy, Inverse Paralogy truth tables</caption><thead><tr><th>A</th><th>R</th><th>P</th><th>I</th></tr></thead><tbody><tr><td>0 0 0 0</td><td>0 0 0 0</td><td>0 0 0 0</td><td>1 1 0 0</td></tr><tr><td>1 1 1 1</td><td>1 1 1 1</td><td>1 1 1 1</td><td>0 0 1 1</td></tr><tr><td>0 0 1 1</td><td>0 0 1 1</td><td>1 0 0 1</td><td>1 0 0 1</td></tr><tr><td>1 1 0 0</td><td>1 1 0 0</td><td>0 1 1 0</td><td>0 1 1 0</td></tr><tr><td>0 1 0 1</td><td>0 1 1 0</td><td>0 1 0 1</td><td>0 1 0 1</td></tr><tr><td>1 0 1 0</td><td>1 0 0 1</td><td>1 0 1 0</td><td>1 0 1 0</td></tr></tbody></table>

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 $\frac{a}{b} = \frac{c}{d}$. As such, it is expected that this proportion 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.
<table><caption>**Table 3.** Properties of logical proportions</caption><thead><tr><th>property</th><th>definition</th><th># of proportions</th><th>homogeneous</th></tr></thead><tbody><tr><td>full identity</td><td>T(a, a, a, a)</td><td>15</td><td>A, R, P</td></tr><tr><td>reflexivity</td><td>T(a, b, a, b)</td><td>6</td><td>A, P</td></tr><tr><td>reverse reflexivity</td><td>T(a, b, b, a)</td><td>6</td><td>R, P</td></tr><tr><td>sameness</td><td>T(a, a, b, b)</td><td>6</td><td>A, R</td></tr><tr><td>symmetry</td><td>T(a, b, c, d) → T(c, d, a, b)</td><td>12</td><td>A, R, P, I</td></tr><tr><td>central permutation</td><td>T(a, b, c, d) → T(a, c, b, d)</td><td>16</td><td>A, I</td></tr><tr><td>all permutations</td><td>∀i, j, T(a, b, c, d) → T(p<sub>i,j</sub>(a, b, c, d))</td><td>1</td><td>I</td></tr><tr><td>transitivity</td><td>T(a, b, c, d) ∧ T(c, d, e, f) → T(a, b, e, f)</td><td>54</td><td>A, P</td></tr><tr><td>code independency</td><td>T(a, b, c, d) → T(a, b, c, d)</td><td>8</td><td>A, R, P, I</td></tr></tbody></table>

### 3.3 Extension to $\mathbb{B}^n$

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 $\mathbb{B}^n$. The simplest way to do it is to consider a definition involving componentwise proportions as follows (where $T$ denotes any proportion and $\vec{a}, \vec{b}, \vec{c}$ and $\vec{d}$ are in $\mathbb{B}^n$):

$$T(\vec{a}, \vec{b}, \vec{c}, \vec{d}) \text{ iff } \forall i \in [1, n], T(a_i, b_i, c_i, d_i)$$

where $\vec{x} = (x_1, \dots, x_n)$ for $x = a, b, c$, and $d$. All the previous properties of Boolean proportions remains valid for their counterpart in $\mathbb{B}^n$: For instance, if $T = A$, then the central permutation property (see Table 3) is still valid:

$$T(\vec{a}, \vec{b}, \vec{c}, \vec{d}) \rightarrow T(\vec{a}, \vec{c}, \vec{b}, \vec{d})$$

## 4 Equation solving process

As said in the introduction, the main problem we want to tackle is to compute missing 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 $2^3 = 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, symmetry and transitivity: $((\vec{a} \wedge \vec{b}) \equiv (\vec{c} \wedge \vec{d})) \wedge ((\vec{a} \wedge \vec{b}) \equiv (\vec{c} \wedge \vec{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.
0 0 0 0
0 1 0 1
1 0 1 0
1 0 1 1
1 1 1 0
1 1 1 1

<caption>**Table 4.** A non univocal proportion</caption>

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 ≠ b) ∨ (b ≠ c) holds. In that case, the unique solution is x = c ≠ (a ≠ 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 $\mathbb{B}^n$, the previous result remains valid, i.e. for 64 proportions, the equation $T(\vec{a}, \vec{b}, \vec{c}, \vec{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 $\mathbb{B}^n$ 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 \cap d$ i.e. the properties that *C* and *D* share: $c \cap d = 100100$. And we know $c \cap \bar{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 100100
c ∩ ⃗ d 000010
d 1??10?

<caption>**Table 5.** Non computable solution</caption>

But in the case where we know $\bar{c} \cap \bar{d} = 010000$, we recover $D$ as in Table 6 where the set $d$ is just $(c \cap d) \cup \bar{c} \cap \bar{d} \cup c$.

c 100110
c ∩ d 100100
$\bar{c} \cap \bar{d}$ 010000
d 101101

<caption>**Table 6.** Computable solution</caption>

**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 $\mathbb{B}^n$ 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 (*a*<sub>*i*</sub>, *b*<sub>*i*</sub>, *c*<sub>*i*</sub>, *d*<sub>*i*</sub>) corresponding to the components of *a*, *b*, *c* and *d*. Among these *n* valuations, 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 $l_1 \wedge l_2 \equiv l_3 \wedge l_4$. 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 \wedge b$ and $\bar{a} \wedge \bar{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$ satisfying this requirement: $c \wedge d$ and $\bar{c} \wedge \bar{d}$. Then the equivalence $l_1 \wedge l_2 \equiv l_3 \wedge l_4$ is just $a \wedge b \equiv c \wedge d$, $a \wedge b \equiv \bar{c} \wedge \bar{d}$, $a \wedge b \equiv \bar{c} \wedge \bar{d}$ or $\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}$. None of these equivalences satisfies the whole class $\{0111, 1011, 1101, 1110\}$. The same reasoning applies for the other class. $\square$

From a practical viewpoint, as soon as we observe this class appearing as a part of the $n$ valuations $(a_i, b_i, c_i, d_i)$, 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 philosophy, 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]$):

$$ \frac{\forall i \in [1, n] \setminus J, T(a_i, b_i, c_i, d_i)}{\forall i \in J, T(a_i, b_i, c_i, d_i)} $$

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 information for a given object $D$. Suppose the known part of $D$ are the attributes belonging to $[1, n] \setminus 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(a_i, b_i, c_i, x_i)$ for every $i \in J$, and the (unique) solution is considered to be the value of $d_i$.

A particular case of this inductive principle has been implemented for classification 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 proportions, 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 proposed 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 indicators, 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 reasoning 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:

$$ (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (\bar{a} \wedge b \equiv c \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv c \wedge \bar{d}) $$

$$ (\bar{a} \wedge \bar{b} \equiv c \wedge d) \wedge (\bar{a} \wedge b \equiv \bar{c} \wedge d) ; (\bar{a} \wedge \bar{b} \equiv c \wedge d) \wedge (a \wedge \bar{b} \equiv \bar{c} \wedge d) $$

$$ (\bar{a} \wedge b \equiv \bar{c} \wedge d) \wedge (a \wedge b \equiv c \wedge d) ; (a \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (a \wedge b \equiv c \wedge d) $$

$$ (\bar{a} \wedge b \equiv c \wedge \bar{d}) \wedge (a \wedge b \equiv \bar{c} \wedge \bar{d}) ; (a \wedge \bar{b} \equiv c \wedge \bar{d}) \wedge (a \wedge b \equiv \bar{c} \wedge \bar{d}) $$

- 12 hybrid proportions:

$$ (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (\bar{a} \wedge b \equiv c \wedge d) ; (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (a \wedge \bar{b} \equiv c \wedge d) $$

$$ (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (a \wedge b \equiv c \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv c \wedge \bar{d}) \wedge (\bar{a} \wedge b \equiv \bar{c} \wedge \bar{d}) $$

$$ (\bar{a} \wedge \bar{b} \equiv c \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv c \wedge \bar{d}) \wedge (a \wedge b \equiv \bar{c} \wedge \bar{d}) $$

$$ (\bar{a} \wedge b \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv c \wedge d) ; (\bar{a} \wedge b \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge b \equiv c \wedge \bar{d}) $$

$$ (\bar{a} \wedge b \equiv c \wedge d) \wedge (a \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) ; (a \wedge b \equiv c \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) $$

$$ (\bar{a} \wedge b \equiv c \wedge d) \wedge (a \wedge b \equiv \bar{c} \wedge d) ; (a \wedge \bar{b} \equiv c \wedge d) \wedge (a \wedge b \equiv \bar{c} \wedge d) $$

- 24 semi-hybrid proportions:

$$ (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (\bar{a} \wedge b \equiv c \wedge d) ; (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv c \wedge d) $$

$$ (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge b \equiv c \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (\bar{a} \wedge b \equiv c \wedge \bar{d}) $$

$$ (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (a \wedge \bar{b} \equiv c \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (a \wedge b \equiv c \wedge d) $$

$$ (\bar{a} \wedge \bar{b} \equiv c \wedge \bar{d}) \wedge (\bar{a} \wedge b \equiv \bar{c} \wedge d) ; (\bar{a} \wedge \bar{b} \equiv c \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv \bar{c} \wedge d) $$

$$ (\bar{a} \wedge \bar{b} \equiv c \wedge \bar{d}) \wedge (a \wedge b \equiv \bar{c} \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv c \wedge d) \wedge (\bar{a} \wedge b \equiv \bar{c} \wedge \bar{d}) $$

$$ (\bar{a} \wedge \bar{b} \equiv c \wedge d) \wedge (a \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv c \wedge d) \wedge (a \wedge b \equiv \bar{c} \wedge d) $$

$$ (\bar{a} \wedge b \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv c \wedge \bar{d}) ; (\bar{a} \wedge b \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge b \equiv c \wedge d) $$

$$ (\bar{a} \wedge b \equiv \bar{c} \wedge d) \wedge (a \wedge \bar{b} \equiv c \wedge d) ; (\bar{a} \wedge b \equiv \bar{c} \wedge d) \wedge (a \wedge b \equiv c \wedge \bar{d}) $$

$$ (\bar{a} \wedge b \equiv c \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) ; (\bar{a} \wedge b \equiv c \wedge \bar{d}) \wedge (a \wedge b \equiv \bar{c} \wedge d) $$

$$ (\bar{a} \wedge b \equiv c \wedge d) \wedge (a \wedge \bar{b} \equiv \bar{c} \wedge d) ; (\bar{a} \wedge b \equiv c \wedge d) \wedge (a \wedge b \equiv \bar{c} \wedge \bar{d}) $$

$$ (a \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge b \equiv c \wedge d) ; (a \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (a \wedge b \equiv c \wedge \bar{d}) $$

$$ (a \wedge \bar{b} \equiv c \wedge \bar{d}) \wedge (a \wedge b \equiv \bar{c} \wedge d) ; (a \wedge \bar{b} \equiv c \wedge d) \wedge (a \wedge b \equiv \bar{c} \wedge \bar{d}) $$

- 16 degenerated proportions:

$$ (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (\bar{a} \wedge \bar{b} \equiv c \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (\bar{a} \wedge \bar{b} \equiv c \wedge d) $$

$$ (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (\bar{a} \wedge \bar{b} \equiv c \wedge \bar{d}) ; (\bar{a} \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (\bar{a} \wedge \bar{b} \equiv c \wedge d) $$

$$ (\bar{a} \wedge b \equiv \bar{c} \wedge \bar{d}) \wedge (\bar{a} \wedge b \equiv c \wedge \bar{d}) ; (\bar{a} \wedge b \equiv \bar{c} \wedge \bar{d}) \wedge (\bar{a} \wedge b \equiv c \wedge d) $$

$$ (\bar{a} \wedge b \equiv \bar{c} \wedge d) \wedge (\bar{a} \wedge b \equiv c \wedge \bar{d}) ; (\bar{a} \wedge b \equiv \bar{c} \wedge d) \wedge (\bar{a} \wedge b \equiv c \wedge d) $$

$$ (a \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv c \wedge \bar{d}) ; (a \wedge \bar{b} \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge \bar{b} \equiv c \wedge d) $$

$$ (a \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (a \wedge \bar{b} \equiv c \wedge \bar{d}) ; (a \wedge \bar{b} \equiv \bar{c} \wedge d) \wedge (a \wedge \bar{b} \equiv c \wedge d) $$

$$ (a \wedge b \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge b \equiv c \wedge \bar{d}) ; (a \wedge b \equiv \bar{c} \wedge \bar{d}) \wedge (a \wedge b \equiv c \wedge d) $$

$$ (a \wedge b \equiv \bar{c} \wedge d) \wedge (a \wedge b \equiv c \wedge \bar{d}) ; (a \wedge b \equiv \bar{c} \wedge d) \wedge (a \wedge b \equiv c \wedge 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 using 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 independent 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 Appliqué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 Intelligence, 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), Dortmund, 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 methodological issues. Tech. rep. (June 2005)