Jump to content

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

(Перенаправлено с «Совместного отрицания »)

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

В булевой логике логическое ИЛИ , [1] нерасхождение или совместное отрицание [1] является функциональным оператором истинности, который дает результат, являющийся отрицанием логического или . То есть предложение формы ( p NOR q ) истинно именно тогда, когда ни p, ни q не являются истинными, т. е. когда и p и q ложны , . Это логически эквивалентно и , где символ означает логическое отрицание , означает ИЛИ , и означает И.

Нерасхождение обычно обозначается как или или (префикс) или .

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

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

Определение

[ редактировать ]

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

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

[ редактировать ]

Таблица истинности заключается в следующем:

Ф Ф Т
Ф Т Ф
Т Ф Ф
Т Т Ф

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

[ редактировать ]

Логическое НО является отрицанием дизъюнкции:

        
        

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

[ редактировать ]

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

В 1911 году Штамм [ pl ] первым опубликовал описание как нессоединения (с использованием , крючок Штамма) и нерасхождение (с использованием , звезда Штамма) и показали свою функциональную полноту. [5] [6] Обратите внимание, что большинство случаев использования в логической записи используйте это для отрицания.

В 1913 г. Шеффер описал нерасхождение и показал его функциональную полноту. Шеффер использовал за несоединение, и за нерасхождение.

В 1935 году Уэбб описал нерасхождение для -значная логика и использовать для оператора. Поэтому некоторые люди называют это оператором Уэбба , [7] Операция Уэбба [8] или функция Уэбба . [9]

В 1940 году Куайн также описал нерасхождение и использование для оператора. [10] Поэтому некоторые люди называют оператор стрелой Пирса или кинжалом Куайна .

В 1944 году Чёрч также описал нерасхождение и использование для оператора. [11]

В 1954 году Боченский использовал в для нерасхождения в польских обозначениях . [12]

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

[ редактировать ]

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

Другие логические операции с точки зрения логического NOR.

[ редактировать ]

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

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

        
        
   
        
        
 
        
        
   
        
        

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

[ редактировать ]

Логическое ИЛИ само по себе представляет собой функционально полный набор связок. [13] Это можно доказать, показав сначала с помощью таблицы истинности , что истинностно-функционально эквивалентен . [14] Тогда, поскольку истинностно-функционально эквивалентен , [14] и эквивалентно , [14] логического NOR достаточно, чтобы определить набор связок , [14] является функционально полным который, как показывает теорема о дизъюнктивной нормальной форме, . [14]

См. также

[ редактировать ]
  1. Перейти обратно: Перейти обратно: а б Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 43. ИСБН  978-0-415-13342-5 .
  2. ^ Холл, Элдон К. (1996). Путешествие на Луну: история компьютера управления Аполлоном . Рестон, Вирджиния, США: Американский институт аэронавтики и астронавтики . п. 196. ИСБН  1-56347-185-Х .
  3. ^ Пирс, CS (1933) [1880]. «Булова алгебра с одной константой». В Хартшорне, К.; Вайс, П. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV. Простейшая математика . Массачусетс: Издательство Гарвардского университета. стр. 13–18.
  4. Перейти обратно: Перейти обратно: а б с Пирс, CS (1933) [1902]. «Простейшая математика». В Хартшорне, К.; Вайс, П. (ред.). Сборник статей Чарльза Сандерса Пирса, том IV. Простейшая математика . Массачусетс: Издательство Гарвардского университета. стр. 189–262.
  5. ^ Штамм, Эдвард Бронислав [на польском языке] (1911). «Вклад в алгебру логики». Ежемесячные журналы по математике и физике (на немецком языке). 22 (1): 137–149. дои : 10.1007/BF01742795 . S2CID   119816758 .
  6. ^ Зак, Р. (18 февраля 2023 г.). «Удар Шеффера перед Шеффером: Эдвард Стамм» . Проверено 2 июля 2023 г.
  7. ^ Уэбб, Дональд Лумис (май 1935 г.). «Генерация любой n-значной логики одной бинарной операцией» . Труды Национальной академии наук . 21 (5). США: Национальная академия наук : 252. Бибкод : 1935PNAS...21..252W . дои : 10.1073/pnas.21.5.252 . ПМЦ   1076579 .
  8. ^ Васюкевич, Вадим О. (2011). «1.10 Венъюнктивные свойства (основные формулы)». Написано в Риге, Латвия. Асинхронные операторы последовательной логики: венъюнкция и секвенция — анализ и проектирование цифровых схем . Конспекты лекций по электротехнике (LNEE). Том. 101 (1-е изд.). Берлин / Гейдельберг, Германия: Springer-Verlag . п. 20. дои : 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. ^ Фрейманн, Майкл; Ренфро, Дэйв Л.; Уэбб, Норман (24 мая 2018 г.) [10 февраля 2017 г.]. «Кто такой Дональд Л. Уэбб?» . История науки и математики. Обмен стеками . Архивировано из оригинала 18 мая 2023 г. Проверено 18 мая 2023 г.
  10. ^ Куайн, WV (1981) [1940]. Математическая логика (пересмотренная ред.). Кембридж, Лондон, Нью-Йорк, Нью-Рошель, Мельбурн и Сидней: Издательство Гарвардского университета. п. 45.
  11. ^ Черч, А. (1996) [1944]. Введение в математическую логику . Нью-Джерси: Издательство Принстонского университета. п. 37.
  12. ^ Боченский, Ю.М. (1954). Краткое содержание математической логики (на французском языке). Нидерланды: Ф.Г. Крундер, Буссум, Нидерланды. п. 11.
  13. ^ Смуллян, Раймонд М. (1995). Логика первого порядка . Нью-Йорк: Дувр. стр. 5, 11, 14. ISBN.  978-0-486-68370-6 .
  14. Перейти обратно: Перейти обратно: а б с д и Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. стр. 41–43. ISBN  978-0-415-13342-5 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 162f81412e1a4cff47b5cfd543fa279f__1713382140
URL1:https://arc.ask3.ru/arc/aa/16/9f/162f81412e1a4cff47b5cfd543fa279f.html
Заголовок, (Title) документа по адресу, URL1:
Logical NOR - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)