Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&25 ≠ 0 → (x&9 = 0 → x&А ≠ 0)
тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х)?
Например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&25 ≠ 0 → (x&9 = 0 → x&А ≠ 0)
тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х)?
💡 Пошаговый разбор и решение:
Преобразуем выражение по законам алгебры логики:
¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.
Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте) без дополнительных пояснений.
Имеем импликацию Z9ZA → Z25 или Z(9 or A) → Z25. Запишем число 25 в двоичной системе счисления: 2510 = 110012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 910 = 010012, двоичная запись искомого числа А должна содержать единичный бит в четвертом разряде (как обычно, считая справа налево, начиная с нуля).
Тем самым, наименьшее А = 100002 = 1610.
Приведём другое решение.
Решим задание с помощью языка программирования PascalABC методом перебора:
var
A, x: integer;
B: boolean;
begin
for A := 0 to 31 do begin
B := True;
for x := 0 to 31 do
if not (((x and 25) = 0) or ((x and 9) <> 0) or ((x and A) <> 0)) then
B := False;
if B then begin
writeln(A);
break;
end;
end;
end.
Приведём аналогичное решение на языке Python.
for A in range(32):
B = True
for x in range(32):
if ((x&25==0) or (x&9!=0) or (x&A!=0))==0:
B=False
if B:
print(A)
break
Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 9 хватит пяти разрядов. Программа выведет ответ 16.
Ответ: 16.
¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.
Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте) без дополнительных пояснений.
Имеем импликацию Z9ZA → Z25 или Z(9 or A) → Z25. Запишем число 25 в двоичной системе счисления: 2510 = 110012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 910 = 010012, двоичная запись искомого числа А должна содержать единичный бит в четвертом разряде (как обычно, считая справа налево, начиная с нуля).
Тем самым, наименьшее А = 100002 = 1610.
Приведём другое решение.
Решим задание с помощью языка программирования PascalABC методом перебора:
var
A, x: integer;
B: boolean;
begin
for A := 0 to 31 do begin
B := True;
for x := 0 to 31 do
if not (((x and 25) = 0) or ((x and 9) <> 0) or ((x and A) <> 0)) then
B := False;
if B then begin
writeln(A);
break;
end;
end;
end.
Приведём аналогичное решение на языке Python.
for A in range(32):
B = True
for x in range(32):
if ((x&25==0) or (x&9!=0) or (x&A!=0))==0:
B=False
if B:
print(A)
break
Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 9 хватит пяти разрядов. Программа выведет ответ 16.
Ответ: 16.
Правильный ответ:
16
📚 Похожие разобранные задания по предмету:
ID 31206 • Задание №9
Автомат получает на вход трёхзначное десятичное число. По этому числу строится новое число по следующим правил...
ID 140300 • Задание №2
От разведчика было получено следующее сообщение.
101110011111110101
В этом сообщении зашифрован пароль — по...
🔗 Другие задания линии №15 по предмету Информатика:
ID 32409
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, ...
ID 32410
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 14...
ID 32411
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Например, 14&5 =...
ID 32412
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 12...
ID 32413
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 14...