ươ
Ch
ạ ố ng 5: Đ i s Boole
ạ ố
Đ i s boole là gì?
Là phép toán đ i s liên quan đ n ạ ố
ệ ố ố ị ế h th ng s nh phân
Do nhà toán h c ng
ệ
ả
ơ
Đ n gi n hóa vi c trình bày
ệ
ề
Thao tác v i logic m nh đ ớ
ọ ườ ư ằ i Anh đ a ra năm 18151864 nh m
1938 Claude đ xu t s d ng đ i s Boole trong thi
ấ ử ụ ạ ố ề ế ế ạ t k m ch
Cung c p cách ti p c n ti
ế ậ ấ ế ệ ả ơ t ki m và đ n gi n
Đ c s d ng r ng rãi trong thi
ượ ử ụ ộ ế ế ạ ệ ử t k m ch đi n t trong máy tính
ề ạ ố
ơ ả
ệ
Khái ni m c b n v Đ i s Boole
Các phép toán trong đ i s Boole th c hi n trên các bi n có 2 giá tr 0 và 1, ự
ạ ố ệ ế ị
ộ
C ng logic: ‘+’ hay OR
Nhân logic: ‘ . ‘ hay AND
Phép bù: ‘’ hay NOT
g mồ
ề ạ ố
ơ ả
ệ
Khái ni m c b n v Đ i s Boole
B ng chân tr : ị
A
B
A AND B
A OR B
NOT A
0
0
0
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
0
ả
ộ ư
ử
ủ Đ u tiên c a các toán t
Toán t
ử ấ ượ ị ộ ư có đ u tiên cao nh t đ ị ầ c đ nh tr đ u tiên.
Bi u th c đ
ộ ư
Đ u tiên
ể
Toán tử ứ
ặ ( ) Bi u th c trong ngo c
1
2
ứ ượ ể ừ c tính t ả trái sang ph i
_ (NOT)
3
. (AND)
4
+ (OR)
ộ ư
ử
ủ Đ u tiên c a các toán t
ạ ố
ề ủ
Các tiên đ c a đ i s Boole
ạ ố
ề ủ
Các tiên đ c a đ i s Boole
ẫ
ố
Nguyên lý đ i ng u
Có s đ i ng u gi a toán t
ự ố ữ ẫ ử AND, OR và bit 0, 1
ạ ố
ị
ủ Các đ nh lý c a đ i s Boole
ạ ố
ị
ủ Các đ nh lý c a đ i s Boole
Hàm Boole
M t hàm Boole là m t
ộ ượ ự ệ ớ c th c hi n v i:
ể
ứ đ ộ bi u th c
ị
Các bi n nh phân ế
ử
Các toán t
AND, OR, NOT
ặ
ấ
ấ
Các d u ngo c và đ u =
ị ủ
Giá tr c a hàm Boole có th là
ể 0 ho c ặ 1
ể ượ
ộ
ể
ạ
M t hàm Boole có th đ
ễ c bi u di n d ng:
ể
ộ
ứ ạ ố M t bi u th c đ i s
ộ ả
ị M t b ng chân tr
Hàm Boole
Hàm Boole bi u di n d
Ho cặ
ớ
ượ ọ
ế ủ
V i: X, Y và Z đ
c g i là các bi n c a hàm.
ễ ướ ạ ể ể ứ ạ ố i d ng bi u th c đ i s :
Hàm Boole
Hàm Boole bi u di n d
X
Y
Z
W
ễ ướ i
0
0
0
0
0
0
1
1
ả ị ể ạ d ng b ng chân tr
0
1
0
0
S hàng c a b ng là 2n, n là ả ủ ố ượ ử ị ố s các bi n nh phân đ c s ụ d ng trong hàm.
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
ế
ự ư ừ S d th a
Khái ni m:ệ
Literal: là các bi n trong hàm Boole ế
ự ế ợ
ủ
ế
ế
ệ
ấ
ỗ
ộ
ỉ
ế là s k t h p c a các bi n mà m i bi n ch xu t hi n m t
Term c a n bi n ủ
ấ
ầ l n duy nh t.
ụ
ủ
ế Ví d : term c a 3 bi n A, B, C là A.B.C
ư ừ ế ứ ộ ể
M t bi u th c là d th a n u nó có ch a ứ
Literal l pặ : XX hay X+X
ủ
ế
Bi n và bù c a bi n
ế : XX’ hay X+X’
H ngằ : 0 hay 1
ể
ố
T i thi u hóa hàm Boole
T i thi u hàm Boolean
ầ ử
ả
Gi m s ph n t ố
(Term)
ả
Gi m s bi n (Literal) ố ế
ố ể :
Ph
ươ
ạ ố
S d ng ph ử ụ
ng pháp đ i s
ề ầ
ể ố
ề
ậ
ể
ớ
ụ
Áp d ng các đ nh lý, tiên đ , các lu t nhi u l n đ t
i thi u hàm Boolean t
i
ứ
ấ
ị ấ m c th p nh t.
ươ : ng pháp
ể
ố
T i thi u hóa hàm Boole
ủ
ầ
Ph n bù c a hàm Boole
ủ
ầ
Ph n bù c a hàm Boole
Ví d : tính ph n bù c a hàm sau: ầ
ướ
ể
ử
B c 1: Chuy n toán t
AND thành OR và ng
ượ ạ c l
i.
ướ
ủ
B c 2: tính ph n bù c a các bi n ế ầ
ụ ủ
ủ
ắ
ạ
D ng chính t c c a hàm Boole
ế ộ ượ ễ ướ ể M t hàm n bi n luôn đ c bi u di n d ạ i 2 d ng:
ể ể c bi u di n d bi u th c đ
D ng t ng các tích (sumofproduct SOP): ỗ
ổ ổ ứ ượ ạ ễ ướ ủ ạ
ạ i ạ d ng t ng (sum) các toán h ng (term), m i toán h ng là tích (product) c a các literal
D ng tích các t ng ạ
ứ ượ ể ể ễ ướ c bi u di n d i
ổ (productofsum POS): bi u th c đ ạ ủ ỗ ổ ạ ạ d ng tích các toán h ng, m i toán h ng là t ng c a các literal
ủ
ắ
ạ
D ng chính t c c a hàm Boole
ạ ứ ế ạ ở ạ ắ d ng chính t c
ủ ứ ừ SOP hay POS và không ch a các literal th a.
D ng chính t c ể ắ : bi u th c n bi n d ng ủ n u ế m i toán h ng c a nó có đ n literal ạ ỗ
M t bi u th c SOP ho c POS không chính t c luôn đ
ắ ặ ượ ộ ể c chuy n thành
Vd:
E = xy’ + x’y + xz + yz
= xy’(z + z’) + x’y(z + z’) + xz(y + y’) + yz(x + x’)
= xy’z + xy’z’ + x’yz + x’yz’ + xyz + xy’z + xyz + x’yz
= xy’z + xy’z’ + x’yz + x’yz’ + xyz
ứ ể ắ ạ d ng chính t c
ủ
ắ
ạ
D ng chính t c c a hàm Boole
ự ữ ệ ạ ộ
Minterm: Th c hi n phép toán AND gi a các literal t o thành m t Term Maxterm: Th c hi n phép toán OR gi a các literal t o thành m t Term
ự ữ ệ ạ ộ
ủ
ắ
ạ
D ng chính t c c a hàm Boole
ể
ễ
ướ ạ
Bi u di n hàm Boole d
i d ng SOP
Các b
ị ủ
ự
ả
c 1
B
ướ : Xây d ng b ng chân tr c a hàm Boole
ỗ ự ế ợ ủ
ự
ế
ộ
B
c 2
ướ : Xây d ng m t minterm cho m i s k t h p c a các bi n mà làm cho
ị
hàm có giá tr là 1
ứ ế
ể
ả
ổ
ượ ở ướ
B
c 3
ướ : Bi u th c k t qu là t ng (OR) các minterm thu đ
b
c
c 2
ướ ể ể ướ ạ ễ c đ bi u di n hàm Boole d i d ng SOP
ể
ễ
ướ ạ
Bi u di n hàm Boole d
i d ng SOP
Ví d : b ng chân tr c a hàm F1
ụ ả ị ủ
ế
Có 3 k t h p c a các bi n cho ủ ế ợ giá tr c a hàm là 1
001, 100, 111
ị ủ
ể
ễ
ướ ạ
Bi u di n hàm Boole d
i d ng SOP
ể
ễ
ướ ạ
Bi u di n hàm Boole d
i d ng POS
Các b
ị ủ
ự
ả
1. Xây d ng b ng chân tr c a hàm Boole.
ỗ ự ế ợ ủ
ế
ộ maxterm cho m i s k t h p c a các bi n mà làm cho hàm có giá
ự 2. Xây d ng m t ị tr là
0
ể
ấ ả
ượ ừ ướ
ứ ế 3. Bi u th c k t qu là
t c các
c t
b
c 2
ả AND t
maxterm thu đ
ướ ể ể ướ ạ ủ ễ c đ bi u di n hàm Boole d i d ng ổ (POS): tích c a các t ng
ể
ễ
ướ ạ
Bi u di n hàm Boole d
i d ng POS
Ví d : b ng chân tr c a hàm
ụ ả ị ủ
Có 5 s k t h p làm cho giá
ị ủ
ự ế ợ tr c a hàm là 0:
000, 010, 011, 101, 110
F1:
ể
ễ
ướ ạ
Bi u di n hàm Boole d
i d ng POS
Các maxterm t
ươ ứ ng ng là
Th c hi n phép AND t
ự ệ ấ ả ượ ứ ủ ể t c các maxterm ta đ c bi u th c POS c s hàm
F1.
ữ
ể
ạ
ắ
ổ
Chuy n đ i gi a các d ng chính t c
Đ chuy n đ i t
ệ
ổ
Đ i các kí hi u
ệ
ặ ừ
ố
ầ
Li
t kê danh sách các tham s không có m t t
hàm ban đ u.
ể ể ổ ừ ộ ạ ộ ạ ắ ắ m t d ng chính t c này sang m t d ng chính t c khác:
ữ
ể
ạ
ắ
ổ
Chuy n đ i gi a các d ng chính t c
Ví d : ụ F (A, B, C) = ∑(1, 4, 5, 6, 7)
ể ượ
ầ
ư
ể
Ph n bù đó có th đ
ễ c bi u di n nh sau:
= m1 + m4 + m5 + m6 + m7
ụ
ị
ượ
ướ
ộ ạ
Áp d ng đ nh lý De Morgan’s chúng ta thu đ
c F d
i m t d ng khác :
F (A, B, C) = п(0, 2, 3) = m0 + m2 + m3
F = M0 . M2 . M3
π = (0, 2, 3)
