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

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

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

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

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

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

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

n	2ⁿ	2^2ⁿ
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⁹
6	64	18 446 744 073 709 551 616	≈ 1.8⋅10¹⁹
7	128	340 282 366 920 938 500 000 000 000 000 000 000 000	≈ 3.4⋅10³⁸
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⁷⁷

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

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

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

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

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

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

Ссылки