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