Решение: Поразрядная конъюнкция и логика
Обозначим через $m \mathbin{\&} n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$. Так, например, $14 \mathbin{\&} 5 = 1110_2 \mathbin{\&} 0101_2 = 0100_2 = 4$. Для какого наименьшего неотрицательного целого числа $A$ формула $((x \mathbin{\&} 42 \ne 0) \land (x \mathbin{\&} 34 = 0)) \to \neg(x \mathbin{\&} A = 0)$ тождественно истинна при любом неотрицательном целом значении переменной $x$?
Решение по шагам
4 шагаПредставим числа $42$ и $34$ в двоичной системе:
$$42 = 101010_2, \qquad 34 = 100010_2$$Условие $x \mathbin{\&} 34 = 0$ означает, что в числе $x$ не могут быть установлены разряды, соответствующие единицам числа $34$: разряды $2^1$ и $2^5$.
Условие $x \mathbin{\&} 42 \ne 0$ требует, чтобы у $x$ был хотя бы один общий установленный разряд с числом $42$. Разряды $2^1$ и $2^5$ запрещены предыдущим условием, поэтому обязательно установлен разряд $2^3$.
Чтобы выражение $x \mathbin{\&} A$ было ненулевым для любого подходящего $x$, число $A$ должно содержать разряд $2^3$. Наименьшее такое число:
$$A = 2^3 = 8$$Где здесь ошибаются
Считать, что достаточно взять число $42$, не исключив разряды, запрещённые условием $x \mathbin{\&} 34 = 0$.
Перепутать номера разрядов при переводе чисел $42$ и $34$ в двоичную систему.
Выбрать $A = 0$, при котором заключение импликации всегда ложно.