3.1. Алгебра логики

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

Логическое высказывание — предложение, о котором можно однозначно сказать, истинно оно или ложно. Например, утверждение «15 делится на 3» истинно, а «15 делится на 2» ложно. Это понятие нужно, чтобы отличать проверяемые утверждения от вопросов и команд.

Логическая переменная — переменная, принимающая одно из двух значений: 0 или 1. Обычно буквами A, B, C обозначают высказывания, а числами записывают их значения: 1 означает истину, 0 — ложь. Переменные позволяют записывать рассуждения коротко, не повторяя каждый раз длинные фразы.

Логическая операция — действие над логическими величинами, образующее новое значение. Например, можно соединить два высказывания союзом «И» или изменить значение одного высказывания на противоположное. Операции нужны, чтобы строить и проверять составные утверждения.

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

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

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

Из простых высказываний получают составные, соединяя их логическими операциями. Например, из «идёт дождь» и «дует ветер» можно составить утверждение «идёт дождь и дует ветер». Оно описывает условие, которое зависит сразу от двух частей, поэтому для проверки нужно знать значение каждой из них.

Отрицание обозначают ¬: оно меняет истину на ложь, а ложь на истину. Конъюнкция ∧ соответствует союзу «И» и истинна только при истинности обоих операндов — так называют значения, над которыми выполняют операцию. Дизъюнкция ∨ соответствует «ИЛИ» и ложна лишь тогда, когда оба операнда ложны; поэтому смысл каждой операции задаёт конкретное правило для её входных значений.

Таблица истинности перечисляет все возможные наборы значений переменных и показывает результат выражения для каждого набора. Каждая из n переменных может принимать два значения, поэтому наборов получается 2ⁿ: например, для A и B это 2² = 4 варианта. Если пропустить хотя бы один набор, проверка окажется неполной и можно не заметить, что выражение даёт другой результат.

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

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

В таблице собраны правила операций и порядок действий. Запись «когда результат равен 1» помогает определить, в каких случаях выражение истинно; остальные случаи дают 0. Проверяйте значения операндов слева направо, а для составного выражения сначала найдите значения подвыражений.

Разбор задач

Задача 1. Определить значение высказывания «15 делится на 3» и записать его как логическую величину. Сначала проверим само утверждение: нужно выяснить, существует ли целое частное при делении 15 на 3. Поскольку 15 : 3 = 5, высказывание истинно.

1. Проверяем деление: 15 : 3 = 5.
2. Убеждаемся, что частное — целое число, значит, 15 действительно делится на 3.
3. Записываем истину логическим значением 1.

Ответ: высказывание истинно, его значение равно 1. Если бы утверждение оказалось ложным, вместо 1 записали бы 0.

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

1. Записываем все наборы: (A, B) = (0, 0), (0, 1), (1, 0), (1, 1).
2. Находим ¬B для каждого набора: 1, 0, 1, 0.
3. Выполняем A ∧ ¬B: результат равен 1 только в строке, где A = 1 и ¬B = 1.

Ответ: значения выражения по порядку строк — 0, 0, 1, 0. Единственная единица появляется в наборе A = 1, B = 0, так как только тогда оба операнда конъюнкции истинны.

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

1. В скобках: A ∨ B = 0 ∨ 1 = 1.
2. Вычисляем отрицание: ¬C = ¬0 = 1.
3. Соединяем результаты: 1 ∧ 1 = 1.

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

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

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

При отрицании иногда меняют 1 на 0, но забывают, что 0 тоже должно измениться на противоположное значение. Это происходит, если запомнить только один пример вместо общего правила. Для проверки составьте обе пары: ¬1 = 0 и ¬0 = 1.

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

Операции иногда выполняют в удобном для себя порядке, не обращая внимания на скобки и приоритет. Из-за этого можно сначала соединить не те части выражения и получить другое значение. Проверьте запись по шагам: скобки, отрицание, конъюнкция, дизъюнкция; промежуточные результаты удобно подписывать.

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

Для изучения алгебры логики нужно уметь различать истинные и ложные утверждения, понимать, что обозначает переменная, и следить за скобками в выражении. Эти навыки помогают верно прочитать запись и не спутать порядок действий. Если смысл переменной непонятен, сначала уточните, какое высказывание она обозначает.

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

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

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

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