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!

© J. Kalisz, WAT, 2008