Таблица истинности - NiNa.Az

Запрос «Значение истинности»^[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	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²ⁿ.

n	2^n	2^2n		Цифры
0	1	2	≈ 2.00⋅10^0	1
1	2	4	≈ 4.00⋅10^0	1
2	4	16	≈ 1.60⋅10^1	2
3	8	256	≈ 2.56⋅10^2	3
4	16	65 536	≈ 6.55⋅10^4	5
5	32	4 294 967 296	≈ 4.29⋅10^9	10
6	64	18 446 744 073 709 552 000	≈ 1.84⋅10^19	20
7	128	340 282 366 920 938 500 000 000 000 000 000 000 000	≈ 3.40⋅10^38	39
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.16⋅10^77	78
9	512	13 407 807 929 942 597 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000	≈ 1.34⋅10^154	155
10	1024	∞	≈ 1.80⋅10^308	309
11	2048	∞	≈ 3.23⋅10^616	617
12	4096		1.04⋅10^1233	1234
13	8192		1.09⋅10^2466	2467
14	16 384		1.19⋅10^4932	4933
15	32 768		1.41⋅10^9864	9865
16	65 536		2.00⋅10^19 728	19 729
17	131 072		4.01⋅10^39 456	39 457
18	262 144		1.61⋅10^78 913	78 914
19	524 288		2.60⋅10^157 826	157 827
20	1 048 576		6.74⋅10^315 652	315 653
21	2 097 152		4.54⋅10^631 305	631 306
22	4 194 304		2.07⋅10^1 262 611	1 262 612
23	8 388 608		4.26⋅10^2 525 222	2 525 223
24	16 777 216		1.82⋅10^5 050 445	5 050 446
25	33 554 432		3.31⋅10^10 100 890	10 100 891
26	67 108 864		1.10⋅10^20 201 781	20 201 782
27	134 217 728		1.20⋅10^40 403 562	40 403 563
28	268 435 456		1.43⋅10^80 807 124	80 807 125
29	536 870 912		2.05⋅10^161 614 248	161 614 249
30	1 073 741 824		4.20⋅10^323 228 496	323 228 497
31	2 147 483 648		1.76⋅10^646 456 993	646 456 994
32	4 294 967 296		3.10⋅10^1 292 913 986	1 292 913 987

Таблицы истинности для функций 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. — (Математическая логика и основания математики).

Ссылки

• Построение таблиц истинности онлайн  (неопр.). Архивировано из оригинала 12 апреля 2014 года.
• Онлайн инструменты по математической логике