Таблица истинности - 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) | НИ | p ↓ q , Xpq | Логическое ИЛИ |
2 | (БПФФ) (p, q) | ↚ | p ↚ q , Мпк | Конверс без импликации |
3 | (БПФТ) (p, q) | ¬p , ~ p | ¬p , Np , Fpq | Отрицание |
4 | (FTFF) (p, q) | ↛ | p ↛ q , Lpq | Существенное отсутствие импликации |
5 | (FTFT) (p, q) | ¬q , ~ q | ¬q , Nq , Гпк | Отрицание |
6 | (FTTF) (p, q) | XOR | p ⊕ q , Jpq | Исключительная дизъюнкция |
7 | (FTTT) (p, q) | NAND | p ↑ q , Dpq | Логическая И-НЕ |
8 | (TFFF) (p, q) | А ТАКЖЕ | p ∧ q , Kpq | Логическое соединение |
9 | (TFFT) (p, q) | XNOR | p Если и только если q , Epq | Логическая двусмысленность |
10 | (TFTF) (p, q) | q | q , Hpq | Функция проекции |
11 | (TFTT) (p, q) | p → q | если p, то q , Cpq | Материальное значение |
12 | (TTFF) (p, q) | п | p , Ipq | Функция проекции |
13 | (TTFT) (p, q) | p ← q | p, если q , Bpq | Обратное значение |
14 | (TTTF) (p, q) | ИЛИ | p ∨ q , Apq | Логическая дизъюнкция |
15 | (TTTT) (p, q) | ⊤ | правда , Vpq | Тавтология |
Логические операторы также можно визуализировать с помощью диаграмм Венна .
Логическое соединение (И)
Логическое соединение - это операция над двумя логическими значениями , обычно значениями двух предложений , которая дает значение истина, если оба ее операнда истинны.
Таблица истинности для p И q (также записываемая как p ∧ q , Kpq , p & q или p q ) выглядит следующим образом:
п | q | p ∧ q |
---|---|---|
Т | Т | Т |
Т | F | F |
F | Т | F |
F | F | F |
В терминах обычного языка, если и p, и q истинны, то конъюнкция p ∧ q истинна. Для всех других присвоений логических значений p и q конъюнкция p ∧ q ложна.
Также можно сказать, что если p , то p ∧ q равно q , иначе p ∧ q равно p .
Логическая дизъюнкция (ИЛИ)
Логическая дизъюнкция - это операция над двумя логическими значениями , обычно значениями двух предложений , которая дает значение истина, если хотя бы один из ее операндов истинен.
Таблица истинности для p OR q (также обозначаемая как p ∨ q , Apq , p || q или p + q ) выглядит следующим образом:
п | q | p ∨ q |
---|---|---|
Т | Т | Т |
Т | F | Т |
F | Т | Т |
F | F | F |
Говоря на английском языке, если p , то p ∨ q равно p , иначе p ∨ q равно q .
Логическое следствие
И логическая импликация, и материальное условие связаны с операцией над двумя логическими значениями , обычно со значениями двух предложений , которая дает значение false, если первый операнд истинен, а второй операнд ложь, и значение true в противном случае.
Таблица истинности, связанная с логической импликацией p, подразумевает q (обозначается как p ⇒ q , или, реже, Cpq ) выглядит следующим образом:
п | q | p ⇒ q |
---|---|---|
Т | Т | Т |
Т | F | F |
F | Т | Т |
F | F | Т |
Таблица истинности, связанная с материальным условным условием if p, then q (обозначается как p → q ), выглядит следующим образом:
п | q | p → q |
---|---|---|
Т | Т | Т |
Т | F | F |
F | Т | Т |
F | F | Т |
Также может быть полезно отметить, что p ⇒ q и p → q эквивалентны ¬p ∨ q .
Логическое равенство
Логическое равенство (также известное как двусмысленное или исключающее ни ) - это операция над двумя логическими значениями , обычно значениями двух предложений , которая производит значение истина, если оба операнда ложны или оба операнда истинны.
Таблица истинности для p XNOR q (также записываемая как p ↔ q , Epq , p = q или p ≡ q ) выглядит следующим образом:
п | q | p ↔ q |
---|---|---|
Т | Т | Т |
Т | F | F |
F | Т | F |
F | F | Т |
Итак, p EQ q истинно, если p и q имеют одинаковое значение истинности (оба истинны или оба ложны), и ложь, если они имеют разные значения истинности.
Исключительная дизъюнкция
Исключительная дизъюнкция - это операция над двумя логическими значениями , обычно значениями двух предложений , которая дает значение истина, если один, но не оба его операнда истинны.
Таблица истинности для p XOR q (также записываемая как Jpq или p ⊕ q ) выглядит следующим образом:
п | q | p ⊕ q |
---|---|---|
Т | Т | F |
Т | F | Т |
F | Т | Т |
F | F | F |
Для двух предложений XOR можно также записать как (p ∧ ¬q) ∨ (¬p ∧ q).
Логическая И-НЕ
Логического типа NAND является операция на двух логических значений , как правило , значения двух предложений , который производит значение FALSE , если оба операнда являются истинными. Другими словами, он выдает значение true, если хотя бы один из его операндов ложен.
Таблица истинности для p NAND q (также обозначаемая как p ↑ q , Dpq или p | q ) выглядит следующим образом:
п | q | p ↑ q |
---|---|---|
Т | Т | 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 | p ↓ q |
---|---|---|
Т | Т | 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 означает ложь |
Сжатые таблицы истинности для бинарных операторов
Для бинарных операторов также используется сжатая форма таблицы истинности, где заголовки строк и заголовки столбцов определяют операнды, а ячейки таблицы определяют результат. Например, в булевой логике используется эта сжатая запись таблицы истинности:
|
|
Это обозначение полезно, особенно если операции коммутативны, хотя можно дополнительно указать, что строки являются первым операндом, а столбцы - вторым операндом. Эти сжатые обозначения особенно полезны при обсуждении многозначных расширений логики, поскольку они значительно сокращают комбинаторный взрыв количества строк, необходимых в противном случае. Он также обеспечивает быстро узнаваемую характерную «форму» распределения значений в таблице, которая может помочь читателю быстрее понять правила.
Таблицы истинности в цифровой логике
Таблицы истинности также используются для определения функции аппаратных справочных таблиц (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-е издание, Кембридж, Массачусетс: Издательство Гарвардского университета.
внешние ссылки
- "Таблица истинности" , Энциклопедия математики , EMS Press , 2001 [1994]
- Таблицы истинности, тавтологии и логическая эквивалентность
- ИСТИННО-ФУНКЦИОНАЛЬНЫЙ АНАЛИЗ ПИРСА И ПРОИСХОЖДЕНИЕ ИСТИННЫХ ТАБЛИЦ Ирвинга Х. Анеллиса
- Преобразование таблиц истинности в логические выражения