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

In general we follow guidelines of technique developed in
http://kpolyakov.spb.ru/download/mea18bit.pdf

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
as a result of Statement 3 of http://kpolyakov.spb.ru/download/bitwise2.pdf
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
Links
1. http://kpolyakov.spb.ru/download/mea18bit.pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: