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