Sheffer stroke

Sheffer stroke
NAND
Определение
Таблица истинности
Логический вентиль
Нормальные формы
Дизъюнктивный
соединительный
Полином Жегалкина
Решетки постовые
0-сохраняющий	нет
1-сохраняющий	нет
монотонный	нет
Аффинный	нет
Самодвойственный	нет
	v ; т ; и ;

В булевых функциях и исчислении высказываний обозначает штрих Шеффера логическую операцию , эквивалентную отрицанию операции соединения . , выражаемую на обычном языке как «не то и другое» Его еще называют несоединением или альтернативным отрицанием. ^[1] (поскольку он фактически говорит, что по крайней мере один из его операндов является ложным) или NAND («не и»). ^[1] В цифровой электронике он соответствует вентилю И-НЕ . Он назван в честь Генри Мориса Шеффера и пишется как $\mid$ или как $\uparrow$ или как ${\overline {\wedge }}$ или как $Dpq$ в польской записи Лукасевича (но не как ||, часто используемой для обозначения дизъюнкции ).

Его двойником является оператор NOR (также известный как стрелка Пирса , кинжал Куайна или оператор Уэбба ). Как и его двойник, NAND может использоваться сам по себе, без какого-либо другого логического оператора, для создания логической формальной системы (что делает NAND функционально завершенным ). Это свойство делает вентиль NAND решающим для современной цифровой электроники , включая его использование в компьютерных процессоров конструкции .

Определение

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

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

Таблица истинности $A\uparrow B$ заключается в следующем.

$A$	$B$	$A\uparrow B$
Ф	Ф	Т
Ф	Т	Т
Т	Ф	Т
Т	Т	Ф

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

Инсульт Шеффера $P$ и $Q$ является отрицанием их соединения

$P\uparrow Q$	$\Leftrightarrow$	$\neg (P\land Q)$
	$\Leftrightarrow$	$\neg$

По законам Де Моргана это также эквивалентно дизъюнкции отрицаний $P$ и $Q$

$P\uparrow Q$	$\Leftrightarrow$	$\neg P$	$\lor$	$\neg Q$
	$\Leftrightarrow$		$\lor$

Альтернативные обозначения и названия

Пирс был первым, кто показал функциональную полноту нессоединения (представив это как ${\overline {\curlywedge }}$ ), но не опубликовал свой результат. ^[2]^[3] Редактор Пирса добавил: ${\overline {\curlywedge }}$ ) для нерасхождения ^{[ нужна ссылка ]}. ^[3]

В 1911 году Штамм первым опубликовал доказательство полноты нессоединения, представив это с помощью $\sim$ ( крючок Штамма ) ^[4] и неразрывность в печати впервые показали их функциональную завершенность. ^[5]

В 1913 году Шеффер описал нерасхождение, используя $\mid$ и показал свою функциональную полноту. Шеффер также использовал $\wedge$ за нерасхождение. ^{[ нужна ссылка ]} Многие люди, начиная с Никода в 1917 году, а затем Уайтхеда, Рассела и многих других, ошибочно полагали, что Шеффер описал нессоединение, используя $\mid$ , назвав это Шефферским ударом.

В 1928 году Гильберт и Акерманн описали несвязность с помощью оператора $/$ . ^[6]^[7]

В 1929 году Лукасевич использовал $D$ в $Dpq$ за несоединение в его польской записи . ^[8]

Альтернативное обозначение несоединения: $\uparrow$ . Неясно, кто первым ввел это обозначение, хотя соответствующие $\downarrow$ для нерасхождения был использован Куайном в 1940 г. ^[9]

История

Инсульт назван в честь Генри Мориса Шеффера , который в 1913 году опубликовал статью в « Трудах Американского математического общества». ^[10] обеспечив аксиоматизацию булевых алгебр с использованием штриха, и доказал ее эквивалентность стандартной формулировке Хантингтона, используя знакомые операторы логики высказываний ( И , ИЛИ , НЕ ). Из-за самодвойственности булевых алгебр аксиомы Шеффера одинаково справедливы для операций И-НЕ и ИЛИ-НЕ вместо штриха. Шеффер в своей статье интерпретировал черту как знак нерасхождения ( НОР ), упомянув о несоединении только в сноске и без специального знака для него. Именно Жан Нико впервые использовал штрих как знак нессоединения (NAND) в статье 1917 года, и с тех пор это стало современной практикой. ^[11]^[12] Рассел и Уайтхед использовали штрих Шеффера во втором издании Principia Mathematica 1927 года и предложили его в качестве замены операций «ИЛИ» и «НЕ» в первом издании.

Чарльз Сандерс Пирс (1880) открыл функциональную полноту NAND или NOR более 30 лет назад, используя термин ampheck (что означает «разрез в обе стороны»), но так и не опубликовал свое открытие. За два года до Шеффера Эдвард Стамм [ pl ] также описал операторы NAND и NOR и показал, что с их помощью можно выразить другие логические операции. ^[5]

Характеристики

И-НЕ не обладает ни одним из следующих пяти свойств, отсутствие каждого из которых обязательно, а отсутствие всех из которых достаточно для хотя бы одного члена набора функционально полных операторов: сохранение истинности, ложность- сохранение, линейность , монотонность , самодвойственность . (Оператор сохраняет истину (или ложь), если его значение равно истине (ложности), когда все его аргументы являются истиной (ложью).) Следовательно, {NAND} является функционально полным набором.

Это также можно реализовать следующим образом: все три элемента функционально полного набора {И, ИЛИ, НЕ} могут быть построены с использованием только И-НЕ . Таким образом, набор {NAND} также должен быть функционально полным.

Другие логические операции с использованием штриха Шеффера.

Выражается в терминах NAND $\uparrow$ , обычными операторами пропозициональной логики являются:

$\neg P$	$\Leftrightarrow$	$P$	$\uparrow$	$P$
	$\Leftrightarrow$		$\uparrow$

$P\rightarrow Q$	$\Leftrightarrow$	$~P$	$\uparrow$	$(Q\uparrow Q)$	$\Leftrightarrow$	$~P$	$\uparrow$	$(P\uparrow Q)$
	$\Leftrightarrow$		$\uparrow$		$\Leftrightarrow$		$\uparrow$

$P\leftrightarrow Q$	$\Leftrightarrow$	$(P\uparrow Q)$	$\uparrow$	$((P\uparrow P)\uparrow (Q\uparrow Q))$
	$\Leftrightarrow$		$\uparrow$

$P\land Q$	$\Leftrightarrow$	$(P\uparrow Q)$	$\uparrow$	$(P\uparrow Q)$
	$\Leftrightarrow$		$\uparrow$

$P\lor Q$	$\Leftrightarrow$	$(P\uparrow P)$	$\uparrow$	$(Q\uparrow Q)$
	$\Leftrightarrow$		$\uparrow$

Функциональная полнота

Штрих Шеффера, взятый сам по себе, представляет собой функционально законченный набор связок. ^[13]^[14] Это можно доказать, показав сначала с помощью таблицы истинности , что $\neg A$ истинностно-функционально эквивалентен $A\uparrow A$ . ^[15] Тогда, поскольку $A\uparrow B$ истинностно-функционально эквивалентен $\neg (A\land B)$ , ^[15] и $A\lor B$ эквивалентно $\neg (\neg A\land \neg B)$ , ^[15] штриха Шеффера достаточно, чтобы определить набор связок $\{\land ,\lor ,\neg \}$ , ^[15] является функционально полным который, как показывает теорема о дизъюнктивной нормальной форме, . ^[15]

См. также

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 43. ИСБН 978-0-415-13342-5 .
^ Пирс, CS (1933) [1880]. «Булова алгебра с одной константой». В Хартшорне, К.; Вайс, П. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV. Простейшая математика . Массачусетс: Издательство Гарвардского университета. стр. 13–18.
^ Jump up to: Перейти обратно: ^а ^б Пирс, CS (1933) [1902]. «Простейшая математика». В Хартшорне, К.; Вайс, П. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV. Простейшая математика . Массачусетс: Издательство Гарвардского университета. стр. 189–262.
^ Зак, Р. (18 февраля 2023 г.). «Удар Шеффера перед Шеффером: Эдвард Стамм» . Проверено 2 июля 2023 г.
^ Jump up to: Перейти обратно: ^а ^б Штамм, Эдвард Бронислав [на польском языке] (1911). «Вклад в алгебру логики». Ежемесячные журналы по математике и физике (на немецком языке). 22 (1): 137–149. дои : 10.1007/BF01742795 . S2CID 119816758 .
^ Гильберт, Д.; Акерманн, В. (1928). Основы теоретической логики (на немецком языке) (1-е изд.). Берлин: Издательство Юлиуса Шпрингера. п. 9.
^ Гильберт, Д.; Акерманн, В. (1950). Люси, Р.Э. (ред.). Принципы математической логики . Перевод Хаммонда, Л.М.; Леки, Г.Г.; Стейнхардт, Ф. Нью-Йорк: Издательство Челси. п. 11.
^ Лукасевич, Дж. (1958) [1929]. Элементы математической логики (на польском языке) (2-е изд.). Варшава: Национальное научное издательство.
^ Куайн, WV (1981) [1940]. Математическая логика (пересмотренная ред.). Кембридж, Лондон, Нью-Йорк, Нью-Рошель, Мельбурн и Сидней: Издательство Гарвардского университета. п. 45.
^ Шеффер, Генри Морис (1913). «Набор пяти независимых постулатов для булевых алгебр с применением к логическим константам» . Труды Американского математического общества . 14 (4): 481–488. дои : 10.2307/1988701 . JSTOR 1988701 .
^ Никод, Жан Жорж Пьер (1917). «Уменьшение количества примитивных предложений логики». Труды Кембриджского философского общества . 19 : 32–41.
^ Черч, Алонзо (1956). Введение в математическую логику . Том. 1. Издательство Принстонского университета . п. 134.
^ Вайсштейн, Эрик В. «Исчисление высказываний» . mathworld.wolfram.com . Проверено 22 марта 2024 г.
^ Фрэнкс, Кертис (2023), «Логика высказываний» , в Залте, Эдвард Н.; Нодельман, Ури (ред.), Стэнфордская энциклопедия философии (изд. осенью 2023 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено 22 марта 2024 г.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. стр. 41–43. ISBN 978-0-415-13342-5 .

Дальнейшее чтение

Боченский, Юзеф Мария ; Менне, Альберт Генрих [на немецком языке] (1960). Точность математической логики . Перевод Берда, Отто (переработанная редакция). Дордрехт, Южная Голландия, Нидерланды: Д. Рейдель . (Примечание. Отредактировано и переведено с французского и немецкого изданий: Précis de logique mathématique )
Пирс, Чарльз Сандерс (1931–1935) [1880]. «Булова алгебра с одной константой». В Хартшорне, Чарльз ; Вайс, Пол (ред.). Сборник статей Чарльза Сандерса Пирса . Том. 4. Кембридж: Издательство Гарвардского университета . стр. 12–20.

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

[:13-1] Jump up to: Перейти обратно: ^а ^б Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 43. ИСБН 978-0-415-13342-5 .

[peirce1880-2] Пирс, CS (1933) [1880]. «Булова алгебра с одной константой». В Хартшорне, К.; Вайс, П. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV. Простейшая математика . Массачусетс: Издательство Гарвардского университета. стр. 13–18.

[peirce1902-3] Jump up to: Перейти обратно: ^а ^б Пирс, CS (1933) [1902]. «Простейшая математика». В Хартшорне, К.; Вайс, П. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV. Простейшая математика . Массачусетс: Издательство Гарвардского университета. стр. 189–262.

[zach2023-4] Зак, Р. (18 февраля 2023 г.). «Удар Шеффера перед Шеффером: Эдвард Стамм» . Проверено 2 июля 2023 г.

[Stamm_1911-5] Jump up to: Перейти обратно: ^а ^б Штамм, Эдвард Бронислав [на польском языке] (1911). «Вклад в алгебру логики». Ежемесячные журналы по математике и физике (на немецком языке). 22 (1): 137–149. дои : 10.1007/BF01742795 . S2CID 119816758 .

[hilbert-ackermann1928-6] Гильберт, Д.; Акерманн, В. (1928). Основы теоретической логики (на немецком языке) (1-е изд.). Берлин: Издательство Юлиуса Шпрингера. п. 9.

[hilbert-ackermann1950-7] Гильберт, Д.; Акерманн, В. (1950). Люси, Р.Э. (ред.). Принципы математической логики . Перевод Хаммонда, Л.М.; Леки, Г.Г.; Стейнхардт, Ф. Нью-Йорк: Издательство Челси. п. 11.

[lukasiewicz1929-8] Лукасевич, Дж. (1958) [1929]. Элементы математической логики (на польском языке) (2-е изд.). Варшава: Национальное научное издательство.

[quine1940-9] Куайн, WV (1981) [1940]. Математическая логика (пересмотренная ред.). Кембридж, Лондон, Нью-Йорк, Нью-Рошель, Мельбурн и Сидней: Издательство Гарвардского университета. п. 45.

[Sheffer_1913-10] Шеффер, Генри Морис (1913). «Набор пяти независимых постулатов для булевых алгебр с применением к логическим константам» . Труды Американского математического общества . 14 (4): 481–488. дои : 10.2307/1988701 . JSTOR 1988701 .

[Nicod_1917-11] Никод, Жан Жорж Пьер (1917). «Уменьшение количества примитивных предложений логики». Труды Кембриджского философского общества . 19 : 32–41.

[Church_1956-12] Черч, Алонзо (1956). Введение в математическую логику . Том. 1. Издательство Принстонского университета . п. 134.

[:18-13] Вайсштейн, Эрик В. «Исчисление высказываний» . mathworld.wolfram.com . Проверено 22 марта 2024 г.

[:2-14] Фрэнкс, Кертис (2023), «Логика высказываний» , в Залте, Эдвард Н.; Нодельман, Ури (ред.), Стэнфордская энциклопедия философии (изд. осенью 2023 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено 22 марта 2024 г.

[:132-15] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. стр. 41–43. ISBN 978-0-415-13342-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

v т и Общие логические связи
Tautology/True $\top$
Alternative denial (NAND gate) $\uparrow$ Converse implication $\leftarrow$ Implication (IMPLY gate) $\rightarrow$ Disjunction (OR gate) $\lor$
Negation (NOT gate) $\neg$ Exclusive or (XOR gate) $\not \leftrightarrow$ Biconditional (XNOR gate) $\leftrightarrow$ Statement (Digital buffer)
Joint denial (NOR gate) $\downarrow$ Nonimplication (NIMPLY gate) $\nrightarrow$ Converse nonimplication $\nleftarrow$ Conjunction (AND gate) $\land$
Contradiction/False $\bot$
Philosophy portal