У меня не было возможности проверить ответы, поэтому
любые замечания относительно предлагаемых решений
" are welcome ". Оригинальные формулировки без изменений.
Case 1 (209,210)
Преобразование уравнения в стиль алгебры Z (k): -
(Z(17) +A + ¬Z(58)) => Z(8)(¬A)Z(58) = 0
¬(Z(17) +A + ¬Z(58)) v Z(8)(¬A)Z(58) = 0
Теперь отрицаем выражения в обеих частях уравнения
(Z(17) +A + ¬Z(58)) ^(¬Z(8) +A + ¬Z(58)) = 1
Получаем систему :-
(Z(58) => A ) + (Z(58) => Z(17)) =1
Z(58 or 8) => A
58 = 111010
v
8 = 001000
---------------------------
58 = 111010
Z(58) => A(max) = 58
58 = 111010
=============================
A(min)[43,55] = 110000 (binary) = 48
A(max)[43,55] = 110010 (bnary) = 50
51 = 110011
52 = 110100
53 = 110101
54 = 110110
55 = 110111
Все 5 имеют единичные биты, не входящие в 58 = 111010
Case 1 (211)
(С.С. Поляков,Саратов) Определите количество натуральных чисел A таких, что выражение
((x & 17 != 0 )=>((x & A != 0)=>(x & 58 !=0)))=>((x & 8 = 0 )^(x & A != 0)^(x & 58 = 0))
тождественно ложно (то есть принимает значение 0 при любом натуральном значении переменной x)?
Решение
Преобразование уравнения в стиль алгебры Z (k):
(Z(17) +A + ¬Z(58)) => Z(8)(¬A)Z(58) = 0
¬(Z(17) +A + ¬Z(58)) v Z(8)(¬A)Z(58) = 0
Теперь отрицаем выражения в обеих частях уравнения.
Вопрос теперь - при каких А уравнение тождестнно истинно ?
(Z(17) +A + ¬Z(58)) ^(¬Z(8) +A + ¬Z(58)) = 1
Получаем систему :
Z(58) => A + Z(17)= 1 (1)
¬((Z(58)Z(8)) +A = 1 (2)
Окончательно система принимает вид :-
(Z(58) => A ) + (Z(58) => Z(17)) =1 (1)
Z(58 or 8) => A (2)
Z(58) => Z(17) = False 58 двоичное
заканчивается на 0 , 17 двоичное на 1
58 = 111010
v
8 = 001000
---------------------------
58 = 111010
Z(58) => A(max) = 1
58 = 111010
============
Множество Х чисел (в порядке возрастания) множества
единичных бит,которых входят в множество единичных
бит числа 58 = 111010. Для любого A ∈ Х : Z(58) => A
и соответсвенно :-
(Z(17) +A + ¬Z(58)) ^(¬Z(8) +A + ¬Z(58)) = 1
10 = 2
1000 = 8
1010 = 10
10000 = 16
10010 = 18
11000 = 24
11010 = 26
100000 = 32
100010 = 34
101000 = 40
101010 = 42
110000 = 48
110010 = 50
111000 = 56
111010 = 58
Answer = {2,8,10,16,18,24,26,32,34,40,42,48,50,56,58}
Case 1 (209,210) есть частный случай этой задачи
Case 2 (212)
Преобразование уравнения в стиль алгебры Z (k): -
(( ¬Z(56) => ¬Z(18)) v ¬A) => (Z(18)A(¬Z(43)) = 0
((Z(56) v ¬Z(18)) v ¬A) => (Z(18)A(¬Z(43)) = 0
¬((Z(56) v ¬Z(18)) v ¬A) v (Z(18)A(¬Z(43)) = 0
¬(Z(56) v ¬Z(18) v ¬A) v (Z(18)A(¬Z(43)) = 0
Теперь отрицаем выражения в обеих частях уравнения
(Z(56) + ¬Z(18) + ¬A)^(¬Z(18) + ¬A + Z(43)) =1
Получаем систему :-
AZ(18) => Z(56) = 1 -> A(min) =40
AZ(18) => Z(43) = 1 -> A(min) =41
В 18 отсутствует выделенные биты из 56, поэтому добавляем
эти биты в в бинарное представление А чтобы сделать импликацию
истинной
56 = 111000
18 = 010010
------------------------
40 = 101000
В 18 отсутствует выделенные биты из 43, поэтому добавляем
эти биты в в бинарное представление А чтобы сделать импликацию
истинной
43 = 101011
18 = 010010
----------------------
41 = 101001 interval [44,62]
A(min) = 101001 = 41
===============
44 = 101010
45 = 101011 - 1
46 = 101110
47 = 101111 - 2
48 = 110000
.....................
56 = 111000
57 = 111001 - 3
58 = 111010
59 = 111011 - 4
60 = 111100
61 = 111101 - 5
62 = 111110
Answer is 5
Case 3 (217)
¬Z(56)^¬Z(43) => ¬A = 1
Z(56) + Z(43) + ¬A = 1
A => Z(56) + Z(43) = 1
(A => Z(56))+(A=>Z(43))= 1
43 = 0101011 (binary )
75= 1001011 (binary )
В 75 отсутствует бит № 6, считая справа налево
начиная с номера бит 0
A(min) из [75,125] есть 1101011 =107
Case 4 (215)
Преобразование уравнения в стиль алгебры Z (k): -
¬Z(56)^¬Z(43) => ¬A = 1
Z(56) + Z(43) + ¬A = 1
A => Z(56) + Z(43) = 1
(A =>Z(43)) +(A=>Z(56)) =1
43 = 0101011 (binary )
43 = 0101011
56 = 0111000
80 = 1010000
1 107=01101011
2 111=01101111
3 123=01111011
4 171=10101011
5 175=10101111
6 191=10111111
7 120 =01111000
8 121 =01111001
9 123 =01111011
10 127 =01111111
11 184 =10111000
12 185 =10111001
13 187 =10111011
Duplicate 191 =10111111
Case 5 (216)
Преобразование уравнения в стиль алгебры Z (k): -
¬Z(56)^¬Z(43) => ¬A = 1
Z(56) + Z(43) + ¬A = 1
A => Z(56) + Z(43) = 1
(A => Z(43)) +(A=> Z(56)) = 1
200 = 11001000
43 = 00101011
235 = 11101011
AMR200(min) = 11101011 = 235
Ответ : 235
Case 6 (205)
Конвертируем исходное уравнение в стиль алгебры Z(k) :-
A => ( ¬Z(31) => ¬Z(35)) = 1
¬A + Z(31) + ¬Z(35) =1
¬(A*Z(35)) + Z(31) = 1
(A*Z(35)) => Z(31) = 1
31 = 011111
=========
35 = 100011 <= нулевой и первый бит защищены
50 = 110010
A(min) (more then 50) = 111100 =
=2^5 + 2^4 + 2^3 +2^2 =32 + 16 +8 +2=60
A(max)=(less then 120)=1011100=92
Case 7 (189)
Конвертируем исходное уравнение в стиль алгебры Z(k) :-
Используем A1 + (B1 & C1) = (A1 + B1) & (A1 + C1) ==>
(¬Z(51) => ¬A) + ¬(¬(Z(11) + ¬A) = 1
(Z(51) + ¬A) + Z(11)&A = 1
(Z(51) +( ¬A + Z(11)&A) = 1 <==
Z(51) + (( ¬A + Z(11))&( ¬A + A) =1
Z(51) + ¬A + Z(11) = 1
¬A + Z(51)+Z(11) =1
A => Z(51) + Z(11) =1
(A=>11) + (A=>51) =1
A => Z(11) =1
A(min) =11
Case 8 (208)
(¬A => ¬Z(62)) => (Z(24)^(¬A)) = 0
(A
((¬A)^Z(62)) + (Z(24)^(¬A)) = 0
¬((¬A)^Z(62))^¬(Z(24)^(¬A)) =1
(A + ¬Z(62))^(A
Z(62) => A (1)
Z(24) => A (2)
62=111110 (binary)
&
24=011000 (binary)
A(min)=01000 = 8 (decimal)
Case 9 (207)
(Z(7) + A + ¬Z(54)) => (Z(27)^¬A^¬Z(7)) = 0
¬(Z(7) + A + ¬Z(54)) + (Z(27)^¬A^¬Z(7)) = 0
¬¬(Z(7) + A + ¬Z(54))^¬(Z(27)^¬A^¬Z(7)) = 1
(Z(7) + A + ¬Z(54))^(¬Z(27) + A + Z(7)) = 1
System 1
Z(54) => A + Z(7) (1)
Z(27) => A + Z(7) (2)
System 2
(Z(54) => A) + (Z(54) => Z(7)) = 1
(Z(27) => A) + (Z(27) => Z(7)) = 1
54 = 110110 (binary)
27 = 011011 (binary)
7 = 000111 (binary)
Z(54) => Z(7) = False
Z(27) => Z(7) = False
System 3
Z(54) => A (1)
Z(27) => A (2)
54 = 110110 (binary)
&
27 = 011011 (binary)
====================
A = 010010 (binary) = 18 (decimal)
Actually, when A=2=10 (binary). Second bit "1" belongs
both 54 = 110110 and 27 = 011011.
So, A(min) = 2
References
1. http://kpolyakov.spb.ru/download/bitwise2.pdf
No comments:
Post a Comment