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

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

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

Табличное задание функций встречается не только в логике, но и в логических функциях. Таблицы оказались довольно удобными, и с начала 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 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

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

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

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

править

Если дано 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 и более переменных встречаются редко.

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

править

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

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

Ссылки

править