## Solution of the equation E(M)⊕E(N) => E(A)*¬E(M & N) ≡ 1 via the calculus of basic predicates by E.A.Mironchick

December 31, 2018

In general we follow guidelines of technique developed in

Per link mentioned above (quoting Helen A. Mironchick)
Let Et (x) be a predicate whose truth set is all x for which x & t ≠ 0.
If t is a power of two, then such a predicate will be called basic.
The basic predicate describes (fixes) a single unit in the binary notation.
Further, for brevity, the predicate Et (x) will be denoted by E(t);
we will also denote the truth set of this predicate.

(quoting ends)

Denote by {X} the binary representation of a natural number X.
The core statement of the post below  is :-

Let R, M, N be natural numbers. R is the minimum
satisfying the condition {M OR N} = {R OR {M & N}},
where “OR” is a bitwise disjunction, and “&” is a bitwise conjunction
Then the smallest A satisfying the equation
E(M)⊕E(N)=>E(A)*¬E (M & N) ≡ 1 would be equal R.

First we intend to show that, E(M) v E(N) = E(R) v E(M&N).
Notice also that everywhere below, “*” is “^”.

Consider expansions in the logical sum of  basic predicates.
E (M) and E(N). All pairs of equal basic predicates will be
collapsed into one and the logical sum of such predicate pairs
will obviously give E(M&N). The logical sum of all those
remaining is exactly E (R). It remains to apply the formulas
of De Morgan.
¬(E(M) v E(N)) = ¬(E(R) v E(M & N))
and get the required equality below
¬E(M)*¬E(N) = ¬E(R)*¬E(M&N)  (1)
Bitwise2 has a familiar formula. Due to the fact that ¬E(N) = Z(N)
Z(M)*Z(N) = Z(M OR N) = Z(R)*Z(M & N)
See :-   Solving the equation ¬Z(M)⊕¬Z(N) => ¬A*Z(M&N) ≡ 1 in the Bitwise2 technique  https://informatics-ege.blogspot.com/2018/12/zmn-am-1-bitwise2.html
Thus, ¬E(M)*¬E(N) = ¬E(R)*¬E (M & N) can be obtained
Convert the original equation as follows
E(M)⊕E(N) => E(A)*¬E(M&N) ≡ 1
(E(M)≡E(N)) v E(A)*¬E(M&N) ≡ 1
¬E(M)*¬E(N) v E(M)*E(N) v E(A)*¬E(M&N) ≡ 1
From the decomposition of M and N into basic predicates
define the numbers REST-M and REST-N such that
each of them has no common unit bits with M&N and in doing so
obtain
{REST-M} + {M & N} = {M}
{REST-N} + {M & N} = {N}
Consequently
E(M) = E(REST-M) v E(M&N)
E(N) = E(REST-N) v E(M&N)
Apply formula (1) to ¬E(M)*¬E(N):-
¬E(R)*¬E(M&N) v (E(REST-M) v E(M & N))*(E(REST-N) v E(M&N)) v
v E(A)*¬E(M&N) ≡ 1
¬E(R)*¬E(M&N) v E(REST-M)*E(REST-N) v E (M&N) v
v E(A)*¬E(M&N) ≡ 1
¬E(R) v E(REST-M)*E(REST-N) v E(M&N) v E(A)≡ 1

Thus A (min) = R