Логические операции
Логические операции применяют к высказываниям и получают новое высказывание с определённым значением истинности. В этой теме сравниваются отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность: их смысл, обозначения, приоритеты и таблицы истинности.
Базовые понятия и обозначения
Высказывание — это повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно. Значение 1 обозначает «истина», а значение 0 — «ложь». Обозначим простые высказывания буквами \(A\), \(B\), \(C\).
Логическая операция — правило построения нового высказывания из одного или нескольких исходных высказываний. Полученное высказывание называют сложным, а исходные — простыми или составляющими.
| Операция | Смысл | Обозначения | Число аргументов |
|---|---|---|---|
| Отрицание | не \(A\) | \(\neg A\), \(\overline{A}\) | 1 |
| Конъюнкция | \(A\) и \(B\) | \(A\land B\), \(A\cdot B\) | 2 |
| Дизъюнкция | \(A\) или \(B\) | \(A\lor B\), \(A+B\) | 2 |
| Импликация | если \(A\), то \(B\) | \(A\to B\) | 2 |
| Эквивалентность | \(A\) тогда и только тогда, когда \(B\) | \(A\leftrightarrow B\), \(A\sim B\) | 2 |
В русском языке слово «или» иногда означает выбор только одного варианта, но в математической логике дизъюнкция обычно нестрогая: \(A\lor B\) истинно и тогда, когда истинны оба высказывания. Поэтому смысл связки нужно определять по её таблице истинности или по условию задачи.
Для конъюнкции достаточно одной ложной части, чтобы всё выражение стало ложным. Для дизъюнкции достаточно одной истинной части, чтобы всё выражение стало истинным.
Таблицы истинности основных операций
Таблица истинности перечисляет все наборы значений переменных и показывает результат операции. Для двух переменных наборов \(2^2=4\), поэтому в таблице бинарной операции четыре строки.
| A | B | \(A\land B\) | \(A\lor B\) | \(A\to B\) | \(A\leftrightarrow B\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Отдельная таблица для отрицания содержит одну переменную и два возможных значения.
| A | \(\neg A\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
Импликация \(A\to B\) ложна только в одном случае: когда условие \(A\) истинно, а следствие \(B\) ложно. Во всех остальных случаях импликация истинна.
Эквивалентность истинна, когда значения \(A\) и \(B\) совпадают. Её можно понимать как равенство истинностных значений двух высказываний.
При каких значениях \(A\) и \(B\) выражение \(A\to B\) ложно?
Приоритет операций
Если в выражении нет скобок, операции выполняются в установленном порядке. Приоритет нужен, чтобы одинаково разобрать выражение и не менять его смысл.
- Отрицание: \(\neg A\).
- Конъюнкция: \(A\land B\) или \(A\cdot B\).
- Дизъюнкция: \(A\lor B\) или \(A+B\).
- Импликация: \(A\to B\).
- Эквивалентность: \(A\leftrightarrow B\).
Скобки имеют приоритет над всеми операциями и выполняются первыми. Например, \(\neg A\lor B\land C\) читается как \(\neg A\lor(B\land C)\), а не как \((\neg A\lor B)\land C\).
Сначала раскрывают скобки изнутри, затем выполняют отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности. Если одинаковые операции стоят рядом, их обычно вычисляют слева направо, но лучше явно расставлять скобки.
Не путайте приоритет и смысл операции. Знак «+» в булевой алгебре означает дизъюнкцию, а не обычное сложение. Импликация не является обычным условием из повседневной речи: она ложна только при \(1\to0\). Дизъюнкция включает случай \(1\lor1=1\).
Разбор выражения по шагам
Построим таблицу истинности выражения \(F=\neg A\lor B\land A\). Сначала учитываем приоритет: отрицание, затем конъюнкция, затем дизъюнкция.
Найдём значение \(F\) при \(A=0\) и \(B=1\), а затем проверим результат преобразованием выражения.
Если требуется не одно значение, а полная таблица, добавляют отдельные столбцы для промежуточных частей: \(\neg A\), \(B\land A\), затем итоговое \(F\). Такой способ уменьшает вероятность ошибки.
| \(A\) | \(B\) | \(\neg A\) | \(B\land A\) | \(F=\neg A\lor(B\land A)\) |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
Полезные равносильности
Равносильные выражения принимают одинаковые значения при любом наборе переменных. Проверять равносильность можно преобразованиями или таблицей истинности. Для отрицания сложных выражений особенно важны законы де Моргана.
Количество строк таблицы зависит от числа различных переменных: для \(n\) переменных будет \(2^n\) наборов. Поэтому при трёх переменных нужно 8 строк, при четырёх — 16. Сначала полезно выписать все наборы в устойчивом порядке: старшая переменная меняется реже, младшая — чаще.
- Логическая связка соединяет высказывания или изменяет одно из них.
- При построении выражения по условию сначала выделяют простые высказывания, затем выбирают связки и расставляют скобки.
- Количество применённых связок и операций рассматривается отдельно: это важно для страницы количество логических операций.
- Свойства операций и их классификация подробнее разобраны на страницах классификация логических связок и полная система логических функций.
Перед вычислением подчеркните главную операцию выражения и подпишите промежуточные столбцы. Для импликации сразу отметьте строку \(1\to0\) как единственную ложную; для эквивалентности — строки с одинаковыми значениями.
Быстрая проверка
Главное
- Основные связки: отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность.
- Импликация ложна только при \(A=1\), \(B=0\); эквивалентность истинна при совпадении значений.
- Приоритет: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность; скобки выполняются первыми.
- Для \(n\) переменных таблица истинности содержит \(2^n\) строк.
- Промежуточные столбцы и явные скобки помогают без ошибок вычислять сложные выражения.