Базисы

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

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

Примерами минимальных базисов служат базисы:

и

В практических реализациях применяются расширенные базисы. Наиболее распространенным из них является базис И ИЛИ НЕ. Усовершенствование технологий изготовления интегральных логических элементов привело к появлению базиса И, ИЛИ, НЕ, Сложение по модулю 2, который применяется во всех современных цифровых системах.

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

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

Введем следующее обозначение .

При использовании базиса И, ИЛИ, НЕ любую функцию алгебры логики можно задать в виде:

()= . (15)

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

Соотношение (15) называется совершенной дизъюнктивной нормальной формой функции () (СДНФ). Члены называют дизъюнктивными членами СДНФ.

Пример 3: Пусть функция задана таблицей истинности

Построим СНДФ функции согласно выражению (15).

()= ()= = . (16)

Соотношение (16) называется совершенной конъюнктивной нормальной формой функции (СКНФ). Члены вида - дизъюнкции всех аргументов функции, взятые с инверсными значениями, называются конъюнктивными членами СКНФ, или конституентами нуля. Последнее связано с соотношением

=0.

Пример 3. Из таблицы истинности примера 2 выбираем столбцы, в которых =0, тогда в соответствии с (16), получим