§ 36. Логические функции и логические выражения

Определения и обозначения

Логическая переменная — величина, принимающая только два значения: 0 («ложь») или 1 («истина»). Например, переменная A может обозначать ответ на вопрос, выполнено ли некоторое условие. Два значения нужны, чтобы однозначно отмечать, верно условие или нет, и использовать его в вычислениях.

Логическая функция — зависимость, которая по значениям логических переменных определяет значение 0 или 1. Например, функция от A и B задаёт результат отдельно для наборов 00, 01, 10 и 11. Понятие функции позволяет описывать правило, а не разбирать каждый возможный случай заново.

Логическое выражение — запись, составленная из логических переменных, констант и логических операций. В выражении A ∧ ¬B переменные соединены операциями И и НЕ, поэтому его результат можно вычислить для любого набора A и B. Такая запись нужна, чтобы кратко и точно представить условие задачи.

Таблица истинности — таблица, показывающая значение логического выражения при всех наборах значений его переменных. В ней каждая строка соответствует одному набору, а последний столбец содержит результат. Таблица помогает проверить выражение и увидеть, при каких условиях оно истинно.

Как это устроено

Два значения логических переменных связаны с тем, что рассматриваемое высказывание либо истинно, либо ложно: третьего варианта в классической логике нет. Числа 1 и 0 удобны как условные обозначения этих состояний, а не как обычные числа для арифметических вычислений. Поэтому при работе с переменной сначала выясняют, какое высказывание за ней стоит, а затем ставят ему в соответствие 1 или 0.

Операции преобразуют значения переменных по определённым правилам, а значит, сами задают логические функции. Отрицание НЕ меняет значение на противоположное: если A = 1, то ¬A = 0, и наоборот. Конъюнкция И требует истинности обоих условий, тогда как дизъюнкции ИЛИ достаточно истинности хотя бы одного; благодаря этим правилам можно составлять более сложные условия.

Чтобы записать условие задачи, сначала выделяют простые высказывания и обозначают их переменными. Затем слова «не», «и», «или» заменяют соответствующими операциями, сохраняя смысл условия: например, «A истинно и B ложно» записывают как A ∧ ¬B. Такой перевод нужен, чтобы проверять условие одинаковым способом для любых исходных данных, а не полагаться на догадки.

В сложном выражении результат зависит от того, какие операции выполнены первыми, поэтому порядок нельзя выбирать произвольно. Скобки задают нужную последовательность явно; если их нет, используют приоритет: сначала отрицание, затем конъюнкция, затем дизъюнкция. Например, A ∨ B ∧ C читают как A ∨ (B ∧ C), а не как (A ∨ B) ∧ C. При сомнении полезно расставить скобки и вычислять промежуточные части по очереди.

Таблицу истинности строят в два этапа: сначала перечисляют все наборы переменных, затем вычисляют выражение для каждой строки. У одной переменной два набора, у двух — четыре, у трёх — восемь; в общем случае для n переменных требуется 2ⁿ строк. Полный перебор нужен потому, что только он гарантирует проверку всех возможных сочетаний, в том числе тех, которые легко упустить при рассуждении.

Основные логические операции

Чтобы пользоваться таблицей, найдите строку с нужными значениями переменных и прочитайте результат операции. Для выражения из нескольких операций сначала примените правила в скобках и столбцы с промежуточными результатами. Так можно последовательно получить итог, не смешивая значения исходных переменных с результатами действий.

Разбор задач

Построить таблицу истинности для выражения ¬A.

У переменной A только два возможных значения, поэтому в таблице нужны две строки. Отрицание заменяет каждое из них на противоположное: единицу на ноль, а ноль на единицу. Запишем вычисления по строкам.

1. Перечислим значения A: 0 и 1.
2. При A = 0 получаем ¬A = 1.
3. При A = 1 получаем ¬A = 0.

Ответ: таблица имеет строки A = 0, ¬A = 1 и A = 1, ¬A = 0. Проверка проста: в каждом случае результат должен отличаться от исходного значения.

Построить таблицу истинности для выражения A ∧ (B ∨ C).

Три переменные дают восемь наборов, поэтому нужно проверить каждый из них. Скобки показывают, что сначала вычисляется B ∨ C, а уже потом его результат соединяется с A операцией И. Выражение будет истинным только тогда, когда A = 1 и внутри скобок получилось 1.

1. Перечислим наборы A, B, C: 000, 001, 010, 011, 100, 101, 110, 111.
2. Вычислим B ∨ C для каждой строки: 0, 1, 1, 1, 0, 1, 1, 1.
3. Выполним И с A. Для первых четырёх строк A = 0, поэтому результат равен 0. Для последних четырёх результаты равны 0, 1, 1, 1.
4. Запишем итоговый столбец в том же порядке строк: 0, 0, 0, 0, 0, 1, 1, 1.

Ответ: выражение истинно для наборов 101, 110 и 111. Перед завершением полезно проверить, что каждая единица в итоговом столбце стоит напротив A = 1, а внутри скобок в этой строке есть хотя бы одна единица.

Определить, при каких значениях A, B и C выражение (A ∨ B) ∧ ¬C истинно.

Скобки объединяют два первых условия: достаточно, чтобы истинным было хотя бы одно из A и B. Кроме того, отрицание C требует, чтобы C было равно 0. Значит, нужно найти строки, где одновременно выполнены оба требования.

1. Переведём условие в запись: (A ∨ B) ∧ ¬C.
2. Перечислим восемь наборов A, B, C и оставим строки с C = 0: 000, 010, 100, 110.
3. Проверим A ∨ B в этих строках. Для 000 результат равен 0, а для 010, 100 и 110 он равен 1.
4. Соединим результат с ¬C. В оставленных строках ¬C = 1, поэтому итоговые единицы получатся для 010, 100 и 110.

Ответ: выражение истинно при (A, B, C) = (0, 1, 0), (1, 0, 0) и (1, 1, 0). Проверка по смыслу подтверждает результат: C ложно, а из A и B истинно хотя бы одно.

Типичные ошибки

Иногда считают, что ИЛИ истинно лишь тогда, когда истинны оба высказывания. Это происходит из-за смешения бытового понимания «или» с операцией И; в логике достаточно хотя бы одной единицы. Проверьте строку 10: для A ∨ B результат равен 1, а для A ∧ B — 0.

При отрицании сложного выражения можно перевернуть не тот результат или забыть изменить 0 на 1 и 1 на 0. Часто отрицание ошибочно относят только к ближайшей переменной, хотя скобки могут относить его ко всему выражению. Чтобы проверить себя, определите, на какую часть указывает знак ¬, вычислите эту часть и только затем поменяйте итог.

Если выполнять операции в произвольном порядке или пропустить скобки, получится другое выражение и, возможно, другая таблица. Причина ошибки — попытка считать слева направо без учёта приоритета. Перед вычислением отметьте скобки и порядок действий, а затем сравните, одинаково ли записаны промежуточные результаты.

Пропуск наборов в таблице приводит к тому, что некоторые возможные результаты остаются непроверенными. Такое случается, если строки перечисляют на глаз или случайно повторяют одну из них. Сверьте число строк с 2ⁿ и проверьте, что каждый набор встречается ровно один раз.

Связь с другими темами

Для работы с логическими функциями нужны понятия высказывания, истинности и ложности, а также умение читать таблицы и двоичные значения. Освоенные операции применяют в алгоритмах и программах: с их помощью задают условия ветвления и продолжения циклов. Логика также помогает проектировать схемы, составлять запросы к базам данных и решать задачи, где перебирают варианты и отбирают подходящие.

Что запомнить

• Логическая переменная принимает только значения 0 или 1.
• Логическая функция задаёт результат для каждого набора значений переменных.
• Отрицание меняет значение переменной или выражения на противоположное.
• Конъюнкция истинна только тогда, когда истинны оба операнда.
• Дизъюнкция ложна только тогда, когда ложны оба операнда.
• Таблица истинности содержит результаты для всех наборов значений переменных.
• При вычислении сложного выражения сначала учитывают скобки и приоритет логических операций.