Bellow we intend to benefit from idea of H.A, Mironchick building a graph
for system of boolean equations using just one variable for establishing
connection between equations in system on snapshot above.
Perform substitute :-
x1 ~ x3 = z1; x2 ~ x4 = z2; x5 ~ x7 = z3; x6 ~ x8 = z4; x9 ~ x10 = z5
Convert original system into
(z1 v z2)^(z1 => z2) = 0
(z2 v z3)^(z2 => z3) = 0
(z3 v z4)^(z3 => z4) = 0
(z4 v z5)^(z4 => z5) = 0
(z1 => z2) => (z5 => z4) =1
Build graph to solve system of first four equations
(z1 => z2) =>(z5=> z4) = ( ¬z1 v z2) => (¬z5 v z4) =
¬(¬z1 v z2) v ( ¬z5 v z4) = z1^(¬z2) v ¬z5 v z4 = 1
Passing Polyakov's control
In other words we get 2^5 + 2^5 = 2^6 = 64 ( solutions for {x})
Straight forward mapping would look like
((x1~x3)v(x2~x4))^((x1~x3)=>(x2~x4)) = 0
((x2~x4)v(x5~x7))^((x2~x4)=>(x5~x7)) = 0
((x5~x7)v(x6~x8))^((x5~x7)=>(x6~x8)) = 0
((x6~x8)v(x9~x10))^((x6~x8)=>(x9~x10)) = 0
((x1~x3)=>(x2~x4))=>((x9~x10)=>(x6~x8)) = 1
Build diagrama based on first equation which would work
for first four equations. Notice that transition pairs are x2x4 , x5x7 , x6x8
In fact adding
((x1~x3)=>(x2~x4))=>((x9~x10)=>(x6~x8)) = 1
would add ( 0 => 0) => (0 =>0) =1 on lines "01" and "10"
e.g. True => True = 1 . So adding this 5-th equation won't decrease number of solutions of original sytem
Thus answer is 64
No comments:
Post a Comment