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

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

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

x↑y = x NAND y = NOT(x AND y) = !(x&&y)
y
1  0  
1  1 x

на которой сразу видно, что функция симметрична относительно главной диагонали, или таблицей истинности из трёх колонок (двенадцать ячеек):

X	Y	Шаблон:Nobr
0	0	1
0	1	1
1	0	1
1	1	0

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

Инверсией штриха Шеффера является конъюнкция.

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

X | X \equiv \neg X

— отрицание;

(X | X) | (Y | Y) \equiv X \lor Y

— дизъюнкция;

(X | Y) | (X | Y) \equiv X \land Y

— конъюнкция;

X | (Y | Y) \equiv X \to Y

— импликация.

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

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