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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: