Monday, September 10, 2018

Unleash the full power of the Mapping Method (Graphs and Systems of Boolean Equations by E.A. Mironchik)


This is an attempt follow up http://kpolyakov.spb.ru/download/mea-2016-8.pdf 
with use case a bit more different then considered in referenced article 

Consider foillowing system

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


Convert system as follows

(x1vx2)^((¬x1^y1^z1^w1)v(x1^¬y1^z1^w1)v(x1^y1^¬z1^w1)v(x1^y1^z1^¬w1)) =1
(x2vx3)^((¬x2^y2^z2^w2)v(x2^¬y2^z2^w2)v(x2^y2^¬z2^w2)v(x2^y2^z2^¬w2)) =1
(x3vx4)^((¬x3^y3^z3^w3)v(x3^¬y3^z3^w3)v(x3^y3^¬z3^w3)v(x3^y3^z3^¬w3)) =1
(x4vx5)^((¬x4^y4^z4^w4)v(x4^¬y4^z4^w4)v(x4^y4^¬z4^w4)v(x4^y4^z4^¬w4)) =1
((¬x5^y5^z5^w5)v(x5^¬y5^z5^w5)v(x5^y5^¬z5^w5)v(x5^y5^z5^¬w5)) =1

Build complete graph for system



    Polyakov's control passed

   

Sunday, September 9, 2018

Solution on one system from BU's queue 10/09/2018


 z1=x1~x3
 z2=x2~x4
 z3=x5~x7
 z4=x6~x8
 z5=x9~x10

(z1 v z2)^(!z1 v z2 ) = 0  Here z2 cannot be 1 thus z2 =0
(z2 v z3)^(!z2 v z3 ) = 0  Here z3 cannot be 1 thus z3 =0
(z3 v z4)^(!z3 v z4 ) = 0  Here z4 cannot be 1 thus z4 =0
(z4 v z5)^(!z4 v z5 ) = 0  Here z5 cannot be 1 thus z5 =0
(z1 => z2) => (z4 v !z5) =1

Convert last equation
(!z1 v z2) => (z4 v !z5) =1
(z1^!z2) v (z4 v !z5) =1
Because z2 = 0 and z4 = 0 and z5 = 0
(z1^!z2) v (0 v 1) = 1
z1 v 1 = 1
Hense z1 =0 or z1 =1

Finally we get
System01
z1 = 1 (x1 =1;x3=1) or (x1=0;x3=0)
z2 = 0 gives two solutions (x2,x4)
z3 = 0 gives two solutions (x5,x7)
z4 = 0 gives two solutions (x6,x8)
z5 = 0 gives two solutions (x9,x10)
Total number of solutions 32

System02
z1 = 0  (x1 =1;x3=0) or (x1=0;x3=1)
z2 = 0 gives two solutions (x2,x4)
z3 = 0 gives two solutions (x5,x7)
z4 = 0 gives two solutions (x6,x8)
z5 = 0 gives two solutions (x9,x10)
Total number of solutions 32

So orinal system has 64 solutions