*********************************************************************
UPDATED as of 03/05/2019. This is supposed to be final draft
fixing a minor issues in original version
*********************************************************************
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)
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
*************
Theorem 1
*************
For truth ∀ x: E(k)(x) => E(m)(x), it is necessary
and sufficient that the set of unit bits "k" is fully
included in the set of unit bits "m"
Necessity
Let j(1), .., j(s) be the numbers of the single unit bits "k",
ordered descending (for example), then
¬E(k)= ¬E(j(1)) * .... *¬E(j(s)) we show that
¬E(k) + E(m) = 1
We have
¬E(k) = ¬E(j(1))* .... *¬E(j(s))
E(m) = E(j(1)) + ... + E(j(s)) + E (rest)
We consistently suppress all factors in conjunction.
¬E(k)+E (m) = ¬E(j(1))* ....*¬E(j(s)) + E(j(1)) + ... + E(j(s)) + E(rest)=1
Sufficiency
If there is at least one single unit bit "k" (with the number "p") not included in the single unit bits "m", then k&2^p! = 0 and at the same time the numbers of the single unit bits "m" do not contain "p", then 2^p with a unit at the place "p" in the binary representation 1000 ... 0 (counting from 0 from right to left) will be multiplied by 0 in the p-th position "m", that is, m&2^p = 0 In this case, k&2^p != 0, that is, E(k,2^p) = 1 if m&2^p = 0 then E(m,2^p) = 0. In this case, Е(к,2^p) => Е(m,2^p) = 0, that is, the condition of the theorem is not satisfied for all "x"
We are all set with Theorem 1
Starting from this point we intend to invoke Theorem 1 where it
appears to be needed without any previous notification
Say $(X) is the set of unit bits in X.
Convert the last equation as follows
(E(R)=> E(REST-M))*(E(R)=> E(REST-N))
v (E(R)=> E(M&N)) v (E(R)=> E(A)) ≡ 1
Assign A(min) value equal R and consider any A < A(min) then
∃ j: ( j !∈ $(A))*(j ∈ $(R)) = True
From here and below our major goal would be to prove that for any
A < A(min) it exists integer y=y(A) which will result
(E(R)=> E(REST-M))*(E(R)=> E(REST-N))
v (E(R)=> E(M&N)) v (E(R)=> E(A)) (y(A)) =0
Set unit bit on place number "j" in y=y(A)
Due to j ∈ $(R) this j !∈ $(M&N). The rest of y's bits
let us set to 0
Notice that this "j" also doesn't belong to at least one of sets
$(REST-M) or $(REST-N), otherwise it would belong
$(M&N). So conjuction below is equal 0.
(E(R,y)=> E(REST-M,y))*(E(R,y)=> E(REST-N,y)) = 0 (1)
Then notice that (E(R,y)=> E(M&N,y)) = 0 (2)
and (E(R,y)=> E(A,y) = 0 (3)
Finally we are getting (due to (1),(2) and (3))
(E(R)=> E(REST-M))^(E(R)=> E(REST-N)) v
v (E(R)=> E(M&N)) v (E(R)=> E(A))(y) = 0
Thus for any A less then R it exists y=y(A) such
that predicate been written above has value 0
for number y=y(A) and A(min) appears to be real
minimum A(min)
Links
1. http://kpolyakov.spb.ru/download/mea18bit.pdf
UPDATED as of 03/05/2019. This is supposed to be final draft
fixing a minor issues in original version
*********************************************************************
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)
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
*************
Theorem 1
*************
For truth ∀ x: E(k)(x) => E(m)(x), it is necessary
and sufficient that the set of unit bits "k" is fully
included in the set of unit bits "m"
Necessity
Let j(1), .., j(s) be the numbers of the single unit bits "k",
ordered descending (for example), then
¬E(k)= ¬E(j(1)) * .... *¬E(j(s)) we show that
¬E(k) + E(m) = 1
We have
¬E(k) = ¬E(j(1))* .... *¬E(j(s))
E(m) = E(j(1)) + ... + E(j(s)) + E (rest)
We consistently suppress all factors in conjunction.
¬E(k)+E (m) = ¬E(j(1))* ....*¬E(j(s)) + E(j(1)) + ... + E(j(s)) + E(rest)=1
Sufficiency
If there is at least one single unit bit "k" (with the number "p") not included in the single unit bits "m", then k&2^p! = 0 and at the same time the numbers of the single unit bits "m" do not contain "p", then 2^p with a unit at the place "p" in the binary representation 1000 ... 0 (counting from 0 from right to left) will be multiplied by 0 in the p-th position "m", that is, m&2^p = 0 In this case, k&2^p != 0, that is, E(k,2^p) = 1 if m&2^p = 0 then E(m,2^p) = 0. In this case, Е(к,2^p) => Е(m,2^p) = 0, that is, the condition of the theorem is not satisfied for all "x"
We are all set with Theorem 1
Starting from this point we intend to invoke Theorem 1 where it
appears to be needed without any previous notification
Say $(X) is the set of unit bits in X.
Convert the last equation as follows
(E(R)=> E(REST-M))*(E(R)=> E(REST-N))
v (E(R)=> E(M&N)) v (E(R)=> E(A)) ≡ 1
Assign A(min) value equal R and consider any A < A(min) then
∃ j: ( j !∈ $(A))*(j ∈ $(R)) = True
From here and below our major goal would be to prove that for any
A < A(min) it exists integer y=y(A) which will result
(E(R)=> E(REST-M))*(E(R)=> E(REST-N))
v (E(R)=> E(M&N)) v (E(R)=> E(A)) (y(A)) =0
Set unit bit on place number "j" in y=y(A)
Due to j ∈ $(R) this j !∈ $(M&N). The rest of y's bits
let us set to 0
Notice that this "j" also doesn't belong to at least one of sets
$(REST-M) or $(REST-N), otherwise it would belong
$(M&N). So conjuction below is equal 0.
(E(R,y)=> E(REST-M,y))*(E(R,y)=> E(REST-N,y)) = 0 (1)
Then notice that (E(R,y)=> E(M&N,y)) = 0 (2)
and (E(R,y)=> E(A,y) = 0 (3)
Finally we are getting (due to (1),(2) and (3))
(E(R)=> E(REST-M))^(E(R)=> E(REST-N)) v
v (E(R)=> E(M&N)) v (E(R)=> E(A))(y) = 0
Thus for any A less then R it exists y=y(A) such
that predicate been written above has value 0
for number y=y(A) and A(min) appears to be real
minimum A(min)
Links
1. http://kpolyakov.spb.ru/download/mea18bit.pdf
