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.
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 [
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 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 n 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 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
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
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 2 fs; t; u; vg, we can associate a Boolean variable i0 defined as: i0 = 1 if i 6= ; and i0 = 0 otherwise.
s = u = v = t = a \ b 6= ; a \ b 6= ; a \ b 6= ; a \ b 6= ;
1 1 1 1
configuration
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 [
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
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 \ 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 n i2 leading to the unique solution a = i1 [ (b n 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 informative enough to uniquely determine the set a.
It could also happen that the given disjoint subsets i1 U and i2 U are themselves 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. Considering 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
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.
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 [
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)
I(c;d)) ^ (I(0a;b)
I(0c;d))
Since we have to choose 2 distinct equivalences among 4 4 = 16 possible ones for
defining a logical proportion, we have [126] = 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 [
First of all, depending on the way the indicators are combined, different types of
logical proportions are obtained [
– 48 degenerated proportions whose definition involves 3 distinct indicators only. 3.2
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:
1 Note that I(a;b) (or I(0a;b)) refers to one element in the set fa ^ b; a ^ b; a ^ b; a ^ bg, 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 bja 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”
[
(c ^ d)) ((a ^ b) (c ^ d)) ^ ((a ^ b)
(c ^ d)) ((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 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) $ R(a; b; d; c) and A(a; b; c; d) $ P (a; d; c; b).
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 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.
property full identity reflexivity reverse reflexivity sameness symmetry central permutation all permutations
transitivity code independency # of proportions homogeneous
A; R; P
A; P R; P
A; R A; R; P; I
A; I
I
A; P A; R; P; I 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 8i 2 [1; n]; T (ai; bi; ci; di) where !x = (x1; ; xn) for x = a, b, c, and d. All the previous properties of Boolean proportions remains valid for their counterpart in Bn: For instance, if T = A, then the central permutation property (see Table 3) is still valid:
T (!a ; !b ; !c ; !d ) ! T (!a ; !c ; !b ; !d ) 4
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 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, symmetry 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. 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1
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 [
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.
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.
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 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 f0111; 1011; 1101; 1110g or the class f1000; 0100; 0010; 0001g.
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 f0111; 1011g, 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 f1101; 1110g, 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 ^ 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 f0111; 1011; 1101; 1110g. 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.
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]): 8i 2 [1; n] n J; T (ai; bi; ci; di)
8i 2 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 [
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] 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 2 J , and the (unique) solution is considered to be the value of di.
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
[
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. 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.
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)