Автор статьи: Андрей Роженцов
Задание № 15 из ЕГЭ по информатике проверяет знание основ алгебры логики и умение работать с логическими выражениями. Оно относится к заданиям повышенного уровня сложности и требует от учащихся:
- понимания законов булевой алгебры
- знания свойств логических операций
- навыков анализа условий истинности выражений
В задании требуется найти такое значение $A$, при котором логическое выражение будет истинным или ложным для всех возможных значений переменной.
Задание № 15 можно решать двумя способами: программным и аналитическим. Программное решение предполагает написание кода, который перебирает различные варианты $A$ и проверяет истинность выражения.
Аналитический метод заключается в том, чтобы упростить выражение, применив законы алгебры логики, и проанализировать результат полученного выражения для разных чисел.
Из преимуществ решения «руками» выделим два:
- скорость решения
- чёткий алгоритм
В статье рассмотрим аналитическое решение задач с числовыми отрезками.
Необходимо вспомнить основные операции алгебры логики:
-
двойное отрицание\
$\lnot \lnot A = A$ -
свойства логического сложения и умножения\
$A \lor 0 = A$\
$A \land 1 = A$\
$A \lor A = A$\
$A \land A = A$ -
раскрытие импликации\
$A \to B = \overline{A} \lor B$ -
законы де Моргана\
$\overline {A \land B} = \overline{A} \lor \overline{B}$\
$\overline {A \lor B} = \overline{A} \land \overline{B}$
Задача 1: простая формула
Рассмотрим задачу с простым условием, не требующую применения формул.
Отметим на числовой прямой отрезки $B$ и $C$.
Каждый промежуток обозначим цифрой и рассмотрим по отдельности.
Точки, находящиеся на границах промежутков, относим по логике, какому отрезку (или отрезкам) они принадлежат. Например, $х = 23$ лежит между 3-м и 4-м промежутками. Точки из 3-го промежутка принадлежат как отрезку $B$, так и отрезку $C$. Точки из 4-го промежутка принадлежат только отрезку $С$. $X = 23$ принадлежит как отрезку $С$, так и отрезку $B$ ($B = [10;23]$ границы нестрогие). Значит, $x = 23$ относится к 3-му промежутку.
Выпишем каждый промежуток и подставим любой х из него в исходное выражение.
I. $X < 10$\
$\lnot 0 \lor (x \in A) \lor \lnot 0 = 1 \lor (x \in A) \lor 1 = 1$
Независимо от значения отрезка $A$ выражение получилось истинным, значит, $A$ — любой отрезок.
II. $10 \leq x < 12$\
$\lnot 1 \lor (x \in A) \lor \lnot 0 = 0 \lor (x \in A) \lor 1 = 1$
Аналогично, A — любой отрезок.
III. $12 \leq x \leq 23$\
$\lnot 1 \lor (x \in A) \lor \lnot 1 = 0 \lor (x \in A) \lor 0 = (x \in A)$
Воспользовались свойством $0 \lor A = A$. Выражение будет истинным в том случае, если скобка $(x~\in~A)$ будет истинной. Это значит, что любой $х \in [12;23]$ должен принадлежать отрезку $A$. Поэтому отрезок $A$ должен быть как минимум от $12$ до $23$ включительно. По условию задачи необходимо найти отрезок минимальной длины, поэтому увеличивать его нет смысла.
IV. $23 < x \leq 30$\
$\lnot 0 \lor (x \in A) \lor \lnot 1 = 1 \lor (x \in A) \lor 0 = 1$
$A$ — любой отрезок.
V. $X > 30$\
$\lnot 0 \lor (x \in A) \lor \lnot 0 = 1 \lor (x \in A) \lor 1 = 1$
$A$ — любой отрезок.
Проанализируем ответы, отличные от тех, где $A$ – любое. Такой ответ только один: $A = [12;23]$. Это и есть итоговый результат.
Длина отрезка: $23 - 12 = 11$.
Ответ: $11$.
Задача 2: сложная формула
Рассмотрим задачу с импликациями и множеством операций.
На числовой прямой отмечаем промежутки из условия задачи и разбиваем числовую прямую на сегменты.
Рассмотрим каждый промежуток и подставим в выражение любой х из него.
I. $Х < 15$\
$0 \to ((0 \land \neg (x \in A)) \to 1) = 0 \to (0 \to 1) = 0 \to 1 = 1$
Независимо от значения $A$, выражение равно $1$, значит, $A$ — любое. Можно было не преобразовывать до конца, потому что последнее действие, которое будет выполняться в выражении, — это импликация, а $0 \to ?$ всегда даёт $1$. Поэтому неважно, какой результат получится в скобке после импликации.
II. $15 \leq x < 21$\
$1 \to ((0 \land \neg (x \in A)) \to 0) = 1 \to (0 \to 0) = 1 \to 1 = 1$
$A$ — любой отрезок.
III. $21 \leq x \leq 40$\
$1 \to ((1 \land \neg (x \in A)) \to 0)$
Чтобы выражение было истинным, необходимо, чтобы последнее действие было равно $1$. В этом случае последнее действие — импликация. Значит, скобка $(1 \land \neg (x \in A)) \to 0$ обязательно должна быть истинной. Тогда выражение в этой скобке $(1 \land \neg (x \in A))$ должно быть равно нулю, чтобы импликация дала $1$. Чтобы при умножении получить $1$, выражение $\neg (x \in A))$ должно быть равно $1$, тогда $(x \in A) = 1$.
Это значит, что любой $х \to [21;40]$ должен принадлежать отрезку $A$, поэтому отрезок $A$ должен быть как минимум от $21$ до $40$ включительно. По условию задачи необходимо найти отрезок минимальной длины, поэтому увеличивать его нет смысла.
IV. $40 < x \leq 63$\
$0 \to (((x \in Q) \land \neg (x \in A)) \to \neg (x \in P)) = 1$
После подстановки в первую скобку $x \to P = 0$ заметим, что $0 \to ? = 1$.
$A$ — любой отрезок.
V. $x > 63$\
$0 \to (((x \in Q) \land \neg (x \in A)) \to \neg (x \in P)) = 1$
Аналогично предыдущему пункту:\
$A$ — любой отрезок.
Проанализируем полученные ответы. Во всех случаях, кроме одного, $A$ — любой отрезок. Значит, $A = [21;40]$ подойдёт по всем пунктам.
Длина отрезка: $40 - 21 = 19$.
Ответ: $19$.
Задача 3: упрощение формул
Взаимное расположение отрезков из условия задачи может быть любым. Рассмотрим пример, где они не пересекаются. Также применим формулы для упрощения выражения.
Заменим скобки одной буквой $(x \in В) = B$ и т. д.
$\overline{((\overline{B} \to C) \to A)} = 0$
По условию задачи значение выражения должно быть равно $0$. Но так как отрицание стоит над всем выражением, то выражение под ним должно быть истинным.
$((\overline{B} \to C) \to A) = 1$
Преобразуем импликацию:
$(\overline{B} \to C) \to A = (\overline{\overline{B}} \lor C) \to A$
Избавляемся от двойного отрицания над переменной $B$, раскрываем импликацию.
$(B \lor C) \to A = \overline{(B \lor C)} \lor A$
Применяем закон де Моргана:
$\overline{(B \lor C)} \lor A = (\overline{B} \land \overline{C}) \lor A$
Для удобства подстановки х возвращаемся к исходным обозначениям.
$((x \notin B) \land (x \notin C)) \lor (x \in A)$
Отмечаем на числовой прямой отрезки $B$ и $C$. Разбиваем всю область на сегменты и подставляем х из каждого сегмента в выражение.
I. $X < 23$\
$(1 \land 1) \lor (x \in A) = 1 \lor (x \in A) = 1$
$A$ никак не влияет на результат, значит, $A$ — любой отрезок.
II. $23 \leq x \leq 37$\
$(0 \land 1) \lor (x \in A) = 0 \lor (x \in A) = (x \in A)$
Для того чтобы выражение равнялось $1$, необходимо, чтобы скобка $(x \in A)$ была равна $1$. Это значит, что любой $х \in [23;37]$ должен принадлежать отрезку $А$. Тогда минимальный отрезок $A = [23;37]$. По условию задачи $A$ должен быть минимальным, увеличивать его нет смысла.
III. $37 < x < 41$\
$(1 \land 1) \lor (x \in A) = 1 \lor (x \in A) = 1$
A — любой отрезок.
IV. $41 \leq x \leq 73$\
$(1 \land 0) \lor (x \in A) = 0 \lor (x \in A) = (x \in A)$
Для того чтобы выражение равнялось $1$, необходимо, чтобы выражение в скобке $(x \in A)$ было равно $1$. Это значит, что любой $х \in [41;73]$ должен принадлежать отрезку $A$. Тогда минимальный отрезок $A = [41;73]$. По условию задачи $A$ должен быть минимальным, увеличивать его нет смысла.
V. $X >73$\
$(1 \land 1) \lor (x \in A) = 1 \lor (x \in A) = 1$
A — любой отрезок.
Анализируем полученные ответы, отличные от тех, где $A$ — любой отрезок.
$A = [23;37]$\
$A = [41;73]$
При различных $х$ необходимо, чтобы промежуток $A$ включал в себя как числа из промежутка $[23;37]$, так и из промежутка $[41;73]$. Тогда отрезок минимальной длины, включающий в себя все значения, — $A = [23;73]$.
Длина отрезка: $73-23 = 50$.
Ответ: $50$.
Три основных шага для решения любой задачи
- Упростить выражение, раскрыть все импликации и применить законы де Моргана везде, где это возможно
- На числовой прямой рассмотреть каждый промежуток, подставить $х$ в выражение и определить $A$ (обращаем внимание на условие задачи)
- Проанализировать полученные ответы, отличные от $A$ — любой отрезок
Для более быстрого решения после преобразования выражения стоит спросить: «При каких значениях переменной $х$ отрезок $A$ влияет на значение выражения?» Так удастся избежать полного перебора и тех случаев, в которых ответ: $A$ — любой отрезок.
Рассмотрим пример.
Задача 4: быстрое решение
Рассмотрим более быстрый способ решения любой задачи.
Преобразуем выражение.
$(Q \to P) \lor (\overline{A} \to R)$
Избавимся от импликации.
$(Q \to P) \lor (\overline{A} \to R) = (\overline{Q} \lor P) \lor (\overline{\overline{A}} \lor R)$
Над А уберём двойное отрицание и избавимся от скобок, так как между ними стоит логическое сложение.
$\overline{Q} \lor P \lor A \lor R$
Возвращаемся к обратной замене.
$(x \notin Q) \lor (x \in P) \lor (x \in A) \lor (x \in R)$
Не будем, как в прошлых задачах, рассматривать все возможные значения x, а сразу найдём те, при которых отрезок А будет влиять на выражение.
Если все слагаемые, кроме А, будут равны 0, то всё выражение будет зависеть от отрезка А. В остальных же случаях выражение всё равно будет истинным, так как одно из слагаемых будет единицей.
Получается, что если $x$ принадлежит $Q$, $х$ не принадлежит $P$ и $х$ не принадлежит $R$, то для того, чтобы выражение было истинным, он обязательно должен принадлежать отрезку $А$. Отметим это на рисунке. Тогда минимальный отрезок $А = [160; 240]$. В задаче спрашивается минимальная длина, поэтому оставляем его без изменений.
Длина: $240 - 160 = 80$.
Ответ: $80$.
Итог
- Знание основных законов алгебры логики, законов де Моргана и следование чёткому алгоритму даёт возможность решить любую задачу, связанную с отрезками, аналитическим способом
- Для более быстрого решения, рассмотренного в последнем примере, стоит задаться вопросом: «При каких значениях х отрезок А влияет на выражение?» Это позволит исключить рассмотрение лишних промежутков и сэкономить время.