Задача к ЕГЭ по информатике на тему «отрезки» №1

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

(x ∈ P ) → (((x ∈ Q )∧¬ (x ∈ A)) → ¬(x ∈ P ))

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

Решение руками

В начале для удобства заменим некоторые выражения:

$x ∈ Q = Q$
$x ∈ P = P$
$x ∈ A = A$

Тогда выражение примет такой вид:

$P =⇒ ((Q ∧ ¬A ) =⇒ ¬P)$

Заменим импликацию на отрицание первого или второе. Выражение будет выглядеть следующим образом:

$¬P ∨ (¬(Q ∧¬A )∨ ¬P )$

Раскроем отрицание в скобке. Теперь выражение имеет такой вид:

$¬P ∨ (¬Q ∨ A ∨¬P )$

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

$¬P ∨ ¬Q ∨ A$

Как можем заметить, нам нужно найти значения x когда выражение равно истине, при этом только А должна равняться единице, а все остальные – 0. Не P и Не Q будут равны 0, когда х будут находиться в пределах отрезков P и Q. Получается, нас интересует отрезок, который находится как в отрезке P,так и в отрезке Q. Это отрезок: $[66;100]$ . Ответ:34.

Решение программой

p = [i for i in range(55, 101)] # задаем отрезок p
q = [i for i in range(66, 130)] # задаем отрезок q
mn = 10**10
for a1 in range(1, 200): # перебираем начало отрезка а
    for a2 in range(a1 + 1, 201): # перебираем конец отрезка а
        c = 0 # флаг, который будет показывать при всех ли х для текущего отрезка а выражение было истинным
        a = [i for i in range(a1, a2)] # формируем отрезок а
        for x in range(1, 500): # перебираем значения x
            # если при текущем x - выражение ложно
            if ((x in p) <= (((x in q) and (x not in a)) <= (x not in p))) == False:
                c = 1 # меняем значение флага
                # и сбрасываем цикл, переходим к следующему отрезку а,
                # так как для данного отрезка а выражение не тождественно истинно
                break
        if c == 0: # если значение флага не менялось, значит, при любом х при данном отрезке а выражение было истинным
            mn = min(len(a)-1,mn) # вычисляем минимальную длину отрезка
print(mn)

Ответ: 34