Question

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

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

$$((x \& 52 
eq 0) \land (x \& 48 = 0)) 	o 
eg(x \& A = 0)$$

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

Accepted Answer

4

Answer

Идея решения: импликация истинна при всех $x$ тогда и только тогда, когда множество $x$, удовлетворяющих посылке, содержится в множестве $x$, удовлетворяющих заключению; переберём возможные значения $A$ и проверим условие.

Обозначим посылку как $P(x) = (x \& 52 
eq 0) \land (x \& 48 = 0)$ и заключение как $Q(x) = 
eg(x \& A = 0)$, то есть $x \& A 
eq 0$.

Импликация $P(x) 	o Q(x)$ истинна при всех $x$ тогда и только тогда, когда для каждого $x$, где $P(x)$ истинна, также истинна $Q(x)$.

Переберём значения $A$ от 0 до некоторого верхнего предела и для каждого проверим, выполняется ли условие на достаточно большом диапазоне значений $x$:

```python
def f(x, a):
    return ((x & 52 != 0) and (x & 48 == 0)) <= (x & a != 0)

for a in range(1, 1000):
    if all(f(x, a) == 1 for x in range(1, 1000)):
        print(a)
        break
```

Функция `f(x, a)` возвращает 1, если импликация истинна для данных $x$ и $a$ (используется тот факт, что в Python `False` соответствует 0, а `True` соответствует 1, и операция `<=` на булевых значениях эквивалентна импликации).

Цикл ищет наименьшее $a$, при котором импликация истинна для всех $x$ в диапазоне от 1 до 999. Первое найденное значение — искомый ответ.

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