Автор статьи: Андрей Роженцов
Продолжаем изучать задачу № 15 из ЕГЭ по информатике. В предыдущей статье мы рассмотрели способ решения через отрезки, в этой поговорим о множествах.
Множество представляет собой набор неповторяющихся элементов. В этой задаче рассматриваются множества целых чисел.
Основная идея аналитического метода остаётся прежней: либо полный перебор всех возможных х и подстановка их в выражение, либо применение законов алгебры логики, чтобы упростить выражение и проанализировать поведение этого выражения для разных чисел.
Задача 1: простая формула
Рассмотрим множество всех целых чисел и нарисуем круги Эйлера, обозначающие множества B и C. Пронумеруем получившиеся области (I–IV) и разместим числа из условия задачи в нужных местах.
Рассмотрим каждую область.
- Числа принадлежат только множеству B\
x = −42, x = −8, x = 16\
Подставим любое из них в выражение.
((x ∈ А) → (x ∈ B)) ∨ (x ∈ C) = ((x ∈ А) → 1) ∨ 0 = 1 ∨ 0 = 1
Независимо от значения множества А выражение равно 1, значит, А — любое множество.
- Числа принадлежат и B, и С\
x = −10, x = 2
((x ∈ А) → (x ∈ B)) ∨ (x ∈ C) = ((x ∈ А) → 1) ∨ 1 = 1 ∨ 1 = 1
Аналогично, А — любое множество.
- Числа принадлежат только С\
x = −4, x = 15, x = 23
((x ∈ А) → (x ∈ B)) ∨ (x ∈ C) = ((x ∈ А) → 0) ∨ 1 = ? ∨ 1 = 1
В этом случае неважно, чему равно значение импликации, т. к. последнее действие — логическое сложение и в итоге получится 1. А — любое множество.
- Числа не принадлежат ни B, ни С
В этой области бесконечное количество чисел. Например: x = 1, x = 3, x = 4 и т. д.
Подставляем любое из этих чисел в выражение.
((x ∈ А) → (x ∈ B)) ∨ (x ∈ C) = ((x ∈ А) → 0) ∨ 0 = (x ∈ А) → 0
Чтобы всё выражение было истинным, выражение в скобках (x ∈ А) должно быть ложным. Это значит, что если x не было в множестве B или в множестве C, то и в множестве А его быть не должно. В множество А мы можем добавлять только те числа, которые были в B или С.
Требование задачи: «Найти максимальную сумму элементов множества А». Значит, чтобы сумма была как можно больше, нет смысла добавлять в множество отрицательные числа. Но добавим как можно больше положительных.
А = {2, 16, 15, 23}
Сумма элементов: 2 + 16 + 15 + 23 = 56
Ответ: 56
Задача 2: сложная формула
Разобьём все x на 4 группы и подставим в выражение (для наглядности можно нарисовать круги Эйлера, как в задаче 1):
- Числа принадлежат и P, и Q\
x = 5, 11, 17\
((x ∈ А) → ¬ (x ∈ P)) ∧ (¬ (x ∈ Q) → ¬ (x ∈ A)) =\
= ((x ∈ A) → ¬ 1) ∧ (¬ 1 → ¬ (x ∈ A)) =\
= ((x ∈ A) → 0) ∧ (0 → ¬ (x ∈ A)) =\
= ((x ∈ A) → 0) ∧ 1 =\
= ((x ∈ A) → 0)
Чтобы всё выражение было истинным, выражение в скобках (x ∈ А) должно быть ложным. Это значит, что если x был в множестве P и в множестве Q, то его не должно быть в множестве А.
- Числа принадлежат только P\
x = 1, 3, 7, 9, 13, 15, 19\
((x ∈ А) → ¬ (x ∈ P)) ∧ (¬ (x ∈ Q) → ¬ (x ∈ A)) =\
= ((x ∈ A) → ¬ 1) ∧ (¬ 0 → ¬ (x ∈ A)) =\
((x ∈ A) → 0) ∧ (1 → ¬ (x ∈ A))
Определим, чему должно быть равно выражение (x ∈ А).
Подставим (x ∈ А) = 1, тогда (1 → 0) ∧ (1 → ¬ 1) = 0 ∧ (1 → 0) = 0
Выражение получилось ложным, значит, такой x не подходит.
Подставим (x ∈ А) = 0, тогда (0 → 0) ∧ (1 → ¬ 0) = 1 ∧ (1 → 1) = 1 ∧ 1 = 1
Чтобы всё выражение было истинным, выражение в скобках (x ∈ А) должно быть ложным. Это значит, что если x принадлежал только множеству P, то его не должно быть в множестве А.
-
Числа принадлежат только Q\
x = 2, 8, 14, 20, 23, 26, 29\
((x ∈ А) → ¬ (x ∈ P)) ∧ (¬ (x ∈ Q) → ¬ (x ∈ A)) =\
= ((x ∈ A) → ¬ 0) ∧ (¬ 1 → ¬ (x ∈ A)) =\
= ((x ∈ A) → 1) ∧ (0 → ¬ (x ∈ A)) =\
= 1 ∧ 1 = 1\
Множество А не влияет на выражение, значит, А — любое множество. -
Числа не принадлежат ни P, ни Q\
Возьмём одно подходящее число, например, х = 50.\
((x ∈ А) → ¬ (x ∈ P)) ∧ (¬ (x ∈ Q) → ¬ (x ∈ A)) =\
= ((x ∈ A) → ¬ 0) ∧ (¬ 0 → ¬ (x ∈ A)) =\
= ((x ∈ A) → 1) ∧ (1 → ¬ (x ∈ A)) =\
= 1 ∧ (1 → ¬ (x ∈ A)) =\
= 1 → ¬ (x ∈ A)
Чтобы выражение было истинным, необходимо чтобы ¬ (x ∈ A) = 1. Значит, (x ∈ A) = 0.\
Это значит, что если x не было ни в множестве P, ни в множестве Q, то и в множестве А его быть не должно.
Рассмотрев все возможные х, запишем правила, которые мы нашли:
- Если x был в множестве P и в множестве Q, то его не должно быть в множестве А
- Если x принадлежал только множеству P, то его не должно быть в множестве А
- Если x не было ни в множестве P, ни в множестве Q, то и в множестве А его быть не должно
Эти три пункта можно перефразировать следующим образом: в множество A можно добавлять только те элементы, которые есть только в множестве Q.
По условию задачи необходимо найти наибольшее количество элементов множества А, поэтому добавляем все числа, которые были только в множестве Q.
А = {2, 8, 14, 20, 23, 26, 29}
Количество чисел: 7
Ответ: 7
Задача 3: анализируем выражение
По условию необходимо, чтобы выражение было истинным при любом целом х. Здесь мы видим три скобки, между которыми стоит логическое сложение. Поэтому если хотя бы одна скобка будет истинной, то и всё выражение будет истинным.
Если взять любой х из первых двух скобок (х = 12, 23, 34, 35, 45, 46, 68, 89), то всё выражение будет истинным, т. к. они принадлежат одному из множеств или обоим.
Но как насчёт других х?
Например, возьмём х = 10 и подставим в выражение:
(x ∈ {12, 23, 34, 45, 56}) ∨ (x ∈ {12, 35, 56, 68, 89}) ∨ (x ∉ А) =\
= 0 ∨ 0 ∨ (x ∉ А) =\
= 0 ∨ (x ∉ А) =\
= (x ∉ А)
Чтобы выражение было истинным, выражение в скобках (x ∉ А) должно быть истинно, значит, (x ∈ A) = 0.
Получается, что если х не из чисел 12, 23, 34, 35, 45, 46, 68, 89, то и в множестве А его быть не должно. Тогда А = {12, 23, 34, 35, 45, 46, 68, 89}. В А добавили все возможные числа, т. к. по условию задачи необходимо было найти максимальное количество элементов. Количество элементов — 8.
Ответ: 8
Задача 4: упрощаем выражение
Для удобства преобразования формул заменим скобки одной буквой: (x Є P) = P, (x ∉ Q) = ¬Q и т. д.
Раскроем импликацию по формуле: A → B = ¬A ∨ B
Применим закон де Моргана для раскрытия отрицания над скобкой:
С помощью формулы избавимся от двойного отрицания:
Для удобства подстановки после всех преобразований сделаем обратную замену:
В отличие от предыдущих задач рассмотрим только те х, при которых множество А будет влиять на выражение.
По условию задачи всё выражение должно быть ложным. Если выражение в скобках (x Є P) или в скобках (x Є Q) будет ложным, то и всё выражение будет ложным, т. к. между ними стоит логическое умножение. Значит, множество А никак не будет влиять на ответ, т. е. А — любое множество. Поэтому только в случае, когда (x Є P) = 1 и (x Є Q) = 1, выражение в скобках (x ∉ А) должно быть равно 0, чтобы выражение получилось ложным. Раз (x ∉ А) = 0, то (x Є А) = 1.
Запишем правило: когда х принадлежит множеству P и множеству Q, он должен принадлежать и множеству А.
Составим множество А = {15, 30}. Это множество можно дополнить и другими числами, ведь это не противоречит нашему правилу. Но по условию задачи необходима минимальная сумма элементов. Значит, дополнять нет смысла, т. к. х не может быть отрицательным (по условию х — натуральное число).
Сумма элементов: 15 + 30 = 45
Ответ: 45
Итог
-
Самый простой способ решения — рассмотрение всех возможных х: тех, что одновременно принадлежат нескольким множествам, и тех, что принадлежат только одному. Не забываем рассмотреть и те, что вообще не принадлежат ни одному множеству
-
Для более быстрого решения, рассмотренного в последнем примере, стоит задаться вопросом: «При каких значениях х множество А влияет на выражение?» Знание основных законов алгебры логики, законов де Моргана даёт возможность решить любую задачу, связанную с множествами, аналитическим способом.