bai thuyet trinh toan roi rat ppsx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (937.71 KB, 19 trang )
m62 visualcommunications is the global leader in presentation effectiveness, from offices in the UK, USA, and Singapore
Beyond Bullet Points
PowerPoint Slides
PowerPoint Training
It’s not the design of your template, it’s what you do with it that counts
Bài gi ng : ả TOÁN R I R CỜ Ạ
Chương VI: ĐƠN GIẢN CÔNG THỨC
PHƯƠNG PHÁP
KARNAUGH
Huỳnh Ngọc Thái Anh -1107501
Lớp: Mạng máy tính và truyền thông k36
I/ Phương pháp KARNAUGH
Maurice Karnaugh
(4.10.1924 - ?.?.?)
-Phương pháp Karnaugh được phát minh bởi Veitch và được
cải tiến bởi Karnaugh.
-Là phương pháp tìm công thức tối tiểu dạng đa thức của
hàm bool 3 hay 4 biến
2/Sắp xếp các phần tử của B
3
và B
4
vào bảng Karnaugh
-
Các phần tử B
3
được xếp vào 1 bảng 2 dòng 4 cột
Các phần tử B
4
được xếp vào 1 bảng 4 dòng 4 cột
Quy tắc :
-ô trên cột chỉ định bởi a→bit thứ 1 là 1
bởi ¬a→bit thứ 1 là 0
Bảng Karnaugh B
3
-ô trên cột chỉ định bởi b→bit thứ 2 là 1
bởi ¬b→bit thứ 2 là 0
-ô trên dòng chỉ định bởi c→bit thứ 3 là 1
bởi ¬c→bit thứ 3 là 0
-ô trên dòng chỉ định bởi d→bit thứ 4 là 1
bởi ¬d→bit thứ 4 là 0
(đối với B4)
<> Định lí:
-Hai bộ n bit chỉ khác nhau 1 bit nằm trong 2 ô kề nhau.
Ngược lại, hai ô kề nhau chứa 2 bộ bit chỉ khác nhau 1 bit.
Ví dụ:
Ô kề nhau theo nghĩa mở rộng:
3/ Sơ đồ Karnaugh của hàm bool 3 biến và 4
biến
Là 1 bảng như phần trước, trong đó ô chứa
các bit làm cho hàm bằng 1 được tô đen
Ví dụ: hàm bool B
4
như sau :
<> Định lí:
1/ Sơ đồ Karnaugh của hàm đồng nhất 0
là bảng rỗng, của hàm đồng nhất 1 là
bảng tất cả các ô điều tô đen.
2/ Quan hệ f ≤ g sơ đồ Karnaugh của g phải phủ toàn bộ sơ
đồ Karnaugh của f.
sơ đồ f ≤ sơ đồ g
3/ Sơ đồ Karnaugh của f.g là phần giao của sơ đồ f và g.
* =
sơ đồ f sơ đồ g sơ đồ f.g
4/ Sơ đồ Karnaugh của fvg là phần hợp của sơ đồ f và g.
v =
sơ đồ f sơ đồ g sơ đồ fvg
5/ Sơ đồ Karnaugh ¬f đối lập các ô trắng đen với sơ đồ f.
f ¬f
6/ Sơ đồ Karnaugh của mỗi từ tối tiểu chỉ có 1 ô được tô đen.
-Một từ tối tiểu là một hàm bool mà dãy nhị phân tương ứng
chỉ có 1 giá trị 1 sơ đồ chỉ có 1 ô được tô đen.
4/ Sơ đồ Karnaugh của một từ tối tiểu.
-Từ tối tiểu có công thức chính là tích của các dòng và các cột
chứa nó.
Tìm được dạng tuyển chuẩn tắc của hàm.
Ví dụ: hàm bool B
3
có sơ đồ:
Là tập hợp của:
Dạng tuyển chuẩn tắc của hàm f là :
f=a¬bc v ab¬c v ¬ab¬c v ¬abc
5/ Sơ đồ Karnaugh của hàm đơn thức:
<> Định lí:
Trong F
n
một đơn thức do p nhân tử tạo thành có sơ đồ là hình
chữ nhật có 2
n-p
ô được tô đen. Ngược lại mỗi hình chữ nhật
có 2
n-p
ô được tô đen là sơ đồ của 1 đơn thức là tích của p
literal. Các cell
Công thức tính 1 cell:
Khi cell trong sơ đồ của 1 đơn thức chứa hoàn toàn trong cột,
dòng nào thì công thức của đơn thức bằng tích các cột, dòng đó.
- Trong F
n
thì có 3
n
đơn thức (= 3
n
cell)
Ví dụ: F
3
có 3
3
=27 đơn thức
có vài sơ đồ Karnaugh
như sau: (xem thêm tại
giáo trình trang 100)
F
4
có 3
4
=81
đơn thức có vài sơ
đồ Karnaugh như sau:
6/ Tìm công thức tối tiểu bằng phương pháp Karnaugh.
Minh họa cách làm :
Cho f= ¬a¬bc¬d v ¬a¬bcd v ¬abc¬d v ¬abcd v a¬b¬c¬d v
a¬b¬cd v ab¬cd v abcd Tìm công thức tối tiểu ?
Bước 1:
Lập bảng chân trị. Vẽ sơ đồ karnaugh
và 1 sơ đồ phụ, mà trong đó người ta cần tô
các ô cho đến khi giống sơ đồ Karnaugh
sơ đồ Karnaugh sơ đồ phụ
Bước 2: Xác định những cell lớn,
là những cell không bị chứa trong
những cell khác.
Tìm cell lớn
còn thiếu ?
Sơ đồ Karnaugh
Cell lớn không là cell lớn
Bước 3: nếu bất kì ô nào trong sơ đồ cell chứa trong 1 cell lớn
duy nhất thì tô đen cell lớn đó trong sơ đồ phụ.
Bước 4:
Nếu sơ đồ phụ giống sơ đồ Karnaugh thì sang bước 6
Nếu không giống thì sang bước 5
ví dụ này ta sang bước 5
Bước 5:
Trong số những cell lớn chưa có mặt trong
sơ đồ ta chọn cell có chứa nhiều ô chưa
được tô đen nhất, đồng thời là lớn nhất. Nếu
có nhiều cell lớn lớn nhất thì chọn 1 trong
số chúng.
Tô đen ô đã chọn rồi trở lại bước 4
Bước 6:
Đến đây thì sơ đồ phụ đã hoàn toàn giống với sơ đồ Karnaugh
Công thức tối tiểu của hàm f là tổng (v) của các công thức
của các cell lớn đã được sử dụng để tô sơ đồ phụ.
Trong ví dụ này các cell được chọn là 1,3,5
+ + =
(cell 1) ¬ac (cell 3) abd (cell 4) a¬b¬c
f= ¬ac v abd v a¬b¬c
Bước 7:So sánh các công thức tìm được ở bước 6 để tìm
công thức có ít phép toán nhất ( tốt nhất ), có thể
có nhiều công thức tốt như nhau.
Huỳnh Ng c Thái Anhọ
Thank you !
THE END
