Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Podstawy sterowania
logicznego
Funkcje boolowskie cz. 3
Funkcjonalność pełna zbioru funkcji
boolowskich
Liczba funkcji X→Y
Twierdzenie
Dla dowolnych zbiorów skończonych X i Y, jeśli X
zawiera k elementów i Y zawiera m elementów, to istnieje mk funkcji odwzorowujących zbiór X w Y.
Podstawy Sterowania Logicznego 2011/12, ©ZM
2/28
Liczba funkcji boolowskich X→Y
W przypadku funkcji boolowskich n zmiennych:
zbiór X (dziedzina) zawiera k=2n elementów,
zbiór Y (przeciwdziedzina) zawiera 2 elementy.
Stąd liczba możliwych do zdefiniowania funkcji boolowskich n zmiennych wynosi
n
2
2
Podstawy Sterowania Logicznego 2011/12, ©ZM
3/28
Elektrotechnika I st, rok 3, moduł C
1
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Liczba funkcji boolowskich X→Y
Liczba
Liczba funkcji
zmiennych
1
22 = 4
2
24 = 16
3
28 = 256
4
216 = 65536
5
232 = 4294967296
Podstawy Sterowania Logicznego 2011/12, ©ZM
4/28
Funkcje boolowskie 1 zmiennej
a
Funkcja
Wyrażenie
Nazwa funkcji
0
1
f0
0
0
0
Stała 0
f1
0
1
a
Przeniesienie
f2
1
0
a
Negacja (NOT)
f3
1
1
1
Stała 1
Podstawy Sterowania Logicznego 2011/12, ©ZM
5/28
Funkcje boolowskie 1 zmiennej
Podstawy Sterowania Logicznego 2011/12, ©ZM
6/28
Elektrotechnika I st, rok 3, moduł C
2
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Funkcje boolowskie 2 zmiennych (1)
ab
Funk
Wyrażenie
Nazwa funkcji
cja
00
01
10
11
f0
0
0
0
0
0
Stała 0
f1
1
0
0
0
Funkcja Peierce’a (NOR)
a + b
f2
0
1
0
0
Iloczyn z zakazem
a ⋅ b
f3
1
1
0
0
Negacja (NOT)
a
Podstawy Sterowania Logicznego 2011/12, ©ZM
7/28
Funkcje boolowskie 2 zmiennych (2)
ab
Funk-
Wyrażenie
Nazwa funkcji
cja
00
01
10
11
f4
0
0
1
0
Iloczyn z zakazem
a ⋅ b
f5
1
0
1
0
Negacja (NOT)
b
f6
0
1
1
0
Nierówność (XOR)
a ⋅ b + a ⋅ b
f7
1
1
1
0
Funkcja Sheffera (NAND)
a ⋅ b
Podstawy Sterowania Logicznego 2011/12, ©ZM
8/28
Funkcje boolowskie 2 zmiennych (3)
ab
Funk
Wyrażenie
Nazwa funkcji
cja
00
01
10
11
f8
0
0
0
1
a ⋅ b
Iloczyn (AND)
f9
1
0
0
1
Równość (XNOR)
a ⋅ b + a ⋅ b
f10
0
1
0
1
Przeniesienie
b
f11
1
1
0
1
Implikacja (jeśli a, to b)
a + b
Podstawy Sterowania Logicznego 2011/12, ©ZM
9/28
Elektrotechnika I st, rok 3, moduł C
3
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Funkcje boolowskie 2 zmiennych (4)
ab
Funk
Wyrażenie
Nazwa funkcji
cja
00
01
10
11
f12
0
0
1
1
a
Przeniesienie
f12
1
0
1
1
Implikacja (jeśli b, to a)
a + b
f14
0
1
1
1
Suma (OR)
a + b
f15
1
1
1
1
1
Stała 1
Podstawy Sterowania Logicznego 2011/12, ©ZM
10/28
Zasada superpozycji i podstawiania
W realizacji technicznej funkcji boolowskich stosuje się zasady:
• Superpozycji, która polega na łańcuchowym łączeniu funktorów,
• Podstawiania, która polega na doborze (zamianie) odpowiedniego wejścia funktora.
Podstawy Sterowania Logicznego 2011/12, ©ZM
11/28
Zasada superpozycji
f (
=
⋅
⋅
+
⋅
+
⋅
+
⋅
1
x , x2, x3 ) 1
x
x2 x3
1
x
x2 x2 x3
1
x
x3
Podstawy Sterowania Logicznego 2011/12, ©ZM
12/28
Elektrotechnika I st, rok 3, moduł C
4
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Zasada podstawiania
f
=
=
3 ( w, x, y, z ) f3 ( 1
x , 1
f ( x2, x3 ), x4, f2 ( x5 , x6 )
= f a ( 1
x , x2, x3, x4, x5, x6 ) f
=
=
3 ( w, x, y, z ) f3 ( x2 , 1
f ( 1
x , x3 ), x5 , f2 ( x3, x4 )
= f b ( 1
x , x2, x3 , x4 , x5, x6 ) Podstawy Sterowania Logicznego 2011/12, ©ZM
13/28
Funkcjonalność pełna zbioru funkcji
boolowskich
Dany jest zbiór F wszystkich funkcji boolowskich n
n
zmiennych:
F = f :
→
n
{ Qn Q }
Niech F b
:
k
ędzie podzbiorem zbioru Fn
k
F ⊂ F ,
n
k
F = {f0, 1
f , ..., f k −1}
Podstawy Sterowania Logicznego 2011/12, ©ZM
14/28
Funkcjonalność pełna zbioru funkcji
boolowskich
Problem
Jakie warunki powinny spełniać funkcje należące do zbioru F , aby stosuj
k
ąc zasadę superpozycji i
podstawiania można było uzyskać każdą funkcję ze zbioru F ?
n
Rozwiązanie
Zbiór F powinien by
k
ć funkcjonalnie pełny.
Podstawy Sterowania Logicznego 2011/12, ©ZM
15/28
Elektrotechnika I st, rok 3, moduł C
5
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Funkcjonalność pełna zbioru funkcji
boolowskich
Twierdzenie
Zbiór funkcji F b
k
ędący podzbiorem zbioru funkcji
logicznych n zmiennych jest funkcjonalnie pełny, gdy zawiera co najmniej jedną funkcję:
nie zachowującą zera,
nie zachowującą jedynki,
nieliniową,
niemonotoniczą,
niesamodualną.
Podstawy Sterowania Logicznego 2011/12, ©ZM
16/28
Postać wielomianowa funkcji boolowskiej Twierdzenie
Każdą funkcję boolowską
n
f : Q → Q
można zapisać w postaci wielomianu
f ( x , ..., x
=
⊕
⊕ ⊕
⊕
1
n )
a
a x
...
a
0
1 1
n xn
⊕ a +
⊕
+
+
⊕
+
⊕
n
x x
a
1 1 2
n
x x
...
a
2 1 3
N x x ... x
1 2
n
gdzie: ai ∈ { a , ..., aN
ai = ∨
0
},
0
1
Podstawy Sterowania Logicznego 2011/12, ©ZM
17/28
Postać wielomianowa funkcji boolowskiej Aby funkcję:
f : Qn → Q
przekształcić do postaci wielomianowej należy: 1. Zapisać funkcję w normalnej postaci dysjunkcyjnej.
2. Zmienne zanegowane zapisać w postaci sumy modulo 2 zgodnie z tożsamością:
x = 1 ⊕ x
3. Działania sumy zastąpić działaniami sumy modulo 2
(+)→ (⊕)
Podstawy Sterowania Logicznego 2011/12, ©ZM
18/28
Elektrotechnika I st, rok 3, moduł C
6
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Postać wielomianowa funkcji boolowskiej 4. Wykonać zaznaczone działania i zredukować wyrazy podobne zgodnie z zasadą sumowania modulo 2
a ⊕ a ⊕ ... ⊕ a = a
gdy n nieparzys e
t
1 4
4 2
4
4 3
0
gdy n parzyste
n razy
Podstawy Sterowania Logicznego 2011/12, ©ZM
19/28
Postać wielomianowa funkcji boolowskiej Przykład
Zamienić na postać wielomianową funkcje:
=
⋅
+
⋅
+
⋅
1
f ( 1
x , x2 ) 1
x
x2
1
x
x2
1
x
x2
f
=
+
2 ( 1
x , x2 ) 1
x
x2
f
=
⋅
⋅
+
⋅
3 ( 1
x , x2, x3 ) 1
x
x2 x3
1
x
x2
Podstawy Sterowania Logicznego 2011/12, ©ZM
20/28
Klasy funkcji boolowskich
Funkcja liniowa
Definicja
Funkcja boolowska
n
f : Q → Q
jest liniowa wtedy gdy może być przedstawiona w postaci wielomianu pierwszego stopnia: f ( x , x ,..., x
1
2
= a0 ⊕ a x
1
1 ⊕ a x
2
2 ⊕ ... ⊕ a x
n )
n
n
Podstawy Sterowania Logicznego 2011/12, ©ZM
21/28
Elektrotechnika I st, rok 3, moduł C
7
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Klasy funkcji boolowskich
Funkcja zachowująca zero
Definicja
Funkcja boolowska
f : Qn → Q
jest funkcją zachowującą zero wtedy gdy:
∀ n x = 0 ⇒ f ( x) = 0
x∈ Q
Argument funkcji równy 0
∀
x
n
= ( x ... x x
x
n −
=
−
⇔ ∀ i∈
n −
i =
−
1
1
0 )
0
x∈ Q
{
∈
0,1, ...,
1}
0
Podstawy Sterowania Logicznego 2011/12, ©ZM
22/28
Klasy funkcji boolowskich
Funkcja zachowująca jeden
Definicja
Funkcja boolowska
f : Qn → Q
jest funkcją zachowującą jeden wtedy gdy:
∀ n x = 1 ⇒ f ( x) = 1
x∈ Q
Argument funkcji równy 1
∀
x
n
= ( x ... x x
x
n −
=
−
⇔ ∀ i∈
n−
i =
−
1
1
0 )
1
x∈ Q
{
∈
0,1, ...,
1}
1
Podstawy Sterowania Logicznego 2011/12, ©ZM
23/28
Klasy funkcji boolowskich
Funkcja monotoniczna
Definicja
Funkcja boolowska
f : Qn → Q
jest funkcją monotoniczną wtedy gdy:
∀
≤
⇔
≤
n
1
x
x2
f ( 1
x ) f ( x2 )
x ,
∈
1 x2
Q
Relacja porządkująca argumenty
∀
≤
⇔ ∀ ∈
∈
−
≤
n x
x
−
1
2
i
x
x
x , x
Q
∈
(0, ,1..., n 1) 1 i
2 i
1
2
Podstawy Sterowania Logicznego 2011/12, ©ZM
24/28
Elektrotechnika I st, rok 3, moduł C
8
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Klasy funkcji boolowskich
Funkcja samodualna
Definicja
Funkcja boolowska
f : Qn → Q
jest funkcją samodualna wtedy gdy:
∀
=
⇔
=
n
1
x
x2
f
∈
( x f x
x , x
Q
∈
( 1) ( 2)
1
2
Argumenty przeciwne
∀
=
⇔ ∀ ∈
∈
−
=
n x
x
−
1
2
i
x
x
x , x
Q
∈
(0, ,1..., n 1) 1 i
2 i
1
2
Podstawy Sterowania Logicznego 2011/12, ©ZM
25/28
Funkcjonalność pełna zbioru funkcji
Przykład 1
x x
f1
f2
1 0
00
1
0
01
1
1
10
0
0
11
0
1
Funkcja
f1
f2
zachowująca 0
nie
TAK
zachowująca 1
nie
TAK
liniowa
TAK
TAK
monotoniczna
nie
TAK
samodualna
TAK
TAK
Podstawy Sterowania Logicznego 2011/12, ©ZM
26/28
Funkcjonalność pełna zbioru funkcji
Przykład 2
x x
NOT
AND
NAND
OR
NOR
XOR
XNOR
1 0
00
1
0
1
0
1
0
1
01
1
0
1
1
0
1
0
10
0
0
1
1
0
1
0
11
0
1
0
1
0
0
1
Funkcja
NOT
AND
NAND
OR
NOR
XOR
XNOR
zachow. 0
nie
TAK
nie
TAK
nie
TAK
nie
zachow. 1
nie
TAK
nie
TAK
nie
nie
TAK
liniowa
TAK
nie
nie
nie
nie
TAK
TAK
monoton.
nie
TAK
nie
TAK
nie
nie
nie
samodualna
TAK
nie
nie
nie
nie
nie
nie
Podstawy Sterowania Logicznego 2011/12, ©ZM
27/28
Elektrotechnika I st, rok 3, moduł C
9
Podstawy Sterowania Logicznego,
Funkcje Boolowskie cz. 3
Funkcje liniowe dwóch zmiennych
f (
=
⊕
⊕
1
x , x2 ) a0
1
a
1
x
a2 x2
a2
a1
a0
Funkcja
0
0
0
0
0
0
1
1
0
1
0
1
x
0
1
1
1 ⊕ 1
x = 1
x
1
0
0
x2
1
0
1
1 ⊕ x =
2
x2
1
1
0
1
x ⊕ x2
1
1
1
1 ⊕
⊕
=
⊕
1
x
x2
1
x
x2
Podstawy Sterowania Logicznego 2011/12, ©ZM
28/28
Elektrotechnika I st, rok 3, moduł C
10