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

Просмотров 7 Комментарии 0

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

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

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

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

Преобразуем данное выражение по законам де Моргана:

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

(x ∈ A)∨ (¬(x ∈ P )∨¬ (x ∈ Q))

(x ∈ A)∨ (x ∕∈ P )∨(x ∕∈ Q)

Найдем случаи, когда выражение ложно. Для этого сделаем отрицание известной части и посмотрим, где оно дает истину:

(x ∈ P) ∧(x ∈ Q )

Отсюда следует, что инверсия дает истину когда $x$ принадлежит одновременно и $P$ , и $Q$ . То есть, в этих ситуациях исходное выражение ложно, значит нужно подобрать такой отрезок $A$ , чтобы «перекрыть» эту часть. Это будет отрезок [39; 19]. Значит, наименьшая длина $A = 39− 19 = 20$ .

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

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

Ответ: 20