System algebraiczny
System algebraiczny to zbiór A = A,α1,α , β1, β
k
m , w którym:
− A jest zbiorem elementów
− 1, ..., k s działaniami maj cymi własno zamkni to ci w zbiorze A,
− 1, ..., m s wyró nionymi stałymi.
Definicja algebry Boole’a
System algebraiczny B = B,+, ,⋅ 1
,
0 jest algebr Boole’a, gdy zbiór B jest co
najmniej dwuelementowy i gdy na tym zbiorze s zdefiniowane dwa działania typu suma i iloczyn, które spełniaj aksjomaty algebry Boole’a.
Aksjomaty algebry Boole’a:
1. ∀ a, b, c ∈ B ( a + b) + c = a + ( b + c) 2. ∀ a, b, c ∈ B ( a ⋅ b)⋅ c = a ⋅ ( b ⋅ c) 3. ∀ a, b ∈ B a + b = b + a 4. ∀ a, b ∈ B a ⋅ b = b ⋅ a 5. ∃! 0 ∈ B ∀ a ∈ B a + 0 = 0 + a = a 6. ∃!1∈ B ∀ a ∈ B a ⋅1 = 1⋅ a = a 7. ∀ a, b, c ∈ B a + ( b ⋅ c) = ( a + b)⋅ ( a + c) 8. ∀ a, b, c ∈ B a ⋅ ( b + c) = ( a ⋅ b) + ( a ⋅ c) 9. ∀ a ∈ B ∃ a ∈ B a ⋅ a = 0 ∧ a + a = 1
Twierdzenie 1
∀ a ∈ B a + a = a
Twierdzenie 2
∀ a ∈ B a ⋅ a = a
Twierdzenie 3
∀ a ∈ B a +1 =1
Twierdzenie 4
∀ a ∈ B a ⋅ 0 = 0
Twierdzenie 5
∀ a, b ∈ B a + a ⋅ b = a
Twierdzenie 6
∀ a, b ∈ B a ⋅ ( a + b) = a
Twierdzenie 7
∀ a ∈ B ∃! a ∈ B
Twierdzenie 8 (de Morgana)
∀ a, b ∈ B a + b = a ⋅ b
Twierdzenie 9 (de Morgana)
∀ a, b ∈ B a ⋅ b = a + b
Twierdzenie 10
∀ a, b ∈ B a + a ⋅ b = a + b
Definicja operacji sumy i iloczynu
Gdy Q = { }
1
,
0 , system algebraiczny B = Q,+, ,⋅ 1
,
0 jest algebr Boole’a.
Operacje sumy i iloczynu s zdefiniowane nast puj co:
0 + 0 = 0
0 ⋅ 0 = 0
0 +1 = 1+ 0 = 1
0 ⋅1 = 1⋅ 0 = 0
1+1 = 1
1⋅1 = 1
0 = 1
1 = 0
Iloczyn kartezja ski
n-krotny iloczyn kartezja ski zbioru Q tj.
n
Q = Q × Q ×...× Q
n razy
jest zbiorem n-tek, której ka dy element nale y do zbioru Q.
Na przykład:
3
Q = Q × Q × Q = { }
1
,
0 ×{ }
1
,
0 ×{ }
1
,
0 = {00 ,
0 00 ,
1 01 ,
0 01 ,
1 10 ,
0 10 ,
1 11 ,
0 11 }
1
Funkcja boolowska
Funkcja boolowska jest jednoznacznym odwzorowaniem n-krotnego iloczynu kartezja skiego Q n w zbiór Q:
f : Qn → Q
∀ x ∈ Qn, f ( x)∈ Q
Suma funkcji boolowskich
Sum funkcji boolowskich n–zmiennych f i g nazywa si tak funkcj h, która spełnia warunki:
h: Qn → Q, f + g = h ⇔ ∀ x ∈ Qn h( x) = (f + g)( x) = f ( x)+ g( x)
Iloczyn funkcji boolowskich
Iloczynem funkcji boolowskich n–zmiennych f i g nazywa si tak funkcj h, która spełnia warunki:
h: Qn → Q, f⋅ g = h ⇔ ∀ x ∈ Qn h( x) = (f⋅ g)( x) = f ( x)⋅ g( x)
Negacja funkcji boolowskiej
Funkcja boolowska f jest negacj funkcji h, tj. f = h , gdy:
∀ x ∈ Qn f ( x) = h( x)
Reprezentacja elementów zbioru Qn za pomoc liczb całkowitych
Zbiór Qn tworzy 2n ci gów zero–jedynkowych o długo ci n. Ka dy taki ci g mo na traktowa jako binarn interpretacj liczby całkowitej:
n 1
−
0
1
n 1
−
j
n
i = 2 x + 2 x − + +
=
−
∈
=
1
... 2 x 1
2 x , x Q , x
x 1, ... , x
n
n
n j
(
n )
j=0
Równanie to definiuje jednoznaczn i ró nowarto ciow zale no pomi dzy elementami zbioru Qn a liczbami całkowitymi, co mo na zapisa jako: i ⇔ x
Funkcja mintermu
Funkcj mintermu mi(x) definiuje si nast puj co:
1
gdy i
x
∀ x ∈ Qn m x
i ( )
⇔
= 0 w innym przypadku
Twierdzenie 11
Ka da funkcja logiczna (boolowska) mo e by jednoznacznie przedstawiona jako suma funkcji mintermu.
f : Qn → Q f ( x 1, ... , x =
mi 1, ... ,
gdzie
⊂
n )
( x
xn )
T
Z
i T
∈
Konstytuenta jedno ci
Dana jest funkcja f : Qn → Q i niech dla n
x ∈ Q zachodzi f ( x) = m x =
i ( )
1
Konstytuent jedno ci Ki funkcji f nazywa si iloczyn n–zmiennych: K = x* x*
=
1
2 ... x*
dla x
x 1, x 2, ... , x
i
n
(
n )
gdzie:
x
x
j
gdy j =1
*
xj =
x
x
j
gdy j = 0
Wniosek
Ka demu mintermowi odpowiada dokładnie jedna konstytuenta jedno ci.
Twierdzenie 12
Ka da funkcja logiczna (boolowska) f : Qn → Q (ró na od stałej 0) mo e by jednoznacznie przedstawiona w postaci sumy konstytuent jedno ci: f : ( x
xn =
gdzie ∀ x ∈ Q
x =
1, ... ,
)
Ki
1 f ( )
1
∈
x Q 1
Wnioski
Posta funkcji odpowiadaj c sumie konstytuent jedno ci nazywa si zupełn normaln postaci dysjunkcyjn
inaczej pierwsz postaci kanoniczn
Ka da funkcja f : Qn → Q ma
dokładnie jedn
zupełn normaln posta kanoniczn
Pochłanianie funkcji
Dane s dwie funkcje n–zmiennych f i g:
f : Qn → Q ,
g : Qn → Q
Funkcja f pochłania funkcj g ( g ⊂ f ), gdy:
∀ x ∈ Qn g( x) =1 f ( x) =1
Gdy funkcja f pochłania funkcj g, to mo na powiedzie , e funkcja g jest zawarta w funkcji f.
Implikant funkcji
Funkcj g zawart w funkcji f nazywamy implikantem funkcji f.
Implikant prosty funkcji boolowskiej
Implikantem prostym w przedstawieniu funkcji boolowskiej f w postaci sumy iloczynów jest elementarny iloczyn boolowski, z którego usuniecie dowolnego literału powoduj , e przestaje on by implikantem.
Twierdzenie
Ka da funkcja logiczna
n
f : Q → Q (ró na od zera) jest równa sumie wszystkich swych implikantów prostych.
Upraszczanie funkcji logicznych
Wykorzystuje si aksjomaty algebry Boole’a i wynikaj ce z nich twierdzenia.
W praktyce in ynierskiej nosz one nazw praw:
sklejania:
a ⋅ x + a ⋅ x = a
( a + x)⋅( a + x)= a
pochłaniania:
a + a ⋅ x = a
a ⋅ ( a + x) = a
Dana jest funkcja dwóch zmiennych f Q 2
:
→ Q zadana tablic kombinacyjn :
x1
x2
f( x1, x2)
0
0
1
0
1
0
1
0
1
1
1
1
Funkcje mintermu dwóch zmiennych:
i
x1
x2
m0( x1, x2) m1( x1, x2) m2( x1, x2) m3( x1, x2) 0
0
0
1
0
0
0
1
0
1
0
1
0
0
2
1
0
0
0
1
0
3
1
1
0
0
0
1
Funkcj f mo emy przedstawi jako sum mintermów:
f (
=
+
+
1
x , 2
x ) m0( 1
x , 2
x ) m2( 1
x , 2
x ) m3( 1
x , 2
x )
Dla poszczególnych mintermów konstytuenty jedno ci wynosz : m
= ⋅
0 ( 1
x , 2
x )
00
K0
1
x
2
x
= ⋅
1
m ( 1
x , 2
x )
01
K1
1
x
2
x
m
= ⋅
2 ( 1
x , 2
x ) 10
K2
1
x
2
x
m
= ⋅
3( 1
x , 2
x ) 11
K3
1
x
2
x
Funkcj f mo na wi c przedstawi w postaci kanonicznej:
f ( x , x = m x , x + m x , x + m x , x = K + K + K
1
2 )
0 ( 1
2 )
2 ( 1
2 )
3 ( 1
2 )
0
2
3
f (
= ⋅ + ⋅ + ⋅
1
x , 2
x )
1
x
2
x
1
x
2
x
1
x
2
x
Dana jest funkcja trzech zmiennych f Q 3
:
→ Q zadana tablic kombinacyjn :
i
x1
x2
x3
f( x1, x2, x3) 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
f ( x x x
1,
2 ,
3 ) =
( ,0 ,1 ,5 ,6 7)
Posta kanoniczna funkcji f:
f ( x , x , x =
,
0 ,
1 ,
5 ,
6 7 = K + K + K + K + K
1
2
3 )
(
)
0
1
5
6
7
f ( x , x , x = x ⋅ x ⋅ x + x ⋅ x ⋅ x + x ⋅ x ⋅ x + x ⋅ x ⋅ x + x ⋅ x ⋅ x 1
2
3 )
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
Przykład 3 – implikanty funkcji
Dana jest funkcja czterech zmiennych f Q 4
:
→ Q zadana tablic kombinacyjn :
i x1 x2 x3 x4 f( x1, x2, x3, x4) g1(x 1, ..., x4) g2( x1, ..., x4) g3( x1, ..., x4) 0 0 0 0 0
0
0
0
0
1 0 0 0 1
0
0
0
0
2 0 0 1 0
1
1
1
1
3 0 0 1 1
1
1
1
1
4 0 1 0 0
0
0
0
0
5 0 1 0 1
0
0
0
0
6 0 1 1 0
1
1
0
1
7 0 1 1 1
1
1
0
1
8 1 0 0 0
1
1
0
0
9 1 0 0 1
0
0
0
0
10 1 0 1 0
1
0
0
0
11 1 0 1 1
1
0
0
0
12 1 1 0 0
0
1
0
0
13 1 1 0 1
0
1
0
0
14 1 1 1 0
0
0
0
0
15 1 1 1 1
1
0
0
0
g ⊄
1
f
g = x ⋅ x ⋅ x ⊂
2
1
2
3
f
g = x ⋅ x ⊂
3
1
3
f
Przykład 4 – upraszczanie funkcji logicznych Z przykładu 1:
f ( x , x = f ,
0 ,
2 3 = x ⋅ x + x ⋅ x + x ⋅ x =
1
2 )
(
)
= (
1
2
1
2
1
2
x + x ⋅ x + x ⋅ x = 1⋅ x + x ⋅ x = x + x ⋅ x 1
1 )
2
1
2
2
1
2
2
1
2
Z przykładu 2:
f ( x x x
1,
2 ,
3 ) =
( ,0 ,1 ,5 ,6 7)=
= x x x
x x x
x x x
x x x
x x x
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 =
= x x x
x x x
x x x
x x x
x x x
x x x
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 =
= x x x
x
x
x x x
x x
x
x
1 ⋅
2 ⋅ ( 3 +
3 ) + ( 1 + 1 )⋅ 2 ⋅ 3 + 1 ⋅ 2 ⋅ ( 3 +
3 ) =
= x ⋅ x + x ⋅ x + x ⋅ x 1
2
2
3
1
2
lub
f ( x x x
1,
2 ,
3 ) =
( ,0 ,1 ,5 ,6 7)=
= x x x
x x x
x x x
x x x
x x x
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 =
= x x x
x x x
x x x
x x x
x x x
x x x
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 +
1 ⋅
2 ⋅
3 =
= x x x
x
x
x
x x
x x
x
x
1 ⋅
2 ⋅ ( 3 +
3 ) + ( 2 +
2 )⋅ 1 ⋅ 3 + 1 ⋅ 2 ⋅ ( 3 +
3 ) =
= x ⋅ x + x ⋅ x + x ⋅ x 1
2
1
3
1
2