Saturday, April 15, 2017

Solution of one system of equations in boolean variables via bitmasks in regards of training for Unified State Examination in Informatics (Russia)

  
In brief, bitmasks are supposed to be a core tool for solution of systems of equations in Boolean variables versus method suggested at
https://inf-ege.sdamgia.ru/test?theme=264
for task 11 which is pretty much similar to sample been analyzed bellow

*************************************
Original task looks like :-
*************************************
Determine total number of corteges
{x1,...,x9,y1,....,y9} which and only which
satisfy system :-

((x1 ≡ y1) → (x2 ≡ y2)) ∧ (x1 → x2) ∧ (y1 → y2) = 1
((x2 ≡ y2) → (x3 ≡ y3)) ∧ (x2 → x3) ∧ (y2 → y3) = 1
...
((x8 ≡ y8) → (x9 ≡ y9)) ∧ (x8 → x9) ∧ (y8 → y9) = 1

Consider truncated system :-

(x1 → x2) ∧ (y1 → y2) = 1
(x2 → x3) ∧ (y2 → y3) = 1
...
(x8 → x9) ∧ (y8 → y9) = 1

Now build well known bitmasks for {x} and {y}

x1 x2 x3 x4 x5 x6 x7 x8 x9
----------------------------------------
1   1   1   1   1   1   1   1   1 
0   1   1   1   1   1   1   1   1 
0   0   1   1   1   1   1   1   1 
0   0   0   1   1   1   1   1   1 
0   0   0   0   1   1   1   1   1 
0   0   0   0   0   1   1   1   1 
0   0   0   0   0   0   1   1   1 
0   0   0   0   0   0   0   1   1 
0   0   0   0   0   0   0   0   1 
0   0   0   0   0   0   0   0   0 



y1 y2 y3 y4 y5 y6 y7 y8 y9
-----------------------------------------
1   1   1   1   1   1   1   1   1 
0   1   1   1   1   1   1   1   1 
0   0   1   1   1   1   1   1   1 
0   0   0   1   1   1   1   1   1 
0   0   0   0   1   1   1   1   1 
0   0   0   0   0   1   1   1   1 
0   0   0   0   0   0   1   1   1 
0   0   0   0   0   0   0   1   1 
0   0   0   0   0   0   0   0   1 
0   0   0   0   0   0   0   0   0 


We would name bellow first matrix "X" an second "Y"

For j=2 to j=9 consider  following two concatenations
"X" ->"Y" and "Y" -> "X"

First one :-

X                                     Y
---------------------------           ------------------------------
|                         |           |                            |
---------------------------           ------------------------------ 
j                         |           |                            |   
---------------------------           ------------------------------ 
. . . .                   |           j+1                          | 
---------------------------           ------------------------------
                                      j+2                          |
                                      ------------------------------        
                                      | . . . . .                  |
---------------------------           ------------------------------  
10                        |           10                           |     
---------------------------           ------------------------------ 
                                      

Record {j} from X with records {j+1,j+2,. . . 10} from Y
and vice versa second one :-

Y                                     X
---------------------------           ------------------------------
|                         |           |                            |
---------------------------           ------------------------------ 
j                         |           |                            |   
---------------------------           ------------------------------ 
. . . .                   |           j+1                          | 
---------------------------           ------------------------------
                                      j+2                          |
                                      ------------------------------        
                                      | . . . . .                  |
---------------------------           ------------------------------  
10                        |           10                           |     
---------------------------           ------------------------------ 
 
Record { j } from Y with records {j+1,j+2,. . . 10} from X
We'll get total 2*(10-j) сorteges making boolean value of implication

   ((x[j-1] ≡ y[j-1])) → (x[j] ≡ y[j]) equal FALSE

**************************************
For instance when j=3 we get
**************************************

x1 x2 x3 x4 x5 x6 x7 x8 x9
----------------------------------------
1   1   1   1   1   1   1   1   1 
0   1   1   1   1   1   1   1   1 
0   0   1   1   1   1   1   1   1   =>
0   0   0   1   1   1   1   1   1 
0   0   0   0   1   1   1   1   1 
0   0   0   0   0   1   1   1   1 
0   0   0   0   0   0   1   1   1 
0   0   0   0   0   0   0   1   1 
0   0   0   0   0   0   0   0   1 
0   0   0   0   0   0   0   0   0 



y1 y2 y3 y4 y5 y6 y7 y8 y9
-----------------------------------------
1   1   1   1   1   1   1   1   1 
0   1   1   1   1   1   1   1   1 
0   0   1   1   1   1   1   1   1 
0   0   0   1   1   1   1   1   1 <=
0   0   0   0   1   1   1   1   1 <=
0   0   0   0   0   1   1   1   1 <=
0   0   0   0   0   0   1   1   1 <=
0   0   0   0   0   0   0   1   1 <=
0   0   0   0   0   0   0   0   1 <=
0   0   0   0   0   0   0   0   0 <=


 Vice Versa Set :-


y1 y2 y3 y4 y5 y6 y7 y8 y9
-----------------------------------------
1   1   1   1   1   1   1   1   1 
0   1   1   1   1   1   1   1   1 
0   0   1   1   1   1   1   1   1 =>
0   0   0   1   1   1   1   1   1 
0   0   0   0   1   1   1   1   1 
0   0   0   0   0   1   1   1   1 
0   0   0   0   0   0   1   1   1 
0   0   0   0   0   0   0   1   1 
0   0   0   0   0   0   0   0   1 
0   0   0   0   0   0   0   0   0

x1 x2 x3 x4 x5 x6 x7 x8 x9
----------------------------------------
1   1   1   1   1   1   1   1   1 
0   1   1   1   1   1   1   1   1 
0   0   1   1   1   1   1   1   1 
0   0   0   1   1   1   1   1   1 <=
0   0   0   0   1   1   1   1   1 <=
0   0   0   0   0   1   1   1   1 <=
0   0   0   0   0   0   1   1   1 <=
0   0   0   0   0   0   0   1   1 <= 
0   0   0   0   0   0   0   0   1 <=
0   0   0   0   0   0   0   0   0 <=

****************************************************************************
 So when j=3 we have 2*7 = 14 corteges where x2≡y2 is True
 and x3≡y3 is False. So,  (x2 ≡ y2) → (x3 ≡ y3) is actually 1 -> 0
 what is False by definition.
****************************************************************************

What is sign that set of corteges generated for each j from [2.3.4,...,9]
should be removed from 100 total solutions of truncated system of boolean
equations.

Now calculate :-

s:= 0 ;
for j=2 to j=10 do
begin
 s:= s + (10-j) ;
end ;
s= 2*s ;
writeln (s) ;

Finally we get s=72

Total number of corteges obtained via decart multiplication of X and Y is equal 100. So number of solutions of original system would be 100-72=28

I appreciate courtesy provided by informatik "BU"
  https://www.youtube.com/watch?v=MDL5Mym5Aac

However, don't behave so nicely as "BU" always does.