Решение. Преобразуем выражение по законам алгебры логики:
Х + (Y → Z) = Х + (¬Y + Z) = Х + Z + ¬Y = Y → (X + Z) = (Y → X) + (Y → Z).
Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.
Заметим, что первое слагаемое логической суммы является импликацией Z41 → Z51, которая не является истинной для всех х (см. ниже). Тогда необходимо и достаточно, чтобы второе слагаемое логической суммы было тождественно истинным.
Действительно, например, для х = 2 поразрядная конъюнкция с числом 41 дает 0, а с числом 51 дает 2. Поэтому импликация (2&41) → (2&51) принимает вид 1 → 0 — ложь.
2: 000010
41: 101001
2&41: 000000, то есть 2&41 = 0. Высказывание 2&41 = 0 истинно.
2: 000010
51: 110011
2&51: 000010 = 2, то есть 2&51 = 2. Высказывание 2&51 = 0 ложно.
Итак, импликация Z41 → ZA должна быть тождественно истинной. Запишем число 41 в двоичной системе счисления: 4110 = 1010012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, третий и пятый биты (как обычно, считая справа налево, начиная с нуля).
Таким образом, наибольшее А = 1010012 = 4110.
Ответ: 41.
Примечание.
Ответ 45 не подходит. Пусть A = 45, а x = 2210 = 101102, тогда:
51: 1100112
22: 0101102
51&22: 0100102, то есть высказывание 22&51 = 0 ложно;
41: 1010012
22: 0101102
41&22: 0000002, то есть высказывание 22&41 ≠ 0 ложно;
45: 1011012
22: 0101102
51&22: 0001002, то есть высказывание 22&45 = 0 ложно.
Следовательно, при x = 22 и A = 45 логическое выражение ложно.
Приведем другое решение.
Выражение x&51 = 0 ∨ (x&41 = 0 → x&А = 0) должно быть истинным для любого х. Возьмем такое х, в котором установлены все биты, кроме тех, которые установлены в числе 41, например, для однобайтового представления х = 110101102.
Выражение x&51 = 0 будет ложно, поскольку и в числе х, и в числе 51 установлен первый бит (биты считаем справа налево, начиная с нуля).
Следовательно, истинной должна быть импликация во второй скобке. Но левая часть импликации x&41 = 0 истинна, поскольку ни один из битов, установленных в числе 41, в числе х не установлен.
Тогда истинной должна быть и правая часть импликации x&А = 0. Следовательно, в числе А могут быть установлены только те биты, которые не установлены в числе х, то есть нулевой, третий и пятый биты. Таким образом, наибольшее А = 1010012 = 4110.
При таком А левая и правая части импликации одинаковы. Следовательно, импликация в правой скобке истинна, а значит, истинно и все выражение.
Приведём другое решение.
Решим задание с помощью языка программирования PascalABC методом перебора:
var
A, x: integer;
B: boolean;
begin
for A := 0 to 63 do begin
B := True;
for x := 0 to 63 do
if not (((x and 51) = 0) or ((x and 41) <> 0) or ((x and (63-A)) = 0)) then
B := False;
if B then begin
writeln((63-A));
break;
end;
end;
end.
Приведём другое решение на языке Python.
for A in range(64):
B = True
for x in range(64):
if ((x&51==0) or (x&41!=0) or (x&(63-A)==0))==0:
B=False
if B:
print(63-A)
break
Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 41 и 51 хватит шести разрядов. Программа выведет ответ 41.
Ответ: 41.
Приведём другое решение на языке Python.
for a in range(100, 0, -1):
k = 0
for x in range(100, 0, -1):
if (x & 51 == 0) or (not(x & 41 == 0) or (x & a == 0)):
k += 1
if k == 100:
print(a)
break
Приведём решение Ильи Андрианова на языке Python.
def F(x, A):
return (x&51 == 0) or ((x&41 == 0) <= (x&A == 0))
R = []
for A in range(0, 10_000):
if all(F(x, A) for x in range(0, 10_000)):
R.append(A)
print(max(R))
→ (x&10 = 0 → х&3