Логические уравнения, подсчёт количества решений, упорядочивание высказываний
Типы логических задач ЕГЭ
В экзаменационной части по информатике логические задачи встречаются в нескольких характерных форматах: решение логических уравнений или систем уравнений с определением конкретных значений переменных; подсчёт количества наборов переменных, при которых сложное логическое выражение истинно (или ложно); задачи на упорядочивание высказываний, где по истинности набора утверждений о некотором объекте нужно установить сам объект или порядок объектов. Все они опираются на законы алгебры логики и на умение строить и анализировать таблицы истинности, но требуют разной техники решения.
Логические уравнения: базовый приём
Логическое уравнение — это равенство логического выражения единице (истине) или нулю (лжи) относительно переменных, значения которых требуется найти. Простейший приём — построить таблицу истинности и найти строки, где выражение принимает нужное значение. Он надёжен, но при большом числе переменных (4-5 и больше) перебор всех 2ⁿ комбинаций становится громоздким, поэтому эффективнее сначала упростить выражение законами алгебры логики, а затем анализировать полученную простую форму.
Пример 1: логическое уравнение с несколькими переменными
Условие. Найдите количество различных наборов значений логических переменных A, B, C, D, при которых истинно выражение: (A→B)∧(B→C)∧(C→D) = 1, где → обозначает импликацию.
Решение. Конъюнкция трёх импликаций истинна тогда и только тогда, когда истинна каждая из них по отдельности. Импликация X→Y ложна только в одном случае: когда X=1, а Y=0; во всех остальных трёх случаях (00, 01, 11) она истинна. Значит, условие (A→B)∧(B→C)∧(C→D)=1 равносильно требованию: нигде в цепочке A,B,C,D не должно быть перехода от 1 к 0 при движении слева направо.
Иными словами, допустимые наборы — это последовательности из нулей, за которыми (при переходе к единицам) следуют только единицы: как только встретилась единица, дальше в цепочке единицы уже не могут смениться нулём. Переберём по количеству единиц в конце цепочки (от 0 до 4):
| A | B | C | D |
|---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 1 | 1 |
К этим четырём добавляется набор 1,1,1,1 (все единицы) — итого 5 подходящих наборов. Это классический результат: для цепочки из n импликаций X₁→X₂→…→Xₙ₊₁ (n переходов, n+1 переменная) количество решений равно n+2 (при n=3 переходах, 4 переменных: 3+2=5, что совпадает с прямым перебором).
Ответ: 5 наборов.
Пример 2: уравнение через равносильные преобразования
Условие. Сколько существует наборов значений переменных X, Y, Z, при которых истинно выражение: ¬(X∧Y)∨(Y∧Z)∨¬Z = 1?
Решение. Проще всего для трёх переменных построить полную таблицу истинности (8 строк) и подсчитать количество единиц в столбце результата, но продемонстрируем и аналитический путь. Раскроем первое слагаемое по закону де Моргана: ¬(X∧Y)=¬X∨¬Y. Выражение примет вид:
Выражение ложно только тогда, когда ложно каждое слагаемое дизъюнкции одновременно: ¬X=0 (значит X=1), ¬Y=0 (значит Y=1), Y∧Z=0, ¬Z=0 (значит Z=1). Но при Y=1 и Z=1 конъюнкция Y∧Z=1, что противоречит требованию Y∧Z=0. Значит, ни при каком наборе X,Y,Z все четыре слагаемых не могут быть одновременно ложны — выражение F ложно быть не может, оно тождественно истинно.
Ответ: выражение истинно при всех наборах значений переменных, то есть при всех 2³=8 наборах.
Подсчёт количества решений без полного перебора
Для выражений с большим числом переменных (5 и более) полный перебор 2ⁿ строк вручную неудобен. Полезные приёмы: разбиение выражения на независимые блоки переменных (если выражение распадается на конъюнкцию частей с непересекающимися множествами переменных, количество решений всего выражения равно произведению количеств решений частей); использование симметрии выражения; сведение к уже разобранному типу задачи (как цепочка импликаций в примере 1). При решении систем логических уравнений (несколько уравнений, которые должны выполняться одновременно) количество решений системы равно количеству наборов переменных, одновременно удовлетворяющих всем уравнениям — такие задачи часто решают, комбинируя ограничения по битам числа переменных, если условия имеют переменные с одинаковыми номерами по индексу (X1, X2, …, Xn для разных уравнений одной системы).
Задачи на упорядочивание высказываний
В задачах этого типа даётся несколько человек (или объектов) и несколько высказываний о них (например, о месте, занятом в соревновании, или об истинности некоторого утверждения), причём известно, что часть высказываний истинна, а часть ложна, либо известно правило (например, «истинно ровно одно из двух высказываний каждого» или «каждый участник сказал одну правду и одну ложь»). Требуется определить, кто есть кто, или каков порядок.
Пример 3: определение победителей по высказываниям
Условие. Три спортсмена — Антонов, Борисов и Волков — заняли первое, второе и третье места в соревновании. На вопрос о результатах трое зрителей высказали предположения: Зритель 1: «Антонов — первый, Волков — второй»; Зритель 2: «Волков — первый, Борисов — второй»; Зритель 3: «Антонов — второй, Волков — третий». Известно, что каждый зритель в своём высказывании (состоящем из двух утверждений) прав ровно в одной части и неправ в другой. Определите итоговое распределение мест.
Решение. Обозначим утверждения: 1а=«Антонов-1», 1б=«Волков-2»; 2а=«Волков-1», 2б=«Борисов-2»; 3а=«Антонов-2», 3б=«Волков-3». По условию у каждого зрителя истинно ровно одно из двух его утверждений. Три спортсмена могут занять три места ровно 6 различными способами (число перестановок из 3 элементов), поэтому надёжнее всего систематически перебрать все 6 вариантов и для каждого проверить условие «ровно одна правда у каждого зрителя», не полагаясь на цепочку предположений, в которой легко запутаться.
Пересчитаем по таблице все 6 перестановок мест (1 — первое место, 2 — второе, 3 — третье) для троих (А — Антонов, Б — Борисов, В — Волков):
| А,Б,В | З1: 1а,1б | З2: 2а,2б | З3: 3а,3б | Подходит? |
|---|---|---|---|---|
1,2,3 | И,Л | Л,И | Л,И | да: 1, 1, 1 истина |
1,3,2 | И,И | Л,Л | Л,Л | нет (З1: 2, З2: 0, З3: 0) |
2,1,3 | Л,Л | Л,Л | И,И | нет (З1: 0, З2: 0) |
2,3,1 | Л,Л | И,Л | И,Л | нет (З1: 0 истин) |
3,1,2 | Л,И | Л,Л | Л,Л | нет (З2: 0, З3: 0) |
3,2,1 | Л,Л | И,И | Л,Л | нет (З1: 0, З3: 0) |
Единственная перестановка, где у каждого зрителя истинно ровно одно утверждение — А=1, Б=2, В=3, то есть Антонов — первый, Борисов — второй, Волков — третий.
Ответ: первое место — Антонов, второе — Борисов, третье — Волков.
Общая стратегия решения задач на упорядочивание
На практике удобнее не рассуждать «от руки» цепочкой предположений (как в первой части разбора примера 3, где легко запутаться), а сразу выписать таблицу всех допустимых вариантов размещения (перестановок, если число вариантов невелико) и для каждого явно посчитать число истинных утверждений у каждого зрителя/участника, отбирая варианты, удовлетворяющие условию задачи. Такой систематический перебор надёжнее, хотя и объёмнее в записи.
Типичные ошибки
При решении логических уравнений частая ошибка — забыть, что импликация X→Y ложна лишь в единственном случае (X=1, Y=0), и по ошибке считать её ложной чаще. При подсчёте количества решений системы уравнений — забыть, что решение должно удовлетворять ВСЕМ уравнениям системы одновременно, а не хотя бы одному. В задачах на упорядочивание высказываний — перепутать условие «ровно одно из двух утверждений истинно» с условием «хотя бы одно истинно» или «оба должны быть согласованы», а также не выполнить проверку найденного ответа подстановкой во все исходные высказывания.
Краткий словарь терминов
Логическое уравнение — равенство логического выражения с переменными заданному значению (0 или 1), которое требуется решить.
Импликация — логическая операция «если…, то…» (A→B), ложная только при A=1 и B=0.
Система логических уравнений — набор уравнений, которые должны выполняться одновременно для одних и тех же переменных.
Количество решений уравнения — число различных наборов значений переменных, при которых уравнение истинно.
Полный перебор — метод решения, при котором проверяются все 2ⁿ возможных комбинаций значений n переменных.
Упорядочивание высказываний — тип логической задачи, где по истинности набора утверждений определяется порядок или соответствие объектов.
Заключение
Логические уравнения и задачи на упорядочивание высказываний требуют сочетания двух навыков: точного применения законов алгебры логики для упрощения выражений и аккуратного, систематического перебора вариантов с обязательной проверкой найденного решения. Освоив эту технику, легко перейти к следующей теме — устройству логических элементов компьютера, которые физически реализуют изученные логические операции в виде электронных схем.
