Тип 15 № 34518 
Преобразование логических выражений. Побитовая конъюнкция
i
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 4.
Для какого наибольшего целого числа А формула
х&А
→ (x&36 = 0 → х&6)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?
Решение. Преобразуем выражение по законам алгебры логики:
¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.
Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.
Имеем импликацию Z36Z6 → ZA или Z(36 or 6) → ZA. Запишем числа 36 и 6 в двоичной системе счисления: 3610 = 1001002, 610 = 1102, найдем побитовую дизъюнкцию: 100110. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только первый, второй или пятый биты (как обычно, считая справа налево, начиная с нуля).
Таким образом, наибольшее А = 1001102 = 3810.
Приведём другое решение.
Решим задание с помощью языка программирования PascalABC методом перебора:
var
A, x: integer;
B: boolean;
begin
for A := 63 downto 0 do begin
B := True;
for x := 0 to 63 do
if not (((x and 6) <> 0) or ((x and 36) <> 0) or ((x and A) = 0)) then
B := False;
if B then begin
writeln(A);
break;
end;
end;
end.
Приведём другое решение на языке Python.
for A in range(63,0,-1):
B = True
for x in range(63):
if ((x&A==0) or (x&36!=0) or (x&6!=0))==0:
B=False
if B:
print(A)
break
Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 6 и 36 хватит шести разрядов. Программа выведет ответ 38.
Ответ: 38.
Приведём решение Ильи Андрианова на языке Python.
def F(x, A):
return (x & A != 0) <= ((x & 36 == 0) <= (x & 6 != 0))
for A in range(1000, 0, -1):
if all(F(x, A) for x in range(1, 10000)):
print(A)
break
Ответ: 38
