Теорема о представлении любой булевой функции в виде СКНФ. Множества переменных подставляемых функций могут пересекаться

Доказательство

Определение

Определение

Замечание 2

Замечание 1

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

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

Будем различать переименование двух видов:

переименование с отождествлением, как в предыдущем примере (переменная переименуется в другую переменную этойже функции);

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

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

Например эквивалентны и .

Функции и не эквивалентны, так как эквивалентные функции имеют одинаковое число существенных переменных.

Утверждение Двойственная суперпозиции функций- есть суперпозиция двойственных.

Тогда утверждение о представлении функции в виде СКНФнепосредственно следует из аналогичного утверждения о представлении функции в виде СДНФ.

Теорема о представлении любой булевой функции в виде СДНФ: для любой булевой функции справедлива следующая формула:

Чтобы провести это сведение возьмем двойственную функцию

и представим ее в виде СДНФ:

, тогда справедливы выкладки:

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

Дата добавления: 2017-01-13