Question

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

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

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

Accepted Answer

21

Answer

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

Раскроем импликацию дважды. Напомним, что $A 	o B \equiv 
eg A \lor B$:

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

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

$$\equiv 
eg(x \in P) \lor (
eg((x \in Q) \land 
eg(x \in A)) \lor 
eg(x \in P))$$

Применим закон де Моргана к $
eg((x \in Q) \land 
eg(x \in A))$:

$$\equiv 
eg(x \in P) \lor (
eg(x \in Q) \lor (x \in A) \lor 
eg(x \in P))$$

$$\equiv 
eg(x \in P) \lor 
eg(x \in Q) \lor (x \in A)$$

Для того чтобы это выражение было истинно при всех $x$, нужно, чтобы для каждого $x$ выполнялось хотя бы одно из трёх условий:
- $x 
otin P$, или
- $x 
otin Q$, или  
- $x \in A$.

Это означает: если $x \in P$ и $x \in Q$ одновременно, то обязательно $x \in A$.

Найдём пересечение отрезков $P$ и $Q$:
- $P = [130; 171]$
- $Q = [150; 185]$
- $P \cap Q = [150; 171]$

Следовательно, отрезок $A$ должен содержать весь отрезок $[150; 171]$.

Длина отрезка $[150; 171]$ равна $171 - 150 = 21$.

Проверим с помощью перебора:

```python
min_length = float('inf')

for a_min in range(1, 200):
    for a_max in range(a_min + 1, 200):
        valid = True
        for x in range(-300, 300):
            p = 130 <= x <= 171
            q = 150 <= x <= 185
            a = a_min <= x <= a_max
            
            formula = (not p) or (not (q and not a)) or (not p)
            
            if not formula:
                valid = False
                break
        
        if valid:
            min_length = min(min_length, a_max - a_min)

print(min_length)
```

Программа перебирает все возможные отрезки $A$ и проверяет, при каких значениях формула истинна для всех $x$. Минимальная длина получается равной 21.

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