Штрих Шеффера (Логическое И-НЕ / NAND): таблица истинности и свойства

В булевой алгебре и цифровой электронике штрих Шеффера (также известный как отрицание конъюнкции, И-НЕ или NAND от англ. Not AND) — это бинарная логическая операция, результатом которой является ложь (0) тогда и только тогда, когда оба операнда истинны (1). Во всех остальных случаях результатом будет истина (1).

Свое название операция получила в честь американского логика Генри Шеффера, который в 1913 году доказал ее удивительное математическое свойство.

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

В естественном языке эту операцию можно описать фразой: «Неверно, что оба условия выполняются одновременно» или «Хотя бы одно из двух ложно».

Обозначения штриха Шеффера

Существует несколько вариантов записи этой операции в математике и информатике для двух операндов $A$ и $B$:

$A \mid B$ (классический штрих — вертикальная черта);
$A \uparrow B$ (стрелка вверх);
$\neg(A \land B)$ (запись через инверсию конъюнкции);
$\overline{A \cdot B}$ (запись, часто используемая в схемотехнике);
A NAND B (в программировании и электронике).

Примечание: В стандарте Юникода для операции И-НЕ предусмотрен специальный символ ⊼ (U+22BC).

Пример из реальной жизни

Представьте, что в банке есть сейф, который открывается одновременным поворотом двух ключей. Сработает сигнализация (Тревога = 1), если сейф попытаются открыть неправильно.

Условие: «Тревога сработает ($A \mid B = 1$), если ключи НЕ повернуты одновременно».

Ключ А повернут ($A=1$), и ключ Б повернут ($B=1$). Всё правильно, сейф открывается. Тревоги нет (Итог = 0). Это единственный случай, когда И-НЕ дает ноль!
Ключ А НЕ повернут ($A=0$), а ключ Б повернут ($B=1$). Тревога сработает (Итог = 1).
Ключ А повернут ($A=1$), а ключ Б НЕ повернут ($B=0$). Тревога сработает (Итог = 1).
Оба ключа НЕ повернуты ($A=0, B=0$). Сейф закрыт, это нормальное состояние защиты. Система наготове (Итог = 1).

Таким образом, выражение $A \mid B$ означает, что события $A$ и $B$ несовместны (не могут быть истинными вместе).

Таблица истинности для штриха Шеффера

Таблица показывает, что результат $A \mid B$ является точной противоположностью (инверсией) результата обычного логического И ($A \land B$).

Для двух переменных ($A \mid B$)

$A$	$B$	$A \land B$ (И)	$A \mid B$ (И-НЕ)
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

Для трех переменных ($A \mid B \mid C$)

Как и импликация, штрих Шеффера вычисляется строго последовательно (слева направо), так как эта операция не ассоциативна. Сначала вычисляется $(A \mid B)$, а затем результат этой операции применяется через штрих к $C$.

$A$	$B$	$C$	$A \mid B$	$(A \mid B) \mid C$
0	0	0	1	1
0	0	1	1	0
0	1	0	1	1
0	1	1	1	0
1	0	0	1	1
1	0	1	1	0
1	1	0	0	1
1	1	1	0	1

(Воспользуйтесь нашим интерактивным калькулятором, чтобы автоматически построить таблицу истинности для любого количества переменных!)

Базис Шеффера и свойства операции

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

Это свойство совершило революцию в производстве микросхем. Производителям электроники оказалось намного дешевле и надежнее выпускать миллионы одинаковых базовых вентилей NAND (например, знаменитые микросхемы 7400-й серии) и собирать из них сложнейшие схемы, чем производить разные виды логических элементов.

Выражение других операций через штрих Шеффера:

Инверсия (Логическое НЕ): Отрицание числа равно штриху Шеффера числа с самим собой.
$$\neg A = A \mid A$$
Конъюнкция (Логическое И): Это инверсия штриха Шеффера.
$$A \land B = (A \mid B) \mid (A \mid B)$$
Дизъюнкция (Логическое ИЛИ): Это штрих Шеффера от инвертированных операндов (согласно законам де Моргана).
$$A \lor B = (A \mid A) \mid (B \mid B)$$
Импликация (Следование):
$$A \rightarrow B = A \mid (B \mid B) = A \mid \neg B$$

Алгебраические свойства:

Коммутативность (Переместительность): Да. От перемены мест переменных результат не меняется.
$$A \mid B = B \mid A$$
Ассоциативность (Сочетательность): Нет. Порядок расстановки скобок важен!
$$(A \mid B) \mid C \neq A \mid (B \mid C)$$
Взаимодействие с константами:
$$A \mid 0 = 1$$(любой штрих с нулем дает истину)

$$A \mid 1 = \neg A$$(штрих с единицей работает как инверсия)
Идемпотентность: Нет. $A \mid A = \neg A$, а не $A$.

Попробуйте покликать кнопки в нашем интерактивном тренажере ниже, чтобы на практике запомнить логику работы операции И-НЕ!