Стрелка Пирса

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

История

Операция была введена в научный обиход американским логиком и философом Чарльзом Сандерсом Пирсом (Charles Sanders Peirce) в конце XIX века. Пирс, работая над проблемами математической логики и теории знаков, впервые описал операцию, которая впоследствии получила его имя. Однако широкое признание и практическое применение стрелка Пирса нашла лишь в XX веке, с развитием цифровой техники и теории переключательных схем. В 1913 году американский логик Генри Шеффер (Henry M. Sheffer) независимо открыл аналогичную операцию — штрих Шеффера, что привело к систематическому изучению функционально полных базисов. Стрелка Пирса стала важным инструментом в теории релейно-контактных схем и впоследствии — в проектировании интегральных микросхем.

Определение и таблица истинности

Стрелка Пирса является логической операцией, обратной дизъюнкции. Если дизъюнкция (A ∨ B) истинна, когда истинен хотя бы один из операндов, то стрелка Пирса (A ↓ B) истинна только в случае, когда оба операнда ложны. Формально: A ↓ B = ¬(A ∨ B).

Таблица истинности для стрелки Пирса:

Здесь 0 обозначает ложь, 1 — истину.

Свойства

Стрелка Пирса обладает рядом важных алгебраических свойств, которые отличают её от других логических операций:

• Коммутативность: A ↓ B = B ↓ A. Порядок операндов не влияет на результат.
• Ассоциативность отсутствует: (A ↓ B) ↓ C ≠ A ↓ (B ↓ C). Порядок выполнения операций существенен.
• Идемпотентность отсутствует: A ↓ A = ¬A, а не A. Повторение операнда даёт его отрицание.
• Функциональная полнота: Как уже упоминалось, с помощью одной только стрелки Пирса можно выразить любую логическую функцию, включая отрицание, конъюнкцию, дизъюнкцию и импликацию. Это делает её универсальным логическим элементом.

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

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

• Отрицание (¬A): A ↓ A
• Конъюнкция (A ∧ B): (A ↓ A) ↓ (B ↓ B) или, что то же самое, ¬(A ↓ B) = (A ↓ B) ↓ (A ↓ B)
• Дизъюнкция (A ∨ B): (A ↓ B) ↓ (A ↓ B)
• Импликация (A → B): A ↓ (B ↓ B) или (A ↓ A) ↓ B
• Эквивалентность (A ↔ B): (A ↓ (B ↓ B)) ↓ (B ↓ (A ↓ A))

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

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

Преимущества использования NOR-элементов

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

Примеры использования

• RS-триггер: Классическая схема триггера может быть построена на двух NOR-элементах.
• Дешифраторы и мультиплексоры: Сложные комбинационные схемы могут быть реализованы исключительно на NOR-элементах.
• Арифметико-логические устройства (АЛУ): NOR-элементы используются в составе АЛУ для выполнения логических операций.

Связь с другими логическими базисами

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

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

• В некоторых учебниках и научных работах стрелка Пирса обозначается символом ⊥ (перпендикулярность), хотя это обозначение не является общепринятым.
• Чарльз Пирс, в честь которого названа операция, был не только логиком, но и одним из основателей прагматизма и семиотики. Его работы по логике опередили своё время и были оценены лишь десятилетия спустя.
• С точки зрения теории множеств, стрелка Пирса соответствует операции дополнения объединения двух множеств.

Источники

• Ч. С. Пирс, «Логические труды» (сборник статей).
• Г. Шеффер, «A set of five independent postulates for Boolean algebras» (1913).
• М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр, «Логические методы управления» (1977).
• У. И. Кох, «Цифровая электроника. Теория и практика» (2008).
• Э. М. Брауэр, «Логика и алгебра» (1985).