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: {+, ⋅,⎯ }

• Inne SFP:

{+,⎯ } czyli {OR, NOT} – iloczyn otrzymuje się na podstawie prawa De Morgana: ⋅

=

+

1

x x 2

1

x

x 2

{⋅,⎯ } czyli {AND, NOT} – suma

+

=

⋅

1

x

x 2

1

x

x 2

{↓} – strzałka Peirce’a czyli {NOR}

Ponieważ NOR( x 1, x 2) = +

, więc

1

x

x 2

Negacja:

x = x ↓ x

Suma: +

=

↓

1

x

x 2

1

x

x 2

Iloczyn: ⋅

=

↓

1

x x 2

1

x

x 2

{|} – kreska Sheffera czyli {NAND}

Ponieważ NAND( x 1, x 2) = ⋅ , więc 1

x

x 2

Negacja:

x = x | x

Suma: x + x = x |

1

2

1 x 2

Iloczyn: x ⋅ x = x |

1

2

1 x 2

Każdą funkcję logiczną można zrealizować przy użyciu wyłącznie funktorów NOR albo funktorów NAND!

© J. Kalisz, WAT, 2007