Solution problem #113 from ege23.doc in 08/2016 style vs Video for 23-rd by Informatik BU

Original source for #113


Building meta chart and fork generation 08.2016 chart providing an answer



    You might want to compare 08/2016 chart generation with well known video been recorded by Informatik BU   https://vk.com/inf_bu?z=video-89501371_456239128%2Fvideos-89501371%2Fpl_-89501371_-2

Solution of one USE Informatics system of Boolean equations in 08.2016 style

Original system



Original system
¬(x1≡x2)v¬(x1≡x3)^(x2≡x3)=1
¬(x3≡x4)v¬(x3≡x5)^(x4≡x5)=1
¬(x5≡x6)v¬(x5≡x7)^(x6≡x7)=1
¬(x7≡x8)v¬(x7≡x9)^(x8≡x9)=1

Convert to equivalent
  (x1≡x2) => (x1⊕x3)^(x2≡x3) =1
  (x3≡x4) => (x3⊕x5)^(x4≡x5) =1
  (x5≡x6) => (x5⊕x7)^(x6≡x7) =1
  (x7≡x8) => (x7⊕x9)^(x8≡x9) =1

   Here we have transition variables x3,x5,x7 rather then transition pairs between equations. Thus we would manage via 08.2016 charts.

 
 Consider a bit more complicated sample of similar system
   ((x1≡x2)≡x3)=>(x1⊕x4)^((x2≡x3)≡x4)=1
   ((x4≡x5)≡x6)=>(x4⊕x7)^((x5≡x6)≡x7)=1
   ((x7≡x8)≡x9)=>(x7⊕x10)^((x8≡x9)≡x10)=1
Transition variables are x4 and x7. Fork 08.2016 chart for this system

Решение одной задачи на побитную конъюнкцию в Алгебре Предикатов {E(k)}

Алгебра предикатов {E(k)} определена в http://kpolyakov.spb.ru/download/mea18bit.pdf

Пусть {N(j)} j=1,2,...,m - конечное множество натуральных чисел. 
Найти наименьшее А при котором имеет место следующее тождество
(E(N(1)=>(E(N(2)=>(E(N(3)=> . . . .=>(E(N(m)=>E(A)) . . . .))) ≡1

Решение
m
 v (¬E(N(j) ) v E(A) ≡ 1
j=1
   m
¬( ^E(N(j) ) v E(A) ≡ 1
  j=1
  m
( ^E(N(j) ) => E(A) ≡ 1
 j=1

Эквивалентно           
                    m
¬E(A) => ¬( ^E(N(j) ) ≡ 1
                    j=1
Далее
                  m 
¬E(A) => ( v ¬E(N(j) ) ≡ 1
                 j=1
В силу дистрибутивности импликации по отношению к дизъюнкции
 m
  v ( ¬E(A) => ¬E(N(j) ) ≡ 1
 j=1

Эквивалентно
  m
  v ( E(N(j)=>E(A) ) ≡ 1
 j=1

  По теореме 1 из https://mapping-metod.blogspot.com/2019/02/2017-versus-bitwise2-1-2.html
получаем    A(min)  =  min{N(j)}
                                      j=1,2,..,m
Если каждое слагаемое дает бит ( каждое N(j) имеет бит не входящий А ) , не входящий в А , то строим двоичное число z0,содержащие все эти биты (наличие совпадающих только упрощает ситуацию). Тогда
  m
( v (E(N(j) => E(A))(z0) = 0
 j=1
то есть если А < A(min), то каждое N(j) имеет такой бит и найденное А(min) действительно минимально. 
Следствие.
Любая задача вида E(M)=>(E(N)=>E(A)) ≡ 1 тривиальна.
A(min)=min{M,N} . Например

Решение разложением по базисным предикатам уравнения побитовой конъюнкции E(15) => (E(35) => E(A)) ≡ 1

Оригинал на новостной ленте ВК Informatics_100

 
https://vk.com/informatics_100?z=photo-40390768_457276356%2Fwall-40390768_198488 

Решение разожением по базисным предикатам ( Елена Мирончик )

E(35) = E(32) v E(2) v E(1)
E(15) = E(12) v E(2) v E(1)
Далее
E(35)^E(15)= (E(32) v E(2) v E(1))^(E(12) v E(2) v E(1))
E(32)^E(12) v E(32)^E(2) v E(32)^E(1) v
v E(2)^E(12) v E(2) v E(2)^E(1) v
v E(1)^E(12) v E(1)^E(2) v E(1)
По закону поглощения
(1) E(35)^E(15) = E(2) v E(1) v E(32)^E(12) = E(3) v E(32)^E(12)
(2) E(35)^E(15) = E(3) v E(32)^E(8) v E(32)^E(4)

Перейдем к уравнению
E(15)=>(E(35)=>E(A)) ≡ 1
¬E(15) v ¬E(35) v E(A) ≡ 1
¬(E(15)^E(35)) v E(A) ≡ 1
¬(E(3) v E(32)^E(12)) v E(A) ≡ 1
(E(3) v E(32)^E(12))=> E(A) ≡ 1

Поскольку (P v Q)=>C ≡ (P=>C)^(Q=>C)
(E(3)=>E(A))^(E(32)^E(12)=>E(A)) ≡ 1
Следовательно (Елена Мирончик)
(E(3)=>E(A)≡ 1)^(E(32)^E(12)=>E(A)≡ 1)=True
(¬E(3) v E(A)≡ 1)^( ¬E(32) v ¬E(12) v E(A) ≡1)=True

Откуда как минимум
(E(3) => E(A) ≡ 1)^(E(12) => E(A) ≡ 1)
**********************************************
A(min) должно содержать все биты 3 и 12 (1111)
**********************************************

То есть A(min) = 15

 

Задание №23 ЕГЭ 2019 Информатика СтатГрад Апрель 2019. Метод отображения

Условие

Решение (задача ни о чем по Борису Трушину)

  

Setting up a cross-reference table in 08/2016 approach of Helen Mironchick when moving to a new line of the system of Boolean equations

UPDATE as of 6/10/2019
  I do have to notice that solving System 5 from http://kpolyakov.spb.ru/download/mea-2016-8.pdf  silently does what described down here without focusing attention on predicates (x3≡x4) and x3^x4  truth and false sets intersections. Actually four sets were obtained and theirs powers have been used to solve System 5. I sincerely apologize for missing this doing original post
END UPDATE

The key place is a detailed description of building a cross-reference table 
when moving to a new line of the system. The chart generation is just a consequence.
First consider system
   (1) F1(x1,y1,z1)=>F2(x2,y2,z2) =1
   (2) F1(x2,y2,z2)=>F2(x3,y3,z3) =1
   (3) F1(x3,y3,z3)=>F2(x4,y4,z4) =1
   (4) F1(x4,y4,z4)=>F2(x5,y5,z5) =1
where F1 and F2 are triple predicates
Denote card(N) the power of set N
Denote n1,n2,m1,m2,s1,s2
    n1=card (falseSet_F2 ∩ falseSet_F1)
    n2=card (falseSet_F2 ∩ truthSet_F1)
    m1=card (truthSet_F2 ∩ falseSet_F1)
    m2=card (truthSet_F2 ∩ truthSet_F1)
    s1=card (falseSet_F1)
    s2=card (truthSet_F1)

Then following 08.2016 diagram would show

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

Perform two runs. First for system
(((x1=>y1)=>z1)⊕((z1=>y1)=>x1))=>((x2≡y2)≡z2)=1
(((x2=>y2)=>z2)⊕((z2=>y2)=>x2))=>((x3≡y3)≡z3)=1
(((x3=>y3)=>z3)⊕((z3=>y3)=>x3))=>((x4≡y4)≡z4)=1
(((x4=>y4)=>z4)⊕((z4=>y4)=>x4))=>((x5≡y5)≡z5)=1
(((x5=>y5)=>z5)⊕((z5=>y5)=>x5))=>((x1≡y1)≡z1)=0

Starting values for G(x1,y1,z1) are defined by
false triples ((x1≡y1)≡z1)
For 000  G(0,0,0) =0

For 101  G(1,0,1) =0

For 011  G(0,1,1) =1

For 110  G(1,1,0) =1
Thus  G(x1,y1,z1) starts  with 2/2
The result of first run is value G(x5,y5,z5) on line "1". It defines the number 
of false solutions - 1952 , which should be deducted from number of solutions of second system.
Second run :-

(((x1=>y1)=>z1)⊕((z1=>y1)=>x1))=>((x2≡y2)≡z2)=1

(((x2=>y2)=>z2)⊕((z2=>y2)=>x2))=>((x3≡y3)≡z3)=1
(((x3=>y3)=>z3)⊕((z3=>y3)=>x3))=>((x4≡y4)≡z4)=1
(((x4=>y4)=>z4)⊕((z4=>y4)=>x4))=>((x5≡y5)≡z5)=1

Set up cross-reference table  && fork 08/2016 diagrams matching requirements

Performing Polyakov's Control

      

23-я из стрима БУ

 Законы алгебры логики

   (x1≡x2) = (x1^x2) v ( !x1^!x2)

Система

(x1≡x2) v (x1≡x3)=1
(x2≡x3) v (x2≡x4)=1
(x3≡x4) v (x3≡x5)=1
(x4≡x5) v (x4≡x6)=1
(x5≡x6) v (x5≡x7)=1
(x6≡x7) v (x6≡x8)=1

Solution of systems of Boolean equations kind of P204 with three variables via format 08/2016

Once again I strongly believe that technique proposed in http://kpolyakov.spb.ru/download/mea-2016-8.pdf seems to be underestimated either not well understood until date. Regardless Unified State Examination Polyakov's forum contains more then enough samples demonstrating advantages of 08.2016 technique. A poor understanding of the ideology 08.2016 in essence for today means a lack of understanding what  kind of flexibility and power Mapping Method provides for USE in  Informatics developers in meantime. 

Original system 

(((x1≡y1)≡z1) =>((x2≡y2)≡z2)) ^ (x1 v y1 v z1)=1
(((x2≡y2)≡z2) =>((x3≡y3)≡z3)) ^ (x2 v y2 v z2)=1
(((x3≡y3)≡z3) =>((x4≡y4)≡z4)) ^ (x3 v y3 v z3)=1
(((x4≡y4)≡z4) =>((x5≡y5)≡z5)) ^ (x4 v y4 v z4)=1
(((x5≡y5)≡z5) =>((x6≡y6)≡z6)) ^ (x5 v y5 v z5)=1
(((x6≡y6)≡z6) =>((x7≡y7)≡z7)) ^ (x6 v y6 v z6)=1
(x7 v y7 v z7)=1

As soon as we have a conditions that allow us to determine the bits of x(j),y(j),z(j)  for the arrows outgoing from the node of the 08/2016 chart, we can start. In particular case, we are ready to go ahead with  08/2016 chart style.  In other words, we have to know bits combination {x,y,z} associated with arrows connecting  neighboring nodes in chart . 

   Cloning to {x,y,z} systems like P175 or P116 is quite straight forward

Variations on the topic of the USE Informatics forum "Another proof of Helen Mironchick's paradigm" - Solving one system of equations in Boolean variables in the style of 08.2016 "GRAPHES AND SYSTEMS OF LOGICAL EQUATIONS"

The source system is described by the digrams in the style of 08.2016 and immediately calculated

  ((x1≡x2)≡x3)=>((x4=>x5)=>x6)=1
  ((x4≡x5)≡x6)=>((x7=>x8)=>x9)=1
  ((x7≡x8)≡x9)=>((x1=>x2)=>x3)=1
System calculation
  ((x1≡x2)≡x3)=>((x4=>x5)=>x6)=1
  ((x4≡x5)≡x6)=>((x7=>x8)=>x9)=1
in first table 
System calculation
  ((x1≡x2)≡x3)=>((x4=>x5)=>x6)=1
  ((x4≡x5)≡x6)=>((x7=>x8)=>x9)=1
  ((x7≡x8)≡x9)=>((x1=>x2)=>x3)=0
in second table

 In the second table, we start the run by setting "2' and "1" values for 3-bit groups, where  (x1=> x2) =>x3 = 0. Upon completion, we count the number (x7≡x8) ≡ x9 equal to 1  in the last column, where, generally speaking, there are bit triples associated with  (x7=>x8) =>x9. 
In the green group (3 triples 001,100,111) and (x7=>x8)=>x9 = (x7≡x8 )≡x9 equal to 1
In the gray group (1 triple 010) and (x7=>x8)=>x9 = 0 ,
but (x7≡x8)≡x9 = 1 

  Passing Polyakov's Control
  

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.

Once again I strongly believe that  technique proposed in http://kpolyakov.spb.ru/download/mea-2016-8.pdf seems to be underestimated either not well understood until date. Regardless Unified State Examination Polyakov's forum contains more then enough samples demonstrating advantages of 08.2016 technique.

  
  ((¬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)

Current status of 08.2016 technique seems much more sophisticated then in original article
http://kpolyakov.spb.ru/download/mea-2016-8.pdf
Now build diagrams required to solve P-149

   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
Classic (2013)  diagram based on truth table.

  
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
   

  

Mapping Method v. 08.2016 vs Classic Bit mask Aanalysis proposed by Informatik BU ( a trivial sample )

Consider Video by mister BU to solve traditional USE's problem 23

     Link to YouTube Video 
     https://www.youtube.com/watch?v=kPZC8E1saCs

     Now fork Mapping Method 08.2016 Diagram.

Here we perform a reverse move through first conjunction of "x" implications,  converting classic implication  diagram for x(j)=>x(j+1) to opposite x(j) order 
   

    

    We are all set in a couple of minutes

    See for details http://kpolyakov.spb.ru/download/mea-2016-8.pdf

Использование предикатов при решении систем уравнений в булевых переменных Версия Метода Отображений 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 )
 
   

Использование предикатов при решении систем уравнений в булевых переменных

Этот пост инициирован анализом подхода Елены А. Мирончик к задаче  Р-40 из ege23.doc
Пусть  F(x,y,z) трехместный предикат определенный на множестве всех трех битовых цепочек. Множество истинности этого предиката есть ровно 5 различных цепочек, конкретные биты входящие в цепочки истинности значения не имеют.
Рассмотрим систему уравнений.

(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

Положим

w1=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)

Тогда построим диаграммы и сгенерируем
таблицу Метода Отображений

   Рассмотрим три случая . Множества истинности каждого
   из рассмотренных ниже предикатов состоит ровно из 5 трех 
   битовых цепочек, своих  для каждого предиката

    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 )

Таким образом, для системы, которая может быть сведена к традиционной матрице Метода отображений для w(j) переменных, результат определяется только мощностью множества истинности предиката, а не формулой определяющей F(x,y,z) 

Ссылки

1. http://kpolyakov.spb.ru/download/mea-2013-10.pdf

Solution one more 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
   
((x1 v y1)^z1 ≡ (x3 v y3)^z3) => ((x2 v y2)^z2) =1
((x2 v y2)^z2)⊕ ((x4 v y4)^z4)) => ((x3 v y3)^z3) =1
((x3 v y3)^z3 ≡ (x5 v y5)^z5) => ((x4 v y4)^z4) =1
((x4 v y4)^z4)⊕ ((x6 v y6)^z6)) => ((x5 v y5)^z5) =1

Follow an idea proposed in P-40 solution (Helen Mironchick ) just with more or less complicated expressions for w1,w2,w3,w4,w5,w6. However, in particular case we would have different outgoing multipliers for bit 0 it would be 5 and for bit 1 it would be 3 vs previously considered ones.

Now make a substitutions ( 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
   w6=(x6 v y6)^z6

   Outgoing multipliers are located  at right hand side of diagrams for  "identity" and "xor"
  

    Passing Polyakov's Control
    

Solution one system of Boolean equations kind of P40 with different outgoing multipliers for different Mapping Method table rows as of 17/07/19

Original system

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

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

w1=(x1=>y1)=>z1
w2=(x2=>y2)=>z2
w3=(x3=>y3)=>z3

Follow an idea proposed in P-40 solution (Helen Mironchick ) just with more or less complicated expressions for w1,w2,w3. However, in particular case we would have different outgoing multipliers for bit 0 it would be 3 and for bit 1 it would be 5. I constructed system having only two and three equations to highlight a core idea and avoid calculations with huge numbers. Just notice that for outgoing bit 1 multiplier for current system would be 5 versus 1  in  P-40. You may see http://kpolyakov.spb.ru/download/mea-2013-10.pdf page 23 to understand from where they come from. In fact, number of members in implication would only change outgoing numbers. Say 4 would have (5,11), 5 would have (11,21)

Final excel drafts  follows below

Next system ( 3 equations )

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

   w1=(x1=>y1)=>z1
   w2=(x2=>y2)=>z2
   w3=(x3=>y3)=>z3
   w4=(x4=>y4)=>z4
   w5=(x5=>y5)=>z5

   Passing Polyakov's Controls
   

Solution one System of Boolean Equations from BU's pending queue as of 06/07/2019 via 08.2016 technique (once again)

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

Mentioned technique was proposed in http://kpolyakov.spb.ru/download/mea-2016-8.pdf
and seems to be underestimated either not well understood until date. 
Regardless Unified State Examination Polyakov's forum contains more then 
enough samples demonstrating advantages of 08.2016 technique

Original source

 (x1=>y1)^(x1vx2)^¬(x1^x2)=1
 (x2=>y2)^(x2vx3)^¬(x2^x3)=1
 (x3=>y3)^(x3vx4)^¬(x3^x4)=1
 (x4=>y4)^(x4vx5)^¬(x4^x5)=1
 (x5=>y5)^(x5vx6)^¬(x5^x6)=1
 (x6=>y6)^(x6vx7)^¬(x6^x7)=1
 (x7=>y7)^(x7vx8)^¬(x7^x8)=1
 (x8=>y8)^(x8vx9)^¬(x8^x9)=1
 x9=>y9=1

In fact we are getting the same type of officially issued systems Just  having different number of equations

Fork diagrams in 08.2016 style. Looks like a shooting gun on sparrows.

  Passing Polyakov's Control

   
   P-180

(x1=>x2)=>(x3=>x4)=1
(x3=>x4)=>(x5=>x6)=1
(x6=>x7)=>(x7=>x8)=1
(x7=>x8)=>(x9=>x10)=1
x1^x3^x5^x7^x9=1

Due to A=>B=¬AvB

Equivalent system is

x2=>x4 =1
x4=>x6 =1
x6=>x8 =1
x9=>x10 =1

  Passing Polyakov's Control

   References
   1. https://youtu.be/RJ4lOLgKOFU