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

Теорема (о функциональной полноте). Для любой булевой функции f найдется формула φ, представляющая функцию f. Если f ≠ 0, то существует представляющая ее формула φ, находящаяся в СДНФ:

и такое представление единственно с точностью до порядка следования конституент единицы. Если f ≠ 1, то существует приставляющая ее формула φ, находящаяся в СКНФ:

,

и такое представление единственно с точностью до порядка следования конституент нуля.

Пример.

Найти СДНФ и СКНФ функции f(x,y,z), заданной следующей таблицей истинности:

Решение. По теореме о функциональной полноте СДНФ имеет вид , а СКНФ — . Для нахождения СДНФ и СКНФ исходной формулы φ составляется ее таблица истинности, а затем по ней строится требуемая совершенная нормальная форма. По СДНФ φ₁ для функции f, можно составить ее таблицу истинности и по ней найти СКНФ φ₂.

Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.