Штрих Шеффера

Штрих Ше́ффера (NAND, отрицание конъюнкции) — бинарная логическая операция, булева функция над двумя переменными. Введена в рассмотрение Генри Шеффером в 1913 году.

Штрих Шеффера
И-НЕ, NAND
Диаграмма Венна
Определение	$\stackrel{¯<!--\; ¯\; -->}{x\cdot <!--\; \cdot \; -->y}$${\overline {x\cdot y}}$
Таблица истинности	$(1110)$$(1110)$
Логический вентиль
Нормальные формы
Дизъюнктивная	$\stackrel{¯<!--\; ¯\; -->}{x}+\stackrel{¯<!--\; ¯\; -->}{y}$${\overline {x}}+{\overline {y}}$
Конъюнктивная	$\stackrel{¯<!--\; ¯\; -->}{x}+\stackrel{¯<!--\; ¯\; -->}{y}$${\overline {x}}+{\overline {y}}$
Полином Жегалкина	$1\oplus <!--\; \oplus \; -->xy$$1\oplus xy$
Принадлежность предполным классам
Сохраняет 0	Нет
Сохраняет 1	Нет
Монотонна	Нет
Линейна	Нет
Самодвойственна	Нет

Штрих Шеффера, обычно обозначаемый | или ↑, эквивалентен операции И-НЕ и задаётся следующей таблицей истинности:

X	Y	X | Y
0	0	1
0	1	1
1	0	1
1	1	0

Таким образом, высказывание X | Y означает, что X и Y несовместны, то есть не являются истинными одновременно. От перемены мест операндов результат операции не изменяется.

Штрих Шеффера, как и стрелка Пирса, образует базис для пространства булевых функций от двух переменных. То есть, используя только штрих Шеффера, можно построить все остальные операции. Например,

$X|X=\mathrm{\neg <!--\; \neg \; -->}X$$X\,|\,X=\neg X$ — отрицание,

$\left(X|X\right)|\left(Y|Y\right)=X\vee <!--\; \vee \; -->Y$$\left({X\,|\,X}\right)\,|\,\left({Y\,|\,Y}\right)=X\vee Y$ — дизъюнкция,

$\left(X|Y\right)|\left(X|Y\right)=X\wedge <!--\; \wedge \; -->Y$$\left({X\,|\,Y}\right)\,|\,\left({X\,|\,Y}\right)=X\wedge Y$ — конъюнкция,

$X|\mathrm{\neg <!--\; \neg \; -->}X$$X\,|\,\neg X$ — константа 1.

Цифровая ТТЛ-микросхема SN7400N, содержащая в корпусе четыре элемента 2И-НЕ, реализующих функцию штрих Шеффера

В электронике это означает, что для реализации всего многообразия схем преобразования сигналов, представляющих логические значения, достаточно одного типового элемента. С другой стороны, такой подход увеличивает сложность реализующих логические выражения схем и тем самым снижает их надёжность. Примером может являться промышленная 155 серия.

Элемент 2И-НЕ (2-in NAND), реализующий штрих Шеффера, обозначается следующим образом (по стандартам ANSI):

В европейских стандартах принято другое обозначение:

ЛитератураПравить

• Математический энциклопедический словарь. — М.: «Сов. энциклопедия », 1988. — С. 639—639.
• Белоусов, Аркадий Алгебра логики и цифровые компьютеры