8.4.2.2. Теорема о функциональной полноте
| Теорема 4.1. | Функциональный базис B является полным тогда и только тогда, когда он целиком не содержится ни в одном из пяти замкнутых классов T0, T1, S, M, L. Иначе говоря, функциональный базис B является полным тогда и только тогда, когда он содержит: хотя бы одну функцию, не принадлежащую классу T0 (T1, S, M, L). |
Доказательство.
Предположим, что базис В целиком принадлежит одному из перечисленных замкнутых классов. Тогда в силу замкнутости класса функций, содержащего функции из В, суперпозиция функций из В дает лишь функции из этого же замкнутого класса. Однако ни один из замкнутых классов не содержит всех переключательных функций. Отсюда следует, что базис В неполон.
Рассмотрим примеры функционально полных базисов, используя таблицу ПФ двух переменных (табл. 4.1).
Базис 
. Любая функция, не равная тождественно нулю, может быть представлена формулой в СДНФ (следствие из теоремы Шеннона). Константы 0,1 могут быть представлены в виде:
, 
.
Анализ таблицы принадлежности замкнутым классам подтверждает функциональную полноту этого базиса. Он является избыточным, из него можно получить еще два функционально полных базиса:
, так как
;
, так как
Базис функционально полон, поскольку для любой функции может быть построен полином Жегалкина над этим базисом.
Поскольку константу 0 можно получить как 0 = 1 ⊕ 1, функционально полным будет также базис {∧, ⊕, 1}. Доказательством этого служит то, что константа 1 не принадлежит классу Т0, тогда как обе функции ∧ и ⊕ принадлежат этому классу, что обеспечивает справедливость теоремы о функциональной полноте. Однако базис {∧, ⊕, 0} уже не будет функционально полным, так как невозможно выразить константу 1 формулой над этим базисом, ибо константа 0 принадлежит классу Т0, как и функции∧ и ⊕.
Важными примерами функционально полных базисов являются универсальные базисы {/}, {↓}, содержащие по одной переключательной функции.