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

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

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

Унарные операции [ править ]

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

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

Логическая истина [ править ]

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

Логическая ложь [ править ]

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

Логическая идентичность [ править ]

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

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

Логическое отрицание [ править ]

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

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

Бинарные операции [ править ]

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

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

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

куда

T = верно.

F = ложь.

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 . ^{[заметка 2]}

Четыре комбинации входных значений для 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. Выходная строка для , таким образом ,${\ displaystyle \ nleftarrow}$${\ displaystyle \ nleftarrow}$${\ displaystyle \ nleftarrow}$

2: БПФФ

а 16-рядный ^[5] ключ -

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

Логическое соединение (И) [ править ]

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

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

В терминах обычного языка, если и 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 ) выглядит следующим образом:

Заявленный на английском языке, если р , то р ∨ д является р , в противном случае р ∨ д является кв .

Логическое следствие [ править ]

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

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

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

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

Логическое равенство [ править ]

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

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

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

Исключительная дизъюнкция [ править ]

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

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

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

Логическая И-НЕ [ править ]

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

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

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

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

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

Логическое ИЛИ [ править ]

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

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

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

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

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

Приложения [ править ]

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

Логическая эквивалентность: ${\ Displaystyle (п \ Rightarrow q) \ Equiv (\ lnot p \ lor q)}$

${\ displaystyle p}$	${\ displaystyle q}$	${\ displaystyle \ lnot p}$	${\ Displaystyle \ lnot p \ lor q}$	${\ displaystyle p \ Rightarrow q}$
Т	Т	F	Т	Т
Т	F	F	F	F
F	Т	Т	Т	Т
F	F	Т	Т	Т

Это свидетельствует о том , что является логическим эквивалентом к .${\ displaystyle p \ Rightarrow q}$${\ Displaystyle \ lnot p \ lor q}$

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

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

п	Q	${\ displaystyle P \ land Q}$	${\ Displaystyle P \ lor Q}$	${\ Displaystyle P \ {\ underline {\ lor}} \ Q}$	${\ displaystyle P \ {\ underline {\ land}} \ Q}$	${\ Displaystyle P \ Rightarrow Q}$	${\ Displaystyle P \ Leftarrow Q}$	${\ displaystyle P \ Leftrightarrow Q}$
Т	Т	Т	Т	F	Т	Т	Т	Т
Т	F	F	Т	Т	F	F	Т	F
F	Т	F	Т	Т	F	Т	F	F
F	F	F	F	F	Т	Т	Т	Т

куда

Т

истинный

F

ложный

${\ displaystyle \ land}$

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

${\ displaystyle \ lor}$

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

${\displaystyle {\underline {\lor }}}$

XOR (исключающее или)

${\displaystyle {\underline {\land }}}$

XNOR ( исключая ни)

${\displaystyle \Rightarrow }$

условное "если-то"

${\displaystyle \Leftarrow }$

условное "тогда-если"

${\displaystyle \Leftrightarrow }$

двусмысленное выражение «если и только если» .

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

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

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

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

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

При использовании целочисленного представления таблицы истинности выходное значение LUT может быть получено путем вычисления битового индекса k на основе входных значений LUT, и в этом случае выходным значением LUT является k- й бит целого числа. Например, чтобы оценить выходное значение LUT с учетом массива из n логических входных значений, битовый индекс выходного значения таблицы истинности может быть вычислен следующим образом: если i- й вход истинен, пусть , иначе пусть . Тогда k- й бит двоичного представления таблицы истинности является выходным значением LUT, где .${\displaystyle V_{i}=1}$${\displaystyle V_{i}=0}$${\displaystyle k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}}$

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

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

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

AB | CR1 1 | 1 01 0 | 0 10 1 | 0 10 0 | 0 0кудаA = первый операндB = второй операндC = нестиR = Результат

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

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

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

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

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

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

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

ABC * | CR0 0 0 | 0 00 1 0 | 0 11 0 0 | 0 11 1 0 | 1 00 0 1 | 0 10 1 1 | 1 01 0 1 | 1 01 1 1 | 1 1То же, что и предыдущий, но ..C * = Перенести из предыдущего сумматора

История [ править ]

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

В 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]
• Таблицы истинности, тавтологии и логическая эквивалентность
• ИСТИННО-ФУНКЦИОНАЛЬНЫЙ АНАЛИЗ ПИРСА И ПРОИСХОЖДЕНИЕ ИСТИННЫХ ТАБЛИЦ, Ирвинг Х. Анеллис
• Преобразование таблиц истинности в логические выражения