Question

Даю 23 балла Пусть M&K — выражение, обозначающее поразрядную конъюнкцию чисел M и K (логическое «И» между соответствующими битами двоичной записи). Определите такое наименьшее натуральное число A, что выражение: ((X&68 ≠ 0) → (X&36 = 0)) → (X&A = 0) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Answer 1

Для решения данной задачи мы будем использовать таблицу истинности.

Выражение ((X&68 ≠ 0) → (X&36 = 0)) → (X&A = 0) является импликацией, поэтому будем рассматривать его в обратном порядке.

Таблица истинности для выражения (X&A = 0) выглядит следующим образом:

| X | A | X&A | X&A = 0 | |---|---|-----|---------| | 0 | 0 | 0 | 1 | | 0 | 1 | 0 | 1 | | 1 | 0 | 0 | 1 | | 1 | 1 | 1 | 0 |

Теперь рассмотрим выражение (X&36 = 0):

| X | X&36 | X&36 = 0 | |---|------|----------| | 0 | 0 | 1 | | 1 | 0 | 1 |

И наконец, выражение (X&68 ≠ 0):

| X | X&68 | X&68 ≠ 0 | |---|------|----------| | 0 | 0 | 0 | | 1 | 0 | 0 |

Теперь объединим все таблицы истинности:

| X | X&68 ≠ 0 | X&36 = 0 | X&A = 0 | (X&36 = 0) → (X&A = 0) | ((X&68 ≠ 0) → (X&36 = 0)) → (X&A = 0) | |---|----------|----------|---------|-----------------------|-----------------------------------| | 0 | 0 | 1 | 1 | 1 | 1 | | 1 | 0 | 1 | 0 | 0 | 1 |

Из таблицы истинности видно, что выражение ((X&68 ≠ 0) → (X&36 = 0)) → (X&A = 0) будет тождественно истинно только в том случае, когда X&36 = 0 всегда, независимо от значения X.

Таким образом, наименьшее натуральное число A будет равно 36.