Podręcznik
2. Układy kombinacyjne
2.4. Układy funkcjonalnie pełne
Układy funkcjonalnie pełne (lub jak czasem mówimy systemy funkcjonalnie pełne) to takie zbiory działań, (zestawy bramek) z których możemy zbudować metodą superpozycji (łączenia bramek) dowolną funkcję boolowską.
{negacja, suma logiczna} czyli {NOT, OR}
{negacja, iloczyn logiczny} czyli {NOT, AND}
{NAND 2 wejściowy}
{NOR 2 wejściowy}
Dowody, że powyższe zbiory są układami funkcjonalnie pełnymi sprowadzają się do przedstawienia za pomocą poszczególnych działań z danego zbioru działań:
sumy, iloczynu i negacji.
Korzystamy w tym celu z prawa podwójnego przeczenia i praw de Morgana. Z kolei funkcjonalna pełność zbioru działań {negacja, suma logiczna, iloczyn logiczny} wynika z twierdzenia o postaci kanonicznej sumacyjnej funkcji boolowskiej.
Można wykazać, że żadne inne działanie dwuargumentowe poza NAND i NOR nie wystarcza do zdefiniowania wszystkich działań jedno i dwuargumentowych. Inaczej mówiąc {NAND 2-wejściowy} i {NOR 2-wejściowy} to jedyne układy funkcjonalnie pełne złożone z jednego działania 2 argumentowego.