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
No comments:
Post a Comment