Algebra Boole'a

[ Pobierz całość w formacie PDF ]
Algebra Boole’a
Algebrą Boole’a
nazywamy zbiór B, wyróżnione jego podzbiory O i I oraz operacje dwuargumentowe
+; •, które dla dowolnych elementów X, Y, Z zbioru B spełniają następujące aksjomaty:
•X+Y
B;
X•Y
B
( domknięcie )
•X+Y=Y+X;
X • Y=Y • X;
( przemienność )
•X •(Y+Z)=X •Y+X •Z;
X+Y •Z=(X +Y) • (X +Z)
( rozdzielność )
•X+O=X
X •I=X
( element neutralny )
•Dla każdego X istnieje X’ takie że: X+X’=I; X •X’=O
( element odwrotny )
Dwuelementową realizację algebry Boole’a otrzymujemy dla
B={0,1};
O=0;
I=1;
1+1=1;
•:
1 •1=1;
Jeżeli X=1, to X’=0
1+0=1;
1 •0=0;
Jeżeli X=0, to X’=1
0+1=1;
0 •1=0;
0+0=0.
0 •0=0.
Ćwiczenie
Sprawdź, czy algebra zbiorówjestrównież algebrą Boole’a. Padaj wszystkie elementy
takiej realizacji.
Teoria układów logicznych
+:
Właściwości algebry Boole’a
Zasada dualizmu.
Zastępującdziałanie ‘•’ działaniem ‘+’,adziałanie ‘+’ działaniem ‘•’ oraz stałą Istałą
0, a stałą 0stałą I w dowolnej tożsamości otrzymujemy również tożsamość.
Idempotentność
X•X=X
X+X=X
Łączność
(X • Y) •Z=X • (Y • Z)
(X +Y) +Z=X +(Y +Z)
Pochłanianie
X• (X+Y)=X
X+(X•Y)=X
Prawa de Morgana
•(X+Y)’=X’•Y’
(X•Y)’=X’+Y’
Prawo podwójnej negacji
(X’)’=X
W algebrze Boole’a nie obowiązuje zasada skracania !!!
Jeżeli A • B=A • C to nie znaczy żeB=C.
Podobnie: Jeżeli A + B=A + C to nie znaczy żeB=C
Ale: Jeżeli A • B=A • Ci A+B=A+CtoB=C
Ćwiczenie
1. Udowodnij
X•X=X
2. Udowodnij prawa de Morgana.
Teoria układówlogicznych
Funkcje logiczne
Funkąją logiczną
n zmiennych nazywamy funkcję która dla każdego n elementowego wektorowa
elementów zbioru {1, 0} przyjmuje pojedynczy element zbioru {1,0) lub jest nieokreślona.
f: {1,0}
n
Formuła boolowską
nazywamy zapis zbudowany ze zmiennych połączonych działaniami +, •, ‘
(negacja).
Formuła boolowska przedstawia funkcję logiczną jeżeli dla kolejnych wektorówprzyjmują zgodne
wartości.
Dla przykładu:f(X
2
,X
1
,X
0
)= X
1
X
0
’+X
2
X
0
+X
2
X
1
X
0
’
(pominięto symbol iloczynu pomiędzy zmiennymi)
Tablicą prawdy
nazywany tablicę wktórej każdemu
wierszowi odpowiada jeden wektor zmiennych wejściowych
dla którego podano odpowiadający mu dziesiętny indeks
naturalny oraz wartość wyjściową funkcji {0,1,-}
i
X
2
X
1
X
0
f
0
0
0
0
0
1
0
0
1
1
2
0
1
0
0
3
0
1
1
-
4
1
0
0
1
Zbiory numerów wektorów
F
0
={ i | f(i)=0 }
5
1
0
1
-
6
1
1
0
0
F
1
={ i | f(i)=1 }
7
1
1
1
-
F
*
={ i | f(i)= — }
Przykład tablicy prawdy
Ćwiczenie
Podać tablicę prawdy oraz zbiory
F
0
,F
1
,F
*
funkcji
f(X
2
,X
1
,X
0
)
określonej formułą
X
2
’ X
1
’ X
0
’+X
2
X
1
’ X
0
+X
1
X
0
’
Teoria układówlogicznych
{1,0}.
Funkcje logiczne – C.D.
Podstawowe funkcje logiczne jednej i dwóch zmiennych
Funkcja NOT
f(x)=x’
Funkcja AND
f(x,y) = x • y
Funkcja OR
f(x,y) = x+y
Funkcja NAND
(NOT AND)
f(x,y) = (x • y)’
Funkcja NOR
(NOT OR)
f(x,y) = (x+y)’
Funkcja EXOR
(SUMA WYŁĄCZAJĄCA; EXCLUSIVE OR) f(x,y)=x’•y+x •y’ =x
y
Ćwiczenie
Podać tablice prawdy funkcji NAND, NOR, EXOR
System(F,O,I,+,
•
)
gdzie: F jest zbiorem wszystkich funkcji logicznych, O, I funkcje stałe zero i jeden
+: operacja logicznej sumy jest określona:
Jeżeli F= F
A
+F
B
to F= { X->F(X)=F
A
(X) + F
B
(X) }
•: operacja logicznego iloczynu jest określona:
Jeżeli F= F
A
• F
B
to F= { X->F(X)=F
A
(X) • F
B
(X) }
jest algebrą Boole’a
∅
Dokładne określenie stanów nie zdefiniowanych dla funkcji nie w pełni określonych jest ważne w procesie
minimalizacji formuł Boolowskich i umożliwia otrzymanie optymalnych rozwiązań praktycznych realizacji
funkcji.
Teoria układówlogicznych
Funkcją w
pełni określoną
nazywamy funkcję która każdemu możliwemu wektorowi wejściowemu
przypisuje określony stan. Oznacza to brak kresek w tablicy prawdy oraz F
*
=
Funkcje logiczne – C.D.(2)
Systemy funkcjonalnie pełne
System operatorów nazywamy systemem funkcjonalnie pełnym jeżeli każda funkcja może
być przedstawiona za pomocą formuły zbudowanej przy użyciu tych operatorów.
Przykłady systemów operatorów funkcjonalnie pełnych:
• {+, • , negacja}
• { + , negacja}
• { • , negacja}
• { NAND}
• {NOR}
Układem funkcji
nazywamy realizację złożoną zdwóch lub więcej funkcji
logicznych.
Często dla wygody lub z powodów praktycznych łączymy tablice prawdy wielu
funkcji w jedną tablicę prawdy z wieloma zmiennymi wyjściowymi.
Takie postępowanie w wielu przypadkach umożliwia również uzyskanie
prostszych realizacji fizycznych.
Przykład:
W(A,B,C,D); X(A,B,C,D); Y(A,B,C,D); Z(A,B,C,D) połączono w jedną tablicę
prawdy.
Teoria układówlogicznych
[ Pobierz całość w formacie PDF ]