Ru.Wikipedia.Org - Таблица истинности

Меню
Главная
Случайная статья
Настройки

Таблица истинности
Материал из https://ru.wikipedia.org

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

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

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$

Исключающее «или»

(XOR, логическая неравнозначность)

$a$	$b$	$a\oplus b$
$0$	$0$	$0$
$0$	$1$	$1$
$1$	$0$	$1$
$1$	$1$	$0$
$a\oplus b$ истинно, если $a\neq 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$

Импликация

(логическое неравенство «не более»)

$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	2.010⁰
1	2	4	4.010⁰
2	4	16	1.610¹
3	8	256	2.610²
4	16	65 536	6.610⁴
5	32	4 294 967 296	4.310⁹
6	64	18 446 744 073 709 552 000	1.810¹⁹
7	128	340 282 366 920 938 500 000 000 000 000 000 000 000	3.410³⁸
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.210⁷⁷

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

Ссылки

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