Таблица истинности - Truth table

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

Таблица истинности имеет один столбец для каждой входной переменной (например, P и Q) и один последний столбец, показывающий все возможные результаты логической операции, которую представляет таблица (например, P XOR Q). Каждая строка таблицы истинности содержит одну возможную конфигурацию входных переменных (например, P = true Q = false) и результат операции для этих значений. См. Примеры ниже для дальнейшего пояснения. Людвигу Витгенштейну приписывают изобретение и популяризацию таблицы истинности в его « Логико-философском трактате» , который был завершен в 1918 году и опубликован в 1921 году. Такая система была также независимо предложена в 1921 году Эмилем Леоном Постом . Еще более ранняя итерация таблицы истинности была также обнаружена в неопубликованных рукописях Чарльза Сандерса Пирса 1893 года, предшествующих обеим публикациям почти на 30 лет.

Унарные операции

Есть 4 унарные операции:

  • Всегда правда
  • Никогда не правда, унарная ложь
  • Унарная идентичность
  • Унарное отрицание

Логическая правда

Выходное значение всегда истинно, независимо от входного значения p.

Логическая истина
п Т
Т Т
F Т

Логическая ложь

Выходное значение никогда не бывает истинным: то есть всегда ложно, независимо от входного значения p.

Логическая ложь
п F
Т F
F F

Логическая идентичность

Логическая идентичность - это операция над одним логическим значением p, для которого выходным значением остается p.

Таблица истинности для оператора логической идентичности выглядит следующим образом:

Логическая идентичность
п п
Т Т
F F

Логическое отрицание

Логическое отрицание - это операция над одним логическим значением , обычно значением предложения , которая производит значение true, если его операнд ложен, и значение false, если его операнд истинен.

Таблица истинности для НЕ p (также записываемая как ¬p , Np , Fpq или ~ p ) выглядит следующим образом:

Логическое отрицание
п ¬p
Т F
F Т

Бинарные операции

Существует 16 возможных функций истинности двух двоичных переменных :

Таблица истинности для всех бинарных логических операторов

Вот расширенная таблица истинности, дающая определения всех шестнадцати возможных функций истинности двух булевых переменных P и Q:

п q  F 0   NOR 1   2   ¬p 3   4   ¬q 5   XOR 6   NAND 7   И 8   XNOR 9  q 10 11 стр. 12 13 ИЛИ 14 Т 15
Т Т F F F F F F F F Т Т Т Т Т Т Т Т
Т F F F F F Т Т Т Т F F F F Т Т Т Т
F Т F F Т Т F F Т Т F F Т Т F F Т Т
F F F Т F Т F Т F Т F Т F Т F Т F Т
Com
Assoc
Adj F 0 NOR 1 4 ¬q 5 2 ¬p 3 XOR 6 NAND 7 И 8 XNOR 9 стр. 12 13 q 10 11 ИЛИ 14 Т 15
Отрицательный Т 15 ИЛИ 14 13 стр. 12 11 q 10 XNOR 9 И 8 NAND 7 XOR 6 ¬q 5 4 ¬p 3 2 NOR 1 F 0
Двойной Т 15 NAND 7 11 ¬p 3 13 ¬q 5 XNOR 9 NOR 1 ИЛИ 14 XOR 6 q 10 2 стр. 12 4 И 8 F 0
L id F F Т Т Т, Ж Т F
Избавлять F F Т Т Т, Ж Т F

куда

T = верно.
F = ложь.
Верхние индексы от 0 до 15 - это число, полученное в результате чтения четырех значений истинности как двоичного числа с F = 0 и T = 1.
Com строка указывает , является ли оператор, оп , является коммутативное - Р оп Q = Q оп Р .
Assoc строка указывает , является ли оператор, оп , является ассоциативно - (Р оп Q) , оп Р = Р оп (Q оп R) .
В строке Adj показан оператор op2 такой, что P op Q = Q op2 P
В строке Neg показан оператор op2 такой, что P op Q = ¬ (Q op2 P)
В Двойной ряд показывает двойной операции , полученный перестановкой Т с Р, а и с или.
В L ID ряд показывает оператор левых тождества , если она имеет какое - либо значение - я такие , что я оп Q = Q .
R ID строка показывает оператор правильных тождества , если он имеет какое - либо значение - я такие , что Р оп I = P .

Четыре комбинации входных значений для p, q считываются построчно из таблицы выше. Функция вывода для каждой комбинации p, q может быть прочитана построчно из таблицы.

Ключ:

Следующая таблица ориентирована по столбцам, а не по строкам. Здесь четыре столбца, а не четыре строки, для отображения четырех комбинаций p, q в качестве входных данных.

p : TTFF
q : TFTF

В этом ключе 16 строк, по одной строке для каждой двоичной функции двух двоичных переменных p, q. Например, в строке 2 этого ключа значение Converse nonimplication (' ') равно только T для столбца, обозначенного уникальной комбинацией p = F, q = T; в то время как в строке 2 значение этой операции равно F для трех оставшихся столбцов p, q. Выходная строка для , таким образом ,

2: БПФФ

а ключ на 16 строк -

оператор Название операции
0 (FFFF) (p, q) ложь , Opq Противоречие
1 (БПФ) (p, q) НИ pq , Xpq Логическое ИЛИ
2 (БПФФ) (p, q) pq , Мпк Конверс без импликации
3 (БПФТ) (p, q) ¬p , ~ p ¬p , Np , Fpq Отрицание
4 (FTFF) (p, q) pq , Lpq Существенное отсутствие импликации
5 (FTFT) (p, q) ¬q , ~ q ¬q , Nq , Гпк Отрицание
6 (FTTF) (p, q) XOR pq , Jpq Исключительная дизъюнкция
7 (FTTT) (p, q) NAND pq , Dpq Логическая И-НЕ
8 (TFFF) (p, q) А ТАКЖЕ pq , Kpq Логическое соединение
9 (TFFT) (p, q) XNOR p Если и только если q , Epq Логическая двусмысленность
10 (TFTF) (p, q) q q , Hpq Функция проекции
11 (TFTT) (p, q) pq если p, то q , Cpq Материальное значение
12 (TTFF) (p, q) п p , Ipq Функция проекции
13 (TTFT) (p, q) pq p, если q , Bpq Обратное значение
14 (TTTF) (p, q) ИЛИ pq , Apq Логическая дизъюнкция
15 (TTTT) (p, q) правда , Vpq Тавтология

Логические операторы также можно визуализировать с помощью диаграмм Венна .

Логическое соединение (И)

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

Таблица истинности для p И q (также записываемая как p ∧ q , Kpq , p & q или p q ) выглядит следующим образом:

Логическое соединение
п q pq
Т Т Т
Т F F
F Т F
F F F

В терминах обычного языка, если и p, и q истинны, то конъюнкция pq истинна. Для всех других присвоений логических значений p и q конъюнкция p  ∧  q ложна.

Также можно сказать, что если p , то pq равно q , иначе pq равно p .

Логическая дизъюнкция (ИЛИ)

Логическая дизъюнкция - это операция над двумя логическими значениями , обычно значениями двух предложений , которая дает значение истина, если хотя бы один из ее операндов истинен.

Таблица истинности для p OR q (также обозначаемая как p ∨ q , Apq , p || q или p + q ) выглядит следующим образом:

Логическая дизъюнкция
п q pq
Т Т Т
Т F Т
F Т Т
F F F

Говоря на английском языке, если p , то pq равно p , иначе pq равно q .

Логическое следствие

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

Таблица истинности, связанная с логической импликацией p, подразумевает q (обозначается как p ⇒ q , или, реже, Cpq ) выглядит следующим образом:

Логическое следствие
п q pq
Т Т Т
Т F F
F Т Т
F F Т

Таблица истинности, связанная с материальным условным условием if p, then q (обозначается как p → q ), выглядит следующим образом:

Материал условный
п q pq
Т Т Т
Т F F
F Т Т
F F Т

Также может быть полезно отметить, что p ⇒ q и p → q эквивалентны ¬p ∨ q .

Логическое равенство

Логическое равенство (также известное как двусмысленное или исключающее ни ) - это операция над двумя логическими значениями , обычно значениями двух предложений , которая производит значение истина, если оба операнда ложны или оба операнда истинны.

Таблица истинности для p XNOR q (также записываемая как p ↔ q , Epq , p = q или p ≡ q ) выглядит следующим образом:

Логическое равенство
п q pq
Т Т Т
Т F F
F Т F
F F Т

Итак, p EQ q истинно, если p и q имеют одинаковое значение истинности (оба истинны или оба ложны), и ложь, если они имеют разные значения истинности.

Исключительная дизъюнкция

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

Таблица истинности для p XOR q (также записываемая как Jpq или p ⊕ q ) выглядит следующим образом:

Исключительная дизъюнкция
п q pq
Т Т F
Т F Т
F Т Т
F F F

Для двух предложений XOR можно также записать как (p ∧ ¬q) ∨ (¬p ∧ q).

Логическая И-НЕ

Логического типа NAND является операция на двух логических значений , как правило , значения двух предложений , который производит значение FALSE , если оба операнда являются истинными. Другими словами, он выдает значение true, если хотя бы один из его операндов ложен.

Таблица истинности для p NAND q (также обозначаемая как p ↑ q , Dpq или p | q ) выглядит следующим образом:

Логическая И-НЕ
п q pq
Т Т F
Т F Т
F Т Т
F F Т

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

В случае логического И-НЕ это явно выражается как соединение НЕ и И.

Отрицание конъюнкции: ¬ ( p  ∧  q ) и дизъюнкция отрицаний: (¬ p ) ∨ (¬ q ) можно свести в таблицу следующим образом:

п q p  ∧  q ¬ ( p  ∧  q ) ¬ p ¬ q p ) ∨ (¬ q )
Т Т Т F F F F
Т F F Т F Т Т
F Т F Т Т F Т
F F F Т Т Т Т

Логическое ИЛИ

Логическим ИЛИ - НЕ является операцией на два логических значениях , как правило , значение двух предложений , который производит значение верно , если оба операнда являются ложными. Другими словами, он выдает значение false, если хотя бы один из его операндов истинен. ↓ также известен как стрелка Пирса в честь ее изобретателя Чарльза Сандерса Пирса и является единственным достаточным оператором .

Таблица истинности для p NOR q (также записываемая как p ↓ q или Xpq ) выглядит следующим образом:

Логическое ИЛИ
п q pq
Т Т F
Т F F
F Т F
F F Т

Отрицание дизъюнкции ¬ ( p  ∨  q ) и конъюнкция отрицаний (¬ p ) ∧ (¬ q ) могут быть сведены в таблицу следующим образом:

п q p  ∨  q ¬ ( p  ∨  q ) ¬ p ¬ q p ) ∧ (¬ q )
Т Т Т F F F F
Т F Т F F Т F
F Т Т F Т F F
F F F Т Т Т Т

Проверка табличных выводов для NAND и NOR при каждом присвоении логических значений функциональным аргументам p и q дает идентичные шаблоны функциональных значений для ¬ ( p  ∧  q ), что и для (¬ p ) ∨ (¬ q ), и для ¬ ( p  ∨  q ) как для (¬ p ) ∧ (¬ q ). Таким образом, первое и второе выражения в каждой паре логически эквивалентны и могут заменять друг друга во всех контекстах, которые относятся исключительно к их логическим значениям.

Эта эквивалентность - один из законов Де Моргана .

Размер таблиц истинности

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

п 2 п 2 2 п
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 463 463 374 607 431 768 211 456 ≈ 3,4 × 10 38
8 256 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 ≈ 1,1 × 10 77

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

Приложения

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

Логическая эквивалентность:
Т Т F Т Т
Т F F F F
F Т Т Т Т
F F Т Т Т

Это свидетельствует о том , что является логическим эквивалентом к .

Таблица истинности для наиболее часто используемых логических операторов

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

п Q
Т Т Т Т F Т Т Т Т
Т F F Т Т F F Т F
F Т F Т Т F Т F F
F F F F F Т Т Т Т
п Q
И
(союз)
ИЛИ
(дизъюнкция)
XOR
(исключающее или)
XNOR
( исключая ни)
условное
"если-то"
условное
"тогда-если"
двусмысленное выражение
«если и только если»

куда    Т    значит правда и    F    означает ложь

Сжатые таблицы истинности для бинарных операторов

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

F Т
F F F
Т F Т
F Т
F F Т
Т Т Т

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

Таблицы истинности в цифровой логике

Таблицы истинности также используются для определения функции аппаратных справочных таблиц (LUT) в цифровых логических схемах . Для LUT с n входом таблица истинности будет иметь 2 ^ n значений (или строки в указанном выше табличном формате), полностью определяя логическую функцию для LUT. Представляя каждое логическое значение как бит в двоичном числе , значения таблицы истинности могут быть эффективно закодированы как целочисленные значения в программном обеспечении автоматизации электронного проектирования (EDA) . Например, 32-битное целое число может кодировать таблицу истинности для LUT с максимум 5 входами.

При использовании целочисленного представления таблицы истинности выходное значение LUT может быть получено путем вычисления битового индекса k на основе входных значений LUT, и в этом случае выходным значением LUT является k- й бит целого числа. Например, чтобы оценить выходное значение LUT с учетом массива из n логических входных значений, битовый индекс выходного значения таблицы истинности может быть вычислен следующим образом: если i- й вход истинен, пусть , иначе пусть . Тогда k- й бит двоичного представления таблицы истинности является выходным значением LUT, где .

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

Применение таблиц истинности в цифровой электронике

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

A B | C R
1 1 | 1 0
1 0 | 0 1
0 1 | 0 1
0 0 | 0 0

where

A = First Operand
B = Second Operand
C = Carry
R = Result

Эта таблица истинности читается слева направо:

  • Пара значений (A, B) равна паре значений (C, R).
  • Или, в этом примере, A плюс B равняется результату R с переносом C.

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

Что касается результата, этот пример можно арифметически рассматривать как двоичное сложение по модулю 2 и как логически эквивалентный бинарной логической операции «исключающее ИЛИ» (исключающая дизъюнкция).

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

Например, в операции сложения нужно два операнда, A и B. Каждый может иметь одно из двух значений, ноль или один. Количество комбинаций этих двух значений равно 2 × 2 или четырем. Таким образом, результат - четыре возможных выхода C и R. Если бы использовать базу 3, размер увеличился бы до 3 × 3, или девяти возможных выходов.

Первый пример «сложения» выше называется полусумматором. Полный сумматор - это когда перенос из предыдущей операции предоставляется в качестве входных данных для следующего сумматора. Таким образом, для описания полной логики сумматора потребуется таблица истинности из восьми строк :

A B C* | C R
0 0 0  | 0 0
0 1 0  | 0 1
1 0 0  | 0 1
1 1 0  | 1 0
0 0 1  | 0 1
0 1 1  | 1 0
1 0 1  | 1 0
1 1 1  | 1 1

Same as previous, but..
C* = Carry from previous adder

История

Исследование Ирвинга Анеллиса показывает, что К.С. Пирс, по- видимому, был первым логиком (в 1893 году), который разработал матрицу таблицы истинности. Из резюме его статьи:

В 1997 году Джон Шоски обнаружил на оборотной стороне страницы печатной копии лекции Бертрана Рассела 1912 года «Философия логического атомизма» матрицы таблиц истинности. Матрица отрицания принадлежит Расселу, рядом с ней находится матрица материального подтекста, созданная Людвигом Витгенштейном. Показано, что неопубликованная рукопись, идентифицированная как составленная Пирсом в 1893 году, включает матрицу таблицы истинности, которая эквивалентна матрице материального значения, обнаруженной Джоном Шоски. Неопубликованная рукопись Пирса, которая, как было установлено, была написана в 1883–1884 годах в связи с сочинением книги Пирса «Об алгебре логики: вклад в философию нотации», опубликованной в American Journal of Mathematics в 1885 году, включает пример косвенная таблица истинности для условного.

Смотрите также

Примечания

использованная литература

Процитированные работы

  • Бохенский, Юзеф Мария (1959), Краткое изложение математической логики , перевод с французского и немецкого изданий Отто Берда, Дордрехт, Южная Голландия: D. Reidel.
  • Эндертон, Х. (2001). Математическое введение в логику , второе издание, Нью-Йорк: Harcourt Academic Press. ISBN  0-12-238452-0
  • Куайн, WV (1982), Методы логики , 4-е издание, Кембридж, Массачусетс: Издательство Гарвардского университета.

внешние ссылки