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

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

Таблица истинности имеет один столбец для каждой входной переменной (например, A и B) и один последний столбец, показывающий все возможные результаты логической операции, которую представляет таблица (например, A XOR B ). Каждая строка таблицы истинности содержит одну возможную конфигурацию входных переменных (например, A=истина, B=ложь) и результат операции для этих значений.

Таблица истинности — это структурированное представление, которое представляет все возможные комбинации значений истинности для входных переменных булевой функции и соответствующих им выходных значений. Функция f f от A до F — это специальное отношение , подмножество A×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, 1), f ₁ ), ((1, 0), f ₂ ), ((1, 1), f ₃ )}, где f ₀ , f ₁ , f ₂ и f ₃ представляют собой логические значения 0 или 1 как члены кодомена {0, 1}, как выходные данные, соответствующие члену домена соответственно. Вместо списка (набора), приведенного выше, таблица истинности затем представляет эти пары ввода-вывода в табличном формате, в котором каждая строка соответствует члену домена в паре с соответствующим выходным значением 0 или 1. Конечно, для булевых функций нам не нужно перечислять все члены домена с их изображениями в кодомене ; мы можем просто перечислить сопоставления, которые сопоставляют элемент с «1», потому что все остальные должны будут автоматически сопоставляться с «0» (это приводит нас к идее минтермов ).

Людвигу Витгенштейну обычно приписывают изобретение и популяризацию таблицы истинности в его « Логико-философском трактате» , который был завершен в 1918 году и опубликован в 1921 году. Такая система была также независимо предложена в 1921 году Эмилем Леоном Постом .

История

Ирвинга Анеллиса Исследования показывают, что К.С. Пирс, по-видимому, был первым логиком (в 1883 году), который разработал матрицу таблицы истинности.

Из краткого изложения статьи Анеллиса:

В 1997 году Джон Шоски обнаружил на оборотной стороне страницы машинописной расшифровки лекции Бертрана Рассела 1912 года «Философия логического атомизма» матрицы таблицы истинности. Матрица отрицания — это матрица Рассела, рядом с которой находится матрица материального импликации Людвига Витгенштейна. Показано, что неопубликованная рукопись, идентифицированная как составленная Пирсом в 1893 году, включает матрицу таблицы истинности, эквивалентную матрице материальной импликации, открытой Джоном Шоски. Неопубликованная рукопись Пирса, идентифицированная как написанная в 1883–1884 годах в связи с сочинением книги Пирса «Об алгебре логики: вклад в философию обозначений», опубликованной в Американском журнале математики в 1885 году, включает пример косвенная таблица истинности для условного выражения.

Приложения

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

$(p\Rightarrow q)\equiv (\lnot p\lor q)$

$p$	$q$	$\lnot p$	$\lnot p\lor q$	$p\Rightarrow q$
Т	Т	Ф	Т	Т
Т	Ф	Ф	Ф	Ф
Ф	Т	Т	Т	Т
Ф	Ф	Т	Т	Т

Это демонстрирует тот факт, что $p\Rightarrow q$ эквивалентно логически ​ $\lnot p\lor q$.

логических

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

п	вопрос	$P\land Q$	$P\lor Q$	$P\ {\underline {\lor }}\ Q$	$P\ {\underline {\land }}\ Q$	$P\Rightarrow Q$	$P\Leftarrow Q$	$P\Leftrightarrow Q$
Т	Т	Т	Т	Ф	Т	Т	Т	Т
Т	Ф	Ф	Т	Т	Ф	Ф	Т	Ф
Ф	Т	Ф	Т	Т	Ф	Т	Ф	Ф
Ф	Ф	Ф	Ф	Ф	Т	Т	Т	Т
п	вопрос	$P\land Q$	$P\lor Q$	$P\ {\underline {\lor }}\ Q$	$P\ {\underline {\land }}\ Q$	$P\Rightarrow Q$	$P\Leftarrow Q$	$P\Leftrightarrow Q$
		И (соединение)	ИЛИ (дизъюнкция)	БЕСПЛАТНО (Эксклюзивный или)	ИСНО-ИЛИ (исключительно ни)	условный "если-то"	условный "если"	двуусловный "если и только если"
где Т означает истину и F означает ложь

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

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

∧ Т Ф Т Т Ф Ф Ф Ф

∨ Т Ф Т Т Т Ф Т Ф

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

истинности в

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

При использовании целочисленного представления таблицы истинности выходное значение LUT можно получить путем вычисления битового индекса k на основе входных значений LUT, и в этом случае выходным значением LUT является k -й бит целого числа. Например, чтобы оценить выходное значение LUT с учетом массива из n логических входных значений, битовый индекс выходного значения таблицы истинности можно вычислить следующим образом: если i -й вход верен, пусть $V_{i}=1$, иначе легко $V_{i}=0$. Тогда k -й бит двоичного представления таблицы истинности является выходным значением LUT, где $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$	$R$
Т	Т	Т	Ф
Т	Ф	Ф	Т
Ф	Т	Ф	Т
Ф	Ф	Ф	Ф

где A — первый операнд, B — второй операнд, C — цифра переноса, а R — результат.

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

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

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

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

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

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

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

АВС* |  ЧР
 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

 То же, что и предыдущее, но...
 C* = перенос из предыдущего сумматора
 

Методы написания таблиц истинности

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

Альтернативный метод

Ли Арчи, профессор Университета Ландера , рекомендует эту процедуру, которая обычно используется в опубликованных таблицах истинности:

1. Выпишите количество переменных (соответствующее количеству утверждений) в алфавитном порядке.
2. Необходимое количество строк — 2. ^н где n — количество переменных. (Например, с тремя переменными 2 ³ = 8).
3. Начните с правого столбца и чередуйте буквы T и F , пока не закончатся строки.
4. Затем перейдите влево к следующему столбцу и чередуйте пары букв T и F , пока не закончатся строки.
5. Затем перейдите к следующему левому столбцу и удваивайте количество букв T и F , пока не закончите.

Этот метод приводит к созданию таблиц истинности, таких как следующая таблица для « P ⊃ (Q ∨ R ⊃ (R ⊃ ¬P)) », созданная Стивеном Коулом Клини :

п	вопрос	р	п ⊃ ( Q ∨ р ⊃ ( р ⊃ ¬ P ))
т	т	т	ж
т	т	ж	т
т	ж	т	ж
т	ж	ж	т
ж	т	т	т
ж	т	ж	т
ж	ж	т	т
ж	ж	ж	т

Комбинаторный метод

Колин Хаусон , с другой стороны, считает, что «это хорошее практическое правило» — делать следующее:

начать со всеми Т, затем все способы (три) два Т можно соединить с одним Ф, затем все способы (три) одно Т можно соединить с двумя Ф, а затем закончить всеми Ф. Если сложное слово составлено из n различных букв предложения, его таблица истинности будет иметь 2 ^н строк, так как есть два способа присвоить Т или F первой букве, и для каждого из них будет два способа присвоить Т или F второй, и для каждого из них будет два способа присвоить Т или F. F до третьего и так далее, давая 2.2.2. …, n раз, что равно 2 ^н .

В результате получаются таблицы истинности, подобные этой таблице, «показывающие, что (A→C)∧(B→C) и (A∨B)→C функционально эквивалентны истинности », смоделированные по образцу таблицы, созданной Хаусоном :

А	Б	С	(А → С) ∧ (В → С)	(А ∨ Б) → С
Т	Т	Т	Т	Т
Т	Т	Ф	Ф	Ф
Т	Ф	Т	Т	Т
Ф	Т	Т	Т	Т
Ф	Ф	Т	Т	Т
Ф	Т	Ф	Ф	Ф
Т	Ф	Ф	Ф	Ф
Ф	Ф	Ф	Т	Т

Размер таблиц истинности

Если входных переменных n , то их 2. ^н возможные комбинации их истинностных значений. Данная функция может выдавать истину или ложь для каждой комбинации, поэтому количество различных функций от n переменных равно двойной экспоненте 2. ^{2 н} .

н	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.2 × 10 77

Таблицы истинности для функций трех и более переменных приводятся редко.

Таблицы истинности сентенциальных операторов

Обзорная таблица

Вот расширенная таблица истинности, дающая определения всех шестнадцати возможных функций истинности двух логических переменных p и q :

п	д		Ф 0	НИ 1	↚ 2	¬p 3	ПРОСТОЙ 4	¬q 5	БЕСПЛАТНО 6	NAND 7	И 8	ИСНО-ИЛИ 9	д 10	ПОДРАЗУМЕВАТЬ 11	п 12	← 13	ИЛИ 14	Т 15
Т	Т		Ф	Ф	Ф	Ф	Ф	Ф	Ф	Ф	Т	Т	Т	Т	Т	Т	Т	Т
Т	Ф		Ф	Ф	Ф	Ф	Т	Т	Т	Т	Ф	Ф	Ф	Ф	Т	Т	Т	Т
Ф	Т		Ф	Ф	Т	Т	Ф	Ф	Т	Т	Ф	Ф	Т	Т	Ф	Ф	Т	Т
Ф	Ф		Ф	Т	Ф	Т	Ф	Т	Ф	Т	Ф	Т	Ф	Т	Ф	Т	Ф	Т
С			✓	✓					✓	✓	✓	✓					✓	✓
Доцент			✓						✓		✓	✓	✓		✓		✓	✓
Прил.			Ф 0	НИ 1	↛ 4	¬q 5	ПРОСТОЙ 2	¬p 3	БЕСПЛАТНО 6	NAND 7	И 8	ИСНО-ИЛИ 9	п 12	ПОДРАЗУМЕВАТЬ 13	д 10	→ 11	ИЛИ 14	Т 15
Нег			Т 15	ИЛИ 14	← 13	п 12	ПОДРАЗУМЕВАТЬ 11	д 10	ИСНО-ИЛИ 9	И 8	NAND 7	БЕСПЛАТНО 6	¬q 5	ПРОСТОЙ 4	¬p 3	↚ 2	НИ 1	Ф 0
Двойной			Т 15	NAND 7	→ 11	¬p 3	← 13	¬q 5	ИСНО-ИЛИ 9	НИ 1	ИЛИ 14	БЕСПЛАТНО 6	д 10	↚ 2	п 12	↛ 4	И 8	Ф 0
Левая рука					Ф				Ф		Т	Т	Т, Ф	Т			Ф
Избавлять							Ф		Ф		Т	Т			Т, Ф	Т	Ф

где

Т = правда.

Ф = ложь.

Верхние индексы ⁰ к ¹⁵ — это число, полученное в результате чтения четырех значений истинности как двоичного числа с F = 0 и T = 1.

Строка 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 op Q = ¬(P op2 Q) .

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

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

Строка R id оператора, показывает правые идентификаторы если он имеет какие-либо значения I такие, что P op I = P .

Таблица Витгенштейна

В предложении 5.101 Логико-философского трактата Витгенштейн перечислил приведенную выше таблицу следующим образом:

	Истинные значения		Оператор		Название операции	Научный труд
0	(ФФФФ)(п, q)	⊥	ЛОЖЬ	Опк	Противоречие	р и не р; и q и не q
1	(БФПФ)(p, q)	НИ	п ↓ q	Xpq	Логическое НО	ни п , ни q
2	(ФФТФ)(п, q)	↚	п ↚ д	миль на галлон	Обратная неимпликация	q , а не p
3	(ФФТТ)(p, q)	¬п , ~п	¬p	Нп , Фпк	Отрицание	не п
4	(ФТФФ)(п, q)	↛	п ↛ д	Лпк	Материальная непричастность	р , а не q
5	(FTFT)(p, q)	¬q , ~q	¬q	Нк , Гпк	Отрицание	не д
6	(ФТТФ)(п, q)	БЕСПЛАТНО	п ⊕ д	Jpq	Эксклюзивная дизъюнкция	p или q , но не оба одновременно
7	(ФТТТ)(п, ​​q)	NAND	п ↑ q	Dpq	Логическое NAND	не одновременно p и q
8	(ТФФФ)(п, q)	И	п ∧ q	Кпк	Логическое соединение	п и д
9	(TFFT)(p, q)	ИСНО-ИЛИ	p тогда и только тогда, когда q	Эпк	Логическое двуусловие	если р, то q ; и если q , то p
10	(ТФТФ)(п, q)	д	д	HPQ	Функция проецирования	д
11	(ТФТТ)(п, ​​q)	п → д	если р , то q	Цена за покупку	Материальное значение	если р , то q
12	(ТТФФ)(п, q)	п	п	IPQ	Функция проецирования	п
13	(ТТФТ)(п, ​​q)	р ← д	если q , то p	Бпк	Обратная импликация	если q , то p
14	(ТТТФ)(п, д)	ИЛИ	п ∨ q	Апк	Логическая дизъюнкция	п или д
15	(ТТТТ)(п, ​​д)	⊤	истинный	ВПК	тавтология	если р, то р; и если q, то q

Таблица истинности, представленная каждой строкой, получается путем добавления последовательности, указанной в «Истинные значения» _строке , к таблице.

п	Т	Т	Ф	Ф
д	Т	Ф	Т	Ф

Например, таблица

п	Т	Т	Ф	Ф
д	Т	Ф	Т	Ф
11	Т	Ф	Т	Т

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

Нулевые операции

Есть 2 нулевые операции:

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

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

Выходное значение всегда истинно, поскольку у этого оператора ноль операндов и, следовательно, нет входных значений.

п	Т
Т	Т
Ф	Т

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

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

п	Ф
Т	Ф
Ф	Ф

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

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

• Унарная идентичность
• Унарное отрицание

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

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

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

п	п
Т	Т
Ф	Ф

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

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

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

п	¬p
Т	Ф
Ф	Т

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

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

Логический союз (И)

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

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

п	д	п ∧ 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 ) выглядит следующим образом:

п	д	п ∨ 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 ) выглядит следующим образом:

п	д	п ↔ q
Т	Т	Т
Т	Ф	Ф
Ф	Т	Ф
Ф	Ф	Т

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

Эксклюзивная дизъюнкция

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

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

п	д	п ⊕ д
Т	Т	Ф
Т	Ф	Т
Ф	Т	Т
Ф	Ф	Ф

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

Логическое NAND

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

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

п	д	п ↑ q
Т	Т	Ф
Т	Ф	Т
Ф	Т	Т
Ф	Ф	Т

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

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

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

п	д	п ∧ q	¬( п ∧ q )	¬ p	¬ q	(¬ p ) ∨ (¬ q )
Т	Т	Т	Ф	Ф	Ф	Ф
Т	Ф	Ф	Т	Ф	Т	Т
Ф	Т	Ф	Т	Т	Ф	Т
Ф	Ф	Ф	Т	Т	Т	Т

Логическое НО

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

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

п	д	п ↓ q
Т	Т	Ф
Т	Ф	Ф
Ф	Т	Ф
Ф	Ф	Т

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

п	д	п ∨ q	¬( п ∨ q )	¬ p	¬ q	(¬ p ) ∧ (¬ q )
Т	Т	Т	Ф	Ф	Ф	Ф
Т	Ф	Т	Ф	Ф	Т	Ф
Ф	Т	Т	Ф	Т	Ф	Ф
Ф	Ф	Ф	Т	Т	Т	Т

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

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

См. также

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

Ссылки

Цитируемые работы

• Боченский, Юзеф Мария (1959). Краткое изложение математической логики . Перевод Берда, Отто. Д. Рейдель. дои : 10.1007/978-94-017-0592-9 . ISBN  978-94-017-0592-9 .
• Эндертон, Х. (2001). Математическое введение в логику (2-е изд.). Харкорт Академик Пресс. ISBN  0-12-238452-0 .
• Куайн, Западная Вирджиния (1982). Методы логики (4-е изд.). Издательство Гарвардского университета. ISBN  978-0-674-57175-4 .

Внешние ссылки

• «Таблица истинности» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Таблицы истинности, тавтологии и логическая эквивалентность
• Анеллис, Ирвинг Х. (2011). «Функциональный анализ истинности Пирса и происхождение таблиц истинности». arXiv : 1108.2429 [ math.HO ].
• Преобразование таблиц истинности в логические выражения