Question

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

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

$$x \land 17 = 0 	o (x \land 29 
eq 0 	o x \land A 
eq 0)$$

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

Accepted Answer

12

Answer

Идея решения: преобразовать логическое выражение в эквивалентную форму, затем найти минимальное $A$, используя анализ двоичных представлений чисел 17 и 29.

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

Применим законы алгебры логики. Обозначим:
- $X = (x \land 17 = 0)$
- $Y = (x \land 29 
eq 0)$
- $Z = (x \land A 
eq 0)$

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

Преобразуем:
$$X 	o (Y 	o Z) = 
eg X \lor (
eg Y \lor Z) = 
eg X \lor 
eg Y \lor Z$$

Это эквивалентно:
$$X \land Y 	o Z$$

То есть:
$$(x \land 17 = 0) \land (x \land 29 
eq 0) 	o (x \land A 
eq 0)$$

Для истинности при всех $x$ необходимо: если $(x \land 17 = 0)$ и $(x \land 29 
eq 0)$, то $(x \land A 
eq 0)$.

**Анализ двоичных представлений**

Запишем числа в двоичной системе:
- $17_{10} = 10001_2$
- $29_{10} = 11101_2$

Условие $(x \land 17 = 0)$ означает, что в позициях битов числа 17 (позиции 0 и 4) число $x$ имеет нули.

Условие $(x \land 29 
eq 0)$ означает, что $x$ имеет хотя бы один единичный бит в позициях 0, 2, 3 или 4.

Поскольку $(x \land 17 = 0)$ исключает единицы в позициях 0 и 4, остаются позиции 2 и 3. Значит, при выполнении обоих условий $x$ имеет единицу в позиции 2 или 3 (или обе).

Чтобы $(x \land A 
eq 0)$ было истинно для всех таких $x$, число $A$ должно иметь единицы в позициях 2 и 3:
$$A = 01100_2 = 12_{10}$$

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

Программа выведет 12.

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