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