Решение Р-46 в технике Е.А. Мирончик 08.2016

Техника, предложенная в http://kpolyakov.spb.ru/download/mea-2016-8.pdf
все еще не очень популярна. Хотя примеры ее применения
в  P-45 и P-46 наглядно демонстрируют, что работа с парами перехода не всегда является доминирующим подходом с точки зрения прозрачности и скорости получения результатов. То же самое касается поста
https://mapping-metod.blogspot.com/2019/03/blog-post.html

Исходная система 

 
Мы используем технику предложенную в
      http://kpolyakov.spb.ru/download/mea-2016-8.pdf

Тактика применная ниже в целом следует идее Е.А.Мирончик при решении P-45 (по тексту файла ege23.doc)

***************************************
Преобразуем исходную систему
в эквивалентную
***************************************
x1⊕x2=1
x3⊕x4=1
x5⊕x6=1
x7⊕x8=1
x9⊕x10=1 
x11+x12=1 
(x1⊕x3)*(x4⊕x8)*(x2⊕x12) =0

Поскольку

x3⊕x4=1 влечет x3+x4 =1
x5⊕x6=1 влечет x5+x6 =1
x7⊕x8=1 влечет x7+x8 =1
x9⊕x10=1 влечет x9+x10 =1

то мы делаем эквивалентное преобразование

*****************
Система 01
*****************
x1⊕x2=1
x3⊕x4=1
x5⊕x6=1   имеет 2^5*3 = 32*3 =96 решений
x7⊕x8=1
x9⊕x10=1 
x11+x12=1  

 

**********************************************
Найдем число решений Системы 02
**********************************************
x1⊕x2=1
x3⊕x4=1
x5⊕x6=1
x7⊕x8=1
x9⊕x10=1 
x11+x12=1 
(x1⊕x3)*(x4⊕x8)*(x2⊕x12) =1

*************************************************
Изменим порядок следования уравнений
в системе
*************************************************
x7⊕x8=1
x8⊕x4=1  <= из последней строки 02
x4⊕x3=1
x3⊕x1=1  <= из последней строки 02
x1⊕x2=1
x2⊕x12=1 <= из последней строки 02
x12+x11=1
x5⊕x6=1
x9⊕x10=1
 

 

Ответ : 96-12=84

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

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 is 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