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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эквиваленция (EQ, XNOR, логическая равнозначность) $a$ $b$ $a\leftrightarrow b$ $0$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ $0$ $1$ $1$ $1$ $a\leftrightarrow b$ истинно, если $a=b$

Исключающее «или» (XOR, логическая неравнозначность) $a$ $b$ $a\oplus b$ $0$ $0$ $0$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$ $a\oplus b$ истинно, если $a\neq b$

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

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

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

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

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

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

$a$	$b$	$c$	$[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

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

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

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

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

n	2n	22n
0	1	2
1	2	4
2	4	16
3	8	256
4	16	65,536
5	32	4,294,967,296	≈ 4.3⋅109
6	64	18,446,744,073,709,551,616	≈ 1.8⋅1019
7	128	340 282 366 920 938 500 000 000 000 000 000 000 000	≈ 3.4⋅1038
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⋅1077

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

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

Область определения аргументов и область значения троичных логических функций принадлежат множеству $\{0,1,2\}$ и принято, что $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. — (Математическая логика и основания математики).

Ссылки

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