1) Введём выражение M K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число A, такое что выражение (X A ≠ 0) → ((X 12 = 0) → (...

попробуем раскрыть (x & a != 0) -> ((x & 12 == 0) -> (x & 49 !=0)) (x & a == 0) | ((x & 12 ==0) -> (x & 49 != 0)) (x & a == 0) | (x & 12 == 0) | (x & 49 != 0) 12 это 001100 49 это 110001 x & 12 == 0 истинно при 3ем и 4ом бите равным 0 в x x & 49 != 0 истинно при 1,5 или 6 бите равным 1 в x остались числа, в который 3ий и 4ый бит равны 1, а 1,5,6 равны 0 мы можем записать в 1,5,6 бит в a единички(a=49), и больше нет никаких битов, которые мы можем безболезненно привести в 1

Преобразуем (X & A ≠ 0) → ((X & 12 = 0) → (X & 49 ≠ 0)), избавившись от импликации. Для этого используем замену a→b = ¬a ∨ b Также учтем, что ¬(p=0) = p≠0 Получаем (X & A = 0) ∨((X & 12 ≠ 0) ∨ (X & 49 ≠ 0)) Можно раскрыть скобки (X & A = 0) ∨ (X & 12 ≠ 0) ∨ (X & 49 ≠ 0) 49₁₀ = 110001₂, 12₁₀ = 001100₂, тогда (X & A = 0) ∨ (X & 001100 ≠ 0) ∨ (X & 110001 ≠ 0) Чтобы результат поразрядной конъюнкции был ненулевым, нужно чтобы в обоих операндах совпадали единичные биты хотя бы в одном разряде. В нашем случае есть три члена, связанные по "ИЛИ" и задача - определить, при каком А выражение всегда будет истинным, т.е. даст хотя бы один единичный бит. Понятно, что значение А влияет только на тот случай, когда нули дали и (X & 001100 ≠ 0), и (X & 110001 ≠ 0). Когда же такое возможно? X & 001100 = 0, если Х имеет вид ??00??, где ? - произвольное состояние бита. X & 110001 = 0, если Х имеет вид 00???0. Объединяя эти два случаю получаем, при Х=0000?0 выражение (X & 001100 ≠ 0) ∨ (X & 110001 ≠ 0) даст нули во всех битах. Тогда (X & A = 0) должно дать хотя бы один единичный бит. Получаем 0000?0 & А = 0, следовательно, А может иметь вид ????0?. Тогда максимальное значение А равно 111101₂ = 61₁₀