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

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

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

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

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

Рассмотрим данное логическое выражение и применим законы де Моргана для его преобразования:

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

Сначала преобразуем импликацию:

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

Затем упрощаем выражение:

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

Это выражение говорит нам о том, что хотя бы одно из следующих условий должно быть истинным:

1. $x$ принадлежит множеству $A$ .

2. $x$ не принадлежит множеству $Q$ .

3. $x$ принадлежит множеству $P$ .

Таким образом, если хотя бы одно из этих условий выполняется, всё выражение будет истинным.

Теперь наша задача состоит в том, чтобы выбрать множество $A$ , которое будет перекрывать область отрезка $Q$ , исключая элементы из $P$ . Это означает, что нам нужно покрыть все значения, которые могут находиться в интервале $(52;71]$ .

Следовательно, минимальная длина множества $A$ должна составлять:

A = 71− 52 = 19

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

p = [i for i in range(21, 53)] # задаем отрезок p
q = [i for i in range(33, 73)] # задаем отрезок q
mn = 10**10
for a1 in range(1, 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 q) <= (x in p))) == False:
                c = 1 # меняем значение флага
                # и сбрасываем цикл, переходим к следующему отрезку а,
                # так как для данного отрезка а выражение не тождественно истинно
                break
        if c == 0: # если значение флага не менялось, значит, при любом х при данном отрезке а выражение было истинным
            mn = min(len(a)-1,mn) # вычисляем минимальную длину отрезка
print(mn)

Ответ: 19