Question

На числовой прямой даны два отрезка: $P = [15; 40]$ и $Q = [21; 63]$ . Укажите наименьшую возможную длину такого отрезка $A$ , для которого логическое выражение

$(x \in P) \to (((x \in Q) \land \neg(x \in A)) \to \neg(x \in P))$

истинно при любом значении переменной $x$ .

$$(x \in P) 	o (((x \in Q) \land 
eg(x \in A)) 	o 
eg(x \in P))$$

истинно при любом значении переменной $x$.

Accepted Answer

19

Answer

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

Обозначим $P \equiv (x \in P)$, $Q \equiv (x \in Q)$, $A \equiv (x \in A)$.

Преобразуем выражение, используя эквивалентность $B 	o C \equiv 
eg B \lor C$:

$$P 	o ((Q \land 
eg A) 	o 
eg P) = 
eg P \lor (
eg(Q \land 
eg A) \lor 
eg P)$$

$$= 
eg P \lor (
eg Q \lor A \lor 
eg P) = 
eg P \lor 
eg Q \lor A$$

Выражение истинно при всех $x$, если оно истинно везде. Это означает:
- либо $x 
otin P$ (т. е. $x \in (-\infty; 15) \cup (40; +\infty)$),
- либо $x 
otin Q$ (т. е. $x \in (-\infty; 21) \cup (63; +\infty)$),
- либо $x \in A$.

Для $x \in P = [15; 40]$ выражение $
eg P$ ложно. Поэтому на этом отрезке должно быть истинно $
eg Q \lor A$.

Пересечение $P \cap Q = [21; 40]$. На этом пересечении $
eg Q$ ложно, значит, должно быть истинно $A$. Следовательно, $A$ должен содержать весь отрезок $[21; 40]$.

Минимальная длина отрезка $A$, содержащего $[21; 40]$, равна $40 - 21 = 19$.

Проверим перебором всех возможных отрезков:

```python
p = list(range(15, 41))
q = list(range(21, 64))
mn = 100

for b in range(15, 64):
    for e in range(15, 64):
        a = list(range(b, e + 1))
        if all([(x in p) <= (((x in q) and (x not in a)) <= 
                (x not in p)) for x in range(1, 100)]):
            mn = min(mn, a[-1] - a[0])

print(mn)
```

Программа перебирает все возможные отрезки $A$ с началом $b$ и концом $e$, проверяет, истинно ли исходное выражение при всех $x$ из диапазона $[1; 99]$, и находит минимальную длину подходящего отрезка.

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