Bài giảng Toán rời rạc - Chương 7: Đại số Bool
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Noäi dung
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Nguyeãn Anh Thi
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Noäi dung
Chöông 7
Ñaïi soá Bool
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Noäi dung
Nguyeãn Anh
Thi
Noäi dung
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Ñònh nghóa
Nguyeãn Anh
Thi
Moät ñaïi soá Bool laø moät taäp hôïp B cuøng hai pheùp toaùn hai ngoâi
Noäi dung
∧, ∨ thoûa:
•
Tính keát hôïp: vôùi moïi x, y, z ∈ B
x ∨ (y ∨ z) = (x ∨ y) ∨ z
x ∧ (y ∧ z) = (x ∧ y) ∧ z
Tính giao hoaùn: vôùi moïi x, y ∈ B
•
x ∨ y = y ∨ x
x ∧ y = y ∧ x
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
•
•
Tính phaân boá: vôùi moïi x, y ∈ B
Nguyeãn Anh
Thi
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
Noäi dung
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
Phaàn töû trung hoøa: trong B coù hai phaàn töû trung hoøa 0, 1
ñoái vôùi pheùp toaùn ∧, ∨ sao cho vôùi moïi x ∈ B, ta coù:
x ∨ 0 = 0 ∨ x = x
x ∧ 1 = 1 ∧ x = x
•
Phaàn töû buø: vôùi moãi x ∈ B, toàn taïi x ∈ B sao cho:
x ∨ x = 1
x ∧ x = 0
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Ví duï
Nguyeãn Anh
Thi
i) P(E) laø moät ñaïi soá Bool vôùi caùc pheùp tính ∩, ∪ cuûa caùc
taäp hôïp. Phaàn töû 0 laø taäp troáng ∅, phaàn töû 1 laø taäp E,
phaàn töû buø cuûa x ∈ P(E) laø E\x.
Noäi dung
ii) Vôùi moãi n ∈ N, n khoâng coù öôùc soá laø soá chính phöông
(nghóa laø khoâng coù daïng pk (2 ≤ k) trong caùch vieát n
thaønh tích nhöõng thöøa soá nguyeân toá) thì Un (taäp hôïp
nhöõng öôùc soá döông cuûa n) cuõng laø moät ñaïi soá Bool vôùi
x ∨ y = BSCNN(x, y)
x ∧ y = USCLN(x, y)
Luùc ñoù, Un coù phaàn töû 1 laø soá n, coøn phaàn töû 0 laø soá
nguyeân 1. Phaàn töû buø cuûa x ∈ Un laø n/x.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Ñònh nghóa
Noäi dung
Taäp hôïp B = {0, 1} vôùi caùc pheùp toaùn:
x ∧ y = x.y
x ∨ y = x + y − xy
laø moät ñaïi soá Bool, ñöôïc goïi laø ñaïi soá Bool nhò phaân. Phaàn töû
buø cuûa x laø x = 1 − x.
Treân B, ta ñònh nghóa moät quan heä thöù töï raát töï nhieân:
0 ≤ 0, 0 ≤ 1, 1 ≤ 1.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Ñònh nghóa
Nguyeãn Anh
Thi
Bieán Bool laø bieán chæ nhaän hai giaù trò 0, 1.
Noäi dung
Haøm Bool n bieán laø aùnh xaï
f : Bn → B
trong ñoù B = {0, 1}. Nhö vaäy haøm Bool n bieán laø haøm soá coù
daïng f = f(x1, x2, . . . , xn), trong ñoù moãi bieán trong x1, x , . . . , xn
chæ nhaän hai giaù trò 0, 1 vaø f nhaän giaù trò trong B = {02, 1}.
Kyù hieäu Fn ñeå chæ taäp caùc haøm Bool n bieán. Vì moãi bieán xi chæ
nhaän hai giaù trò 0, 1 neân chæ coù 2n tröôøng hôïp cuûa boä bieán
(x1, x2, . . . , xn). Do ñoù ñeå moâ taû f, ta coù theå laäp baûng goàm 2n
haøng ghi taát caû caùc giaù trò cuûa f tuøy theo 2n tröôøng hôïp cuûa
bieán. Ta goïi ñaây laø baûng chaân trò cuûa f.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Noäi dung
Ví duï
Xeùt keát quaû f trong vieäc thoâng qua moät quyeát ñònh döïa vaøo 3
phieáu baàu x, y, z. Moãi phieáu chæ laáy moät trong hai giaù trò 1 (taùn
thaønh) hoaëc 0 (baùc boû). Keát quaû f laø 1 (thoâng qua quyeát ñònh)
neáu ñöôïc ña soá phieáu taùn thaønh, laø 0 (khoâng thoâng qua quyeát
ñònh) neáu ña soá phieáu baùc boû.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Khi ñoù haøm Bool theo ba bieán x, y, z coù baûng chaân trò sau:
Noäi dung
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f
0
0
0
1
0
1
1
1
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Caùc pheùp toaùn treân haøm Bool
Nguyeãn Anh
Thi
Noäi dung
Caùc pheùp toaùn treân Fn ñöôïc ñònh nghóa nhö sau:
Pheùp coäng Bool ∨ Vôùi f, g ∈ Fn ta ñònh nghóa toång Bool cuûa f vaø
g:
f ∨ g = f + g − fg
∀x = (x1, x2, . . . , xn) ∈ Bn,
(f ∨ g)(x) = f(x) + g(x) − f(x)g(x)
Deã thaáy, f ∨ g ∈ Fn vaø (f ∨ g)(x) = max{f(x), g(x)}
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Caùc pheùp toaùn treân haøm Bool
Nguyeãn Anh
Thi
Noäi dung
Pheùp nhaân Bool ∧:
Vôùi f, g ∈ Fn ta ñònh nghóa tích Bool cuûa f vaø g
f ∧ g = fg
∀x = (x , x2, . . . , xn) ∈ Bn, (f ∧ g)(x) = f(x)g(x)
Deã thaáy1, f ∧ g ∈ Fn vaø (f ∧ g)(x) = min{f(x), g(x)}.
Pheùp laáy buø Vôùi f ∈ Fn ta ñònh nghóa haøm buø cuûa f nhö sau:
f = 1 − f
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Daïng noái rôøi chính taéc cuûa haøm
Bool
Nguyeãn Anh
Thi
Noäi dung
Xeùt taäp hôïp caùc haøm Bool cuûa n bieán Fn, theo n bieán
x1, x2, . . . , xn
•
•
Moãi haøm Bool xi hay xi ñöôïc goïi laø töø ñôn.
Ñôn thöùc laø tích khaùc khoâng cuûa moät soá höõu haïn caùc töø
ñôn.
•
•
Töø toái tieåu laø tích khaùc khoâng cuûa ñuùng n töø ñôn.
Coâng thöùc ña thöùc laø coâng thöùc bieåu dieãn haøm Bool thaønh
toång cuûa caùc ñôn thöùc.
•
Daïng noái rôøi chính taéc laø coâng thöùc bieåu dieãn haøm Bool
thaønh toång caùc töø toái tieåu.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Noäi dung
Ví duï
x, x, y, y, z, z, t, t laø caùc töø ñôn.
xyzt, xyt laø caùc ñôn thöùc.
xyzt laø töø toái tieåu.
f = xyz ∨ yz.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Coâng thöùc ña thöùc toái tieåu
Ñôn giaûn hôn
Cho hai coâng thöùc ña thöùc cuûa moät haøm Bool:
Noäi dung
f = m1 ∨ m2 ∨ · · · ∨ mk (F)
f = M1 ∨ M2 ∨ · · · ∨ Ml (G)
Ta noùi raèng coâng thöùc F ñôn giaûn hôn coâng thöùc G neáu toàn taïi
moät ñôn aùnh h : {1, 2, . . . , k} → {1, 2, . . . , l} sao cho vôùi moïi
i ∈ {1, 2, . . . , k} thì soá töø ñôn cuûa mi khoâng nhieàu hôn soá töø
ñôn cuûa Mh(i)
.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Coâng thöùc ña thöùc toái tieåu
Nguyeãn Anh
Thi
Noäi dung
Ñònh nghóa
Neáu F ñôn giaûn hôn G vaø G ñôn giaûn hôn F thì ta noùi F vaø G
ñôn giaûn nhö nhau.
Ñònh nghóa
Coâng thöùc F cuûa haøm Bool f ñöôïc goïi laø toái tieåu neáu vôùi baát kyø
coâng thöùc G cuûa f maø ñôn giaûn hôn F thì F vaø G ñôn giaûn nhö
nhau.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Phöông phaùp bieåu ñoà Karnaugh
Nguyeãn Anh
Thi
Phöông phaùp bieåu ñoà Karnaugh cho pheùp chuùng ta nhanh
choùng tìm ñöôïc caùc coâng thöùc ña thöùc toái tieåu cuûa nhöõng haøm
Bool 3, 4 bieán.
Noäi dung
Tröôøng hôïp 3 bieán: f laø haøm Bool theo 3 bieán x, y, z. Khi ñoù
baûng chaân trò cuûa f goàm 8 haøng. Thay cho baûng chaân trò cuûa f
ta veõ moät baûng chöõ nhaät goàm 8 oâ, töông öùng vôùi 8 haøng cuûa
baûng chaân trò:
101 111 011 001
100 110 010 000
Caùch bieåu dieãn cuï theå nhö sau: hai coät ñaàu daønh cho x, hai coät
sau daønh cho x, hai coät giöõa cho y, coät ñaàu vaø coät cuoái cho y,
doøng ñaàu daønh cho z, doøng cuoái daønh cho z.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Noäi dung
Khi moät oâ naèm trong daõy ñöôïc ñaùnh daáu bôûi x thì taïi ñoù x = 1,
bôûi x thì taïi ñoù x = 0, töông töï cho y, z.
Caùc oâ taïi ñoù f baèng 1 seõ ñöôïc ñaùnh daáu (toâ ñaäm hay gaïch
cheùo). Taäp caùc oâ ñöôïc ñaùnh daáu ñöôïc goïi laø bieåu ñoà Karnaugh
cuûa f, kyù hieäu laø kar(f).
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Tröôøng hôïp 4 bieán: f laø haøm Bool theo 4 bieán x, y, z, t. Khi ñoù
baûng chaân trò cuûa f goàm 16 haøng. Thay cho baûng chaân trò cuûa f
ta veõ moät baûng chöõ nhaät goàm 16 oâ, töông öùng vôùi 16 haøng cuûa
baûng chaân trò:
Nguyeãn Anh
Thi
Noäi dung
1010 1110 0110 0010
1011 1111 0111 0011
1001 1101 0101 0001
1000 1100 0100 0000
Khi moät oâ naèm trong daõy ñöôïc ñaùnh daáu bôûi x thì taïi ñoù x = 1,
bôûi x thì taïi ñoù x = 0, töông töï cho x, y, z.
Caùc oâ taïi ñoù f baèng 1 seõ ñöôïc ñaùnh daáu (toâ ñaäm hoaëc gaïch
cheùo). Taäp caùc oâ ñöôïc ñaùnh daáu ñöôïc goïi laø bieåu ñoà Karnaugh
cuûa f, kyù hieäu laø kar(f).
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Noäi dung
Trong caû hai tröôøng hôïp, hai oâ ñöôïc goïi laø keà nhau (theo nghóa
roäng), neáu chuùng laø hai oâ lieàn nhau hoaëc chuùng laø oâ ñaàu, oâ cuoái
cuûa cuøng moät haøng (coät) naøo ñoù.
Nhaän xeùt raèng do caùch ñaùnh daáu nhö treân, hai oâ keà nhau chæ
leäch nhau ôû moät bieán duy nhaát.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Tải về để xem bản đầy đủ
41 trang
15/01/2024
6640
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương 7: Đại số Bool", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_chuong_7_dai_so_bool.pdf
