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

Штрих Шеффера — это бинарная логическая операция, которая в булевой алгебре и математической логике принимает значение «ложь» тогда и только тогда, когда оба операнда истинны. В классической логике высказываний штрих Шеффера является функционально полной связкой, то есть с её помощью можно выразить любую другую логическую операцию (конъюнкцию, дизъюнкцию, отрицание и т. д.). Операция названа в честь американского логика Генри Мориса Шеффера, который в 1913 году ввёл её в научный обиход. Штрих Шеффера также известен как операция NAND (от англ. Not AND — «не-И»), что отражает её суть: результат операции является отрицанием конъюнкции.

Определение и обозначение

Штрих Шеффера обозначается вертикальной чертой (|) и читается как «не-и». Для двух высказываний \(A\) и \(B\) результат операции \(A \mid B\) определяется следующей таблицей истинности:

Здесь 0 обозначает «ложь», 1 — «истину». Таким образом, \(A \mid B\) ложно только в том случае, когда оба высказывания истинны. В терминах булевых функций штрих Шеффера является отрицанием конъюнкции: \(A \mid B = \neg (A \land B)\).

История

Операция была впервые описана Генри Морисом Шеффером в статье «A Set of Five Independent Postulates for Boolean Algebras», опубликованной в 1913 году в журнале Transactions of the American Mathematical Society. Шеффер показал, что для построения всей булевой алгебры достаточно одной бинарной операции, которая впоследствии получила его имя. Однако ещё до Шеффера, в 1880-х годах, американский философ и логик Чарльз Сандерс Пирс независимо обнаружил функциональную полноту операции NAND, но его работы остались неопубликованными при жизни. Пирс использовал для обозначения этой операции символ «↓» (стрелка Пирса), который позже стал обозначать другую операцию — NOR (стрелка Пирса). В современных источниках штрих Шеффера часто ассоциируется с именем Шеффера, хотя приоритет открытия принадлежит Пирсу.

Свойства

Штрих Шеффера обладает рядом важных алгебраических свойств:

• Коммутативность: \(A \mid B = B \mid A\). Порядок операндов не влияет на результат.
• Неассоциативность: \((A \mid B) \mid C \neq A \mid (B \mid C)\) в общем случае. Например, при \(A=1, B=1, C=0\) левая часть даёт 1, а правая — 0.
• Идемпотентность отсутствует: \(A \mid A = \neg A\), то есть повторение операнда даёт отрицание, а не сам операнд.
• Функциональная полнота: с помощью одной только операции NAND можно выразить любую булеву функцию. Это свойство делает штрих Шеффера базисом для построения всех логических схем.

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

Благодаря функциональной полноте, все основные логические операции могут быть записаны через штрих Шеффера:

• Отрицание: \(\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 \leftrightarrow B = (A \mid B) \mid ((A \mid A) \mid (B \mid B))\).

Эти выражения показывают, что для реализации любой логической схемы достаточно одного типа логического элемента — элемента NAND.

Применение в цифровой электронике

В цифровой электронике штрих Шеффера реализуется в виде логического элемента «И-НЕ» (NAND). Этот элемент является универсальным: из него можно построить любые другие логические вентили (И, ИЛИ, НЕ и т. д.). На практике большинство интегральных схем, особенно в семействах ТТЛ (транзисторно-транзисторная логика) и КМОП (комплементарная структура металл-оксид-полупроводник), используют именно элементы NAND в качестве базовых. Например, в микросхемах серии К155 (советский аналог 7400) содержатся четыре двухвходовых элемента И-НЕ. Универсальность NAND позволяет минимизировать номенклатуру компонентов и упростить проектирование цифровых устройств.

Связь с другими операциями

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

Критика и ограничения

Хотя штрих Шеффера является мощным инструментом в теории и практике, его применение имеет некоторые недостатки. В логических схемах использование только элементов NAND может приводить к увеличению числа вентилей для реализации сложных функций по сравнению с использованием разнородных элементов. Кроме того, в некоторых контекстах (например, в квантовой логике или многозначных логиках) операция NAND не обладает свойством функциональной полноты, что ограничивает её применимость.

Интересные факты

• В 1913 году Шеффер предложил не только операцию NAND, но и операцию NOR (стрелка Пирса), которая также является функционально полной. Однако в современной литературе за ним закрепилось название только для NAND.
• В компьютерной архитектуре команда NAND часто используется в процессорах для выполнения арифметических и логических операций, так как она позволяет реализовать любой алгоритм с минимальным набором инструкций.
• В теории формальных языков штрих Шеффера применяется для построения минимальных систем аксиом, например, в исчислении высказываний.

Источники

• Шеффер, Г. М. «A Set of Five Independent Postulates for Boolean Algebras» // Transactions of the American Mathematical Society, 1913, т. 14, с. 481–488.
• Горбатов, В. А. «Основы дискретной математики». — М.: Высшая школа, 1986. — 400 с.
• Яблонский, С. В. «Введение в дискретную математику». — М.: Наука, 1986. — 384 с.
• Титце, У., Шенк, К. «Полупроводниковая схемотехника». — М.: ДМК Пресс, 2008. — 832 с.