инсульт Шеффера

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

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

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

Определение

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

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

Таблица истинности выглядит следующим образом. ${\displaystyle A\uparrow B}$

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

Черта Шеффера в and является отрицанием их союза ${\displaystyle P}$ ${\displaystyle Q}$

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

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

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

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

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

В 1928 году Гильберт и Аккерман описали неконъюнкцию с помощью оператора . ^{[6] [7]} ${\displaystyle /}$

В 1929 году Лукасевич использовал in для обозначения несвязности в своей польской нотации . ^[8] ${\displaystyle D}$ ${\displaystyle Dpq}$

Альтернативная нотация для неконъюнкции — . Неясно, кто первым ввел эту нотацию, хотя соответствующая для недизъюнкции использовалась Куайном в 1940 году. ^[9] ${\displaystyle \uparrow }$ ${\displaystyle \downarrow }$

История

Штрих назван в честь Генри Мориса Шеффера , который в 1913 году опубликовал статью в Transactions of the American Mathematical Society ^[10], предоставив аксиоматизацию булевых алгебр с использованием штриха, и доказал ее эквивалентность стандартной формулировке ее Хантингтона , использующего известные операторы пропозициональной логики ( AND , OR , NOT ). Из-за самодвойственности булевых алгебр аксиомы Шеффера одинаково справедливы для операций NAND или NOR вместо штриха. Шеффер интерпретировал штрих как знак недизъюнкции ( NOR ) в своей статье, упомянув неконъюнкцию только в сноске и без специального знака для нее. Жан Никод первым использовал штрих как знак неконъюнкции (NAND) в статье 1917 года, и с тех пор это стало современной практикой. ^{[11] [12]} Рассел и Уайтхед использовали штрих Шеффера во втором издании Principia Mathematica 1927 года и предложили его в качестве замены операциям «ИЛИ» и «НЕ» первого издания.

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

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

НЕ-И является коммутативным, но не ассоциативным, что означает, что но . ^[13] ${\displaystyle P\uparrow Q\leftrightarrow Q\uparrow P}$ ${\displaystyle (P\uparrow Q)\uparrow R\not \leftrightarrow P\uparrow (Q\uparrow R)}$

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

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

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

Другие булевы операции в терминах штриха Шеффера

Выраженные в терминах НЕ-И , обычные операторы пропозициональной логики таковы: ${\displaystyle \uparrow }$

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

• Булев домен
• КМОП-матрица
• Эквивалент затвора (GE)
• Логический граф
• Минимальные аксиомы для булевой алгебры
• NAND флэш-память
• NAND-логика
• Закон Пирса
• Стрелка Пирса = NOR
• Единственный достаточный оператор

Ссылки

1. Howson, Colin (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. стр. 43. ISBN 978-0-415-13342-5.
2. Пирс, CS (1933) [1880]. «Булева алгебра с одной константой». В Hartshorne, C.; Weiss, P. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV. Простейшая математика . Массачусетс: Издательство Гарвардского университета. стр. 13–18.
3. Peirce, CS (1933) [1902]. «Простейшая математика». В Hartshorne, C.; Weiss, P. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV «Простейшая математика» . Массачусетс: Издательство Гарвардского университета. стр. 189–262.
4. Зак, Р. (18 февраля 2023 г.). «Удар Шеффера перед Шеффером: Эдвард Стамм» . Проверено 2 июля 2023 г.
5. Штамм, Эдвард Бронислав [на польском языке] (1911). «Beitrag zur Algebra der Logik». Monatshefte für Mathematik und Physik (на немецком языке). 22 (1): 137–149. дои : 10.1007/BF01742795. S2CID  119816758.
6. Гильберт, Д.; Акерманн, В. (1928). Grundzügen der theoretischen Logik (на немецком языке) (1-е изд.). Берлин: Verlag фон Юлиус Шпрингер. п. 9.
7. Гильберт, Д.; Аккерман, В. (1950). Люс, Р. Э. (ред.). Принципы математической логики . Перевод Хаммонда, Л. М.; Леки, Г. Г.; Стейнхардта, Ф. Нью-Йорк: Chelsea Publishing Company. стр. 11.
8. Лукасевич, Дж. (1958) [1929]. Elementy logiki matematycznej (на польском языке) (2-е изд.). Варшава: Państwowe Wydawnictwo Naukowe.
9. Куайн, У. В. (1981) [1940]. Математическая логика (пересмотренное издание). Кембридж, Лондон, Нью-Йорк, Нью-Рошель, Мельбурн и Сидней: Издательство Гарвардского университета. стр. 45.
10. Шеффер, Генри Морис (1913). «Набор из пяти независимых постулатов для булевых алгебр с применением к логическим константам». Труды Американского математического общества . 14 (4): 481–488. doi : 10.2307/1988701 . JSTOR  1988701.
11. Никод, Жан Жорж Пьер (1917). «Сокращение числа примитивных предложений логики». Труды Кембриджского философского общества . 19 : 32–41.
12. Чёрч, Алонзо (1956). Введение в математическую логику . Т. 1. Princeton University Press . С. 134.
13. Рао, Г. Шанкер (2006). Математические основы компьютерных наук. IK International Pvt Ltd. стр. 21. ISBN 978-81-88237-49-4.
14. Weisstein, Eric W. "Исчисление высказываний". mathworld.wolfram.com . Получено 22.03.2024 .
15. Фрэнкс, Кертис (2023), «Пропозициональная логика», в Zalta, Edward N.; Nodelman, Uri (ред.), The Stanford Encyclopedia of Philosophy (ред. осень 2023 г.), Metaphysics Research Lab, Stanford University , получено 22.03.2024
16. Эмиль Леон Пост (1941). Двузначные итеративные системы математической логики. Annals of Mathematics studies. Том 5. Принстон: Princeton University Press. doi : 10.1515/9781400882366. ISBN 9781400882366.
17. Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. С. 41–43. ISBN 978-0-415-13342-5.

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

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

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

• Статья Шеффера Строка в Интернет-энциклопедии философии
• http://hyperphysicals.phy-astr.gsu.edu/hbase/electronic/nand.html
• Реализации 2- и 4-входовых вентилей NAND
• Доказательства некоторых аксиом с помощью функции штриха Ясуо Сето @ Project Euclid