F1-35

Implikanty funkcji boolowskiej

• Wyrażenie g jest

implikantem

funkcji f

(czyli g

⇒

f ) jeśli

dla każdej kombinacji zmiennych, dla której g = 1
otrzymuje się f = 1 (ale niekoniecznie odwrotnie)

• Każdy term lub suma termów w

fb

jest implikantem

funkcji opisanej tą formą

•

Implikant prosty

w formie sumacyjnej dla n zmiennych:

taki iloczyn p złożony z m literałów (m ≤ n), będący

implikantem funkcji f, który po odrzuceniu choćby jednego

literału przestaje być implikantem tej funkcji

•

Każdą formę boolowską można przekształcić do

postaci sumy zawierającej wyłącznie implikanty
proste

•

Nieredukowalna forma boolowska:

suma implikantów

prostych, która po odrzuceniu

któregokolwiek z nich nie opisuje tej funkcji

• W trakcie

minimalizacji

fb

można otrzymać jedną lub

więcej nieredukowalnych

fb

. Wybiera się formę o

najmniejszej złożoności Z = (suma termów i tworzących je
literałów).

Przykład

► Funkcja ta ma dwie nieredukowalne formy boolowskie,

Z

= 9

► Wspólne

implikanty

proste

określane są jako

l

A C

AC

i

l

l

l

l

C

AC

+

+

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

l

f A B C

A B C

A BC

A BC

ABC

AB C

A C B

B

A B C

C

AC B

B

A C

A B

A

A C B

B

BC A

A

AC B

B

A C

BC

( , , )

(

)

(

)

(

)

(

)

(

)

(

)

=

+

+

+

+

=

+

+

+

+

+

=

+

=

+

+

+

+

+

=

+

istotne

i tworzą

jądro

.

►

Implikanty proste

nie są

istotne

.

l

A B

BC

i

© J. Kalisz, WAT, 2008