Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&33 = 0 → (x&45≠0 → x&А ≠ 0)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Преобразуем выражение по законам алгебры логики:
Х → (¬Y → ¬Z) = ¬Х + (¬Y → ¬Z) = ¬Х + Y + ¬Z = Y + ¬(XZ) = XZ → Y.
Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте) без дополнительных пояснений.
Имеем импликацию Z33ZA → Z45 или Z(33 or A) → Z45. Запишем число 45 в двоичной системе счисления: 4510 = 1011012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 3310 = 1000012, двоичная запись искомого числа А должна содержать единичные биты во втором и третьем разрядах (как обычно, считая справа налево, начиная с нуля).
Тем самым, наименьшее А = 0011002 = 1210.
Приведём другое решение.
Решим задание с помощью языка программирования 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 33) <> 0) or ((x and 45) = 0) or ((x and A) <> 0)) then
B := False;
if B then begin
writeln(A);
break;
end;
end;
end.
Приведём аналогичное решение на языке Python.
for A in range(64):
B = True
for x in range(64):
if ((x&33!=0) or (x&45==0) or (x&A!=0))==0:
B=False
if B:
print(A)
break
Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 33 и 45 хватит шести разрядов. Программа выведет ответ 12.
Ответ: 12.