Bài giảng Toán rời rạc - Chương 7: Đại số Bool - Nguyễn Anh Thi

Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Bài giảng môn học Toán Rời Rạc
Nguyễn Anh Thi
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Chương 7
Đại số Bool
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Nội dung
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Định nghĩa
Một đại số Bool là một tập hợp B cùng hai phép toán hai ngôi
∧,∨ thỏa:
• Tính kết hợp: với mọi x, y, z ∈ B
x ∨ (y ∨ z) = (x ∨ y) ∨ z
x ∧ (y ∧ z) = (x ∧ y) ∧ z
• Tính giao hoán: với mọi x, y ∈ B
x ∨ y = y ∨ x
x ∧ y = y ∧ x
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
• Tính phân bố: với mọi x, y ∈ B
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
• Phần tử trung hòa: trong B có hai phần tử trung hòa 0, 1
đối với phép toán ∧,∨ sao cho với mọi x ∈ B, ta có:
x ∨ 0 = 0 ∨ x = x
x ∧ 1 = 1 ∧ x = x
• Phần tử bù: với mỗi x ∈ B, tồn tại x ∈ B sao cho:
x ∨ x = 1
x ∧ x = 0
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Ví dụ
i) P(E) là một đại số Bool với các phép tính ∩,∪ của các
tập hợp. Phần tử 0 là tập trống ∅, phần tử 1 là tập E,
phần tử bù của x ∈ P(E) là E\x.
ii) Với mỗi n ∈ N, n không có ước số là số chính phương
(nghĩa là không có dạng pk (2 ≤ k) trong cách viết n
thành tích những thừa số nguyên tố) thì Un (tập hợp
những ước số dương của n) cũng là một đại số Bool với
x ∨ y = BSCNN(x, y)
x ∧ y = USCLN(x, y)
Lúc đó, Un có phần tử 1 là số n, còn phần tử 0 là số
nguyên 1. Phần tử bù của x ∈ Un là n/x.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Định nghĩa
Tập hợp B = {0, 1} với các phép toán:
x ∧ y = x.y
x ∨ y = x+ y− xy
là một đại số Bool, được gọi là đại số Bool nhị phân. Phần tử
bù của x là x = 1− x.
Trên B, ta định nghĩa một quan hệ thứ tự rất tự nhiên:
0 ≤ 0, 0 ≤ 1, 1 ≤ 1.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Định nghĩa
Biến Bool là biến chỉ nhận hai giá trị 0, 1.
Hàm Bool n biến là ánh xạ
f : Bn → B
trong đó B = {0, 1}. Như vậy hàm Bool n biến là hàm số có
dạng f = f(x1, x2, . . . , xn), trong đó mỗi biến trong x1, x2, . . . , xn
chỉ nhận hai giá trị 0, 1 và f nhận giá trị trong B = {0, 1}.
Ký hiệu Fn để chỉ tập các hàm Bool n biến. Vì mỗi biến xi chỉ
nhận hai giá trị 0, 1 nên chỉ có 2n trường hợp của bộ biến
(x1, x2, . . . , xn). Do đó để mô tả f, ta có thể lập bảng gồm 2n
hàng ghi tất cả các giá trị của f tùy theo 2n trường hợp của
biến. Ta gọi đây là bảng chân trị của f.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Ví dụ
Xét kết quả f trong việc thông qua một quyết định dựa vào 3
phiếu bầu x, y, z. Mỗi phiếu chỉ lấy một trong hai giá trị 1 (tán
thành) hoặc 0 (bác bỏ). Kết quả f là 1 (thông qua quyết định)
nếu được đa số phiếu tán thành, là 0 (không thông qua quyết
định) nếu đa số phiếu bác bỏ.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Khi đó hàm Bool theo ba biến x, y, z có bảng chân trị sau:
x y z f
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Các phép toán trên hàm Bool
Các phép toán trên Fn được định nghĩa như sau:
Phép cộng Bool ∨ Với f, g ∈ Fn ta định nghĩa tổng Bool của f và
g:
f ∨ g = f+ g− fg
∀x = (x1, x2, . . . , xn) ∈ Bn,
(f ∨ g)(x) = f(x) + g(x)− f(x)g(x)
Dễ thấy, f ∨ g ∈ Fn và (f ∨ g)(x) = max{f(x), g(x)}
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Các phép toán trên hàm Bool
Phép nhân Bool ∧:
Với f, g ∈ Fn ta định nghĩa tích Bool của f và g
f ∧ g = fg
∀x = (x1, x2, . . . , xn) ∈ Bn, (f ∧ g)(x) = f(x)g(x)
Dễ thấy, f ∧ g ∈ Fn và (f ∧ g)(x) = min{f(x), g(x)}.
Phép lấy bù Với f ∈ Fn ta định nghĩa hàm bù của f như sau:
f = 1− f
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Dạng nối rời chính tắc của hàm
Bool
Xét tập hợp các hàm Bool của n biến Fn, theo n biến
x1, x2, . . . , xn
• Mỗi hàm Bool xi hay xi được gọi là từ đơn.
• Đơn thức là tích khác không của một số hữu hạn các từ
đơn.
• Từ tối tiểu là tích khác không của đúng n từ đơn.
• Công thức đa thức là công thức biểu diễn hàm Bool thành
tổng của các đơn thức.
• Dạng nối rời chính tắc là công thức biểu diễn hàm Bool
thành tổng các từ tối tiểu.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Ví dụ
x, x, y, y, z, z, t, t là các từ đơn.
xyzt, xyt là các đơn thức.
xyzt là từ tối tiểu.
f = xyz ∨ yz.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Công thức đa thức tối tiểu
Đơn giản hơn
Cho hai công thức đa thức của một hàm Bool:
f = m1 ∨m2 ∨ · · · ∨mk (F)
f = M1 ∨M2 ∨ · · · ∨Ml (G)
Ta nói rằng công thức F đơn giản hơn công thức G nếu tồn tại
một đơn ánh h : {1, 2, . . . , k} → {1, 2, . . . , l} sao cho với mọi
i ∈ {1, 2, . . . , k} thì số từ đơn của mi không nhiều hơn số từ
đơn của Mh(i).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Công thức đa thức tối tiểu
Định nghĩa
Nếu F đơn giản hơn G và G đơn giản hơn F thì ta nói F và G
đơn giản như nhau.
Định nghĩa
Công thức F của hàm Bool f được gọi là tối tiểu nếu với bất kỳ
công thức G của f mà đơn giản hơn F thì F và G đơn giản như
nhau.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Phương pháp biểu đồ Karnaugh
Phương pháp biểu đồ Karnaugh cho phép chúng ta nhanh
chóng tìm được các công thức đa thức tối tiểu của những hàm
Bool 3, 4 biến.
Trường hợp 3 biến: f là hàm Bool theo 3 biến x, y, z. Khi đó
bảng chân trị của f gồm 8 hàng. Thay cho bảng chân trị của f
ta vẽ một bảng chữ nhật gồm 8 ô, tương ứng với 8 hàng của
bảng chân trị:
101 111 011 001
100 110 010 000
Cách biểu diễn cụ thể như sau: hai cột đầu dành cho x, hai cột
sau dành cho x, hai cột giữa cho y, cột đầu và cột cuối cho y,
dòng đầu dành cho z, dòng cuối dành cho z.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Khi một ô nằm trong dãy được đánh dấu bởi x thì tại đó x = 1,
bởi x thì tại đó x = 0, tương tự cho y, z.
Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm hay gạch
chéo). Tập các ô được đánh dấu được gọi là biểu đồ Karnaugh
của f, ký hiệu là kar(f).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Trường hợp 4 biến: f là hàm Bool theo 4 biến x, y, z, t. Khi đó
bảng chân trị của f gồm 16 hàng. Thay cho bảng chân trị của f
ta vẽ một bảng chữ nhật gồm 16 ô, tương ứng với 16 hàng của
bảng chân trị:
1010 1110 0110 0010
1011 1111 0111 0011
1001 1101 0101 0001
1000 1100 0100 0000
Khi một ô nằm trong dãy được đánh dấu bởi x thì tại đó x = 1,
bởi x thì tại đó x = 0, tương tự cho x, y, z.
Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm hoặc gạch
chéo). Tập các ô được đánh dấu được gọi là biểu đồ Karnaugh
của f, ký hiệu là kar(f).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Trong cả hai trường hợp, hai ô được gọi là kề nhau (theo nghĩa
rộng), nếu chúng là hai ô liền nhau hoặc chúng là ô đầu, ô cuối
của cùng một hàng (cột) nào đó.
Nhận xét rằng do cách đánh dấu như trên, hai ô kề nhau chỉ
lệch nhau ở một biến duy nhất.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Định lý
Cho f, g là các hàm Bool theo n biến x1, x2, . . . , xn. Khi đó:
a) kar(fg) = kar(f) ∪ kar(g)
b) kar(f ∨ g) = kar(f) ∩ kar(g)
c) kar(f) gồm đúng một ô khi và chỉ khi f là một từ tối tiểu.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Định nghĩa
Biểu đồ Karnaugh của một đơn thức được gọi là tế bào. Khi
đơn thức m có dạng tích của p từ đơn (1 ≤ p ≤ n) thì tế bào
tương ứng sẽ là một hình chữ nhật (trong bảng mã mở rộng)
gồm có 2n−p ô.
Nếu T là một tế bào thì T là biểu đồ Karnaugh của một đơn
thức duy nhất m. Cách xác định m như sau: lần lượt chiếu T
lên các cạnh, nếu toàn bộ hình chiếu nằm trọn trong một từ
đơn thì từ đơn đó mới xuất hiện trong m.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Ví dụ
Biểu đồ Karnaugh của đơn thức xyzt là
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Ví dụ
Biểu đồ Karnaugh của đơn thức yzt là
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Ví dụ
Biểu đồ Karnaugh của đơn thức yt là
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Ví dụ
Tế bào sau là biểu đồ Karnaugh của đơn thức nào?
Là biểu đồ Karnaugh của đơn thức yt.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Định nghĩa
Cho hàm Bool f. Ta nói T là một tế bào lớn của kar(f) nếu T
thỏa hai tính chất sau:
a) T là một tế bào và T ⊆ kar(f).
b) Không tồn tại tế bào T′ nào thỏa T′ 6= T và T ⊆ T′ ⊆ kar(f).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ Karnaugh như
sau:
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Các tế bào lớn kar(f)
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Định nghĩa
Một họ phủ tối tiểu của kar(f) là một họ L các tế bào lớn của
kar(f) có hợp là biểu đồ Karnaugh của f sao cho khi rút bớt
một tế bào lớn ra khỏi L thì hợp của họ còn lại không phủ kín
biểu đồ Karnaugh của f nữa.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Thuật toán tìm các họ phủ tối
tiểu bằng biểu đồ Karnaugh
Bước 1: Tìm tất cả các tế bào lớn của biểu đồ Karnaugh của f.
Ghi số của các tế bào lớn vào từng ô thuộc Kar(f) trong bảng
mã, gọi là bảng "tổng hợp".
Bước 2: Tìm từ trái sang phải, từ trên xuống dưới những ô chỉ
có duy nhất một tế bào lớn phủ nó, ta chọn tế bào lớn duy
nhất đó vào danh sách L.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Thuật toán tìm các họ phủ tối
tiểu bằng biểu đồ Karnaugh
Bước 3: Nếu hợp các tế bào lớn trong danh sách L đã phủ
Karnaugh của f thì ta sang bước 4. Nếu không,
a) Ta chọn một ô trong kar(f) chưa được họ L phủ, chọn một
tế bào lớn phủ ô đó vào danh sách L.
b) Kiểm tra xem có thể bỏ bớt tế bào lớn nào ra khỏi danh
sách L mà không ảnh hưởng đến phần hợp của các tế bào
lớn trong L hay không.
c) Trở lại đầu bước 3.
Bước 4: L là một họ phủ tối tiểu của Kar(f).
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Tạo công thức đa thức tối tiểu
Mỗi họ phủ tối tiểu cho ta một công thức đa thức rút gọn khá
tốt biểu diễn f. Ta so sánh những công thức đó. Những công
thức đơn giản nhất sẽ là những công thức đa thức tối tiểu của f.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Ví dụ
Cho hàm Bool f có biểu đồ Karnaugh sau:
Bước 1:Ta xác định tất cả các tế bào lớn của f bằng cách đánh
số những ô thuộc cùng một tế bào lớn.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Bước 2: ô (2, 2) chỉ bị phủ bởi T3.
ô (2, 4) chỉ bị phủ bởi T4.
ô (3, 1) chỉ bị phủ bởi T2.
ô (3, 3) chỉ bị phủ bởi T7.
Nên ta phải chọn T2,T3,T4,T7 vào danh sách L.
Vậy lúc này L = {T2,T3,T4,T7}.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Bước 3: Hợp những tế bào lớn trong L:
Chỉ còn lại hai ô (4, 2), (4, 4) lần lượt được phủ bởi T1,T5 và
T1,T6.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
• Chọn thêm T1 vào L, ta được danh sách
L1 = {T2,T3,T4,T7,T1}, phủ đủ Kar(f).
• Không chọn T1, ta chọn T5 vào danh sách L thành
L2 = {T2,T3,T4,T7,T5}, lúc này chỉ còn ô (4, 4). (Nếu
chọn T1 vào L2, ta có thể bỏ bớt T5). Ta phải chọn thêm
T6 mới phủ được Kar(f). Lúc này,
L2 = {T2,T3,T4,T7,T5,T6}.
Cả hai danh sách đều không thể rút gọn được nữa, nên cả hai
đều là họ phủ tối tiểu của Kar(f).
Từ hai họ phủ tối tiểu L1, L2 ở trên, ta thu được hai công thức
đa thức thu gọn sau:
f = xy ∨ xz ∨ yz ∨ xyz ∨ zt (1)
f = xy ∨ xz ∨ yz ∨ xyz ∨ xt ∨ yt (2)
Ta thấy công thức (1) đơn giản hơn công thức (2), nên công
thức (1) là công thức đa thức tối tiểu của f.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
Mạng các cổng
Các cổng
NOT
Ký hiệu cổng:
AND
Ký hiệu cổng:
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
OR
Ký hiệu cổng:
NAND
Ký hiệu cổng:
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Nội dung
NOR
Ký hiệu cổng:
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc