F1-35

Implikanty formy boolowskiej

• Implikantem funkcji boolowskiej f jest takie wyrażenie g (co zapisujemy g ⇒ f ), które przyjmuje wartość 1 dla tej samej kombinacji zmiennych, dla których f = 1.

Np. dla funkcji

f ( ,

A ,

B C) = ABC + ABC + ABC + ABC + ABC

implikantami są poszczególne 1-mintermy lub ich sumy.

• Implikantem prostym jest implikant o minimalnej liczbie literałów. Można go otrzymać z 1-mintermów po redukcji zmiennych. Na przykład

ABC + ABC = AC

ABC + ABC = AC

ABC + ABC = AB

ABC + ABC = BC

Implikant prosty jest zatem takim implikantem, który w formie boolowskiej nie może być zredukowany do mniejszej liczby literałów przez wykorzystanie innego implikanta.

Przykład:

f( x , x )= x + x x = x (1+ x )=

1

2

1

1 2

1

2

1

x

Implikant 1 x jest implikantem prostym, natomiast implikant 1

x x nie jest implikantem prostym, gdyż literał

2

x może być

2

odrzucony, nie zmieniając funkcji f.

Każdą formę boolowską można przekształcić do postaci sumy zawierającej wyłącznie implikanty proste.

© J. Kalisz, J.Pasierbiński, WAT, 2007