Question

Помогите пожалуйста , поставлю самый лучший за правильный ответ =))) 1) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение (X & 29≠0)⇒((X & 9=0)⇒(X & A≠0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)? 2) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение ((X & 13≠0)∧(X & 39≠0))⇒((X & A≠0)∧(X & 13≠0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)? 3) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число A, такое что выражение (((X & 13≠0)∨(X & A≠0))⇒(X & 13≠0))∨((X & A≠0)∧(X & 39=0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Answer 1

1) равносильно:
(x&29 =0) +(x&9≠0) + x&A ≠0 =1
рассмотрим, когда сумма двух первые два слагаемых равна 0, 
                а третье слагаемое=1
29=11101   первое слагаемое =0 при    ¬29 =  00 010     + 
9=1001       ----->(=0)                     при        9 =  01 001
                                                                         -----------
                                                                              .. 011  
----------------------------------------------------------------       100  <---- A=100 =4
2) равносильно:
(x&13=0) + (x&39 =0) + (x&A≠0)*(x&13≠0) = 1
рассмотрим, когда сумма двух первых  слагаемых    =0,
          а третье (произведение) =1
13 = 1101    обратное -->  0010 
39= 100111           --->     011000
                                                10
                                   --------------  поразрядное сложение
                                          11010   т.е.  дают 0 двум первым сл.
(x&A≠0) *x&13≠0) =1  ?   
13 =1101  -->  0010
A=        --->            1
 (из первого рассуждения    11010+  
                                                          1
                                                    0010
                                                   --------
                                                  ... 0111  --->  A= 1000 =8
3)равносильно:
(x&13=0) *(x&A=0) +x&13≠0+(x&A≠0)*(x&39=0) =1
рассмотрим, когда первое произведение =0:
13 =1101  ---> обратное-->  0010---> A=2 =10(в 2с/с)
(X&13≠0) можно и не учитывать (пока)
рассмотрим (x&A≠0) * (x&39=0) =1
это будет при А=011000, обратном (39=100111)
складываем оба А:
011000
       10
----------
    11010 = 2^4+2^3+2 = 28   <------- ответ

Answer 2

1. Перепишем выражение в эквивалентном виде: (X & 29 ≠ 0) → ((X & 9 = 0) → (X & A ≠ 0)) Перепишем условие внутри скобок в эквивалентном виде: ¬(X & 9 = 0) ∨ (X & A ≠ 0) Перепишем условие внутри скобок в эквивалентном виде: (X & 9 ≠ 0) → (X & A ≠ 0) Теперь мы можем переписать исходное выражение в следующем виде: ¬(X & 29 ≠ 0) ∨ ((X & 9 ≠ 0) → (X & A ≠ 0)) Таким образом, нам нужно найти такое наименьшее натуральное число A, чтобы это выражение было тождественно истинно. Заметим, что если X & 29 = 0, то условие будет выполнено независимо от значения A. Таким образом, нам нужно рассмотреть только случай X & 29 ≠ 0. При этом X & 9 ≠ 0, так как в противном случае выражение будет истинным независимо от значения A. Поэтому мы можем сократить выражение до: (X & 29 ≠ 0) → (X & A ≠ 0) Теперь заметим, что наименьшее значение A, для которого это выражение будет тождественно истинным, это наименьший общий делитель чисел 29 и 2^k - 1, где k - номер наименьшего бита в числе X, установленного в 1 при условии X & 29 ≠ 0. В данном случае наименьший такой бит соответствует числу 2^1, поэтому нужно найти НОД(29, 2^1 - 1) = НОД(29, 1) = 1. Ответ: A = 1.

2. Аналогично первому пункту, перепишем выражение в эквивалентном виде: (X & 13 ≠ 0) ∧ (X & 39 ≠ 0) → (X & A ≠ 0) ∧ (X & 13 ≠ 0) Перепишем условие внутри скобок в эквивалентном виде: ¬((X & A ≠ 0) ∧ (X & 13 = 0)) Перепишем это условие в эквивалентном виде: (X & A = 0) ∨ (X & 13 ≠ 0) Теперь мы можем переписать исходное выражение в следующем виде: ¬((X & 13 ≠ 0) ∧ (X & 39 ≠ 0)) ∨ ((X & A = 0) ∨ (X & 13 ≠ 0