Таблица истинности составных высказываний
Табли́ца и́стинности составны́х выска́зываний — способ наглядно представить, как значение составного высказывания зависит от значений входящих в него простых высказываний. В классической логике каждое простое высказывание может принимать одно из двух значений: 1 (истина) или 0 (ложь).
Истинность составных высказываний, образованных в результате выполнения каких-либо логических операций над простыми высказываниями, зависит только от истинности исходных высказываний. Определить истинность составного высказывания, если известны значения истинности входящих в него элементарных высказываний, можно с помощью построения таблицы истинности.
Таблица истинности устанавливает соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию, и значениями функции[1].
Основные понятия
Под высказыванием понимается повествовательное предложение, которое является либо истинным, либо ложным, но не тем и другим сразу.
Логика высказываний, или пропозициональная логика, изучает способы математических рассуждений о высказываниях.
Высказывания могут быть простыми (неделимыми) или составными.
Примеры простых высказываний: «4 — чётное число», «5 — нечётное число», «идёт дождь», «я прогуливаюсь».
Примеры составных высказываний: «4 — чётное число, а 5 — нечётное число», «если идёт дождь, то я не прогуливаюсь».
В этих примерах курсивом выделены слова, связывающие высказывания для образования составных высказываний.
Из последнего составного высказывания и высказывания «идёт дождь» можно заключить, что «я не прогуливаюсь»; причём это рассуждение считается правильным. Из того же составного высказывания и высказывания «я прогуливаюсь», можно вывести «не идёт дождь»; и это рассуждение считается правильным[2].
Таблица истинности — это таблица, описывающая логическую функцию. Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь» (либо, либо).
Табличное задание функций встречается не только в логике, но и в логических функциях. Таблицы оказались довольно удобными, и с начала XX века за ними закрепилось это специальное название. Таблицы истинности нужны, чтобы[1]:
- Проверить, является ли формула тавтологией (всегда истинна).
- Установить эквивалентность двух формул (их таблицы совпадают).
- Найти контрпримеры (наборы значений, при которых формула ложна).
- Упростить логические выражения.
- Проанализировать условия в программировании и схемотехнике.
Таблицы для базовых логических операций
- Отрицание (инверсия, «НЕ», ¬) — унарная операция (действует на одно высказывание).
| A | ¬A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Результат противоположен исходному значению.
- Конъюнкция (логическое «И», ∧, &) — бинарная операция (действует на два высказывания).
| A | B | A∧B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат «1» только если оба операнда «1»; иначе — «0».
- Дизъюнкция (логическое «ИЛИ», ∨) — бинарная операция.
| A | B | A∨B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Результат «1», если хотя бы один операнд «1»; только «0∨0» даёт «0».
- Импликация («ЕСЛИ… ТО», →) — бинарная операция.
| A | B | A→B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат «0» только в случае «1→0» (из истины следует ложь); во всех остальных случаях — «1».
- Эквиваленция («ТОГДА И ТОЛЬКО ТОГДА», ~, ↔) — бинарная операция.
| A | B | A↔B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат «1», если значения операндов совпадают (оба «0» или оба «1»); иначе — «0».
Построение таблицы истинности для составных высказываний
Для построения таблицы истинности для составных высказываний нужно:
- Определить число переменных (операндов). Если их n, то число строк в таблице — 2n (все возможные комбинации 0 и 1).
- Перечислить все комбинации значений переменных. Например, для A и B: (0,0), (0,1), (1,0), (1,1).
- Выполнять операции по приоритету:
- скобки (если есть);
- отрицание (¬);
- конъюнкция (∧);
- дизъюнкция (∨);
- импликация (→);
- эквиваленция (↔).
- Заполнить столбцы для каждой подформулы, двигаясь от простых операций к сложным.
- Последний столбец — итоговое значение всего выражения.
Выражение: (A∧B)→¬C
Шаг 1. Переменных — 3 (A, B, C), значит, строк — 2³=8.
Шаг 2. Перечислить все комбинации A, B, C:
| № | A | B | C |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 |
| 3 | 0 | 1 | 0 |
| 4 | 0 | 1 | 1 |
| 5 | 1 | 0 | 0 |
| 6 | 1 | 0 | 1 |
| 7 | 1 | 1 | 0 |
| 8 | 1 | 1 | 1 |
Шаг 3. Добавить столбцы для подформул:
- A∧B (конъюнкция A и B);
- ¬C (отрицание C);
- (A∧B)→¬C (импликация).
Итоговая таблица:
| A | B | C | A∧B | ¬C | (A∧B)→¬C |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Вывод: выражение ложно только в одном случае — когда A=1, B=1, C=1.