Решение одной системы уравнений в булевских переменных в стиле 08.2016 "ГРАФЫ И СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ"

Исходная система описана диграммами в стиле 08.2016 и сразу же просчитана

  ((x1≡x2)≡x3)=>((x4=>x5)=>x6)=1
  ((x4≡x5)≡x6)=>((x7=>x8)=>x9)=1
  ((x7≡x8)≡x9)=>((x10=>x11)=>x12)=1
  ((x10=>x11)=>x12)=>((x1≡x2)≡x3)=1

Решение (диаграммы и просчет (1) - (3) ) :-

     Прогон системы и получение ответа для исходной

      ((x1≡x2)≡x3)=>((x4=>x5)=>x6)=1

      ((x4≡x5)≡x6)=>((x7=>x8)=>x9)=1
      ((x7≡x8)≡x9)=>((x10=>x11)=>x12)=1
      ((x10=>x11)=>x12)=>((x1≡x2)≡x3)=0

Контроль по Полякову

  

Solution of problems kind of P149 (ege23.doc) via 08.2016 technique "GRAPHS AND SYSTEMS OF LOGICAL EQUATIONS"

"Poor understanding of Mapping Method (08.2016) is still a half of distress" B.D.

First of all be aware that intellectual property of approach been applied completely belongs to Helen Mironchick (unpublished manuscript ). See also PDF attachment to thread on USE in Informatics Polyakov's  forum  http://egekp.unoforum.pro/?1-6-0-00000120-000-0-0-1561979337   MEA's post 229. Posting below is nothing different from exercising technique proposed by MEA in mentioned PDF attachment targeting better understanding of solution been suggested in those  thread.
We would consider a sample P149 and one more system which doesn't look as standard as P149 and requires a bit more experience in building 08.2016 diagrams.



  ((¬x1=>y1)^z1)≡((¬x2 v y2)=>z2)
  ((¬x2=>y2)^z2)≡((¬x3 v y3)=>z3)
  ((¬x3=>y3)^z3)≡((¬x4 v y4)=>z4)
  ((¬x4=>y4)^z4)≡((¬x5 v y5)=>z5)

  Convert system to equivalent

  ((x1 v y1)^z1)≡((x2=>y2)=>z2)
  ((x2 v y2)^z2)≡((x3=>y3)=>z3)
  ((x3 v y3)^z3)≡((x4=>y4)=>z4)
  ((x4 v y4)^z4)≡((x5=>y5)=>z5)

      Traditional solution ( classic version of Mapping Method as of 2013 ) might be found in my old  blog entry  http://mapping-metod.blogspot.com/2017/12/149-ege23pdf.html
  Passing Polyakov's control



Consider a bit more complicated system

  ((x1 v y1)^z1)=> ((x2=>y2)=>z2)=1
  ((x2 v y2)^z2)=> ((x3=>y3)=>z3)=1
  ((x3 v y3)^z3)=> ((x4=>y4)=>z4)=1
  ((x4 v y4)^z4)=> ((x5=>y5)=>z5)=1

Now build diagrams required to solve updated problem with implications

     Passing Polyakov's Control

Использование предикатов при решении систем уравнений в булевых переменных ( Версия Метода Отображений 08.2016 )

 Пусть F(x,y,z) трехместный предикат определенный на множестве всех трех битовых цепочек.

 Мощность множества истинности этого предиката равна 5 , мощность области определения 

предиката  очевидно равна 8.  Рассмотрим систему уравнений.

F(x2,y2,z2) => F(x1,y1,z1) =1

F(x3,y3,z3) => F(x2,y2,z2) =1 
F(x4,y4,z4) => F(x3,y3,z3) =1
F(x1,y1,z1) => F(x4,y4,z4) =1

Положим
w1=F(x1,y1,z1)
w2=F(x2,y2,z2)
w3=F(x3,y3,z3)
w4=F(x4,y4,z4)

    Рассмотрим три различных предиката, удовлетворяющих исходному условию

      F(x,y,z)= ((x=>y)=>z) ;

      F(x,y,z)= (x=>y^z);

      F (x,y,z) = ((x v y) => z) ;

    Просчитаем по Полякову каждый случай  ( POC - Proof of concept )

Таким образом,если система может быть сведена к диаграмме типа 08.2016 

для w(j) переменных, результат определяется только мощностью множества 

истинности предиката, а не формулой определяющей F(x,y,z)

Bring into play predicates when solving systems of equations in Boolean variables

This post was initiated by the analysis of the approach of Helen A. Mironchick to the task P-40 from ege23.doc.

Let F (x, y, z) be a triple predicate defined on the set of all three bit chains. The truth set of this predicate is exactly 5 different chains, specific bits included in the chains of truth do not matter.Consider the system of equations.

F (x1, y1, z1) ≡ F (x3, y3, z3) => F (x2, y2, z2) = 1

F (x2, y2, z2) ⊕ F (x4, y4, z4) => F (x3, y3, z3) = 1

F (x3, y3, z3) ≡ F (x5, y5, z5) => F (x4, y4, z4) = 1

F (x4, y4, z4) ⊕ F (x6, y6, z6) => F (x5, y5, z5) = 1

Setw1 = F (x1, y1, z1)

w2 = F (x2, y2, z2)

w3 = F (x3, y3, z3)

w4 = F (x4, y4, z4)

w5 = F (x5, y5, z5)

w6 = F (x6, y6, z6)

Then we plot the diagrams and generateMapping Method table

    Consider three cases. Truth sets of each
    of the predicates considered below consists of 5 three bit
    chains, its own for each predicate constructed

     F (x, y, z) = ((x => y) => z);
     F (x, y, z) = (x => y ^ z);
     F (x, y, z) = ((x v y) => z);

     Calculate according to Polyakov each case (POC - Proof of concept)

 

Thus, for a system that can be reduced to the  traditional matrix of  the  Mapping Method  for w (j) variables, the result is determined only by the power of the truth set of the predicate, and not by the formula defining F (x, y, z)

Solution one system (another draft ) of Boolean equations kind of P40 with different outgoing multipliers for different Mapping Method table rows as of 18/07/19

Original system

  ((x1vy1)^z1 ≡ (x3vy3)^z3)=>((x2vy2)^z2) =1

  ((x2vy2)^z2)⊕ ((x4vy4)^z4))=>((x3vy3)^z3) =1

  ((x3vy3)^z3 ≡ (x5vy5)^z5)=>((x4vy4)^z4) =1

  ((x4vy4)^z4)⊕ ((x6vy6)^z6))=>((x5vy5)^z5) =1

Now make a substitution ( kind of design had been suggested in P-40 from ege23.pdf )

   w1=(x1 v y1)^z1

   w2=(x2 v y2)^z2
   w3=(x3 v y3)^z3
   w4=(x4 v y4)^z4
   w5=(x5 v y5)^z5

   Outgoing multipliers are located  at right hand side of diagrams

   Passing Polyakov's Control

  

Solution of one system of boolean equations via reverse pass per Helen Mironchick (II)

"Ignorance of the mapping method is still half the misfortune ..."
  B.D. 

***************************************************************************
  I do emphasize again that core idea of reverse pass to center belongs 
 to Helen Mironchick (unpublished manuscript) .
*************************************************************************** 
Original system

(x1^x2=>x3)^x4=>x5=1
(y1^y2=>y3)^y4=>y5=1
(z1^z2=>z3)^z4=>z5=1
(x1=>y3)=>z4=1

#1 - x1
#2 - x1^x2
#3 - (x1^x2=>x3)
#4 - (x1^x2=>x3)^x4
#5 - (x1^x2=>x3)^x4=>x5)

   Passing Polyakov's Control

Solution of one system of boolean equations via reverse pass per Helen Mironchick

"Ignorance of the mapping method is still half the misfortune ..."
  B.D.

Down here we rely on technique proposed in 
https://mapping-metod.blogspot.com/2019/03/blog-post.html
Original system

((x1^x2=>x3)^x4=>x5)^x6=>x7=1
((y1^y2=>y3)^y4=>y5)^y6=>y7=1
x1=>y7=1

#1 - x1
#2 - x1^x2
#3 - (x1^x2=>x3)
#4 - (x1^x2=>x3)^x4
#5 - (x1^x2=>x3)^x4=>x5)
#6 - (x1^x2=>x3)^x4=>x5)^x6
#7 - ((x1^x2=>x3)^x4=>x5)^x6=>x7=1

   Passing Polyakov's Control

Another system solved via pass to center per Helen Mironchick unpublished manuscript 

((x1^x2=>x3)^x4=>x5)^x6=>x7=1
((y1^y2=>y3)^y4=>y5)^y6=>y7=1
x1=>y5=1

#1 - x1
#2 - x1^x2
#3 - (x1^x2=>x3)
#4 - (x1^x2=>x3)^x4
#5 - (x1^x2=>x3)^x4=>x5)
#6 - (x1^x2=>x3)^x4=>x5)^x6
#7 - ((x1^x2=>x3)^x4=>x5)^x6=>x7=1

    Passing Polyakov's Control

Метод Отображений - тестирование проход к центру и обратный проход

Оригинальна схема прохода к центру предложена 
Еленой А. Мирончик . Смотри 
https://vk.com/doc6125348_505417587?hash=44fb5048df995959ea&dl=210d2b189eb483566a

Одно из основных преимуществ метода - это толерантность к числу уравнений системы

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

((((x1=>x2)=>x3)=>x4)=>x5)=>x6 =1
((((y1=>y2)=>y3)=>y4)=>y5)=>y6 =1
((((z1=>z2)=>z3)=>z4)=>z5)=>z6 =1
(x3=>y4)=>z5 =1

                                  X3 Y4 Z5

                            0    23  19  27
                            1    20  24  16

 Контроль по Полякову

   Ссылки

  1. https://vk.com/doc6125348_505417587?hash=44fb5048df995959ea&dl=210d2b189eb483566a

Solution of one problem 23 from USE in Informatics 2019

Original task

Solution

System below is equivalent to original one.
The previous system is supposed to make convertion itself
a real headaches generator

(x1=>x2)^(y2=>y1)^(x1 v y1)=1
(x2=>x3)^(y3=>y2)^(x2 v y2)=1
(x3=>x4)^(y4=>y3)^(x3 v y3)=1
(x4=>x5)^(y5=>y4)^(x4 v y4)=1
(x5=>x6)^(y6=>y5)^(x5 v y5)=1
x6 v y6=1

Proceed with building fork diagram with transition pair (x2,y2) &&  forking matrix

   Passing Polyakov's Control
  

  

   

Helen Mironchick's Solution of one sysem of boolean equations from USE in Informatics forum (16.05.2019)

Algebra of Predicates versus K.Yu. Polyakov, Sets and Logic in the Unified State Examination Problems // Informatics , № 10, 2015

Consider three complicated cases for every clone of classical problem #18 of USE in Informatics ( Russian abbreviation  EGE )
1. Solution of challenging equation with mixed basic predicates of type E() && DEL()  via technique proposed by Helen Mironchick
2. Solution of the equation E(M)⊕E(N) => E(A)*¬E(M & N) ≡ 1 via the calculus of basic predicates according to Helen Mironchick
3. Predicate algebra and classical examples of the Unified State Examination  in Informatics problem #18 
Segments of the real axis and discrete sets of integers 


*********
Case 1
*********
Solution of challenging equation with mixed basic predicates of type E() && DEL()  via technique proposed by Helen Mironchick 

Denote by DEL (n, m) the statement "a natural number n is divided without a remainder by a positive integer m". For what is the smallest natural number A, the formula
    (D(34)⊕D(51) => ¬D(A)^D(272)) v Е(15) ≡ 1  
is identically true (that is, it takes the value 1 for any natural value of the variable x)?

The absorption of predicates of type ¬D() from one basis in a disjunction and the suppression of predicates of type D() from one basis in a conjunction makes the calculus constructed  by Helen Mironchik a universal approach that converts problem 18's DEL() of any complexity into a simple equation in DEL() predicates.

Further notice belongs to Helen :-

D(16) = ¬E(1)*¬E(2)*¬E(4)*¬E(8) = 
   =  ¬(E(1) v E(2) v E(4) v E(8)) = ¬E(15)
E(15)=¬D(16)

Convert original equation from implication to disjunction

(D(34)≡D(51)) v ¬D(A)^D(272)) v ¬D(16) ≡ 1
D(34)^D(51) v ¬D(34)^¬D(51) v ¬D(A)^D(272)) v ¬D(16) ≡ 1
D(34)^D(51) v ¬D(34)^¬D(51) v ¬D(A)^D(17)^D(16) v ¬D(16) ≡ 1

Suppress D(17) in first and fourth terms via ¬D(17),
then suppress D(2^4) via ¬D(2^4) in fourth term

D(34) = D(2)^D(17)
D(51) = D(3)^D(17)
D(31)^D(51) = D(2)^D(3)^D(17)

¬D(34) = (¬D(2) v ¬D(17))
¬D(51) = (¬D(3) v ¬D(17))

¬D(34)^¬D(51) = ¬D(2)^¬D(3) v ¬D(17)

D(2)^D(3)^D(17) v ¬D(2)^¬D(3) v ¬D(17) v 
  v  ¬D(A)^D(17)^D(2^4) v ¬D(2^4) ≡ 1

D(6) v ¬D(2)^¬D(3) v ¬D(17) v ¬D(A) v ¬D(2^4) ≡ 1

Thus A(min) = 6

*********
Case 2 
*********
Solution of the equation E(M)⊕E(N) => E(A)*¬E(M & N) ≡ 1 via the calculus of basic predicates  according  to Helen 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)

Once again the decomposition of E() type predicates into logical sum of basic predicates , which are actually  predicates associated with powers of 2. The decomposition itself  works as universal approach for solving the problems #18 of per bits conjunction type having any level of complexity. Here is important to understand the principal difference between Bitwise2 technique and technique relying on decomposition into basic predicates. The last one
provide quite straight forward way to suppress the factors of  ¬E(2^s) type in conjuction via terms of E(2^s)  type coming into equation to be logically added to conjunction kind of  ¬E(2^5)*¬E(2^4)*¬E(2^3)*¬E(2^1)  + E(2^5) +  E(2^3) + E(2^1) = ¬E(2^4) + E(2^5) + E(2^3) + E(2^1)


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)

*********
Case 3
*********
Predicate algebra and classical examples of the Unified State Examination problem Informatics № 18 ( Segments of the real axis and discrete sets of integers )

See
1)  Алгебра предикатов и классические примеры задач ЕГЭ Информатика № 18
2)   See Алгебра предикатов и классические задачи ЕГЭ Информатика № 18 с XOR и "~"



Refences 
1. A. Mironchik, ALGEBRA OF PREDICATES AND RELATED GEOMETRIC MODELS CREATION IN REGARDS OF UNIFIED STATE EXAMINATION IN INFORMATICS (RUSSIAN EGE) ,
Informatics at school №3 , 2019
2. http://kpolyakov.spb.ru/download/mea18bit.pdf