ПРЕДСТАВЛЕНИЕ ФАЛ В РАЗЛИЧНЫХ БАЗИСАХ

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

Система ФАЛ {И, ИЛИ, НЕ} является функционально полной, но не минимальной.

Минимальной функционально полной системой, называется такая система, исключение из которой хотя бы одной функции делает систему неполной. К ним относятся системы функций {И, НЕ} и {ИЛИ, НЕ}.

Для того чтобы приведенную выше функцию записать в базисе {И, НЕ}, необходимо в выражении функции заменить конъюнкции дизъюнкциями, а для записи функции в базисе {ИЛИ, НЕ} дизъюнкции заменяются конъюнкциями. Указанные преобразования выполняются на основании закона двойного отрицания и правила де Моргана:

Пример. Выразить функцию

в базисах {И, НЕ} и {ИЛИ, НЕ}.

Непосредственный переход от представленной формы записи к указанным базисам приведет к сложным инверсиям, поэтому для получения более простых выражений запишем заданную функцию в ДНФ:

Теперь для перехода к базису {ИЛИ, НЕ} дважды проинвертируем каждый член полученного выражения

Чтобы заданную функцию записать в базисе {ИЛИ, НЕ}, инвертируем дважды ее ДНФ

Таким образом, от базиса {И, ИЛИ, НЕ} можно перейти к минимальным полным базисам {И, НЕ} и {ИЛИ, НЕ}.