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

Бинарная операция, которая истинна тогда и только тогда, когда оба операнда ложны.

В булевой логике , логическое НЕ ИЛИ , ^[1] недизъюнкция , или совместное отрицание ^[1] является оператором истинностно-функциональным , который производит результат, который является отрицанием логического ИЛИ . То есть, предложение формы ( p НЕ q ) истинно точно тогда, когда ни p , ни q не являются истинными, т. е. когда оба p и q являются ложными . Это логически эквивалентно и , где символ означает логическое отрицание , означает ИЛИ , а означает И . ${\displaystyle \neg (p\lor q)}$ ${\displaystyle \neg p\land \neg q}$ ${\displaystyle \neg }$ ${\displaystyle \lor }$ ${\displaystyle \land }$

Недизъюнкция обычно обозначается как или ( префикс) или . ${\displaystyle \downarrow }$ ${\displaystyle {\overline {\vee }}}$ ${\displaystyle X}$ ${\displaystyle \operatorname {NOR} }$

Как и его дуальный оператор NAND ( также известный как штрих Шеффера — обозначаемый как , или ), NOR может использоваться сам по себе, без какого-либо другого логического оператора, для создания логической формальной системы (делая NOR функционально полной ). ${\displaystyle \uparrow }$ ${\displaystyle \mid }$ ${\displaystyle /}$

Компьютер , использовавшийся в космическом корабле, который впервые доставил людей на Луну , бортовой компьютер Apollo , был полностью построен с использованием вентилей NOR с тремя входами. ^[2]

Определение

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

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

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

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

Логическое НЕ-ИЛИ является отрицанием дизъюнкции: ${\displaystyle \downarrow }$

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

Пирс первым показал функциональную полноту недизъюнкции, хотя он и не опубликовал свой результат. ^{[3] [4]} Пирс использовал для неконъюнкции и для недизъюнкции (фактически, то, что использовал сам Пирс, и он не ввел, в то время как редакторы Пирса сделали такое недвусмысленное использование ). ^[4] Пирс назвал ${\displaystyle {\overline {\curlywedge }}}$ ${\displaystyle \curlywedge }$ ${\displaystyle \curlywedge }$ ${\displaystyle {\overline {\curlywedge }}}$ ${\displaystyle \curlywedge }$ampheck (от древнегреческого ἀμφήκης , amphēkēs , «режущий в обоих направлениях»).^[4]

В 1911 году Штамм  [pl] первым опубликовал описание как неконъюнкции (используя крючок Штамма), так и недизъюнкции (используя звездочку Штамма) и показал их функциональную полноту. ^{[5] [6]} Обратите внимание, что большинство случаев использования в логической нотации используют this для отрицания. ${\displaystyle \sim }$ ${\displaystyle *}$ ${\displaystyle \sim }$

В 1913 году Шеффер описал недизъюнкцию и показал ее функциональную полноту. Шеффер использовал для неконъюнкции и для недизъюнкции. ${\displaystyle \mid }$ ${\displaystyle \wedge }$

В 1935 году Уэбб описал недизъюнкцию для -значной логики и использовал ее для оператора. Поэтому некоторые называют его оператором Уэбба , ^[7] операцией Уэбба ^[8] или функцией Уэбба . ^[9] ${\displaystyle n}$ ${\displaystyle \mid }$

В 1940 году Куайн также описал недизъюнкцию и использование оператора. ^[10] Поэтому некоторые называют оператор стрелой Пирса или кинжалом Куайна . ${\displaystyle \downarrow }$

В 1944 году Чёрч также описал недизъюнкцию и использование оператора. ^[11] ${\displaystyle {\overline {\vee }}}$

В 1954 году Бохеньский использовал для обозначения недизъюнкции в польской нотации . ^[12] ${\displaystyle X}$ ${\displaystyle Xpq}$

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

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

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

Логическое НЕ-ИЛИ, взятое само по себе, является функционально полным набором связок. ^[14] Это можно доказать, сначала показав с помощью таблицы истинности , что является истинностно-функционально эквивалентным . ^[15] Затем, поскольку является истинностно-функционально эквивалентным , ^[15] и эквивалентно , ^[15] логического НЕ-ИЛИ достаточно для определения набора связок , ^[15] который, как показано, является истинностно-функционально полным по теореме о дизъюнктивной нормальной форме . ^[15] ${\displaystyle \neg A}$ ${\displaystyle A\downarrow A}$ ${\displaystyle A\downarrow B}$ ${\displaystyle \neg (A\lor B)}$ ${\displaystyle A\lor B}$ ${\displaystyle \neg (\neg A\land \neg B)}$ ${\displaystyle \{\land ,\lor ,\neg \}}$

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

Другие булевы операции в терминах логического НЕ-ИЛИ

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

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

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

• Побитовое НЕ-ИЛИ
• Булева алгебра
• Булев домен
• Булева функция
• Функциональная полнота
• NOR-вентиль
• Логика высказываний
• Единственный достаточный оператор
• Штрих Шеффера как символ логического НЕ-И

Ссылки

1. Howson, Colin (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. стр. 43. ISBN 978-0-415-13342-5.
2. Холл, Элдон С. (1996). Путешествие на Луну: История бортового компьютера Apollo . Рестон, Вирджиния, США: Американский институт аэронавтики и астронавтики . стр. 196. ISBN 1-56347-185-X.
3. Пирс, CS (1933) [1880]. «Булева алгебра с одной константой». В Hartshorne, C.; Weiss, P. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV. Простейшая математика . Массачусетс: Издательство Гарвардского университета. стр. 13–18.
4. Peirce, CS (1933) [1902]. «Простейшая математика». В Hartshorne, C.; Weiss, P. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV «Простейшая математика» . Массачусетс: Издательство Гарвардского университета. С. 189–262.
5. Штамм, Эдвард Бронислав [на польском языке] (1911). «Beitrag zur Algebra der Logik». Monatshefte für Mathematik und Physik (на немецком языке). 22 (1): 137–149. дои : 10.1007/BF01742795. S2CID  119816758.
6. Зак, Р. (18 февраля 2023 г.). «Удар Шеффера перед Шеффером: Эдвард Стамм» . Проверено 2 июля 2023 г.
7. Вебб, Дональд Лумис (май 1935). «Генерация любой n-значной логики одной бинарной операцией». Труды Национальной академии наук . 21 (5). США: Национальная академия наук : 252–254. Bibcode : 1935PNAS...21..252W. doi : 10.1073/pnas.21.5.252 . PMC 1076579. PMID  16577665. 
8. Васюкевич, Вадим О. (2011). "1.10 Venjunctive Properties (Basic Formulae)". Написано в Риге, Латвия. Асинхронные операторы последовательной логики: Venjunction & Sequention — Digital Circuits Analysis and Design . Lecture Notes in Electrical Engineering (LNEE). Том 101 (1-е изд.). Берлин / Гейдельберг, Германия: Springer-Verlag . стр. 20. doi :10.1007/978-3-642-21611-4. ISBN 978-3-642-21610-7. ISSN  1876-1100. LCCN  2011929655. стр. 20: Историческая справка […] Логический оператор NOR, называемый стрелкой Пирса и также известный как операция Вебба.(xiii+1+123+7 страниц) (Примечание. На задней обложке этой книги ошибочно указан том 4, хотя на самом деле это том 101.)
9. Фрейманн, Майкл; Ренфро, Дэйв Л.; Уэбб, Норман (2018-05-24) [2017-02-10]. "Кто такой Дональд Л. Уэбб?". История науки и математики. Stack Exchange . Архивировано из оригинала 2023-05-18 . Получено 2023-05-18 .
10. Куайн, У. В. (1981) [1940]. Математическая логика (пересмотренное издание). Кембридж, Лондон, Нью-Йорк, Нью-Рошель, Мельбурн и Сидней: Издательство Гарвардского университета. стр. 45.
11. Чёрч, А. (1996) [1944]. Введение в математическую логику . Нью-Джерси: Princeton University Press. стр. 37.
12. Боченский, JM (1954). Précis de logique mathématique (на французском языке). Нидерланды: Ф.Г. Крундер, Буссум, Пайс-Бас. п. 11.
13. Рао, Г. Шанкер (2006). Математические основы компьютерных наук. IK International Pvt Ltd. стр. 22. ISBN 978-81-88237-49-4.
14. Smullyan, Raymond M. (1995). Логика первого порядка . Нью-Йорк: Dover. С. 5, 11, 14. ISBN 978-0-486-68370-6.
15. Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. С. 41–43. ISBN 978-0-415-13342-5.

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

• Медиа, связанные с Logical NOR на Wikimedia Commons