Таблица истинности

Запрос «Значение истинности»^[d] перенаправляется сюда. На эту тему нужно создать отдельную статью.

Таблица истинности — таблица, описывающая логическую функцию.

Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь» (${\displaystyle true}$ либо ${\displaystyle false}$, ${\displaystyle 1}$ либо ${\displaystyle 0}$).

Табличное задание функций встречается не только в логике, но и в логических функциях. Таблицы оказались довольно удобными, и с начала XX века за ними закрепилось это специальное название. Особенно часто таблицы истинности применяются в булевой алгебре.

Таблицы истинности для основных двоичных логических функций

Полная таблица истинности для двух элементов

Область определения аргументов и область значения двоичных логических функций принадлежат множеству ${\displaystyle \{0,1\}}$ и принято, что ${\displaystyle 0<1}$.

Двоичные логические функции 1 переменной (унарные)

Идентичность (логическая тождественность) ${\displaystyle a}$ ${\displaystyle \mathrm {id} (a)}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle \mathrm {id} (a)}$ истинно, если ${\displaystyle a}$ истинно; ложно, если ${\displaystyle a}$ ложно

Отрицание (НЕ, NOT, логическая инверсия) ${\displaystyle a}$ ${\displaystyle \neg a}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle \neg a}$ истинно, если ${\displaystyle a}$ ложно; ложно, если ${\displaystyle a}$ истинно

Двоичные логические функции 2 переменных

Конъюнкция (И, AND, & логическое умножение) ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\land b}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle a\land b}$ истинно, если истинно ${\displaystyle a}$ и истинно ${\displaystyle b}$

Дизъюнкция (ИЛИ, OR, логическое сложение) ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\lor b}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle a\lor b}$ истинно, если истинно ${\displaystyle a}$ или истинно ${\displaystyle b}$

								Исключающее «или» (XOR, логическая неравнозначность) ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\oplus b}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle a\oplus b}$ истинно, если ${\displaystyle a\neq b}$	Эквиваленция (EQ, XNOR, логическая равнозначность) ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\leftrightarrow b}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle a\leftrightarrow b}$ истинно, если ${\displaystyle a=b}$

Импликация (логическое неравенство «не более») ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\rightarrow b}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle a\rightarrow b}$ истинно, если ${\displaystyle a\leqslant b}$

Обратная импликация (логическое неравенство «не менее») ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\leftarrow b}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle a\leftarrow b}$ истинно, если ${\displaystyle a\geqslant b}$

Штрих Шеффера (И-НЕ, NAND, инверсия конъюнкции) ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\mid b}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle a\mid b}$ истинно, если ложно ${\displaystyle a}$ или ложно ${\displaystyle b}$

Стрелка Пирса (ИЛИ-НЕ, NOR, инверсия дизъюнкции) ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\downarrow b}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle a\downarrow b}$ истинно, если ложно ${\displaystyle a}$ и ложно ${\displaystyle b}$

Двоичные логические функции 3 переменных (тернарные)

Условная дизъюнкция

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle c}$	${\displaystyle [a,b,c]}$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Истинность функции ${\displaystyle [a,b,c]}$ определяется по формуле: «если значение ${\displaystyle a}$ истинно, то результатом функции будет значение ${\displaystyle b}$, иначе — значение ${\displaystyle c}$», что соответствует тернарной условной операции.

Помимо условной дизъюнкции существуют и другие функционально полные тернарные операции.

Размер двоичной таблицы истинности

Если дано n входных параметров двоичной функции, то можно описать 2^n возможных комбинаций входных параметров. Так как функции возвращают значения истина или ложь для каждой комбинации, то количество различных функций (таблиц истинности) от n переменных равны значению двойной экспоненциальной функции 2^2n.

n	2^n	2^2n
0	1	2
1	2	4
2	4	16
3	8	256
4	16	65 536
5	32	4 294 967 296	≈ 4.3⋅10^9
6	64	18 446 744 073 709 551 616	≈ 1.8⋅10^19
7	128	340 282 366 920 938 500 000 000 000 000 000 000 000	≈ 3.4⋅10^38
8	256	115 792 089 237 316 200 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000	≈ 1.2⋅10^77

Таблицы истинности для функций 3 и более переменных встречаются редко.

Таблицы истинности для некоторых троичных логических функций

Область определения аргументов и область значения троичных логических функций принадлежат множеству ${\displaystyle \{0,1,2\}}$ и принято, что ${\displaystyle 0<1<2}$:

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
min(x,y)	2	1	0	1	1	0	0	0	0

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
max(x,y)	2	2	2	2	1	1	2	1	0

x	2	1	0	2	1	0	2	1	0
y	2	2	2	1	1	1	0	0	0
F2TN22310	0	0	0	0	2	2	0	2	1

Программирование

В программировании обозначение логических операций зависит от синтаксиса конкретного языка программирования, однако, зачастую, применяются следующие обозначения:

• Эквиваленция: =, ==
• Отрицание: NOT, НЕ, !
• Конъюнкция: AND, И, &, &&
• Дизъюнкция: OR, ИЛИ, |, ||
• Исключающее «или»: XOR, ^, ~

См. также

• Идентичность
• Отрицание
• Конъюнкция
• Дизъюнкция
• Импликация
• Обратная импликация
• Двоичные функции (Булевы)
• Троичные функции
• Алгебра логики
• Битовые операции
• Троичная логика
• Карта Карно

Литература

• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. — М.: Наука, 1966. — (Математическая логика и основания математики).

Ссылки

• Построение таблиц истинности онлайн
• Онлайн инструменты по математической логике