Алгебра логики: логические операции и таблицы истинности

Отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность; построение таблиц истинности

Высказывания и логические величины

Алгебра логики (булева алгебра, по имени математика Джорджа Буля) изучает высказывания — повествовательные предложения, о которых можно однозначно сказать, истинны они или ложны. Например, «5 больше 3» — истинное высказывание, «Москва — столица Франции» — ложное. В алгебре логики истинность обозначают единицей (1, «истина», True), а ложность — нулём (0, «ложь», False); эти два значения называют логическими величинами. Из простых высказываний с помощью логических операций можно строить составные (сложные) высказывания.

Логическое отрицание НЕ

Отрицание (инверсия, операция НЕ) — простейшая логическая операция, применяемая к одному высказыванию A и обозначаемая ¬A (читается «не A»). Результат отрицания истинен тогда и только тогда, когда исходное высказывание A ложно, и наоборот: отрицание меняет значение высказывания на противоположное.

Логическое умножение И (конъюнкция)

Конъюнкция (логическое умножение, операция И) применяется к двум высказываниям A и B и обозначается A∧B (читается «A и B»). Результат конъюнкции истинен только в том случае, когда оба высказывания A и B истинны одновременно; если хотя бы одно из них ложно, конъюнкция ложна. Название «логическое умножение» объясняется тем, что таблица истинности конъюнкции совпадает с таблицей умножения чисел 0 и 1.

Логическое сложение ИЛИ (дизъюнкция)

Дизъюнкция (логическое сложение, операция ИЛИ) применяется к двум высказываниям и обозначается A∨B (читается «A или B»). Результат дизъюнкции ложен только тогда, когда оба высказывания ложны одновременно; если хотя бы одно из них истинно, дизъюнкция истинна. Важно, что это «неисключающее ИЛИ»: высказывание A∨B истинно и в том случае, когда истинны оба высказывания A и B сразу.

Логическое следование (импликация)

Импликация (логическое следование) обозначается A→B (читается «если A, то B», или «из A следует B»). Высказывание A называют условием (посылкой), B — следствием. Импликация ложна только в одном-единственном случае — когда посылка A истинна, а следствие B ложно (истина не может порождать ложь). Во всех остальных случаях, включая случай, когда посылка A сама ложна, импликация считается истинной — это часто вызывает удивление у школьников, но логично: из ложного условия формально может «следовать» что угодно.

Логическая равнозначность (эквивалентность)

Эквивалентность (равнозначность) обозначается A↔B (читается «A равносильно B», «A тогда и только тогда, когда B»). Результат эквивалентности истинен, если оба высказывания A и B имеют одинаковое логическое значение (оба истинны или оба ложны одновременно), и ложен, если их значения различаются.

Таблицы истинности базовых операций

Таблица истинности — это таблица, показывающая значение логического выражения для всех возможных комбинаций значений входящих в него переменных. Для двух логических переменных A и B существует ровно четыре такие комбинации (00, 01, 10, 11). Сведём таблицы истинности всех рассмотренных операций в одну общую таблицу:

Приоритет логических операций

Когда в одном логическом выражении встречается несколько операций, важно знать порядок их выполнения — приоритет. От более высокого приоритета к более низкому логические операции выполняются в следующем порядке: сначала отрицание ¬, затем конъюнкция ∧, затем дизъюнкция ∨, затем импликация →, и в последнюю очередь эквивалентность ↔. Изменить порядок выполнения, как и в обычной арифметике, можно с помощью скобок.

Пример 1. Построение таблицы истинности составного выражения

Дано: постройте таблицу истинности для логического выражения F=(A∨B)∧¬C, зависящего от трёх переменных A, B, C.

Решение. Для трёх переменных существует 2³=8 комбинаций их значений. Для каждой строки сначала вычисляем промежуточные результаты A∨B и ¬C, а затем — их конъюнкцию F:

Ответ: выражение F истинно ровно в трёх случаях из восьми — когда C ложно и хотя бы одна из переменных A, B истинна; таблица выше показывает это для всех восьми комбинаций.

Пример 2. Вычисление значения выражения при заданных переменных

Дано: известно, что A=1, B=0, C=1. Найдите значение логического выражения F=¬A∨(B→C).

Решение. Сначала вычисляем отрицание: ¬A=¬1=0. Затем вычисляем импликацию в скобках: B→C при B=0, C=1 истинна (так как посылка B ложна, импликация истинна независимо от следствия), значит B→C=1. Наконец, вычисляем дизъюнкцию:

$F=0\vee 1=1$

Ответ: F=1 (выражение истинно).

Программная иллюстрация: построение таблицы истинности

Рассмотрим программу на Python, которая программно генерирует все комбинации значений трёх логических переменных с помощью функции itertools.product и вычисляет для каждой из них значение выражения F=(A∨B)∧¬C — результат должен совпасть с таблицей из примера 1.

from itertools import product

def NOT(a):

return 1 — a

def AND(a, b):

return a & b

def OR(a, b):

return a | b

def IMPL(a, b):

return OR(NOT(a), b)

def EQV(a, b):

return 1 if a == b else 0

print("A B C | F=(A|B)&!C")

for a, b, c in product([0, 1], repeat=3):

f = AND(OR(a, b), NOT(c))

print(f"{a} {b} {c} | {f}")

Функция product([0, 1], repeat=3) перебирает все 2³=8 комбинаций значений трёх переменных в лексикографическом порядке — том же самом, в котором построена таблица истинности в примере 1, поэтому вывод программы должен строка в строку совпасть со столбцом F в этой таблице. Такой подход к «прямому перебору» — стандартный способ проверить формулу, эквивалентны ли два логических выражения, если сравнить столбцы их результатов при всех комбинациях переменных.

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

Самая распространённая ошибка — считать импликацию A→B ложной всякий раз, когда посылка A ложна: на самом деле в этом случае импликация всегда истинна, ложной она бывает только при истинной посылке и ложном следствии. Вторая ошибка — путать дизъюнкцию (ИЛИ) с исключающим ИЛИ: обычная дизъюнкция A∨B истинна и тогда, когда истинны оба высказывания одновременно, а не только когда истинно ровно одно из них. Третья ошибка — нарушать приоритет операций при вычислении составных выражений без скобок, например, вычислять дизъюнкцию раньше конъюнкции, хотя по правилам приоритета конъюнкция выполняется первой.

Краткий словарь терминов

Высказывание — повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно.

Конъюнкция — логическая операция И (A∧B), истинная только тогда, когда истинны оба операнда.

Дизъюнкция — логическая операция ИЛИ (A∨B), ложная только тогда, когда ложны оба операнда.

Импликация — логическая операция следования (A→B), ложная только при истинной посылке и ложном следствии.

Эквивалентность — логическая операция равнозначности (A↔B), истинная тогда, когда оба операнда имеют одинаковое значение.

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

Заключение

Алгебра логики предоставляет строгий математический аппарат для работы с высказываниями: базовые операции — отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность — вместе с их таблицами истинности позволяют формально анализировать и вычислять любые сколь угодно сложные составные высказывания. Этот аппарат лежит в основе не только решения текстовых логических задач, но и устройства самих компьютеров, в которых логические элементы, построенные на тех же операциях И, ИЛИ и НЕ, реализуют вычисления на аппаратном уровне. Изучив измерение, кодирование и хранение информации, а также логические основы её обработки, мы завершаем рассмотрение раздела «Измерение и кодирование информации».