Podstawy Sterowania Logicznego,

Funkcje Boolowskie cz. 2

Podstawy sterowania

logicznego

Funkcje boolowskie cz. 2

Minimalizacja funkcji boolowskich Funkcja makstermu

Definicja

Funkcją makstermu M ( x) nazywa si

i

ę funkcję

zdefiniowaną następująco

∀

i

x

n

M (

0

gdy

x∈ Q

( x

i

) 

⇔

= 

∈

1 w innym przypadku

Podstawy Sterowania Logicznego 2011/12, ©ZM

2/19

Funkcja makstermu

Przykład

Funkcje makstermu 2 zmiennych

i

x

x

M ( x , x )

M ( x , x )

M ( x , x )

M ( x , x )

1

0

0

0

1

1

0

1

2

0

1

3

0

1

0

0

0

0

1

1

1

1

0

1

1

0

1

1

2

1

0

1

1

0

1

3

1

1

1

1

1

0

Podstawy Sterowania Logicznego 2011/12, ©ZM

3/19

Elektrotechnika I st., rok 3, moduł C

1

Podstawy Sterowania Logicznego,

Funkcje Boolowskie cz. 2

Funkcja boolowska jako iloczyn

makstermów

Twierdzenie

Każda funkcja boolowska może być przedstawiona jako iloczyn odpowiednich funkcji makstermu

n

f : Q → Q f ( x , ... , xn =

1

) ∏ Mi( x ,..., 1

xn )

i∈ F

n

gdzie F ⊂ Q ∧ ∀

f

x∈ F

( x)= 0

Podstawy Sterowania Logicznego 2011/12, ©ZM

4/19

Funkcja boolowska jako iloczyn

makstermów

Przykład

Funkcja boolowska zadana jest tablicą kombinacyjną

i

x

x

f( x , x )

1

0

0

1

f ( x , x

0

1 ) = ∑ (2, 3)

0

0

0

1

1

0

1

1

2

1

0

0

3

1

1

0

f ( x , x = M x , x ⋅ M x , x

0

1 )

2 ( 0

1 )

3 ( 0

1 )

Podstawy Sterowania Logicznego 2011/12, ©ZM

5/19

Konstytuanta zera

Dana jest funkcja boolowska

n

f : Q → Q

Dla

n

x ∈ F ⊂ Q

zachodzi

f ( x) = M i ( x) = 0

Podstawy Sterowania Logicznego 2011/12, ©ZM

6/19

Elektrotechnika I st., rok 3, moduł C

2

Podstawy Sterowania Logicznego,

Funkcje Boolowskie cz. 2

Konstytuanta zera

Definicja

Konstytuantą zera k funkcji f nazywa si

i

ę sumę n

zmiennych

*

*

*

k = x

+ ... + x + x dla x

x

, ... x , x

i

n 1

−

=

1

0

( n 1−

1

0 )

gdzie:

 x

gdy x

j

j =

*

x j =

1

 x gdy x

j

j = 0

Podstawy Sterowania Logicznego 2011/12, ©ZM

7/19

Konstytuanta zera

Wniosek

Każdemu makstermowi odpowiada dokładnie jedna konstytuanta zera.

Podstawy Sterowania Logicznego 2011/12, ©ZM

8/19

Konstytuanta zera

Przykład

Konstytuaty zera dla 2 zmiennych

Konstytuanta

i

x

x

Maksterm

1

0

zera

0

0

0

M ( x , x )

k = x + x

0

0

1

0

1

0

1

0

1

M ( x , x )

k = x + x

1

0

1

1

1

0

2

1

0

M ( x , x )

k = x + x

2

0

1

2

1

0

3

1

1

M ( x , x )

k = x + x

3

0

1

3

1

0

Podstawy Sterowania Logicznego 2011/12, ©ZM

9/19

Elektrotechnika I st., rok 3, moduł C

3

Podstawy Sterowania Logicznego,

Funkcje Boolowskie cz. 2

Funkcja jako iloczyn konstytuant zera Twierdzenie

Każdą funkcję boolowską f (różną od stałej 1) można jednoznacznie przedstawić w postaci iloczynu konstytuant zera

n

f : Q → Q

f ( x ) = ∏k i

x∈ F

Podstawy Sterowania Logicznego 2011/12, ©ZM

10/19

Zupełna normalna postać koniunkcyjna funkcji

Definicja

Postać funkcji odpowiadającą iloczynowi konstytuant zera nazywa się

zupełną normalną postacią koniunkcyjną funkcji lub inaczej

drugą normalną postacią kanoniczną Podstawy Sterowania Logicznego 2011/12, ©ZM

11/19

Zupełna normalna postać koniunkcyjna funkcji

Twierdzenia

Każda funkcja logiczna

f : Qn → Q

ma dokładnie jedną

drugą normalną postać kanoniczną

Podstawy Sterowania Logicznego 2011/12, ©ZM

12/19

Elektrotechnika I st., rok 3, moduł C

4

Podstawy Sterowania Logicznego,

Funkcje Boolowskie cz. 2

Zupełna normalna postać koniunkcyjna funkcji

Przykład 1

Funkcja boolowska zadana jest tablicą kombinacyjną

i

x

x

f( x , x )

1

0

0

1

0

0

0

1

1

0

1

1

2

1

0

0

3

1

1

0

f ( x , x = k x , x ⋅k x , x

0

1 )

2 ( 0

1 )

3 ( 0

1 )

f ( x , x = x + x ⋅ x + x

0

1 )

( 0 1) ( 0 1)

Podstawy Sterowania Logicznego 2011/12, ©ZM

13/19

Zupełna normalna postać koniunkcyjna funkcji

Przykład 2

Funkcja boolowska zadana jest tablicą kombinacyjną

i

x

x

x

f( x , x , x )

2

1

0

0

1

2

0

0

0

0

1

1

0

0

1

1

2

0

1

0

0

3

0

1

1

0

4

1

0

0

0

5

1

0

1

1

6

1

1

0

1

7

1

1

1

1

Podstawy Sterowania Logicznego 2011/12, ©ZM

14/19

Minimalizacja funkcji boolowskiej do postaci koniunkcyjnej za pomocą tablicy Karnaugha Przykład – cz. 1

Dana jest funkcja boolowska

f ( x , x , x , x

0

1

2

3 ) = ∑ (5, 6, 9, 10 )

x x

1 0

0 0

0 1

1 1

1 0

x x

3 2

0 0

0

0

0

0

0 1

0

1

0

1

1 1

0

0

0

0

1 0

0

1

0

1

f ( x ) = x ⋅ x ⋅ x ⋅ x + x ⋅ x ⋅ x ⋅ x + x ⋅ x ⋅ x ⋅ x + x ⋅ x ⋅ x ⋅ x

0

1

2

3

0

1

2

3

0

1

2

3

0

1

2

3

Podstawy Sterowania Logicznego 2011/12, ©ZM

15/19

Elektrotechnika I st., rok 3, moduł C

5

Podstawy Sterowania Logicznego,

Funkcje Boolowskie cz. 2

Minimalizacja funkcji boolowskiej do postaci koniunkcyjnej za pomocą tablicy Karnaugha Przykład – cz. 2

Dana jest funkcja boolowska

f ( x , x , x , x

0

1

2

3 ) = ∑ (5, 6, 9, 10 )

x x

1 0

0 0

0 1

1 1

1 0

x x

3 2

0 0

0

0

0

0

0 1

0

1

0

1

1 1

0

0

0

0

1 0

0

1

0

1

f ( x ) = ( x + x ⋅ x + x ⋅ x + x ⋅ x + x

0

1 ) ( 0

1 ) ( 2

3 ) ( 2

3 )

Podstawy Sterowania Logicznego 2011/12, ©ZM

16/19

Tablica Karnaugh dla funkcji 5 zmiennych x x x

2 1 0

000

001

011

010

110

111

101

100

x x

4 3

00

A

A

01

B

B

11

C

C

10

D

D

Podstawy Sterowania Logicznego 2011/12, ©ZM

17/19

Tablica Karnaugh dla funkcji 6 zmiennych x x x

2 1 0

000

001

011

010

110

111

101

100

x x x

5 4 3

000

A

A

C

001

D

F

F

D

011

B

010

E

E

110

E

E

111

B

101

D

F

F

D

100

C

Podstawy Sterowania Logicznego 2011/12, ©ZM

18/19

Elektrotechnika I st., rok 3, moduł C

6

Podstawy Sterowania Logicznego,

Funkcje Boolowskie cz. 2

Tablica Karnaugh dla funkcji 7 zmiennych 0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

x x x x

3 2 1 0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

x x x

6 5 4

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

000

A

A

E

E

001

C

C

011

D

D

D

D

010

110

111

D

D

D

D

101

B

C

B

B

C

B

100

E

E

Podstawy Sterowania Logicznego 2011/12, ©ZM

19/19

Elektrotechnika I st., rok 3, moduł C

7