F1-24 SFP.pdf

F1-24

Systemy funkcjonalnie pełne (SFP)

• SFP – zbiór operacji umożliwiających zapis każdej funkcji

logicznej w postaci wyrażenia zawierającego wyłącznie

operatory z tego zbioru, i który traci tę właściwość po

zmniejszeniu go o choćby jedną operację.

• Podstawowy SFP to zbiór boolowski : {+, ⋅ , ’ }

• Najmniejsze dwa SFP zawierają tylko jedną operację:

1) funkcja NOR y = ( a + b ) '

Negację otrzymuje się z ( a + a ) ' = a' ,

sumę z (( a + b ) ' ) ' = a + b , iloczyn z ( a' + b' ) ' = ab

2) funkcja NAND

y = ( a·b ) '

Negację otrzymuje się z ( a · a ) ' = a' ,

sumę z ( a'·b' ) ' = a + b , iloczyn z (( a·b ) ' ) ' = ab

Teoretycznie:

Każdą funkcję logiczną można zrealizować przy użyciu

wyłącznie funktorów NOR albo funktorów NAND!