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