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

Эта статья о NOR в логическом смысле. Чтобы узнать об электронных воротах, см. Ворота NOR . Чтобы узнать о других значениях, см. Nor .

«Стрела Пирса» перенаправляется сюда. Не путать с Pierce-Arrow , производителем автомобилей.

«Операция Уэбба» перенаправляется сюда. Не путать с веб-операциями .

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

НИ
Определение	${\overline {x+y}}$
Таблица истинности	$(0001)$
Логический вентиль
Нормальные формы
Дизъюнктивный	${\overline {x}}\cdot {\overline {y}}$
соединительный	${\overline {x}}\cdot {\overline {y}}$
Полином Жегалкина	$1\oplus x\oplus y\oplus xy$
Решетки постовые
0-сохраняющий	нет
1-сохраняющий	нет
монотонный	нет
Аффинный	нет

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

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

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

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

Определение

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

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

истинности Таблица ​ $A\downarrow B$ как следует:

$A$	$B$	$A\downarrow B$
Ф	Ф	Т
Ф	Т	Ф
Т	Ф	Ф
Т	Т	Ф

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

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

$P\downarrow Q$	$\Leftrightarrow$	$\neg (P\lor Q)$
	$\Leftrightarrow$	$\neg$

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

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

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

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

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

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

В 1944 году Чёрч также описал нерасхождение и использование ${\overline {\vee }}$ для оператора.

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

Свойства

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

логического

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

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

$\neg P$     $\Leftrightarrow$     $P\downarrow P$ $\neg$     $\Leftrightarrow$		$P\rightarrow Q$     $\Leftrightarrow$     ${\Big (}(P\downarrow P)\downarrow Q{\Big )}$ $\downarrow$ ${\Big (}(P\downarrow P)\downarrow Q{\Big )}$     $\Leftrightarrow$     $\downarrow$
$P\land Q$     $\Leftrightarrow$     $(P\downarrow P)$ $\downarrow$ $(Q\downarrow Q)$     $\Leftrightarrow$     $\downarrow$		$P\lor Q$     $\Leftrightarrow$     $(P\downarrow Q)$ $\downarrow$ $(P\downarrow Q)$     $\Leftrightarrow$     $\downarrow$

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

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

См. также

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

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

• СМИ, связанные с логическим NOR, на Викискладе?