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

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

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

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

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

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

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

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

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

п	Т
Т	Т
F	Т

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

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

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

п	F
Т	F
F	F

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

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

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

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

п	п
Т	Т
F	F

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

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

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

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

п	¬p
Т	F
F	Т

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

Есть 16 возможных функции истины из двух бинарные переменные:

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

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

п	q		F^0	НИ^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	НИ^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	НИ^1	F^0
Двойной			Т^15	NAND^7	→^11	¬p^3	←^13	¬q^5	XNOR^9	НИ^1		ИЛИ ЖЕ^14	XOR^6	q^10	↚^2	п^12	↛^4	И^8	F^0
L id					F				F			Т	Т	Т, Ж	Т			F
Избавлять							F		F			Т	Т			Т, Ж	Т	F

куда

T = верно.

F = ложь.

В Com строка указывает, есть ли у оператора op, является коммутативный - P op Q = Q op P.

В Assoc строка указывает, есть ли у оператора op, является ассоциативный - (P op Q) op R = P op (Q op R).

В Adj строка показывает оператора op2 такой, что P op Q = Q op2 P

В Neg строка показывает оператора op2 такой, что P оп Q = ¬ (Q op2 P)

В Двойной строка показывает двойная операция получается заменой T на F и AND на OR.

В L id строка показывает оператор левые личности если есть - значения я такой, что I op Q = Q.

В Избавлять строка показывает оператор правильные личности если есть - значения я такой, что P op I = P.^{[заметка 2]}

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

Ключ:

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

п: Т Т F F
q: Т Ф Т Ф

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

2: F F T F

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

	[5]		оператор	Название операции
0	(F F F F) (p, q)	⊥	ложный, Opq	Противоречие
1	(F F F T) (p, q)	НИ	п ↓ q, Xpq	Логическое ИЛИ
2	(F F T F) (p, q)	↚	п ↚ q, Мпк	Конверс без импликации
3	(F F T T) (p, q)	¬p, ~ р	¬p, Np, Fpq	Отрицание
4	(F T F F) (p, q)	↛	п ↛ q, Lpq	Существенное отсутствие импликации
5	(F T F T) (p, q)	¬q, ~ q	¬q, Nq, Гпк	Отрицание
6	(F T T F) (p, q)	XOR	п ⊕ q, Jpq	Исключительная дизъюнкция
7	(F T T T) (p, q)	NAND	п ↑ q, Dpq	Логическая И-НЕ
8	(Т F F F) (p, q)	И	п ∧ q, КПК	Логическое соединение
9	(Т F F T) (p, q)	XNOR	п Если и только если q, Epq	Логическая двусмысленность
10	(Т Ф Т Ф) (p, q)	q	q, Hpq	Функция проекции
11	(Т Ф Т Т) (p, q)	п → q	если п тогда q, Cpq	Материальное значение
12	(Т Т F F) (p, q)	п	п, IPQ	Функция проекции
13	(Т Т Ф Т) (p, q)	п ← q	п если q, Бпк	Обратное значение
14	(Т Т Т Ф) (p, q)	ИЛИ ЖЕ	п ∨ q, Apq	Логическая дизъюнкция
15	(Т Т Т Т) (п, д)	⊤	истинный, Впк	Тавтология

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

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

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

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

Логическое соединение

п	q	п ∧ q
Т	Т	Т
Т	F	F
F	Т	F
F	F	F

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

Также можно сказать, что если п, тогда п ∧ q является q, иначе п ∧ q является п.

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

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

Таблица истинности для p ИЛИ q (также записывается как p ∨ q, Apq, p || q, или же р + д) как следует:

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

п	q	п ∨ q
Т	Т	Т
Т	F	Т
F	Т	Т
F	F	F

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

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

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

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

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

п	q	п ⇒ q
Т	Т	Т
Т	F	F
F	Т	Т
F	F	Т

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

Материал условный

п	q	п → q
Т	Т	Т
Т	F	F
F	Т	Т
F	F	Т

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

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

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

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

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

п	q	п ↔ q
Т	Т	Т
Т	F	F
F	Т	F
F	F	Т

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

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

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

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

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

п	q	п ⊕ q
Т	Т	F
Т	F	Т
F	Т	Т
F	F	F

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

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

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

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

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

п	q	п ↑ q
Т	Т	F
Т	F	Т
F	Т	Т
F	F	Т

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

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

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

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

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

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

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

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

п	q	п ↓ q
Т	Т	F
Т	F	F
F	Т	F
F	F	Т

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

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

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

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

Приложения

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

Логическая эквивалентность: ${\displaystyle (p\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 }$

двусмысленный "если и только если".

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

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

∧ F Т F F F Т F Т

∨ F Т F F Т Т Т Т

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

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

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

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

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

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

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

A B | C R1 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, или девяти возможных выходов.

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

A B C * | C R0 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 годах в связи с сочинением книги Пирса «Об алгебре логики: вклад в философию нотации», появившейся в Американский журнал математики в 1885 году включает пример косвенной таблицы истинности для условного.

Примечания

1. Информацию об обозначениях можно найти в Бохенский (1959), Enderton (2001), и Куайн (1982).
2. Здесь операторы с равными левыми и правыми тождествами (XOR, AND, XNOR и OR) также являются коммутативные моноиды потому что они также ассоциативный. Хотя это различие может не иметь значения при простом обсуждении логики, оно может быть весьма важным в более продвинутой математике. Например, в теория категорий ан обогащенная категория описывается как база категория обогащается по моноиду, и любой из этих операторов можно использовать для обогащения.

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

• Философский портал
• Психологический портал

• Логический домен
• Булевозначная функция
• Минимизатор эвристической логики эспрессо
• Таблица возбуждения
• Логика первого порядка
• Функциональная полнота
• Карты Карно
• Логический вентиль
• Логическая связка
• Логический график
• Метод аналитических таблиц
• Исчисление высказываний
• Функция истины

Рекомендации

1. Enderton, 2001
2. Георг Хенрик фон Райт (1955). "Людвиг Витгенштейн, Биографический очерк". Философский обзор. 64 (4): 527–545 (стр. 532, примечание 9). Дои:10.2307/2182631. JSTOR  2182631.
3. Эмиль Пост (Июль 1921 г.). «Введение в общую теорию элементарных предложений». Американский журнал математики. 43 (3): 163–185. Дои:10.2307/2370324. HDL:2027 / uiuo.ark: / 13960 / t9j450f7q. JSTOR  2370324.
4. Анеллис, Ирвинг Х. (2012). "Функциональный анализ Пирса и происхождение таблицы истины". История и философия логики. 33: 87–97. Дои:10.1080/01445340.2011.621702.
5. Людвиг Витгенштейн (1922) Логико-философский трактат Предложение 5.101
6. В публикацию Пирса вошли работы Кристин Лэдд (1881): Доктор философии Пирса. студентка Кристин Лэдд-Франклин нашла таблицу истинности в Логико-философский трактат Предложение 5.101, на 40 лет раньше, чем Витгенштейн. Кристин Лэдд (1881 г.), «Об алгебре логики», стр.62., Исследования по логике, Изд. К. С. Пирса, 1883 г.

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

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

внешняя ссылка

• "Таблица истинности", Энциклопедия математики, EMS Press, 2001 [1994]
• Таблицы истинности, тавтологии и логическая эквивалентность
• ИСТИННО-ФУНКЦИОНАЛЬНЫЙ АНАЛИЗ ПИРСА И ПРОИСХОЖДЕНИЕ ИСТИННЫХ ТАБЛИЦ Ирвинг Х. Анеллис
• Преобразование таблиц истинности в логические выражения