First what we would have to use comes from Polyakov's ege18.doc
Sample as is
See Решение задания ЕГЭ - 18 с битовыми операциями
(x&26 ¬=10 ) = ¬Z(16) + Z(8) + Z(2)
(x&27 = 11 ) = Z(16)*¬Z(8)*¬Z(2)*¬Z(1)
26 = 11010
10 = 01010
27 = 11011
11 = 01011
Due to
¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
A + ¬A*B = (A + ¬A)*(A + B) = A + B
After applying conversions mentioned above
We are going to obtain via Polyakov's formulas :-
¬Z(16) + Z(8) + Z(2) + Z(16)*¬Z(8)*¬Z(2)*¬Z(1) + A = 1
¬Z(16) + Z(8) + Z(2) + ¬Z(1) + A = 1
¬(Z(16)*Z(1)) + Z(8) + Z(2) + A = 1
Z(16 OR 1) => Z(8) + Z(2) + A = 1
(Z(17)=> A) + (Z(17)=>Z(8)) + (Z(17)=>Z(2)) = 1
Z(17) => A = 1
Thus A(max) = 17
So issue when "b1-c1=b2-c2" might be resolved via Bitwise2 technique and Problem 5 gets resolved without any new development efforts.
Also notice that in general (b-c) doesn't have to be a basic predicate. Sample bellow has (b-c) = 96. But the multitude of "c" bits "1" must be included in the multitude of "b" bits "1"
********************
Another samples
********************
Here we sequentially apply
¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
A + ¬A*B = (A + ¬A)*(A + B) = A + B
***************************************************
(x&248 ¬= 152) v (x&252 = 156) v (x&A = 0) = 1
***************************************************
252 = 11111100
156 = 10011100
248 = 11111000
152 = 10011000
(x&248 ¬= 152) = ¬Z(96) + Z(128) + Z(16) + Z(8)
(x&252 = 156) = Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
¬Z(96) + Z(128) + Z(16) + Z(8) +
Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4) + A = 1
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4) + A = 1
¬(Z(96)*Z(4)) + Z(128) + Z(16) + Z(8) + A = 1
Z(100) => Z(128) + Z(16) + Z(8) + A = 1
(Z(100)=>Z(128)) + (Z(100)=>Z(16)) + (Z(100)=>Z(8)) +
(Z(100)=>A) = 1
Z(100) => A = 1
Thus A(max) = 100
****************************************************************
(x&248 ¬= 152)v(x&252 = 156)v(x&250 = 154)v(x&A = 0) = 1
****************************************************************
252 = 11111100
156 = 10011100
248 = 11111000
152 = 10011000
250 = 11111010
154 = 10011010
(x&248 ¬= 152) = ¬Z(96) + Z(128) + Z(16) + Z(8)
(x&252 = 156) = Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
(x&250 = 154) = Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2)
¬Z(96) + Z(128) + Z(16) + Z(8) + Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
+ Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) + A = 1
Converting Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4) and get
¬Z(96) + Z(128) + Z(16) + Z(8) entries like before run (1)
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4)
+ Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) + A = 1
Converting Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) and get
¬Z(96) + Z(128) + Z(16) + Z(8) entries like before run (2)
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4) + ¬Z(2) + A = 1
Now we are ready to apply De Morgan rules :-
¬(Z(96)*Z(4)*Z(2)) + Z(128) + Z(16) + Z(8) + A = 1
Finally getting done
Z(102) => Z(128) + Z(16) + Z(8) + A = 1
(Z(102)=>Z(128)) + (Z(102)=>Z(16)) + (Z(102)=>Z(8)) + (Z(102)=>A) = 1
Z(102) => A = 1
Thus A(max) = 102
*****************************************************
(x&252 ¬= 188) v (x&248 = 184) v (x&A = 0) = 1
*****************************************************
252 = 11111100
188 = 10111100
248 = 11111000
184 = 10111000
Here we sequentially apply
¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
A + ¬A*B = (A + ¬A)*(A + B) = A + B
(x&252 ¬= 184) = ¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8)
(x&248 = 188) = Z(64)*¬Z(128)*¬Z(32)*¬Z(16)*¬Z(8)*¬Z(4)
¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8) +
Z(64)*¬Z(128)*¬Z(32)*¬Z(16)*¬Z(8)*¬Z(4) + A = 1
¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8) + ¬Z(4) + A = 1
¬(Z(64)*Z(4)) + Z(128) + Z(32) + Z(16) + Z(8) + A = 1
Z(68) => + Z(128) + Z(32) + Z(16) + Z(8) + A = 1
(Z(68)=>Z(128)) + (Z(68)=>Z(32)) + (Z(68)=>Z(16)) +
(Z(68)=>Z(8)) + (Z(68)=>A) = 1
Z(68) => A = 1
Thus A(max) = 68
Sample as is
See Решение задания ЕГЭ - 18 с битовыми операциями
(x&26 ¬=10 ) = ¬Z(16) + Z(8) + Z(2)
(x&27 = 11 ) = Z(16)*¬Z(8)*¬Z(2)*¬Z(1)
26 = 11010
10 = 01010
27 = 11011
11 = 01011
Due to
¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
A + ¬A*B = (A + ¬A)*(A + B) = A + B
After applying conversions mentioned above
We are going to obtain via Polyakov's formulas :-
¬Z(16) + Z(8) + Z(2) + Z(16)*¬Z(8)*¬Z(2)*¬Z(1) + A = 1
¬Z(16) + Z(8) + Z(2) + ¬Z(1) + A = 1
¬(Z(16)*Z(1)) + Z(8) + Z(2) + A = 1
Z(16 OR 1) => Z(8) + Z(2) + A = 1
(Z(17)=> A) + (Z(17)=>Z(8)) + (Z(17)=>Z(2)) = 1
Z(17) => A = 1
Thus A(max) = 17
So issue when "b1-c1=b2-c2" might be resolved via Bitwise2 technique and Problem 5 gets resolved without any new development efforts.
Also notice that in general (b-c) doesn't have to be a basic predicate. Sample bellow has (b-c) = 96. But the multitude of "c" bits "1" must be included in the multitude of "b" bits "1"
********************
Another samples
********************
Here we sequentially apply
¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
A + ¬A*B = (A + ¬A)*(A + B) = A + B
***************************************************
(x&248 ¬= 152) v (x&252 = 156) v (x&A = 0) = 1
***************************************************
252 = 11111100
156 = 10011100
248 = 11111000
152 = 10011000
(x&248 ¬= 152) = ¬Z(96) + Z(128) + Z(16) + Z(8)
(x&252 = 156) = Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
¬Z(96) + Z(128) + Z(16) + Z(8) +
Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4) + A = 1
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4) + A = 1
¬(Z(96)*Z(4)) + Z(128) + Z(16) + Z(8) + A = 1
Z(100) => Z(128) + Z(16) + Z(8) + A = 1
(Z(100)=>Z(128)) + (Z(100)=>Z(16)) + (Z(100)=>Z(8)) +
(Z(100)=>A) = 1
Z(100) => A = 1
Thus A(max) = 100
****************************************************************
(x&248 ¬= 152)v(x&252 = 156)v(x&250 = 154)v(x&A = 0) = 1
****************************************************************
252 = 11111100
156 = 10011100
248 = 11111000
152 = 10011000
250 = 11111010
154 = 10011010
(x&248 ¬= 152) = ¬Z(96) + Z(128) + Z(16) + Z(8)
(x&252 = 156) = Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
(x&250 = 154) = Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2)
¬Z(96) + Z(128) + Z(16) + Z(8) + Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4)
+ Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) + A = 1
Converting Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(4) and get
¬Z(96) + Z(128) + Z(16) + Z(8) entries like before run (1)
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4)
+ Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) + A = 1
Converting Z(96)*¬Z(128)*¬Z(16)*¬Z(8)*¬Z(2) and get
¬Z(96) + Z(128) + Z(16) + Z(8) entries like before run (2)
¬Z(96) + Z(128) + Z(16) + Z(8) + ¬Z(4) + ¬Z(2) + A = 1
Now we are ready to apply De Morgan rules :-
¬(Z(96)*Z(4)*Z(2)) + Z(128) + Z(16) + Z(8) + A = 1
Finally getting done
Z(102) => Z(128) + Z(16) + Z(8) + A = 1
(Z(102)=>Z(128)) + (Z(102)=>Z(16)) + (Z(102)=>Z(8)) + (Z(102)=>A) = 1
Z(102) => A = 1
Thus A(max) = 102
*****************************************************
(x&252 ¬= 188) v (x&248 = 184) v (x&A = 0) = 1
*****************************************************
252 = 11111100
188 = 10111100
248 = 11111000
184 = 10111000
Here we sequentially apply
¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B
A + ¬A*B = (A + ¬A)*(A + B) = A + B
(x&252 ¬= 184) = ¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8)
(x&248 = 188) = Z(64)*¬Z(128)*¬Z(32)*¬Z(16)*¬Z(8)*¬Z(4)
¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8) +
Z(64)*¬Z(128)*¬Z(32)*¬Z(16)*¬Z(8)*¬Z(4) + A = 1
¬Z(64) + Z(128) + Z(32) + Z(16) + Z(8) + ¬Z(4) + A = 1
¬(Z(64)*Z(4)) + Z(128) + Z(32) + Z(16) + Z(8) + A = 1
Z(68) => + Z(128) + Z(32) + Z(16) + Z(8) + A = 1
(Z(68)=>Z(128)) + (Z(68)=>Z(32)) + (Z(68)=>Z(16)) +
(Z(68)=>Z(8)) + (Z(68)=>A) = 1
Z(68) => A = 1
Thus A(max) = 68



No comments:
Post a Comment