Аналитическое представление булевых функций и нормальные формы

Основы аналитического представления: понятия минтерма и макстерма

Добро пожаловать в курс «Аналитическое представление булевых функций и нормальные формы». Это первая статья нашего цикла, и мы начнем с фундамента, на котором строится вся цифровая логика и схемотехника.

Мы привыкли видеть булевы функции в виде таблиц истинности. Это наглядно, когда переменных мало (две или три). Но представьте, что переменных десять. Таблица истинности для такой функции будет содержать строки. Работать с такими громоздкими таблицами неудобно.

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

Базовые определения

Прежде чем переходить к сложным конструкциям, вспомним основные операции и введем понятие литерала.

В булевой алгебре мы оперируем тремя основными действиями:

Конъюнкция (логическое И, умножение), обозначается или .

Дизъюнкция (логическое ИЛИ, сложение), обозначается или .

Отрицание (инверсия, НЕ), обозначается или .

> Литерал — это булева переменная или её отрицание. Например, для переменной литералами являются и .

Минтермы: Конституенты единицы

Начнем с первого «кирпичика» для построения функций.

Минтерм (от англ. minimum term) от переменных — это конъюнкция (произведение) всех переменных, где каждая переменная входит в произведение ровно один раз: либо сама по себе, либо с отрицанием.

Минтерм обладает уникальным свойством: он принимает значение истина (1) только на одном единственном наборе значений переменных.

Рассмотрим пример для двух переменных и . Всего существует возможных комбинации их значений. Для каждой комбинации можно составить свой минтерм:

| | | Минтерм | Описание | |---|---|---|---| | 0 | 0 | | Истинно только если и | | 0 | 1 | | Истинно только если и | | 1 | 0 | | Истинно только если и | | 1 | 1 | | Истинно только если и |

Обратите внимание на закономерность: если переменная равна 0, мы берем её с отрицанием (), чтобы превратить 0 в 1. Если переменная равна 1, мы берем её без изменений. В результате произведение всех единиц дает 1.

Минтермы часто обозначают буквой с индексом, соответствующим двоичному номеру строки:

Где — минтерм для нулевой строки (000), — отрицания переменных, — операция конъюнкции.

Именно поэтому минтермы называют конституентами единицы — каждый из них «отвечает» за одну единицу в таблице истинности.

!Визуализация минтерма как детектора конкретной комбинации входных сигналов

Макстермы: Конституенты нуля

Второе важное понятие — это макстерм. Это понятие, двойственное минтерму.

Макстерм (от англ. maximum term) от переменных — это дизъюнкция (сумма) всех переменных, где каждая переменная входит ровно один раз: либо сама по себе, либо с отрицанием.

Свойство макстерма противоположно: он принимает значение ложь (0) только на одном единственном наборе значений переменных. Во всех остальных случаях он равен 1.

Рассмотрим пример для тех же переменных и :

| | | Макстерм | Описание | |---|---|---|---| | 0 | 0 | | Ложно только если и | | 0 | 1 | | Ложно только если и | | 1 | 0 | | Ложно только если и | | 1 | 1 | | Ложно только если и |

Здесь правило построения обратное: если переменная в наборе равна 0, мы берем её без отрицания. Если переменная равна 1, мы берем её с отрицанием. Это нужно для того, чтобы в сумме получились все нули (так как ).

Макстермы обозначают заглавной буквой :

Где — макстерм для строки с индексом 3 (011), — переменная (так как в наборе 0), — отрицания переменных (так как в наборе 1), — операция дизъюнкции.

Макстермы называют конституентами нуля.

Совершенная дизъюнктивная нормальная форма (СДНФ)

Теперь, зная, что такое минтермы, мы можем представить любую булеву функцию в виде формулы. Эта форма называется Совершенная дизъюнктивная нормальная форма (СДНФ).

Идея проста: функция истинна тогда, когда истинен хотя бы один из наборов переменных, на которых она равна 1. Значит, мы можем просто сложить (дизъюнкция) все минтермы, соответствующие единицам функции.

Алгоритм построения СДНФ:

Выбрать в таблице истинности все строки, где функция .

Для каждой такой строки записать минтерм.

Соединить полученные минтермы знаком дизъюнкции ().

Пример: Дана функция , которая равна 1 на наборах (0,0,1) и (1,1,0). На остальных наборах она равна 0.

Строка (0,0,1): . Минтерм: .

Строка (1,1,0): . Минтерм: .

Итоговая формула СДНФ:

Где — функция в совершенной дизъюнктивной нормальной форме, — отрицания переменных, — конъюнкция, — дизъюнкция.

Совершенная конъюнктивная нормальная форма (СКНФ)

Аналогично можно построить функцию, опираясь на нули. Эта форма называется Совершенная конъюнктивная нормальная форма (СКНФ).

Идея: функция должна быть ложной только на тех наборах, где она равна 0. Мы берем макстермы (которые равны 0 на этих наборах) и перемножаем их. Если хотя бы один макстерм станет 0, вся формула станет 0.

Алгоритм построения СКНФ:

Выбрать в таблице истинности все строки, где функция .

Для каждой такой строки записать макстерм.

Соединить полученные макстермы знаком конъюнкции ().

Пример: Возьмем простую функцию , которая равна 0 только на наборе (0,1). На остальных она равна 1.

Строка (0,1): . Макстерм: (помним: для макстерма 0 без инверсии, 1 с инверсией).

Итоговая формула СКНФ:

Где — функция в совершенной конъюнктивной нормальной форме, — переменная, — отрицание переменной, — дизъюнкция.

Если бы нулей было несколько, мы бы взяли их произведение. Например, если функция равна 0 на (0,0) и (1,1):

Где — искомая функция, — макстерм для набора 00, — макстерм для набора 11, — конъюнкция.

Понятие функциональной полноты

Изучив СДНФ и СКНФ, мы приходим к важнейшему выводу теоретической информатики.

Поскольку любую таблицу истинности можно превратить в СДНФ или СКНФ, это означает, что любую булеву функцию можно выразить, используя только три операции: И, ИЛИ, НЕ.

> Система булевых функций называется функционально полной, если любую булеву функцию можно представить в виде суперпозиции (комбинации) функций этой системы.

Набор является классическим примером функционально полной системы. Именно поэтому процессоры и микросхемы строятся на базовых логических вентилях AND, OR, NOT (и их производных), ведь с их помощью можно реализовать любую логику работы устройства.

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

Совершенная дизъюнктивная нормальная форма (СДНФ): определение и способы построения

В предыдущей статье мы заложили фундамент аналитического представления булевых функций, разобрав понятия минтерма и макстерма. Мы выяснили, что минтерм — это произведение переменных, которое обращается в единицу только на одном конкретном наборе значений, а макстерм — это сумма, обращающаяся в ноль также лишь на одном наборе.

Теперь пришло время объединить эти знания в стройную систему. Сегодня мы детально разберем Совершенную дизъюнктивную нормальную форму (СДНФ). Это не просто способ записи функции, это её «паспорт» — уникальное представление, которое позволяет однозначно идентифицировать любую логическую функцию.

Что такое СДНФ?

Давайте разберем название по словам, чтобы понять суть:

Дизъюнктивная: означает, что внешняя, связующая операция во всем выражении — это дизъюнкция (логическое ИЛИ, сложение, обозначение или ).

Нормальная форма: означает, что выражение имеет стандартную, унифицированную структуру.

Совершенная: это самое важное слово. Оно означает, что каждое слагаемое в выражении содержит все переменные данной функции (либо в прямом виде, либо с отрицанием).

> Определение: СДНФ — это дизъюнкция (сумма) минтермов, соответствующих тем наборам переменных, на которых функция равна 1.

Математически это записывается так:

Где — булева функция, — символ дизъюнкции (суммирования) по всем элементам, — набор значений переменных, — множество наборов, на которых функция равна 1, — минтерм, соответствующий набору .

Главное свойство СДНФ — единственность. Для любой таблицы истинности существует только одна СДНФ. Это позволяет сравнивать две функции: если их СДНФ совпадают (с точностью до перестановки слагаемых), значит, функции тождественны.

Способ 1: Построение СДНФ по таблице истинности

Это самый наглядный и простой метод, который мы кратко затрагивали ранее. Он идеально подходит, когда у вас уже есть таблица истинности или когда вы проектируете логику работы устройства «с нуля».

Алгоритм действий

Анализ таблицы: Найдите в таблице истинности все строки, где значение функции . Строки с нулями нас не интересуют.

Формирование минтермов: Для каждой найденной строки запишите конъюнкцию (произведение) всех переменных.

* Если переменная в этой строке равна 1, пишите её как есть (например, ). * Если переменная равна 0, пишите её с отрицанием (например, ).

Сборка формулы: Соедините все полученные минтермы знаками дизъюнкции ().

Практический пример

Рассмотрим функцию трех переменных , заданную таблицей:

| | | | | Примечание | |---|---|---|---|---| | 0 | 0 | 0 | 0 | Пропускаем | | 0 | 0 | 1 | 1 | Набор 1 | | 0 | 1 | 0 | 0 | Пропускаем | | 0 | 1 | 1 | 1 | Набор 2 | | 1 | 0 | 0 | 0 | Пропускаем | | 1 | 0 | 1 | 0 | Пропускаем | | 1 | 1 | 0 | 1 | Набор 3 | | 1 | 1 | 1 | 0 | Пропускаем |

Шаг 1. Мы выделили три строки, где функция равна 1.

Шаг 2. Составим минтермы для этих строк: * Набор 1 (0, 0, 1): . Минтерм: . * Набор 2 (0, 1, 1): . Минтерм: . * Набор 3 (1, 1, 0): . Минтерм: .

Шаг 3. Объединяем их:

Где — искомая функция в СДНФ, слагаемые в скобках — минтермы, — операция логического сложения.

Способ 2: Алгебраическое приведение к СДНФ

Что делать, если таблицы истинности нет, а есть формула, которая выглядит «некрасиво» или неполно? Например: . Это ДНФ (дизъюнктивная нормальная форма), но не СДНФ, так как в первом слагаемом не хватает , а во втором — .

Для приведения к совершенной форме используются законы булевой алгебры.

Ключевые инструменты

Нам понадобятся два закона:

Закон исключенного третьего: . (Переменная или её отрицание всегда истинны).

Закон тождества: . (Умножение на единицу не меняет значения).

Суть метода: мы искусственно домножаем каждое слагаемое на «единицу», представленную как , где — недостающая переменная.

Алгоритм действий

Привести выражение к обычной ДНФ (раскрыть скобки, применить законы де Моргана, если нужно).

Найти слагаемые, в которых отсутствуют некоторые переменные.

Домножить такие слагаемые на скобку вида .

Раскрыть скобки и привести подобные слагаемые (удалить дубликаты, так как ).

Практический пример

Дана функция от трех переменных . Приведем её к СДНФ.

Анализ: * В слагаемом не хватает переменной . * В слагаемом не хватает переменных и .

Шаг 1. Дополняем первое слагаемое:

Где мы использовали свойство для введения переменной .

Шаг 2. Дополняем второе слагаемое (): Сначала введем :

Теперь в каждом полученном куске не хватает . Дополним их:

Шаг 3. Собираем всё вместе: Объединяем результаты шага 1 и шага 2:

(Здесь для краткости знак конъюнкции опущен, означает ).

Шаг 4. Удаляем дубликаты: Мы видим, что слагаемое встречается дважды. По закону идемпотентности , оставляем только одно.

Итоговая СДНФ:

Где каждое слагаемое — это полноценный минтерм, содержащий все три переменные.

Отличие ДНФ от СДНФ

Часто новички путают эти понятия. Давайте зафиксируем разницу.

ДНФ (Дизъюнктивная нормальная форма): Сумма каких-то* произведений элементарных переменных. Переменные могут повторяться, некоторых может не хватать. Пример:* . СДНФ (Совершенная ДНФ): Сумма минтермов. Каждое слагаемое обязано содержать все* переменные функции, и каждое слагаемое уникально. Пример:*

СДНФ всегда длиннее и громоздче, чем обычная ДНФ, но она обладает строгой структурой.

Физический смысл и реализация

Почему СДНФ так важна для инженеров? Потому что она дает прямой рецепт для создания цифровой схемы.

Любую функцию в СДНФ можно реализовать в двухуровневой логике:

Первый уровень: Элементы И (AND). Каждому минтерму соответствует один элемент И, на входы которого подаются переменные (или их инверсии).

Второй уровень: Один большой элемент ИЛИ (OR), который собирает выходы всех элементов И.

!Двухуровневая реализация СДНФ: массив вентилей И, объединенных одним вентилем ИЛИ.

Такая структура называется ПЛМ (Программируемая Логическая Матрица) и широко использовалась в ранней микроэлектронике, так как она универсальна.

Заключение

СДНФ — это каноническая форма записи булевой функции, представляющая собой сумму минтермов. Мы научились строить её двумя способами:

Выбирая единицы из таблицы истинности.

Алгебраически «разворачивая» формулу до полных наборов переменных.

СДНФ фокусируется на том, когда функция истинна. Но что, если нулей в таблице гораздо меньше, чем единиц? Неужели нам придется писать огромную формулу? В таких случаях удобнее использовать «двойника» СДНФ — Совершенную Конъюнктивную Нормальную Форму (СКНФ), которая описывает функцию через её нули. О ней мы поговорим в следующей статье.

Совершенная конъюнктивная нормальная форма (СКНФ): алгоритмы получения и связь с СДНФ

Приветствую вас, коллеги. Мы продолжаем погружение в аналитическое представление булевых функций. В прошлой лекции мы детально разобрали Совершенную Дизъюнктивную Нормальную Форму (СДНФ), которую строили, опираясь на «единицы» в таблице истинности. Мы представляли функцию как сумму ситуаций, когда она истинна.

Но мир логики симметричен. Иногда гораздо проще сказать, чего не должно произойти, чем перечислять всё, что разрешено. Представьте систему безопасности: вместо того чтобы описывать тысячи безопасных состояний, проще описать три аварийных и сказать: «Система работает нормально, если не произошло ни одно из этих событий».

Именно эту логику реализует Совершенная конъюнктивная нормальная форма (СКНФ). Сегодня мы научимся её строить и увидим, как она связана со своим «зеркальным отражением» — СДНФ.

Определение СКНФ

Давайте разберем термин по частям, как мы делали это ранее:

Конъюнктивная: внешняя, связующая операция — это конъюнкция (логическое И, умножение, или ).

Нормальная форма: стандартная структура записи.

Совершенная: каждая скобка (макстерм) содержит все переменные функции.

> Определение: СКНФ — это конъюнкция (произведение) макстермов, соответствующих тем наборам переменных, на которых функция равна 0.

Математическая запись выглядит следующим образом:

Где — булева функция, — символ конъюнкции (произведения) по всем элементам, — набор значений переменных, — множество наборов, на которых функция равна 0, — макстерм, соответствующий набору .

Если СДНФ — это «сумма произведений», то СКНФ — это «произведение сумм». И если СДНФ ищет, где функция истинна, то СКНФ отсекает варианты, где она ложна.

Способ 1: Построение СКНФ по таблице истинности

Этот алгоритм зеркален алгоритму для СДНФ, но с важными отличиями в деталях, где студенты часто допускают ошибки. Будьте внимательны.

Алгоритм действий

Поиск нулей: Выберите в таблице истинности все строки, где значение функции .

Формирование макстермов: Для каждой такой строки запишите дизъюнкцию (сумму) всех переменных.

* Важное правило инверсии: Если переменная в наборе равна 0, мы записываем её без отрицания (). Если переменная равна 1, мы записываем её с отрицанием (). Почему так?* Наша цель — сделать макстерм равным 0 именно на этом наборе. Сумма равна 0 только тогда, когда все слагаемые равны 0. Поэтому мы инвертируем единицы, превращая их в нули.

Сборка формулы: Соедините все полученные скобки знаком конъюнкции ( или ).

!Визуализация процесса выбора нулей из таблицы и превращения их в произведение сумм.

Практический пример

Рассмотрим функцию трех переменных . Допустим, она почти всегда равна 1, кроме двух случаев.

| | | | | Анализ | |---|---|---|---|---| | 0 | 0 | 0 | 1 | Пропускаем | | 0 | 0 | 1 | 0 | Набор 1 (индекс 1) | | 0 | 1 | 0 | 1 | Пропускаем | | 0 | 1 | 1 | 1 | Пропускаем | | 1 | 0 | 0 | 1 | Пропускаем | | 1 | 0 | 1 | 0 | Набор 2 (индекс 5) | | 1 | 1 | 0 | 1 | Пропускаем | | 1 | 1 | 1 | 1 | Пропускаем |

Шаг 1. Мы нашли две строки с нулями: (0, 0, 1) и (1, 0, 1).

Шаг 2. Составляем макстермы. * Набор 1 (0, 0, 1): . Чтобы получить сумму равную 0, нам нужно инвертировать . Макстерм: . * Набор 2 (1, 0, 1): . Нам нужно инвертировать и . Макстерм: .

Шаг 3. Перемножаем скобки:

Где — функция в СКНФ, скобки — макстермы, — логическое И.

Заметьте, насколько компактной получилась запись! Если бы мы строили СДНФ для этой же функции, нам пришлось бы складывать 6 минтермов (для всех строк с единицами). СКНФ в данном случае гораздо эффективнее.

Способ 2: Алгебраическое приведение к СКНФ

Если у нас есть формула, которая является произведением сумм (КНФ), но не является совершенной (в скобках не хватает переменных), мы можем «достроить» её алгебраически.

Ключевые инструменты

Нам понадобятся:

Закон противоречия: . (Ложь, что переменная и её отрицание истинны одновременно).

Свойство нуля: . (Прибавление нуля не меняет значения).

Второй дистрибутивный закон: . Это самый сложный для восприятия, но самый важный закон для построения СКНФ.

Алгоритм действий

Найти скобки, где не хватает переменных.

В такую скобку добавить «нуль» в виде произведения недостающей переменной на её инверсию: .

Раскрыть скобку по дистрибутивному закону: . Теперь вместо одной неполной скобки у нас две, но в каждой появилась новая переменная.

Повторять, пока все скобки не станут полными.

Удалить повторяющиеся скобки ().

Практический пример

Дана функция двух переменных: . Это КНФ, но не СКНФ, так как не хватает переменной .

Шаг 1. В выражение добавим недостающий через «нуль»:

Где — это логический ноль.

Шаг 2. Применяем дистрибутивный закон (расщепляем сумму на произведение):

Где и — полученные макстермы.

Итог:

Теперь это Совершенная КНФ.

Связь между СДНФ и СКНФ

СДНФ и СКНФ — это два способа описать одну и ту же сущность. Между ними существует жесткая математическая связь.

Представьте, что у нас есть возможных наборов переменных (строк в таблице). Пусть на множестве наборов функция равна 1, а на множестве функция равна 0.

Очевидно, что эти множества не пересекаются и вместе составляют все возможные варианты:

Где — индексы минтермов для СДНФ, — индексы макстермов для СКНФ, — объединение множеств.

Правило перехода по индексам

Если вы знаете номера минтермов, входящих в СДНФ, то в СКНФ войдут макстермы со всеми остальными номерами.

Пример: Функция от 3 переменных ( строк, индексы от 0 до 7). Допустим, СДНФ функции выглядит так:

Здесь присутствуют минтермы с индексами {0, 3, 5, 7}. Это значит, что на этих строках функция равна 1. Следовательно, на остальных строках {1, 2, 4, 6} функция равна 0.

Значит, СКНФ этой же функции будет состоять из макстермов с этими индексами:

Это свойство позволяет мгновенно переходить от одной формы к другой, не переписывая таблицу истинности.

Что выбрать: СДНФ или СКНФ?

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

Если в таблице истинности единиц меньше, чем нулей строим СДНФ (формула будет короче).

Если в таблице истинности нулей меньше, чем единиц строим СКНФ (формула будет короче).

Заключение

Мы завершили изучение канонических форм — СДНФ и СКНФ. Теперь вы умеете превращать любую таблицу истинности в строгую формулу двумя способами: собирая единицы или отсекая нули.

Однако, «совершенные» формы имеют один существенный недостаток — они часто бывают слишком длинными и избыточными. В реальной инженерии никто не хочет паять схему из 100 элементов, если ту же логику можно реализовать на 5 элементах.

Поэтому следующая большая тема нашего курса — минимизация булевых функций. Мы научимся брать эти громоздкие СДНФ и СКНФ и «сжимать» их до минимально возможного размера, используя карты Карно и метод Куайна. До встречи на следующей лекции!

Аналитическое представление булевых функций и нормальные формы

В булевой алгебре существует несколько способов задания логической функции: словесное описание, таблица истинности и аналитическое выражение (формула). Таблицы истинности наглядны, но с ростом количества переменных они становятся громоздкими. Для анализа и синтеза сложных цифровых схем инженеры и математики используют аналитическое представление.

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

Минтермы и Макстермы

Прежде чем строить сложные формы, разберем их элементарные «кирпичики». Пусть у нас есть набор переменных .

Минтерм (Конституента единицы)

Минтерм — это конъюнкция (логическое И), в которую входят все переменные функции (либо сами переменные, либо их отрицания).

Свойство минтерма: он равен 1 (истине) только на одном единственном наборе значений переменных.

Пример для двух переменных и : * — это минтерм. Он равен 1 только если и .

Где — отрицание, — конъюнкция.

Макстерм (Конституента нуля)

Макстерм — это дизъюнкция (логическое ИЛИ), в которую входят все переменные функции (либо сами переменные, либо их отрицания).

Свойство макстерма: он равен 0 (лжи) только на одном единственном наборе значений переменных.

Пример для двух переменных и : * — это макстерм. Он равен 0 только если и .

Где — дизъюнкция, — отрицание.

Совершенная Дизъюнктивная Нормальная Форма (СДНФ)

Любую функцию, которая хотя бы раз принимает значение 1, можно представить в виде СДНФ. Это «сумма» (дизъюнкция) всех минтермов, на которых функция равна единице.

Алгоритм построения СДНФ:

Выбрать в таблице истинности все строки, где функция .

Для каждой такой строки записать минтерм:

* Если переменная равна 1, записываем её как есть (). * Если переменная равна 0, записываем её с отрицанием ().

Соединить полученные минтермы знаками дизъюнкции ().

Пример построения СДНФ

Рассмотрим функцию трех переменных:

| | | | | Минтерм | |:---:|:---:|:---:|:---:|:---| | 0 | 0 | 0 | 0 | - | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 0 | - | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | - | 1 | 0 | 1 | 0 | - | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 0 | -

Итоговая формула СДНФ:

Где — искомая функция, — конъюнкция, — дизъюнкция, — отрицание.

Совершенная Конъюнктивная Нормальная Форма (СКНФ)

Это двойственная форма представления. Любую функцию, которая не является тождественной единицей, можно представить как «произведение» (конъюнкцию) макстермов.

Алгоритм построения СКНФ:

Выбрать в таблице истинности все строки, где функция .

Для каждой такой строки записать макстерм:

* Если переменная равна 0, записываем её как есть (). (Обратите внимание: наоборот по сравнению с СДНФ) * Если переменная равна 1, записываем её с отрицанием ().

Соединить полученные макстермы знаками конъюнкции ().

Используя ту же таблицу выше, найдем строки с нулями (0,0,0), (0,1,0), (1,0,0), (1,0,1), (1,1,1). Для первой строки (0,0,0) макстерм будет .

Функциональная полнота

Мы выяснили, что любую функцию можно записать через СДНФ или СКНФ. Это означает, что используя всего три операции — И (), ИЛИ () и НЕ () — можно построить любую логику. Такой набор функций называется функционально полным.

Определение: Система булевых функций называется функционально полной, если любую булеву функцию можно выразить через суперпозицию (подстановку) функций этой системы.

Минимизация базиса

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

Закон де Моргана:

Где — переменные, — дизъюнкция, — конъюнкция, — отрицание.

Это означает, что дизъюнкцию можно выразить через конъюнкцию и отрицание. Следовательно, система (И, НЕ) также является функционально полной. Аналогично полна система (ИЛИ, НЕ).

Однородные базисы: Штрих Шеффера и Стрелка Пирса

Существуют функции, которые являются полными системами сами по себе. Одной такой функции достаточно, чтобы выразить любую другую логическую операцию.

Штрих Шеффера (И-НЕ)

Обозначается как или NAND. Это отрицание конъюнкции.

Где — штрих Шеффера, — конъюнкция, — отрицание.

Доказательство полноты (выразим базис через штрих):

Отрицание:

Где — инверсия . Если на оба входа И-НЕ подать один и тот же сигнал, на выходе будет его инверсия.

Конъюнкция:

Где — конъюнкция. Мы берем результат штриха Шеффера и инвертируем его (используя свойство из пункта 1).

Стрелка Пирса (ИЛИ-НЕ)

Обозначается как или NOR. Это отрицание дизъюнкции.

Где — стрелка Пирса, — дизъюнкция, — отрицание.

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