Тип 15 № 34516 
Раздел кодификатора ФИПИ: Преобразование логических выражений. Побитовая конъюнкция
i
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?
Решение. Преобразуем выражение по законам алгебры логики:
(¬Х + ¬Y) → (W → ¬Z) = ¬(¬Х + ¬Y) + (¬W + ¬Z) = ХY + ¬(WZ) = WZ → XY.
Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.
Имеем импликацию Z48ZA → Z28Z45 или Z(48 or А) → Z(28 or 45). Поскольку 2810 = 111002, 4510 = 1011012, для побитовой дизъюнкции имеем: 28or45 = 111101. Тогда Z(48 or А) = Z61.
Импликация принимает вид Z(48 or A) → Z61. Единичные биты двоичной записи числа 61 должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 48orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 48, А и 61 в двоичной системе счисления и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:
48: 110000
A: ??1101
61: 111101
В записи наименьшего числа, дающего при поразрядной дизъюнкции с числом 48 единицы в необходимых разрядах, на месте знаков ? должны стоять нули. Таким образом, искомым числом является А = 11012 = 1310.
Приведём другое решение.
Решим задание с помощью языка программирования 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 28) = 0) and ((x and 45) = 0) or ((x and 48) <> 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&28==0) and (x&45==0) or (x&48!=0) or (x&A!=0))==0:
B=False
if B:
print(A)
break
Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 28, 45 и 48 хватит шести разрядов. Программа выведет ответ 13.
Ответ: 13.
Ответ: 13
