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

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

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

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

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

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

[math]\displaystyle{ X\,|\,X = \neg X }[/math] — отрицание,

[math]\displaystyle{ \left( {X \,|\,X } \right)\,|\,\left( {Y \,|\,Y } \right) = X \vee Y }[/math] — дизъюнкция,

[math]\displaystyle{ \left( {X \,|\,Y } \right)\,|\,\left( {X \,|\,Y } \right) = X \wedge Y }[/math] — конъюнкция,

[math]\displaystyle{ X \,|\, \neg X }[/math] — константа 1.

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

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