Практическая работа 3.1 Таблицы истинности логических функций

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

Логическая переменная — величина, которая принимает одно из двух значений: истина или ложь. Истину обычно обозначают числом 1, а ложь — числом 0. Например, высказывание «число 5 больше 2» истинно и получает значение 1. Такое обозначение позволяет работать с высказываниями по чётким правилам.

Логическая функция — правило, которое по значениям логических переменных определяет значение логического выражения. Например, функция может сообщать, истинно ли условие A ∧ B при выбранных значениях A и B. Она нужна, чтобы исследовать выражение для всех возможных вариантов, а не только для одного примера. Результат функции также равен 0 или 1.

Логическая операция — действие над логическими значениями. Отрицание записывают ¬A и читают «не A», конъюнкцию A ∧ B — «A и B», дизъюнкцию A ∨ B — «A или B». Также используют импликацию A → B («если A, то B») и эквиваленцию A ↔ B («A тогда и только тогда, когда B»). Обозначения помогают записывать условия коротко и однозначно.

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

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

Сначала определяют, сколько переменных входит в выражение. Для n переменных существует 2ⁿ разных наборов: у каждой переменной два возможных значения, поэтому варианты перемножаются. Например, для A и B это 2 × 2 = 4 набора, а для A, B и C — 2 × 2 × 2 = 8. Если строк будет меньше, часть случаев останется непроверенной; если больше — появятся повторы.

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

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

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

В конце проверяют полноту таблицы. Для двух переменных должны встретиться 00, 01, 10 и 11; для большего числа переменных проверяют соответствующее количество строк 2ⁿ. Удобно перечислять наборы по порядку, как двоичные числа, но допустим и другой порядок. Главное, чтобы каждый возможный набор встретился ровно один раз: тогда ни один случай не потерян и не посчитан дважды.

Значения основных логических операций для двух переменных

Найдите в первых двух столбцах нужный набор значений, а затем прочитайте результат в столбце выбранной операции. Для выражений с отрицанием учитывайте, к какой переменной оно относится. Импликация ложна только в строке A = 1, B = 0, а эквиваленция истинна при равных значениях переменных.

Разбор задач

Задача. Построить таблицу истинности выражения ¬A ∨ B. В нём две переменные, поэтому требуется четыре строки. Сначала удобно вычислить отрицание A, а затем объединить его с B операцией дизъюнкции.

1. Записываем все наборы A и B: 00, 01, 10, 11. Это полный список, потому что 2² = 4.
2. Вычисляем ¬A: при A = 0 получаем 1, а при A = 1 получаем 0. Значения по строкам будут 1, 1, 0, 0.
3. Для ¬A ∨ B ставим 1, если хотя бы один из двух операндов равен 1. Итоговые значения: 1, 1, 0, 1.

Ответ: таблица для наборов 00, 01, 10, 11 даёт значения выражения 1, 1, 0, 1. Ноль получился только при A = 1 и B = 0, когда обе части дизъюнкции ложны. Каждое итоговое значение можно проверить по соответствующей строке.

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

1. Создаём столбцы A ∧ B и ¬A. Для наборов 00, 01, 10, 11 конъюнкция принимает значения 0, 0, 0, 1, а отрицание A — 1, 1, 0, 0.
2. В каждой строке объединяем результаты операцией ∨. Получаем: 0 ∨ 1 = 1, 0 ∨ 1 = 1, 0 ∨ 0 = 0, 1 ∨ 0 = 1.
3. Записываем полученные значения в итоговый столбец и сверяем каждую строку с определением дизъюнкции: она ложна, только если обе части ложны.

Ответ: итоговый столбец равен 1, 1, 0, 1 для наборов 00, 01, 10, 11. Промежуточные столбцы показывают, что именно проверялось в каждой строке. Совпадение с предыдущим примером не означает, что выражения всегда равносильны: это можно утверждать только после сравнения всех строк.

Задача. Построить таблицу истинности выражения (A → B) ∧ (B → C). Три переменные дают 2³ = 8 наборов. Каждую импликацию нужно вычислить отдельно, поскольку итоговая конъюнкция истинна лишь тогда, когда истинны обе.

1. Записываем наборы A, B, C: 000, 001, 010, 011, 100, 101, 110, 111. Такой порядок перебирает все двоичные сочетания ровно по одному разу.
2. Считаем A → B: её значения по строкам — 1, 1, 1, 1, 0, 0, 1, 1. Считаем B → C: 1, 1, 0, 1, 1, 1, 0, 1. В каждом столбце ноль появляется только при истинной первой переменной импликации и ложной второй.
3. Выполняем конъюнкцию полученных столбцов: итог равен 1, 1, 0, 1, 0, 0, 0, 1. Единицу оставляем только там, где обе импликации равны 1.

Ответ: для наборов 000, 001, 010, 011, 100, 101, 110, 111 выражение принимает значения 1, 1, 0, 1, 0, 0, 0, 1. Например, в наборе 010 ложна импликация B → C, поэтому вся конъюнкция ложна. Проверка итогового столбца по двум промежуточным выявляет возможные ошибки.

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

Некоторые пропускают набор или записывают его повторно, потому что перебирают значения без системы. Обычно это случается, когда число строк заранее не проверили по формуле 2ⁿ. Перед вычислениями посчитайте нужные строки и перечислите наборы по порядку. Затем проверьте, что каждый набор отличается от остальных хотя бы одной переменной.

Конъюнкцию иногда принимают за дизъюнкцию: считают, что для «и» достаточно одной истинной части, или требуют для «или» истинности обеих частей. Причина — перенос привычного смысла слов без проверки логических правил. Для самопроверки найдите строку 1 и 0: конъюнкция там ложна, а дизъюнкция истинна. Также проверьте крайние случаи 00 и 11.

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

Для импликации ошибочно считают, что ложная посылка всегда делает всё выражение ложным. Такое представление возникает из-за бытового прочтения конструкции «если — то», но логическое правило другое. Проверьте строку A = 0, B = 0: импликация истинна; единственная ложная строка — A = 1, B = 0. Сравнение со столбцом A → B помогает закрепить правило.

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

Для построения таблиц нужно понимать значения «истина» и «ложь», а также их двоичные обозначения 1 и 0. Ещё до вычислений следует знать смысл операций: отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции. Эти понятия превращают словесное условие в выражение, с которым можно работать по формальным правилам. Без понимания операций таблица будет набором чисел без смысла.

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

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

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