Таблица истинности — таблица, описывающая логическую функцию.
Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность.
Например, в двузначной логике они могут принимать значения «истина» либо «ложь» (
t
r
u
e
{\displaystyle true}
либо
f
a
l
s
e
{\displaystyle false}
,
1
{\displaystyle 1}
либо
0
{\displaystyle 0}
).
Табличное задание функций встречается не только в логике, но и в логических функциях. Таблицы оказались довольно удобными, и с начала XX века за ними закрепилось это специальное название. Особенно часто таблицы истинности применяются в булевой алгебре .
Таблицы истинности для основных двоичных логических функций
править
Полная таблица истинности для двух элементов
Область определения аргументов и область значения двоичных логических функций принадлежат множеству
{
0
,
1
}
{\displaystyle \{0,1\}}
и принято, что
0
<
1
{\displaystyle 0<1}
.
Двоичные логические функции 1 переменной (унарные)
править
Идентичность
(логическая тождественность)
a
{\displaystyle a}
i
d
(
a
)
{\displaystyle \mathrm {id} (a)}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
i
d
(
a
)
{\displaystyle \mathrm {id} (a)}
истинно, если
a
{\displaystyle a}
истинно;
ложно, если
a
{\displaystyle a}
ложно
Отрицание
(НЕ, NOT, логическая инверсия)
a
{\displaystyle a}
¬
a
{\displaystyle \neg a}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
0
{\displaystyle 0}
¬
a
{\displaystyle \neg a}
истинно, если
a
{\displaystyle a}
ложно;
ложно, если
a
{\displaystyle a}
истинно
Двоичные логические функции 2 переменных
править
Конъюнкция
(И, AND, & логическое умножение)
a
{\displaystyle a}
b
{\displaystyle b}
a
∧
b
{\displaystyle a\land b}
0
{\displaystyle 0}
0
{\displaystyle 0}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
a
∧
b
{\displaystyle a\land b}
истинно, если истинно
a
{\displaystyle a}
и истинно
b
{\displaystyle b}
Дизъюнкция
(ИЛИ, OR, логическое сложение)
a
{\displaystyle a}
b
{\displaystyle b}
a
∨
b
{\displaystyle a\lor b}
0
{\displaystyle 0}
0
{\displaystyle 0}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
a
∨
b
{\displaystyle a\lor b}
истинно, если истинно
a
{\displaystyle a}
или истинно
b
{\displaystyle b}
Эквиваленция
(EQ, XNOR, логическая равнозначность)
a
{\displaystyle a}
b
{\displaystyle b}
a
↔
b
{\displaystyle a\leftrightarrow b}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
a
↔
b
{\displaystyle a\leftrightarrow b}
истинно, если
a
=
b
{\displaystyle a=b}
Исключающее «или»
(XOR, логическая неравнозначность)
a
{\displaystyle a}
b
{\displaystyle b}
a
⊕
b
{\displaystyle a\oplus b}
0
{\displaystyle 0}
0
{\displaystyle 0}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
0
{\displaystyle 0}
a
⊕
b
{\displaystyle a\oplus b}
истинно, если
a
≠
b
{\displaystyle a\neq b}
Импликация
(логическое неравенство «не более»)
a
{\displaystyle a}
b
{\displaystyle b}
a
→
b
{\displaystyle a\rightarrow b}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
a
→
b
{\displaystyle a\rightarrow b}
истинно, если
a
⩽
b
{\displaystyle a\leqslant b}
Обратная импликация
(логическое неравенство «не менее»)
a
{\displaystyle a}
b
{\displaystyle b}
a
←
b
{\displaystyle a\leftarrow b}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
a
←
b
{\displaystyle a\leftarrow b}
истинно, если
a
⩾
b
{\displaystyle a\geqslant b}
Штрих Шеффера
(И-НЕ, NAND, инверсия конъюнкции)
a
{\displaystyle a}
b
{\displaystyle b}
a
∣
b
{\displaystyle a\mid b}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
1
{\displaystyle 1}
0
{\displaystyle 0}
a
∣
b
{\displaystyle a\mid b}
истинно, если ложно
a
{\displaystyle a}
или ложно
b
{\displaystyle b}
Стрелка Пирса
(ИЛИ-НЕ, NOR, инверсия дизъюнкции)
a
{\displaystyle a}
b
{\displaystyle b}
a
↓
b
{\displaystyle a\downarrow b}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
1
{\displaystyle 1}
0
{\displaystyle 0}
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
0
{\displaystyle 0}
a
↓
b
{\displaystyle a\downarrow b}
истинно, если ложно
a
{\displaystyle a}
и ложно
b
{\displaystyle b}
Двоичные логические функции 3 переменных (тернарные)
править
Условная дизъюнкция
a
{\displaystyle a}
b
{\displaystyle b}
c
{\displaystyle c}
[
a
,
b
,
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
Истинность функции
[
a
,
b
,
c
]
{\displaystyle [a,b,c]}
определяется по формуле: «если значение
a
{\displaystyle a}
истинно, то результатом функции будет значение
b
{\displaystyle b}
, иначе — значение
c
{\displaystyle c}
», что соответствует тернарной условной операции .
Помимо условной дизъюнкции существуют и другие функционально полные тернарные операции.
Размер двоичной таблицы истинности
править
Если дано n входных параметров двоичной функции, то можно описать 2n возможных комбинаций входных параметров. Так как функции возвращают значения истина или ложь для каждой комбинации, то количество различных функций (таблиц истинности) от n переменных равны значению двойной экспоненциальной функции 22n .
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
}
{\displaystyle \{0,1,2\}}
и принято, что
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. — (Математическая логика и основания математики).