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

Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь» ( ${\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}$

Эквиваленция (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}$

Исключающее «или» (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}$

Импликация (логическое неравенство "не более") ${\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	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

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

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

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

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

n	2 n	2 2 n
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. — (Математическая логика и основания математики).

Ссылки