Interested Article - Таблица истинности

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

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

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

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

Таблица истинности, содержащая в шестнадцати столбцах и четырёх строках битовые значения, и операции над ними
Полная таблица истинности для двух элементов

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

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

Идентичность

(логическая тождественность)

истинно, если истинно;

ложно, если ложно

Отрицание

(НЕ, NOT, логическая инверсия)

истинно, если ложно;

ложно, если истинно

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

Конъюнкция

(И, AND, & логическое умножение)

истинно, если истинно и истинно
Дизъюнкция

(ИЛИ, OR, логическое сложение)

истинно, если истинно или истинно
Эквиваленция

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

истинно, если
Исключающее «или»

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

истинно, если
Импликация

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

истинно, если
Обратная импликация

(логическое неравенство "не менее")

истинно, если
Штрих Шеффера

(И-НЕ, NAND, инверсия конъюнкции)

истинно, если ложно или ложно
Стрелка Пирса

(ИЛИ-НЕ, NOR, инверсия дизъюнкции)

истинно, если ложно и ложно

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

Условная дизъюнкция
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

Истинность функции определяется по формуле: "если значение истинно, то результатом функции будет значение , иначе - значение ", что соответствует тернарной условной операции .

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

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

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

n 2 n 2 2 n
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 9
6 64 18,446,744,073,709,551,616 ≈ 1.8⋅10 19
7 128 340 282 366 920 938 500 000 000 000 000 000 000 000 ≈ 3.4⋅10 38
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 77

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

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

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

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

Ссылки

Источник —

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