Toán Rời Rạc(Chương IV: Đại số Bool)


(Tài liệu chưa được thẩm định)
Nguồn: Nguyễn Tất Thành
Người gửi: Nguyễn Huy Long
Ngày gửi: 20h:10' 01-09-2013
Dung lượng: 2.3 MB
Số lượt tải: 50
Số lượt thích: 0 người
ĐẠI SỐ
BOOLE
CHƯƠNG
4
Nội dung
1. Đại số Boole.
2. Hàm Boole.
3. Các cổng Logic.
4. Mạch tối tiểu.
5. Phương pháp biểu đồ Karnaugh.
1. Đại số Boole
Định nghĩa 1:
Một đại số Bool là tập hợp A cùng với 2 phép toán  và  thõa mãn các tính chất sau:
Tính kết hợp
Tính giao hoán
Tính phân bố
Phần tử trung hòa
Phần tử bù

1. Đại số Boole
Các tính chất của đại số Bool:
i. Tính kết hợp:
x, y, z  A, ta có:
x  (y  z) = (x  y)  z và
x  (y  z) = (x  y)  z

ii. Tính giao hoán:
x, y, z  A, ta có:
x  y = y  x và
x  y = y  x
1. Đại số Boole
iii. Tính phân bố:
x, y, z  A, ta có:
x  (y  z) = (x  y)  (x  z) và
x  (y  z) = (x  y)  (x  z)

iv. Phần tử trung hòa:
Tồn tại 2 phần tử trung hòa 0 và 1 đối với 2 phép toán  và  sao cho x  A
ta có: x  0 = x và
x  1 = x
1. Đại số Boole
v. Phần tử bù:
x  A, x  A sao cho:
x  x = 1 và
x  x = 0

1. Đại số Boole
Ví dụ: Xét tập hợp A = {0, 1} với 2 phép toán  và  như sau:
x  y = x.y (x.y là x nhân với y)
x  y = x + y – x.y

Ta kiểm tra 5 tính chất của đại số Bool:

i. Tính giao hoán:
x  y = x.y = y.x = y  x  dpcm
1. Đại số Boole
ii. Tính kết hợp:
Trường hợp 1:
x  (yz) = x.(y.z) = (x.y).z = (xy)  z
Trường hợp 2: Dùng bảng chân trị.

1. Đại số Boole
iii. Tính phân bố: Dùng bảng chân trị.
Xét trường hợp 1 (SV làm trường hợp 2)

1. Đại số Boole
iv. Phần tử trung hòa:
x  0 = x + 0 – x.0 = x và
x  1 = x.1 = x
 0 và 1 là 2 phần tử trung hòa của A

v. Phần tử bù:
0  0 = 0  1 = 0 + 1 – 0.1 = 1
1  1 = 1  0 = 1.0 = 0

Kết luận:
Tập hợp A = {0, 1} với 2 phép toán được định nghĩa trên là một đại số Bool

2. Hàm Boole
Định nghĩa:
Một hàm Bool n biến là một ánh xạ
f: Bn  B
Trong đó B = {0, 1}
Như vậy, hàm Bool n biến là một hàm số có dạng : f = f(x1, x2, ..., xn);
Trong đó mỗi biến x1, x2, ..., xn chỉ nhận hai giá trị 0, 1 và f nhận giá trị trong
B = {0, 1}.
2. Hàm Boole
Vì mỗi biến xi chỉ nhận 2 giá trị 0, 1 nên chỉ có 2n trường hợp của bộ biến
(x1, x2, ..., xn)
Do đó, để mô tả hàm 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
Tập hợp các hàm Bool n biến được ký hiệu bởi Fn

2. Hàm Boole
Ví dụ: Xét kết qủa 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 qủa:
f là 1 (thông qua quyết định) nếu được đa số phiếu tán thành,
f là 0 (không thông qua quyết định) nếu đa số phiếu bác bỏ.
Khi đó f là hàm Bool theo 3 biến x, y, z có bảng chân trị như sau:
2. Hàm Boole
Các phép toán trên hàm Bool
Phép cộng: Ký hiệu: 
Cho 2 hàm Bool f, g  Fn, ta định nghĩa tổng Bool của f và g như sau:
f  g = f + g – fg

Phát biểu khác: x = (x1, x2, ..., xn)  Bn
(f  g)(x) = f(x) + g(x) – f(x)g(x)

Hiển nhiên: (f  g)  Fn
Các phép toán trên hàm Bool
Phép nhân: Ký hiệu: 
Cho 2 hàm Bool f, g  Fn, ta định nghĩa tích Bool của f và g như sau:
f  g = fg
Phát biểu khác: x = (x1, x2, ..., xn)  Bn
(f  g)(x) = f(x)g(x)
Ta thường viết fg thay cho f  g
Hiển nhiên: (f  g)  Fn
Các phép toán trên hàm Bool
Phép lấy hàm bù:
Cho f  Fn, ta định nghĩa hàm bù của f như sau:



Dạng nối rời chính tắc của hàm Bool
Cho các hàm Bool: x1, x2, ..., xn  Fn
Ta có các định nghĩa như sau:
Từ đơn: là mỗi hàm bool xi hay xi
Đơn thức: là tích khác không của một số hữu hạn từ đơn
Từ tối tiểu: là tích khác không của đúng n từ đơn
Dạng nối rời chính tắc của hàm Bool
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ủa các từ tối tiểu
Dạng nối rời chính tắc của hàm Bool
Ví dụ:

Là công thức đa thức
3. Các cổng Logic
Mạng logic:
Xem hình ảnh tổng quát của một mạng logic sau:



Trong đó:



Ta nói mạng logic trên tổng hợp hay biểu diễn hàm Bool f
3. Các cổng Logic
Cổng NOT:
Ký hiệu cổng:


Bảng chân trị:



Biểu diễn hàm:
Nếu đưa mức HIGH vào ngõ vào của cổng, ngõ ra sẽ là mức LOW và ngược lại
3. Các cổng Logic
Cổng AND:
Ký hiệu cổng:

Bảng chân trị:

Biểu diễn hàm:
F(x, y) = xy

Cổng AND có ít nhất 2 ngõ vào.
Ngõ ra là 1 khi tất cả các ngõ vào là 1. Ngược lại là 0
3. Các cổng Logic
Cổng OR:
Ký hiệu cổng:

Bảng chân trị:

Biểu diễn hàm:
F(x, y) = x  y

Cổng OR có ít nhất là 2 ngõ vào.
Ngõ ra là 1, nếu có một ngõ vào là 1, Ngược lại là 0
3. Các cổng Logic
Cổng NAND:
Ký hiệu cổng:
Cổng NAND là
kết hợp 2 cổng
AND và NOT
Bảng chân trị:

Là cổng bù của AND Có ngõ ra là ngược lại với cổng AND
3. Các cổng Logic
Cổng NOR:
Ký hiệu cổng:

Cổng NOR là
kết hợp 2 cổng
OR và NOT

Bảng chân trị:


Là cổng bù của OR. Có ngõ ra ngược với cổng OR
4. Mạch tối tiểu
Mạch tối tiểu là mạng các cổng logic biểu diễn cho một đa thức tối tiểu.
Ví dụ:
Giả sử ta có các đa thức tối tiểu sau:



Hãy vẽ mạch tối tiểu cho 2 đa thức tối tiểu trên.


4. Mạch tối tiểu
Ví dụ một mạch logic của 1 hàm f
5. Phương pháp biểu đồ Karnaugh
Công thức đa thức tối tiểu:
Cho 2 công thức đa thức của 1 hàm bool:
f = f1 v f2 v ... v fk và
g = g1 v g2 v ... v gh

Ta nói rằng công thức f đơn giản hơn công thức g nếu số từ đơn fi không nhiều hơn số từ đơn gj.
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
5. Phương pháp biểu đồ Karnaugh
Công thức đa thức tối tiểu (tt):
Công thức đa thức tối tiểu của một hàm Bool f là một công thức đa thức của f trong đó không có công thức đa thức nào của f thực sự đơn giản hơn nó.
Một hàm Bool f có thể có nhiều công thức đa thức tối tiểu
5. Phương pháp biểu đồ Karnaugh
Xét hàm Bool f theo n biến x1, x2, ..., xn với n = 3 hoặc 4
Trường hợp n = 3:
f là hàm Bool theo 3 biến x, y, z. Khi đó bảng chân trị của f gồm 23 = 8 hàng.
5. Phương pháp biểu đồ Karnaugh
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ị, được đánh dấu như sau:
Lưu ý: thứ tự xyz
5. Phương pháp biểu đồ Karnaugh
Qui ước trong bảng chữ nhật:
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 và 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).
5. Phương pháp biểu đồ Karnaugh
Trường hợp n = 4:
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ị, được đánh dấu như sau:
Lưu ý: thứ tự xyzt

5. Phương pháp biểu đồ Karnaugh









Qui ước trong bảng chữ nhật: Tương tự qui ước với hàm Bool 3 biến xyz

5. Phương pháp biểu đồ Karnaugh
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.

5. Phương pháp biểu đồ Karnaugh
Qui định tên ô: có 2 cách:








Yêu cầu: Nên sử dụng cách 1.
Cách 1:
Cách 2:
5. Phương pháp biểu đồ Karnaugh
Định lý:
Cho f, g là các hàm Bool theo n biến x1, x2, ..., xn. Khi đó:
kar(fg) = kar(f)  kar(g)
kar(f v g) = kar(f)  kar(g)
kar(f) gồm đúng một ô khi và chỉ khi f là một từ tối tiểu
5. Phương pháp biểu đồ Karnaugh
Tế bào:
Tế bào là hình chữ nhật gồm 2k ô; Với
k = 1..n-1, n là số biến của hàm Bool f

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
Cách xác định tế bào của 1 đơn thức:
Lần lượt chiếu đơn thức lên các cạnh của nó. Nếu toàn bộ hình chiếu nằm trọn trong một tế bào thì thì đó chính là tế bào cần tìm
5. Phương pháp biểu đồ Karnaugh
Ví dụ 1.
Xét các hàm Bool theo 4 biến x, y, z, t.
Biểu đồ karnaugh của đơn thức là:
5. Phương pháp biểu đồ Karnaugh
Ví dụ 2.
Xét các hàm Bool theo 4 biến x, y, z, t.
Biểu đồ karnaugh của đơn thức là:

5. Phương pháp biểu đồ Karnaugh
Ví dụ 3.
Xét các hàm Bool theo 4 biến x, y, z, t.
Biểu đồ karnaugh của đơn thức là:

5. Phương pháp biểu đồ Karnaugh
Ví dụ 4.
Xét các hàm Bool theo 4 biến x, y, z, t.
Biểu đồ karnaugh của đơn thức là:

5. Phương pháp biểu đồ Karnaugh
Ví dụ 5.
Xét các hàm Bool theo 4 biến x, y, z, t
Biểu đồ karnaugh sau đây là của đơn thức nào?



5. Phương pháp biểu đồ Karnaugh
Ví dụ 6.
Xét các hàm Bool theo 4 biến x, y, z, t
Các biểu đồ karnaugh sau đây là của đơn thức nào?

x
x z
y z t
5. Phương pháp biểu đồ Karnaugh
Tế bào lớn:
Cho hàm Bool f. Ta nói T là một tế bào lớn của kar(f) nếu T thoả 2 tính chất sau:
T là một tế bào và T  kar(f)
Không tồn tại tế bào T’ nào thỏa:
T’  T và
T  T’  kar(f)

Thuật toán tìm đa thức tối tiểu
Bước 1: Vẽ biểu đồ karnaugh của f.
Bước 2: Xác định tất cả các tế bào lớn của kar(f).
Bước 3: Xác định các tế bào lớn T nhất thiết phải chọn.
Ta nhất thiết phải chọn tế bào lớn T khi tồn tại một ô của kar(f) mà ô này chỉ nằm trong tế bào lớn T và không nằm trong bất kỳ tế bào lớn nào khác.
Thuật toán tìm đa thức tối tiểu
Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn
+ Nếu các tế bào lớn chọn được ở bước 3 đã phủ được kar(f) thì ta có duy nhất một phủ tối tiểu gồm các tế bào lớn
của kar(f).
+ Nếu các tế bào lớn chọn được ở bước 3 chưa phủ được kar(f) thì:
- Xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn chứa ô này, ta chọn một trong các tế bào lớn này.
Thuật toán tìm đa thức tối tiểu
Bước 4 (tt):
- Cứ tiếp tục như thế ta sẽ tìm được tất cả các phủ gồm các tế bào lớn của kar(f).
- Loại bỏ các phủ không tối tiểu, ta tìm được tất cả các phủ tối tiểu gồm các tế bào lớn của kar(f)

Thuật toán tìm đa thức tối tiểu
Bước 5: Xác định các công thức đa thức tối tiểu của f.
Từ các phủ tối tiểu gồm các tế bào lớn của kar(f) tìm được ở bước 4, ta xác định được các công thức đa thức tương ứng của f.
Loại bỏ các công thức đa thức mà có một công thức đa thức nào đó thực sự đơn giản hơn chúng.
Các công thức đa thức còn lại chính là các công thức đa thức tối tiểu của f.

Thuật toán tìm đa thức tối tiểu
Ví dụ 1: Tìm tất cả các công thức đa thức tối tiểu của hàm Bool:
f(x,y,z,t) =
Cách làm:

Thuật toán tìm đa thức tối tiểu
Thuật toán tìm đa thức tối tiểu
Bước 1: Vẽ kar(f)



Bước 2: Kar(f) có các
tế bào lớn như sau:


x
yz
Thuật toán tìm đa thức tối tiểu
Bước 3: Xác định các tế bào lớn nhất thiết phải chọn
Ta có thể đánh số ô để dể theo dõi:

Thuật toán tìm đa thức tối tiểu
Ô 1,4,7,8,9,10 nằm trong một tế bào lớn duy nhất là x  Ta chọn x.
Ô 3,6 nằm trong một tế bào lớn duy nhất là yz  Ta chọn yz
x
yz
Thuật toán tìm đa thức tối tiểu
Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn
Ta được duy nhất một phủ tối tiểu gồm các tế bào lớn của kar(f): x v yz

x
yz
x v yz
Thuật toán tìm đa thức tối tiểu
Bước 5: Xác định các công thức đa thức tối tiểu của f.
Ứng với phủ tối tiểu gồm các tế bào lớn tìm được ở bước 4, ta tìm được duy nhất một công thức đa thức tối tiểu của f là


5. Phương pháp biểu đồ Karnaugh
Ví dụ 7: Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh như sau:





5. Phương pháp biểu đồ Karnaugh
Bước 1: Biểu đồ Karnaugh của f có 2 tế bào lớn:





Bước 2:
Ô (3,1) nằm duy nhất trong
Ô (1,1) nằm duy nhất trong
Hai tế bào lớn này đã phủ kín kar(f) nên ta qua thẳng bước 4.
5. Phương pháp biểu đồ Karnaugh
Bước 4: Ta chỉ có duy nhất 1 phép phủ ứng với công thức đa thức tối tiểu duy nhất của f :

f =



5. Phương pháp biểu đồ Karnaugh
Ví dụ 8: Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh như sau:

5. Phương pháp biểu đồ Karnaugh
Bước 1: Biểu đồ kar(f) có 4 tế bào lớn:


5. Phương pháp biểu đồ Karnaugh
Bước 2:
Ô (2,4) nằm trong tế bào lớn duy nhất
Ô (4,2) nằm trong tế bào lớn duy nhất
Chọn (gạch chéo hoặc tô) 2 tế bào lớn này, ta được sơ đồ sau:




Còn lại ô (3,3) chưa được phủ, nằm trong 2 tế bào lớn nên ta qua bước 3

Ô (3,3)
5. Phương pháp biểu đồ Karnaugh
Bước 3: Ô (3,3) nằm trong 2 tế bào lớn là
và .
Chọn tùy ý một trong 2 tế bào trên ta đều phủ kín kar(f).

Bước 4: Ta được phép phủ tối tiểu tương ứng với 2 công thức đa thức:
f =
f =
Bước 5: Cả 2 công thức này đều đơn giản như nhau nên ta được 2 công thức đa thức tối tiểu.


5. Phương pháp biểu đồ Karnaugh
Ví dụ 9. Tìm các tết bào lớn của hàm Bool f có biểu đồ karnaugh như sau:




5. Phương pháp biểu đồ Karnaugh
Kar(f) có 6 tế bào lớn:



5. Phương pháp biểu đồ Karnaugh
5. Phương pháp biểu đồ Karnaugh
5. Phương pháp biểu đồ Karnaugh
Bài tập 1: Tìm CTĐTTT của hàm f với biểu đồ kar(f) sau:




Bài tập 2: Tìm CTĐTTT của hàm f với biểu đồ kar(f) sau:


END
Add your company slogan