Таблица истинности — это математическая таблица, используемая в логике (в частности, в связи с булевой алгеброй , булевыми функциями и исчислением высказываний ), которая устанавливает функциональные значения логических выражений для каждого из их функциональных аргументов, то есть для каждой комбинации значений, принимаемых их логическими переменными . [1] В частности, таблицы истинности можно использовать для того, чтобы показать, является ли пропозициональное выражение истинным для всех допустимых входных значений, то есть логически допустимым .
Таблица истинности имеет один столбец для каждой входной переменной (например, A и B), и один последний столбец, показывающий все возможные результаты логической операции, которую представляет таблица (например, A XOR B). Каждая строка таблицы истинности содержит одну возможную конфигурацию входных переменных (например, A=true, B=false) и результат операции для этих значений.
Таблица истинности — это структурированное представление, которое представляет все возможные комбинации значений истинности для входных переменных булевой функции и их соответствующих выходных значений. Функция f от A до F — это специальное отношение , подмножество A×F, что просто означает, что f может быть перечислена как список пар вход-выход. Очевидно, что для булевых функций выход принадлежит двоичному набору, т. е. F = {0, 1}. Для n-арной булевой функции входы поступают из домена, который сам по себе является декартовым произведением двоичных наборов, соответствующих входным булевым переменным. Например, для бинарной функции f (A, B) домен f равен A×B, что может быть перечислено как: A×B = {(A = 0, B = 0), (A = 0, B = 1), (A = 1, B = 0), (A = 1, B = 1)}. Каждый элемент в домене представляет собой комбинацию входных значений для переменных A и B. Теперь эти комбинации можно объединить с выходными данными функции, соответствующими этой комбинации, тем самым формируя набор пар вход-выход как специальное отношение, которое является подмножеством A×F. Для того чтобы отношение было функцией, специальным требованием является то, что каждый элемент домена функции должен быть сопоставлен одному и только одному члену кодомена. Таким образом, сама функция f может быть указана как: f = {((0, 0), f 0 ), ((0, 1), f 1 ), ((1, 0), f 2 ), ((1, 1), f 3 )}, где f 0 , f 1 , f 2 и f 3 являются булевыми значениями 0 или 1 как члены кодомена {0, 1}, как выходы, соответствующие члену домена, соответственно. Вместо списка (набора), приведенного выше, таблица истинности представляет эти пары вход-выход в табличном формате, в котором каждая строка соответствует члену домена, сопряженному с соответствующим ему выходным значением, 0 или 1. Конечно, для булевых функций нам не нужно перечислять все члены домена с их изображениями в кодомене ; мы можем просто перечислить отображения, которые сопоставляют член с «1», потому что все остальные должны будут автоматически сопоставляться с «0» (что приводит нас к идее минтермов ).
Людвигу Витгенштейну обычно приписывают изобретение и популяризацию таблицы истинности в его «Логико-философском трактате» , который был завершен в 1918 году и опубликован в 1921 году. [2] Подобная система была также независимо предложена в 1921 году Эмилем Леоном Постом . [3]
Исследования Ирвинга Анеллиса показывают, что К. С. Пирс, по-видимому, был первым логиком (в 1883 году), который разработал матрицу таблицы истинности. [4]
Из резюме статьи Анеллиса: [4]
В 1997 году Джон Шоски обнаружил на обороте страницы распечатанной стенограммы лекции Бертрана Рассела 1912 года «Философия логического атомизма» матрицы истинности. Матрица для отрицания принадлежит Расселу, рядом с ней находится матрица для материальной импликации, написанная рукой Людвига Витгенштейна. Показано, что неопубликованная рукопись, идентифицированная как составленная Пирсом в 1893 году, включает матрицу истинности, которая эквивалентна матрице для материальной импликации, обнаруженной Джоном Шоски. Неопубликованная рукопись Пирса, идентифицированная как составленная в 1883–1884 годах в связи с составлением Пирсом «Об алгебре логики: вклад в философию обозначений», которая появилась в Американском журнале математики в 1885 году, включает пример косвенной таблицы истинности для условного выражения.
Таблицы истинности могут быть использованы для доказательства многих других логических эквивалентностей . Например, рассмотрим следующую таблицу истинности:
Это демонстрирует тот факт, что логически эквивалентно .
Ниже приведена таблица истинности, которая дает определения 7 наиболее часто используемых из 16 возможных функций истинности двух булевых переменных P и Q:
Для бинарных операторов также используется сжатая форма таблицы истинности, где заголовки строк и столбцов определяют операнды, а ячейки таблицы определяют результат. Например, булева логика использует эту сжатую запись таблицы истинности:
Эта нотация полезна, особенно если операции коммутативны, хотя можно дополнительно указать, что строки являются первым операндом, а столбцы — вторым операндом. Эта сжатая нотация особенно полезна при обсуждении многозначных расширений логики, поскольку она значительно сокращает комбинаторный взрыв числа строк, который в противном случае был бы необходим. Она также обеспечивает быстро распознаваемую характерную «форму» распределения значений в таблице, что может помочь читателю быстрее понять правила.
Таблицы истинности также используются для указания функции таблиц аппаратного поиска (LUT) в цифровых логических схемах . Для LUT с n входами таблица истинности будет иметь 2^ n значений (или строк в приведенном выше табличном формате), полностью определяя булеву функцию для LUT. Представляя каждое булево значение как бит в двоичном числе , значения таблицы истинности могут быть эффективно закодированы как целочисленные значения в программном обеспечении для автоматизации электронного проектирования (EDA) . Например, 32-битное целое число может кодировать таблицу истинности для LUT с 5 входами.
При использовании целочисленного представления таблицы истинности выходное значение LUT может быть получено путем вычисления битового индекса k на основе входных значений LUT, в этом случае выходное значение LUT является k -м битом целого числа. Например, чтобы оценить выходное значение LUT, заданное массивом из n булевых входных значений, битовый индекс выходного значения таблицы истинности может быть вычислен следующим образом: если i -й вход истинен, пусть , иначе пусть . Тогда k -й бит двоичного представления таблицы истинности является выходным значением LUT, где .
Таблицы истинности — это простой и понятный способ кодирования булевых функций, однако, учитывая экспоненциальный рост размера по мере увеличения числа входов, они не подходят для функций с большим числом входов. Другие представления, которые более эффективны с точки зрения памяти, — это текстовые уравнения и диаграммы бинарных решений .
В цифровой электронике и информатике (области прикладной логической инженерии и математики) таблицы истинности могут использоваться для сведения базовых булевых операций к простым корреляциям входов и выходов без использования логических вентилей или кода. Например, двоичное сложение может быть представлено с помощью таблицы истинности:
где A — первый операнд, B — второй операнд, C — цифра переноса, а R — результат.
Эту таблицу истинности читаем слева направо:
В этой таблице не описываются логические операции, необходимые для реализации этой операции, а просто указывается функция входных значений для выходных.
Что касается результата, этот пример можно арифметически рассматривать как двоичное сложение по модулю 2 и как логически эквивалентный двоичной логической операции «исключающее ИЛИ» (исключающая дизъюнкция).
В этом случае его можно использовать только для очень простых входов и выходов, таких как 1 и 0. Однако если количество типов значений, которые можно иметь на входах, увеличивается, размер таблицы истинности увеличивается.
Например, в операции сложения нужны два операнда, A и B. Каждый может иметь одно из двух значений, ноль или единицу. Количество комбинаций этих двух значений равно 2×2, или четырем. Таким образом, результатом являются четыре возможных выхода C и R. Если бы использовалось основание 3, размер увеличился бы до 3×3, или девяти возможных выходов.
Первый пример "сложения" выше называется полусумматором. Полный сумматор - это когда перенос из предыдущей операции предоставляется в качестве входных данных для следующего сумматора. Таким образом, для описания логики полного сумматора потребуется таблица истинности из восьми строк:
АБВ* | КР0 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* = Перенос из предыдущего сумматора
Что касается направляющих столбцов [5] слева от таблицы, которые представляют пропозициональные переменные , разные авторы дают разные рекомендации о том, как их заполнять, хотя это не имеет логического значения. [6]
Ли Арчи, профессор Университета Ландера , рекомендует следующую процедуру, которая обычно применяется в опубликованных таблицах истинности:
Этот метод приводит к таблицам истинности, таким как следующая таблица для « P ⊃ (Q ∨ R ⊃ (R ⊃ ¬P)) », созданная Стивеном Коулом Клини : [7]
Колин Хаусон , с другой стороны, считает, что «хорошим практическим правилом» является следующее:
начать со всех T, затем всеми способами (три) двух T, которые можно объединить с одним F, затем всеми способами (три) одного T, которые можно объединить с двумя F, и затем закончить всеми F. Если соединение построено из n различных букв предложения, его таблица истинности будет иметь 2 n строк, так как есть два способа присвоить T или F первой букве, и для каждого из них будет два способа присвоить T или F второй, и для каждого из них будет два способа присвоить T или F третьей, и так далее, давая 2.2.2. …, n раз, что равно 2 n . [6]
Это приводит к таблицам истинности, подобным этой таблице, «показывающей, что (A→C)∧(B→C) и (A∨B)→C являются истинностно-функционально эквивалентными », смоделированной по образцу таблицы, созданной Хаусоном : [6]
Если есть n входных переменных, то есть 2 n возможных комбинаций их значений истинности. Заданная функция может выдавать true или false для каждой комбинации, поэтому число различных функций n переменных равно двойной экспоненте 2 2 n .
Таблицы истинности для функций трех и более переменных приводятся редко.
Может быть полезно иметь вывод таблицы истинности, выраженный как функция некоторых переменных значений, а не просто буквальное значение истины или лжи. Их можно назвать «таблицами функций», чтобы отличать их от более общих «таблиц истинности». [8] Например, одно значение, , может использоваться с вентилем XOR для условного инвертирования другого значения, . Другими словами, когда ложно, вывод равен , а когда истинно, вывод равен . Таблица функций для этого будет выглядеть следующим образом:
Аналогично, мультиплексор 4-к-1 с выбранными входами и , входами данных , , и , и выходом (как показано на рисунке) будет иметь следующую таблицу функций:
Вот расширенная таблица истинности, дающая определения всех шестнадцати возможных функций истинности двух булевых переменных p и q : [примечание 1]
где
В предложении 5.101 «Логико-философского трактата» [ 9] Витгенштейн перечислил приведенную выше таблицу следующим образом:
Таблица истинности, представленная каждой строкой, получается путем добавления последовательности, указанной в строке «Значения истинности» , к таблице [примечание 3]
Например, таблица
представляет собой таблицу истинности для материальной импликации . Логические операторы также могут быть визуализированы с помощью диаграмм Венна .
Существует 2 нуль-операции:
Выходное значение всегда истинно, поскольку этот оператор не имеет операндов и, следовательно, входных значений.
Выходное значение никогда не бывает истинным: то есть всегда ложным, поскольку этот оператор не имеет операндов и, следовательно, входных значений.
Существует 2 унарные операции:
Логическая идентичность — это операция над одним логическим значением p, для которой выходное значение остается p.
Таблица истинности для оператора логической идентичности выглядит следующим образом:
Логическое отрицание — это операция над одним логическим значением , обычно значением предложения , которая возвращает значение « истина» , если ее операнд — «ложь», и значение «ложь» , если ее операнд — «истина».
Таблица истинности для NOT p (также обозначается как ¬p , Np , Fpq или ~p ) выглядит следующим образом:
Существует 16 возможных функций истинности двух двоичных переменных , каждый оператор имеет свое имя.
Логическая конъюнкция — это операция над двумя логическими значениями , обычно значениями двух предложений , которая производит значение «истина» , если оба ее операнда истинны.
Таблица истинности для p AND q (также записывается как p ∧ q , Kpq , p & q , или p q ) выглядит следующим образом:
В терминах обычного языка, если и 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 ) выглядит следующим образом:
В английском языке это звучит так: если p , то p ∨ q есть p , в противном случае p ∨ q есть q .
Логическая импликация и материальное условное выражение связаны с операцией над двумя логическими значениями , обычно значениями двух предложений , которая дает значение « ложь» , если первый операнд истинен, а второй операнд ложен, и значение « истина» в противном случае.
Таблица истинности, связанная с логическим выводом 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 имеют одинаковое значение истинности (оба истинны или оба ложны), и ложно, если они имеют разные значения истинности.
Исключающая дизъюнкция — это операция над двумя логическими значениями , обычно значениями двух утверждений , которая возвращает значение «истина» , если один, но не оба ее операнда истинны.
Таблица истинности для p XOR q (также обозначается как Jpq или p ⊕ q ) выглядит следующим образом:
Для двух предложений XOR можно также записать как (p ∧ ¬q) ∨ (¬p ∧ q).
Логическая операция НЕ-И — это операция над двумя логическими значениями , обычно значениями двух предложений , которая выдает значение ложь , если оба ее операнда истинны. Другими словами, она выдает значение истина , если хотя бы один из ее операндов ложен.
Таблица истинности для p NAND q (также обозначается как p ↑ q , Dpq или p | q ) выглядит следующим образом:
Часто бывает полезно выразить логическую операцию как составную операцию , то есть как операцию, которая построена или составлена из других операций. Возможны многие такие композиции, в зависимости от операций, которые принимаются как базовые или «примитивные», и операций, которые принимаются как составные или «производные».
В случае логического НЕ-И его можно четко выразить как соединение НЕ и И.
Отрицание конъюнкции: ¬( p ∧ q ) и дизъюнкция отрицаний: (¬ p ) ∨ (¬ q ) могут быть представлены в виде следующей таблицы:
Логическое НЕ-ИЛИ — это операция над двумя логическими значениями , обычно значениями двух предложений , которая выдает значение true, если оба ее операнда ложны. Другими словами, она выдает значение false , если хотя бы один из ее операндов истинен. ↓ также известна как стрелка Пирса в честь ее изобретателя Чарльза Сандерса Пирса и является единственным достаточным оператором .
Таблица истинности для p NOR q (также обозначается как p ↓ q или Xpq ) выглядит следующим образом:
Отрицание дизъюнкции ¬( p ∨ q ) и конъюнкция отрицаний (¬ p ) ∧ (¬ q ) могут быть представлены в виде следующей таблицы:
Проверка табличных выводов для NAND и NOR при каждом назначении логических значений функциональным аргументам p и q дает идентичные шаблоны функциональных значений для ¬( p ∧ q ) как для (¬ p ) ∨ (¬ q ), и для ¬( p ∨ q ) как для (¬ p ) ∧ (¬ q ). Таким образом, первое и второе выражения в каждой паре логически эквивалентны и могут быть заменены друг на друга во всех контекстах, которые относятся исключительно к их логическим значениям.
Эта эквивалентность является одним из законов де Моргана .
Это объясняет, почему строка «Трактата» в приведенной здесь таблице не указывает на ту же строку «Истинные значения» , что и в «Трактате».
