Представление логических функций в базисах «И-НЕ» и «ИЛИ-НЕ»

Логические функции могут быть выражены через базисы, содержащие ограниченный набор операций. Два таких базиса — это «И-НЕ» и «ИЛИ-НЕ». Эти базисы позволяют выразить любую логическую функцию, что делает их полными.

Базис «И-НЕ» (функция NAND)

Операция И-НЕ, также известная как штрих Шеффера или NAND (Not AND), обозначается как A ↑ B. Это операция, которая возвращает 0 только тогда, когда обе переменные равны 1. В остальных случаях результатом является 1.

Функция NAND является полной, так как с ее помощью можно выразить все основные логические операции:

• Отрицание (НЕ): ¬A = A ↑ A
• Конъюнкция (И): A ∧ B = (A ↑ B) ↑ (A ↑ B)
• Дизъюнкция (ИЛИ): A ∨ B = (A ↑ A) ↑ (B ↑ B)

Таким образом, используя только операцию NAND, можно создать любые логические выражения и схемы.

Базис «ИЛИ-НЕ» (функция NOR)

Операция ИЛИ-НЕ, также известная как стрелка Пирса или NOR (Not OR), обозначается как A ↓ B. Эта операция возвращает 1 только тогда, когда обе переменные равны 0. В остальных случаях результатом является 0.

Функция NOR также является полной и позволяет выразить все основные логические операции:

• Отрицание (НЕ): ¬A = A ↓ A
• Дизъюнкция (ИЛИ): A ∨ B = (A ↓ A) ↓ (B ↓ B)
• Конъюнкция (И): A ∧ B = ((A ↓ B) ↓ (A ↓ B))

Благодаря этим выражениям, все логические функции можно построить, используя только операцию NOR.

Заключение

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