This paper gives a formula for the solution of an analogical equation between Booleans using the Shefer stroke (NAND). Naturally, a counterpart using the Pierce arrow (NOR) is also given. Although not so intuitive, these formulae are somewhat elegant. The formulae are obtained in the following way: a rapid review on analogies between sets is given. The result on sets is transposed to Booleans. This result is rewritten using solely the operators mentioned above and simplified. Boolean analogies, Analogies on sets, Shefer stroke (NAND), Pierce arrow (NOR) IARML@IJCAI'2023: Workshop on the Interactions between Analogical Reasoning and Machine Learning, at IJCAI'2023, htp:/ceur-ws.org CEUR Workshop Proceedings (CEUR-WS.org) IS N1613-073
time, under the condition
An axiomatic approach (Section 2) that postulates reflexivity ( A : B :: A : B) and symmetry
(C : D :: A : B) of conformity (::), in addition to the exchange of the means (A : C :: B : D), for
any analogy A : B :: C : D, allows to define analogy on commutative magmas and commutative
monoids (Section 3). The additional postulate of contiguity (the same analogy should hold on
the inverse of objects) allows to define analogies on commutative groups (Section 4). Adding
the postulate of similarity (all features in should appear in
or ) is used to determine the
solution of analogical equations between sets in [
General of fSoyrmmmiteytry of con- : :: : Itniovsersion of ra- : :: : jIencvtesrs(cioonntiogfuitoyb)- −1 : −1 :: −1 : −1 Distribution in objects (similarity) eExxtcrheamnegse of the : :: : Emxecahnasnge of the : :: : any feature in must appear in either or or both. 2. Postulates for analogy The classical way of writing down an analogy with A : B :: C : D involves two basic articulations denoted by the signs : for ratio and :: that we choose to call conformity2. The four terms are traditionally divided into the means and , and the extremes and . Studies in the notion of analogy in its technical sense (not in its vernacular sense of mere similarity or comparison, as in analogical reasoning) extract two underlying notions, those of similarity and contiguity.
Conformity can be postulated to be reflexive and symmetric. 3. The ratios can be thought to be inversible4. From the Greek antiquity, it is considered that analogy (in its strict technical meaning) cannot go without the exchange of the means5. All this leads to the postulates given in Table 1. 2The character : (U+2236) is named ratio in the ISO 10646 standard (Unicode) and :: (U+2237) is named proportion. 3I.e., a dependency relation. An equivalence relation requires transitivity in addition. 4Invertendo in the Latin tradition. 5Permutando or alternando in the Latin tradition. Analogy
counter-clockwise rotation inverse of reading clockwise rotation inversion of ratios exchange of the extremes mity symmetry of confor(vi) Exchange of the means is another possible choice. For this last choice, it means that the postulates (ii) and (v) are indeed dispensable. 3. Analogy induced on commutative magmas and monoids Let (ℰ , ⋆) be a magma, i.e., a set equipped with an internal law, without any specific property. To define analogy on such a structure, the only device ofered is its internal operation. Drawing a parallel with numbers, where, for arithmetic and geometric analogies, one has + = + and × = × , it is natural to posit the following equivalence to induce analogy from a exch. means counter-clock. rot. clock. rot.
exch. extr. magma. However, observe that there are two possibilities, because the internal operation could be non-commutative.
or With (3.1), the axiom of reflexivity of conformity would impose immediately that ⋆ be commutative because
For (3.2), the expression of each postulate is shown in Table 1. (o) and (i) hold because, equality being an equivalence relation, it is a dependency relation. The inverse of objects and the distribution in objects are left undefined. For all other axioms, a suficient condition for them to be met is that ⋆ be commutative.
To summarize, to naturally induce analogy from the structure of a magma, it sufices for the internal operation to be commutative. The two definitions (3.1) and (3.2) are then the same. The axioms of object inversion and distribution within objects can be left unspecified. Observe that neither conformity nor ratio are directly defined. Finally, nothing can be said in the general case for the problem of solving an analogical equation on a commutative magma: given a triplet (, , ) ∈ ℰ 3, find such that : :: : , i.e., find such that ⋆ = ⋆ ,
On a commutative monoid, i.e., a magma with associativity of the internal operation and a neutral element, analogy can be naturally induced in the same way as for a commutative magma. 4. Analogy induced on commutative groups Let (ℰ , ⋆) be a group. Let −1 denote the inverse element of .
• Ratios can be defined directly: The column marked Group in Table 1 gives the expression of each of the postulates using (4.2). Similarly as for magmas, conformity being equality, reflexivity and symmetry hold. Postulating the axiom of inversion of objects, i.e., has the consequence that can be expressed in two ways in function of the other terms. Commutativity on the entire group is suficient to ensure the equality = ⋆ −1 ⋆ = ⋆ −1 ⋆ .
(4.4) Hence, provided the group is commutative, the group structure entails all the axioms listed in Table 1 with the exception of the axiom of distribution in objects. 5. Analogy between sets Let ℰ be a set. The set of all subsets of ℰ is noted (ℰ ). Equipped with union, ( (ℰ ), ∪) is a commutative monoid. Union is an internal operation in (ℰ ) that is associative and commutative. The neutral element is ∅ (∅ ∪ = ∪ ∅ = ). However there is no inverse element in general, i.e., for any set in (ℰ ), there is no set such that ∪ = ∅. Similarly, ( (ℰ ), ∩) is a commutative monoid. The neutral element is ℰ . follows. another operation noted
The symmetrical diference on sets (noted element of any set in (ℰ ) is itself: : :: :
∩ that is associative and commutative. The neutral element is ∅ (∅△ ( (ℰ ), △) is a commutative group. Symmetrical diference is an internal operation in (ℰ ) = △ △∅ = ). The inverse
) is a commutative group, △
= ∅. Similarly, ( (ℰ ), with ℰ as the neutral element, and each element is its one inverse.
For any quadruple of sets in a power set (ℰ ), if the two analogies induced by the two structures of commutative monoids ( (ℰ ), ∪) and ( (ℰ ), ∩) hold at the same time, then, the analogy induced by the structure of commutative group ( (ℰ ), △) holds too (and similarly for ⇔ ( ∩ ) = ( ∩ ) ∧ ( ∪ ) = ( ∪ ) ⇒ ( ∖ ) ∪ ( ∖ ) = ( ∖ ) ∪ ( ∖ ) = △ ⇔ : :: :
△ ⇔
⇔ : :: : (the counterpart of logical equivalence on Booleans) are defined as
△ and corresponding to XOR on Booleans), and = ( ∪ ) ∖ ( ∩ ) ( △ ) (5.1) (5.2) The second line above is only an implication. Now, the analogy induced by the structure of a commutative group of ( (ℰ ), △) (or, similarly, ( (ℰ ), )△) is the same as when the two analogies induced by the two commutative monoids ( (ℰ ), ∪) and ( (ℰ ), ∩) hold at the same time, under the condition ⊂ ∪ ∧ ∩ ⊂ . This is (1.1) given in the introduction. being the elements. postulate of inversion of objects (iii). ⊂ ∪ transcribes the postulate of distribution in objects (iv) for sets with the features ∩
⊂ is obtained by taking the set complements, i.e., using the △ : :: : of unknown between sets is given by (1.2). ndu ono i
m logy oth (b) a b
∧ an by (a)
T F F T F T F F F F T F T F F T ) c ( F F F F T T T T T T T T F F F F ( ℰ ∖ = △ ) d ( F T T F F T T F F T T F F T T F ( ℰ ∖ = △ ) ced (d) du c)= in :( y p log rou a g an by T F F T F T T F F T T F T F F T
Correspondence, on sets, between the two analogies induced by the commutative monoids ( (ℰ ), ∪) and ( (ℰ △), ∩) holding at the same time and each of the analogies induced by the commutative groups 6. Analogies between Booleans There exists a correspondence between operations on sets and operations on Booleans. Here we use the correspondence between union and or, intersection and and, and the fact that the complement of a set in another one corresponds to taking the conjunction with the negation: ∖ corresponds to ∧¬ . With this, the solution of an analogy between Booleans, a : b :: c : d, transcribed from the solution of an analogy between sets, under the condition (transcribed from the condition on sets) that is: ⇒ ∨ ∧
∧ ⇒ ,
= (( ∨ ) ∧ ¬ ) ∨ ( ∧ ).
(6.1)
(6.2)
The condition corresponds to the cases in conflict in [
The Shefer stroke (usually noted |, but noted ↑ here6) denotes the NAND operator. For two Boolean variables and ,
↑ = ¬( ∧ ).
It is known that the singleton containing the Shefer stroke as sole Boolean operator is functionally complete. This means that any Boolean expression can be rewritten using solely the Shefer stroke. For instance, Intuitive operators are associative and commutative as is the case for + or × on numbers. However, remarkably, the Shefer stroke is commutative (7.1) (7.2) (7.3) (7.4) (7.5) (7.6) (7.7) (7.8) (8.1) (8.2) but not associative, i.e., in general
By virtue of ↑ = ¬ , trivially,
The Pierce arrow is the NOR operator, i.e.,
The notation 2 for ↑ can be introduced, and applying it twice, reduces (7.7) to: It has similar properties as the Shefer stroke: it is commutative, but not associative, negation is obtained by self-application ∧ = ( ↑ )↑( ↑ ), ∨ = ( ↑ )↑( ↑ ), ¬ = ↑.
↑ = ↑, ( ↑ )↑ ̸= ↑( ↑ ). ( ↑ )↑( ↑ ) = ¬(¬ ) = .
( 2)2 = . ↓ = ¬( ∨ ).
¬ = ↓,
6As in [
The notation 2 can be used with the Pierce arrow with the same meaning and same value as with the Shefer stroke: Consequently, (7.8) also holds for the Pierce arrow. 9. Relations between the Shefer stroke and the Pierce arrow The following properties can easily be established by using the expression of disjunction for the two operators: ∧ = ( ↓ )↓( ↓ ) ∨ = ( ↓ )↓( ↓ ). 2 = ¬ = ↑ = ↓.
2↑ 2 = ( ↓ )2, 2↑( 2↑ 2) = ( ↓( ↓ ))2.
2↓ 2 = ( ↑ )2, 2↓( 2↓ 2) = ( ↑( ↑ ))2. (8.3) (8.4) (8.5) (9.1) (9.2) (9.3) (9.4) Rather than using , and for variable names, we used , and on purpose, to ease the reading of Section 10. The same can be done for conjunction: 10. Formulae for the solution of a Boolean analogy The rewriting of the solution of an analogy between Booleans into an expression that involves only the Shefer stroke can be worked out by hand from (6.2). It is safer to rely on a program to automatically perform this rewriting. We give such a program in Figure 2. It starts from a tree representation of (6.2), i.e., (6.2) in Polish notation.
The result is as follows, with spaces for clarity.
= ( ( ( ((( ↑ )↑( ↑ ))↑( ↑ )) ↑ ((( ↑ )↑( ↑ ))↑( ↑ )) ) ↑
( ((( ↑ )↑( ↑ ))↑( ↑ )) ↑ ((( ↑ )↑( ↑ ))↑( ↑ )) ) ) ↑
((( ↑ )↑( ↑ ))↑(( ↑ )↑( ↑ ))) )
This lengthy formula can be simplified by
• locating occurrences of (7.8), i.e., ( ↑ )↑( ↑ ) = ,
• introducing the 2 notation, and
7The dual of an operator is defined as follows [
return f'(({p}↑{q})↑({p}↑{q}))' def or_(p, q):
return f'(({p}↑{p})↑({q}↑{q}))' def not_(p):
return f'({p}↑{p})' def a():
return 'a' def b():
return 'b' def c():
return 'c' # d = ' ((b or c) and non(a)) or (b and c)' d = or_( and_(or_(b(), c()), not_(a())), and_(b(), ˓→ c()) ) print(d)
This second formula could have been obtained directly from (10.1) by exploiting the relations seen in Section 9, i.e., the duality between the two operators. (10.1) (10.2)
Remarkably, (10.1) is equivalent to the following formula, where the whole is squared and variables are squared.8
= (︀ ( ↑( ↑ )) ↑ ( 2↑ 2) )︀ 2
The equivalence between (10.1) and (10.3) is shown by the table of truth values for the two formulae in Table 4. The grayed-out lines are the two lines corresponding to the cases where condition (6.1) is not verified. In this table, the symmetry around the central line says that the value of is negated by taking the negation of each of the variables , and . This just states that, considered as an operator on three variables, the solution of an analogy is self-dual: ( 2, 2, 2) = (, ,
)2.
= ( 2 ↓ ( 2↓ 2) ) ↓ ( ↓ ) This follows intuition as, being the solution of an analogy, the postulate of inversion of objects (iii) should hold. For the same reason, an equivalent form to (10.2) is: Thus, remarkably, the formulae using the Pierce arrow (NOR) are the same as the ones using the Shefer stroke (NAND). That is, (10.4) is the same as (10.1) and (10.2) is the same as (10.3), except for the operator. 8The submitted version of this paper contained a regrettable error in the justification of this equivalence. We fortunately became aware of it before the feedback of the reviewers, who, of course, spotted it. We thank one of them for suggesting a proof of this equivalence. (10.3) (10.4) This paper gave formulae for the solution of an analogical equation between Booleans using solely the Shefer stroke (NAND) or the Pierce arrow (NOR).
These formulae were obtained by transposing a formula on sets to Booleans. To justify this
ifrst formula, we reminded postulates for analogy and briefly showed how analogy can be
induced from some algebraic structures (see also [
Although not so intuitive, the formulae for Booleans using the Shefer stroke or the Pierce
arrow are somewhat elegant. They reflect the self-duality of the solution of a Boolean analogical
equation. Any of the two operators, Shefer stroke or Pierce arrow, can indiferently be used for
them. It is an open question whether these formulae are the most economical ones in terms
of number of occurrences of operators or variables, i.e., whether their eficiency is the best
possible [