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

В этой статье вы сможете узнать:

• какие логические операции существуют и как они обозначаются;
• как построить таблицу истинности для логического выражения;
• в каком порядке выполняются логические операции при отсутствии скобок.

Логическое высказывание

Логическое высказывание — это утверждение, которое может быть либо истинным (1, True), либо ложным (0, False), и не может быть одновременно и тем, и другим. Логические операции позволяют строить сложные высказывания из простых.

Отрицание (инверсия)

Отрицание меняет значение высказывания на противоположное. Обозначается чертой над выражением ($\overline{A}$) или словом «не»/NOT.

Конъюнкция (логическое умножение, «И»)

Конъюнкция истинна только тогда, когда истинны оба операнда. Обозначается $A \wedge B$, $A \cdot B$ или AND.

Дизъюнкция (логическое сложение, «ИЛИ»)

Дизъюнкция истинна, если истинен хотя бы один из операндов. Обозначается $A \vee B$ или OR.

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

Импликация $A \rightarrow B$ («если $A$, то $B$») ложна только в одном случае — когда $A$ истинно, а $B$ ложно; во всех остальных случаях она истинна.

Важно запомнить: из ложного посылки следует что угодно — импликация с ложным $A$ всегда истинна.

Эквивалентность (равнозначность)

Эквивалентность $A \leftrightarrow B$ истинна тогда и только тогда, когда значения $A$ и $B$ совпадают.

Исключающее ИЛИ (сложение по модулю два, XOR)

Операция XOR ($A \oplus B$) истинна, если значения $A$ и $B$ различны, — это отрицание эквивалентности.

Приоритет выполнения операций

При отсутствии скобок логические операции выполняются в следующем порядке (от высшего приоритета к низшему):

1. Отрицание ($\overline{A}$)
2. Конъюнкция ($\wedge$)
3. Дизъюнкция ($\vee$)
4. Исключающее ИЛИ ($\oplus$)
5. Импликация ($\rightarrow$)
6. Эквивалентность ($\leftrightarrow$)

Операции одного приоритета выполняются слева направо; скобки всегда меняют порядок вычисления, как и в обычной арифметике.

Построение таблицы истинности

Чтобы построить таблицу истинности для выражения с $n$ переменными, нужно перебрать все возможные комбинации значений этих переменных — их будет $2^n$. Столбцы таблицы обычно располагают в порядке вычисления промежуточных результатов, от простых подвыражений к итоговому выражению.

Пример. Постройте таблицу истинности для выражения $\overline{A} \vee (B \wedge A)$.

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

1. Определите количество переменных $n$ в выражении и вычислите число строк таблицы: $2^n$.
2. Запишите все возможные комбинации значений переменных, обычно в порядке возрастания двоичного числа (от 00…0 до 11…1).
3. Определите порядок выполнения операций с учётом скобок и приоритета (отрицание → конъюнкция → дизъюнкция → импликация → эквивалентность).
4. Добавьте в таблицу промежуточные столбцы для каждого подвыражения в порядке их вычисления.
5. Вычислите итоговый столбец, комбинируя значения промежуточных столбцов согласно последней операции в выражении.

Примеры решения

Пример 1. Вычислите значение выражения $A \wedge \overline{B} \vee C$ при $A=1$, $B=0$, $C=0$.

Сначала отрицание: $\overline{B} = \overline{0} = 1$.

Затем конъюнкция (более высокий приоритет, чем дизъюнкция): $A \wedge \overline{B} = 1 \wedge 1 = 1$.

Затем дизъюнкция: $1 \vee C = 1 \vee 0 = 1$.

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

Пример 2. Для какого набора значений $A$ и $B$ импликация $A \rightarrow B$ ложна?

Импликация ложна только тогда, когда $A$ истинно, а $B$ ложно.

Ответ: $A=1$, $B=0$.

Пример 3. Постройте таблицу истинности для $A \rightarrow (B \vee \overline{A})$ и определите, является ли выражение тождественно истинным.

Ответ: выражение не тождественно истинно, так как при $A=1$, $B=0$ оно ложно.

Часто задаваемые вопросы

Почему импликация с ложной посылкой всегда истинна? Это соглашение классической логики: высказывание «если $A$, то $B$» считается ложным только тогда, когда обещание нарушено — то есть когда $A$ выполнено, а $B$ нет; если же $A$ вообще не выполнено, условие импликации не нарушается, и она автоматически считается истинной.

Чем эквивалентность отличается от исключающего ИЛИ? Это взаимно противоположные операции: эквивалентность истинна, когда значения операндов совпадают, а исключающее ИЛИ (XOR) истинно, когда значения операндов различаются — фактически XOR является отрицанием эквивалентности.

Как запомнить порядок выполнения логических операций? Можно использовать мнемонику по аналогии с арифметикой: отрицание похоже на унарный минус (выполняется первым), конъюнкция — как умножение, дизъюнкция — как сложение, а импликация и эквивалентность имеют самый низкий приоритет и выполняются в последнюю очередь.

Сколько строк будет в таблице истинности для выражения с 4 переменными? Число строк равно $2^4=16$, поскольку каждая из 4 переменных может принимать одно из двух значений (0 или 1), и нужно перебрать все возможные комбинации.

Похожие темы для изучения

• Законы алгебры логики и упрощение выражений
• Таблицы истинности и логические схемы
• Кодирование и измерение информации
• Системы счисления: перевод чисел между системами

Задачи для самостоятельного решения

1. Постройте таблицу истинности для выражения $A \vee \overline{B}$.
2. Вычислите значение выражения $(A \wedge B) \vee \overline{C}$ при $A=0$, $B=1$, $C=0$.
3. Определите, при каких значениях $A$ и $B$ эквивалентность $A \leftrightarrow B$ ложна.
4. Постройте таблицу истинности для выражения $A \rightarrow B \rightarrow C$ (учитывая, что импликация выполняется слева направо).
5. Упростите вычисление выражения $\overline{A \wedge A}$ для любого значения $A$, не используя таблицу истинности.
6. Объясните, почему выражения $A \rightarrow B$ и $\overline{A} \vee B$ имеют одинаковые таблицы истинности.