Question

Обозначим через $m \& n$ поразрядную конъюнкцию (побитовое И) неотрицательных целых чисел $m$ и $n$. Например, $14 \& 5 = 1110_2 \& 0101_2 = 0100_2 = 4$.

Для какого наименьшего неотрицательного целого числа $A$ формула

$$x \& 25 
eq 0 	o (x \& 17 = 0 	o x \& A 
eq 0)$$

тождественно истинна (принимает значение 1 при любом неотрицательном целом значении переменной $x$)?

Accepted Answer

8

Answer

Идея решения: преобразовать логическое выражение в эквивалентную импликацию между множествами битов, затем найти минимальное число, удовлетворяющее условию.

**Преобразование формулы**

Обозначим:
- $X = (x \& 25 
eq 0)$
- $Y = (x \& 17 = 0)$
- $Z = (x \& A 
eq 0)$

Исходная формула: $X 	o (Y 	o Z)$.

По законам логики: $X 	o (Y 	o Z) \equiv 
eg X \lor (
eg Y \lor Z) \equiv 
eg X \lor 
eg Y \lor Z \equiv (X \land Y) 	o Z$.

Таким образом, условие эквивалентно: $(x \& 25 
eq 0) \land (x \& 17 = 0) 	o (x \& A 
eq 0)$.

**Анализ в терминах битов**

Импликация истинна для всех $x$ тогда и только тогда, когда множество значений $x$, удовлетворяющих левой части, содержится в множестве значений, удовлетворяющих правой части.

Левая часть: $x \& 25 
eq 0$ и $x \& 17 = 0$.
- $25 = 11001_2$ — в $x$ должны быть единицы на позициях 0, 3, 4.
- $17 = 10001_2$ — в $x$ не должны быть единицы одновременно на позициях 0 и 4.

Пересечение этих условий: $x$ имеет единицы на позициях из $\{0, 3, 4\}$, но не на позициях из $\{0, 4\}$ одновременно. Это означает, что $x$ должен иметь единицу на позиции 3 (бит с весом $2^3 = 8$).

Правая часть: $x \& A 
eq 0$ — в $x$ должна быть хотя бы одна единица на позициях, где единица в $A$.

Для истинности импликации: каждое $x$, имеющее единицу на позиции 3, должно иметь единицу на позиции, где единица в $A$. Минимальное $A$ — это число с единицей только на позиции 3.

$$A = 1000_2 = 8_{10}$$

```python
for A in range(32):
    valid = True
    for x in range(32):
        if (x & 25 != 0) and (x & 17 == 0) and (x & A == 0):
            valid = False
            break
    if valid:
        print(A)
        break
```

Программа проверяет все значения $A$ от 0 до 31 и для каждого проверяет, что не существует $x$, нарушающего формулу. Первое подходящее значение — 8.

Задание №15Математическая логикаЕГЭ по информатике