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.
