Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 12&6 = 11002&01102 = 01002 = 4.
Для какого наибольшего целого числа А формула
х&А
→ (x&10 = 0 → х&3)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?
Преобразуем выражение по законам алгебры логики:
¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.
Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.
Имеем импликацию Z10Z3 → ZA или Z(10 or 3) → ZA. Запишем числа 10 и 3 в двоичной системе счисления: 1010 = 10102, 310 = 112, найдем побитовую дизъюнкцию: 1011. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, первый и третий биты (как обычно, считая справа налево, начиная с нуля).
Тем самым, наибольшее А = 10112 = 1110.
Приведём другое решение.
Решим задание с помощью языка программирования PascalABC методом перебора:
var
A, x: integer;
B: boolean;
begin
for A := 0 to 15 do begin
B := True;
for x := 0 to 15 do
if not (((x and 3) <> 0) or ((x and 10) <> 0) or ((x and (15-A)) = 0)) then
B := False;
if B then begin
writeln((15-A));
break;
end;
end;
end.
Приведём аналогичное решение на языке Python.
for A in range(16):
B = True
for x in range(16):
if ((x&(15-A)==0) or (x&10!=0) or (x&3!=0))==0:
B=False
if B:
print(15-A)
break
Заметим, что можно не перебирать числа, большие 15, поскольку для записи чисел 3 и 10 хватит четырёх разрядов. Программа выведет ответ 11.
Ответ: 11.