Решение одной системы логических уравнений с помощью битовых масок в плане подговки к ЕГЭ по информатике

Если коротко, то битовые маски наиболее гибкий инструмент
для решения систем уравнений в булевых переменных
в сравнении с методом, предложенным на нескольких известных сайтах
runet'a. Не буду скрывать, следующее  видео :-
https://www.youtube.com/watch?v=MDL5Mym5Aac
прозводит сильное впечатление в сравнении с некоторыми роликами
на YouTube по той же задаче. Таже техника эффектно применена здесь :-
https://www.youtube.com/watch?v=uQtANwb_-Qs 
https://www.youtube.com/watch?v=MDL5Mym5Aac
задача 23 демо версии ЕГЭ 2017. Битовые маски для (x} и {y}
конкатенируются следуя логике конкретного случая.

In meantime mister "BU" seems to be the best IT trainer on the Net,
either he wants it to happen or doesn't. He deserves words "Thank you Sir"
uncountable number of times.

******************************************************************************
Рассмотрим пример  на сайте Константина Полякова
Вариант 9 задача 23 (№ 476)  с печально известным номером 23 
******************************************************************************
Найти количество решений системы
{x1,...,x9,y1,....,y9}

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

********************************
Начнем с системы вида :-
********************************

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

Решения этой системы описываются хорошо известными масками -

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


Будем называть первую матрицу X,a вторую Y
Для  j от 2 до 9 рассмотрим конкатенации
"X" ->"Y" и  "Y" -> "X"

Первая  :-
X                                     Y
---------------------------           ------------------------------
|                         |           |                            |
---------------------------           ------------------------------ 
j                         |           |                            |   
---------------------------           ------------------------------ 
. . . .                   |           j+1                          | 
---------------------------           ------------------------------
                                      j+2                          |
                                      ------------------------------        
                                      | . . . . .                  |
---------------------------           ------------------------------  
10                        |           10                           |     
---------------------------           ------------------------------ 

Запись {j} из  X с записями {j+1,j+2,. . . 10} из Y
и вторые конкатенации из Y в X :-

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

Запись { j } из Y с записями {j+1,j+2,. . . 10} из X
Мы получим 2*(10-j) кортежей, делающих следуюшую имликацию
ложной ((x[j-1] ≡ y[j-1])) → (x[j] ≡ y[j])

**************************************
Например, при j=3 получаем
**************************************

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 множество :-

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 x 4  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 <=

****************************************************************************
Таким образом при j=3 имеем 2*7 = 14 кортежей где x2≡y2 is True
и  x3≡y3 is False. Тогда (x2 ≡ y2) → (x3 ≡ y3) есть 1 -> 0 ,
что ложно по определению
****************************************************************************

Это означает, для каждого j из набора [2.3.4,...,9]
2*(10 - j) кортежей должно быть удалено из множества решений усеченной
системы системы уравнений. В духе ЕГЭ пишем на паскале


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

72

Таким образом, ответ 10*10 - 72 = 28

Метод отображений для той же задачи

https://www.youtube.com/watch?v=2n0qJ4VSaAQ

   x9y9 даст 28

********************************************************************
Рассмотрим 11 из https://inf-ege.sdamgia.ru/test?theme=264 

*******************************************************************

(¬(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

где ¬ есть логическое отрицание

********************************
Начнем с системы вида :-
********************************

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

Решения этой системы описываются хорошо известными масками -

x1  x2  x3  x4  x5  x6 x 7  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


Будем называть первую матрицу X,a вторую Y
Первая строка из Х конкатенирутся с первой строкой из  Y
¬(x1 ≡ y1) is False (0) =>  ¬(x1 ≡ y1) → ¬(x2 ≡ y2) is True 

Вторая строка из Х конкатенирутся с первой,второй строками из Y
¬(x2 ≡ y2) is False (0) =>  ¬(x2 ≡ y2) → ¬(x3 ≡ y3) is True 

Третья строка из Х конкатенирутся первой,второй,третьей строками из Y
¬(x3 ≡ y3) is False (0) =>  ¬(x3 ≡ y3) → ¬(x4 ≡ y4) is True 
. . . . . 

Восьмая строка из Х конкатенирутся с первой,второй,третьей,...,восьмой строками из Y
¬(x8 ≡ y8) is False (0) =>  ¬(x8 ≡ y8) → ¬(x9 ≡ y9) is True

Всего решений 1+2+3+4+5+6+7+8 = (8*9)/2 = 56/2 = 28 

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

                                              It's hard to know what the right thing is.
                                             Once you know it's hard not to do it.
                                                 Harry Fertig (Kingsley,The Confession film 1999)

In brief, bitmasks are supposed to be a core tool for solution of systems of equations in Boolean variables versus method suggested at several officially
approved sites.

*************************************
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 9 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

********************************************************************
Consider 11 from https://inf-ege.sdamgia.ru/test?theme=264
********************************************************************

(~(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

where ~ is logical negation

********************************
Truncate system above:-
********************************

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

Last system is described by well known masks.

x1  x2  x3  x4  x5  x6 x 7  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


Let us call first matrix X and second matrix Y

Concatenate first raw from X with first raw from Y
~(x1 ≡ y1) is False (0) =>  ~(x1 ≡ y1) → ~(x2 ≡ y2) is True 

Concatenate second raw from X with first and second raws from Y
~(x2 ≡ y2) is False (0) =>  ~(x2 ≡ y2) → ~(x3 ≡ y3) is True 

Concatenate third raw from X with first and second and third raws from Y
~(x3 ≡ y3) is False (0) =>  ~(x3 ≡ y3) → ~(x4 ≡ y4) is True 
. . . . . 

Concate eight's raw from X with first and second and third and .. and eight's raws from Y
~(x8 ≡ y8) is False (0) =>  ~(x8 ≡ y8) → ~(x9 ≡ y9) is True

Total number of corteges solve original system  1+2+3+4+5+6+7+8 = (8*9)/2 = 56/2 = 28