## 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

*************************************
*************************************
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”
However, don’t behave so nicely as “BU” always does.

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

1. Greetings! This is my 1st comment here so I just wanted to give a quick shout out and say I genuinely
other blogs/websites/forums that cover the same
subjects? Thank you so much!

2. dbaxps says:

Unfortunately all manuals written by EGE developers and myself were done in russian . I did a couple in English just because of offensive content. To hide it from some categories of readers.
Here is my core blog clearly demonstrating power of Mapping method by Helen Mironchick. Same task may be solved via mentioned method in a few minutes. Fell free to see
https://informatics-ege.blogspot.com/ and my page on VK
https://vk.com/bderzhavets .
Thanks a lot for your feedback.
Boris

3. dbaxps says:

I pointed to my sources only because you would be able to find stuff been written in English. Would you understand Russian Please,see original work belongs to Helen