bi_rain_hot_boy
New Member
Download miễn phí Niên luận Tìm công thức tối tiểu của một hàm Bool bằng phương pháp Karnaugh
Mục lục:
Chương1: Tổng quan trang 5
I - Lời mở đầu trang 5
II - Mục tiêu trang 5
III - Hướng giải quyết trang 5
Chương 2: Nội dung trang 6
I - Lý thuyết trang 6
II - Ứng dụng trang 12
Ch ư ơng 3: Kết luận và hướng phát triển trang17
I - Kết quả đạt được trang 17
II - Hạn chế trang 17
III - Hướng phát triển trang 17
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Mục lục:Chương1: Tổng quan trang 5
I - Lời mở đầu trang 5
II - Mục tiêu trang 5
III - Hướng giải quyết trang 5
Chương 2: Nội dung trang 6
I - Lý thuyết trang 6
II - Ứng dụng trang 12
Ch ư ơng 3: Kết luận và hướng phát triển trang17
I - Kết quả đạt được trang 17
II - Hạn chế trang 17
III - Hướng phát triển trang 17
T ÀI LI ỆU THAM KH ẢO
[1] Toán rời rạc - Nguyễn Đức Nghĩa & Nguyễn Tô Thành
[2] Toán rời rạc 1 – Khoa CNTT
[3] Cấu trúc dữ liệu và giải thuật – Khoa CNTT
[4] Ngôn ngữ lập trình C++ và hướng đối tượng - Gs Phạm Văn Ất
Chương 1
TỔNG QUAN
I - LỜI MỞ ĐẦU
Trong thời đại ngày nay với sự phát triển nhanh chóng của công nghệ thông tin thì việc giải bài toán lập trình là việc khá đơn giản, nhưng để tìm ra một phương pháp tối ưu là điều rất khó.
Khi chúng ta áp dụng hàm bool để thiết kế một công thức.Tuy nhiên, những công thức nhận được không phải luôn luôn đơn giản vì số từ tối tiểu trong trường hợp tổng quát là rất nhiều.Người ta có thể bắt đầu từ một công thức đã biết của một hàm bool đêư đi đến một công thức đơn giản của nó nhờ vào các tính chất của các phép tính bool. Có rất nhiều cách để tìm công thức đơn giản, phương pháp Karnaugh là một trong những phương pháp tối ưu để giải quyết vấn đề trên.
Đề tài tìm công thức tối tiểu của một hàm bool bằng phương pháp Karnaugh là chương trình DeMo ứng dụng phương pháp đơn giản công thức của một hàm bool dựa áp dụng trên hàm bool 4 biến.
II - MỤC TIÊU ĐỀ TÀI
Trong bài toán tìm công thức tối tiểu này, chúng ta sẽ sử dụng các ngôn ngữ lập trình đã học và dựa vào các kiến thức của môn học Toán Rời Rạc 1, môn cấu trúc dữ liệu và giải thuật.
Thông qua đề tài này, nhằm giúp cho sinh viên ngành CNTT nói riêng và sinh viên ham thích nghiên cứu trong lĩnh vực Công nghệ nói chung hiểu biết thêm kiến thức về đơn giản công thức và cách thức ứng dụng chúng để thiết kế một mạch điện đơn giản qua đó làm giảm bớt phần khó khăn trong việc tìm ra lời giải tối ưu cho các bài toán thực tế.
III - HƯỚNG GIẢI QUYẾT.
Về lý thuyết: Tìm hiểu các khái niệm về phương pháp Karnaugh,trình bày giải thuật và lưu đồ xử lý các thủ tục được cài đặt.và các kiến thức về lập trình trên ngôn ngữ sử dụng để giải quyết yêu cầu đề tài.
Về chương trình: Sử dụng ngôn ngữ lập trình chính là C++ để viết chương trình, cài đặt các thuật toán thực hiện các yêu cầu của đề tài, nghiên cứu và cài đặt các thủ tục hàm đồ họa để hỗ trợ giao diện người dùng sử dụng phần mềm đồ họa than thiện.
Kế hoạch thực hiện:
Tìm hiểu lý thuyết 1 tuần
Xây dựng giải thuật 2 tuần
Viết chương trình 2 tuần
Thiết kế giao diện 1 tuần
Viết báo cáo và hoàn chỉnh chương trình 1 tuần
Chương 2
NỘI DUNG
I - LÝ THUYẾT
PHƯƠNG PHÁP KARNAUGH:
1.Giới thiệu phương pháp
Phương pháp Karnaugh được phát minh bởi Veitch và được cải tiến bởi Karnaugh.Phương pháp này cho 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.Riêng hàm bool nhiều biến hơn thì việc áp dụng công thức này là phức tạp.Do yêu cầu của đề tài chỉ áp dụng trên hàm bool 4 biến.
2.Sắp xếp các phần tử của B4 vào bảng Karnaugh
Các phần tử của B4 được sắp xếp vào một bảng hình chữ nhật gồm 4 dòng và 4 cột.
- -
A A A A
1010 1110 0110 0010
1011 1111 0111 0011
1001 1101 0101 0001
1000 1100 0100 0000
C D
C D
-
C D
- -
C D
- - B B B B
Định lý 16:
Hai bộ n bít chỉ khác nhau 1 bít nằm trong hai ô kề nhau.Ngược lại , hai ô kệ nhau chứa hai bộ n bít chỉ khác nhau 1 bít.
3.Sơ đồ Karnaugh của hàm 4 biến.
Sơ đồ Karnaugh của hàm bool 4 biến là một bảng giống như trong phần trước, trong đó những ô chứa bộ các bít làm cho hàm bằng 1 được tô đen.
Ví dụ:
Hàm bool 4 biến:
B4
F
0000
0
0001
1
0010
0
0011
0
0100
1
0101
1
0110
0
0111
1
1000
0
1001
0
1010
0
1011
0
1100
0
1101
0
1110
1
1111
1
F=0100 1101 0000 0011
Có bảng chân trị và sơ đồ Karnaugh như sau:
- -
A A A A -
C D
C
D
-
C D
- -
C D
- -
B B B B
Định lý 17:
Sơ đồ karnaugh của một hàm đồng nhất 0 là bảng rỗng . Sơ đồ karnaugh của hàm đồng nhất 1 là bảng tất cả các ô đều tô đen.
Quan hệ f<=g tưng đương với sơ đồ Karnaugh của g phải phủ toàn bộ sơ đồ Karnaugh của f.
Sơ đồ Karnaugh của tích fg là phần giao của sơ đồ Karnaugh cuả f và của g.
Sơ đồ Karnaugh của tổng f Ú g phần hợp của sơ đồ Karnaugh của f và g.
-
5) Sơ đồ Karnaugh của f có được bằng cách tô trắng các ô đen và tô đen ô trắng trong sơ đồ Karnaugh của f.
6) Sơ đồ Karnaugh của một từ tối tiểu chỉ có một ô tô đen.
4. Sơ đồ Karnaugh của một từ tối tiểu
Một từ tối tiểu tương ướng với một hàm bool mà dãy nhị phân của nó chỉ có một giá trị 1, nên sơ đồ Karnaugh của nó chỉ một ô được tô đen.
Để xác định các nguyên tử nhân tố của một từ tối tiểu nhờ sơ đồ Karnaugh của nó chỉ cân xem ô tô đen tương ứng với từ tối tiểu đó thuộc các dòng và các cột nào. 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 đó.
Những điều này cùng với 4 phần của định lý trên cho phép ta tìm một cách dễ dàng tuyển chuẩn tắc của mộtn hàm bool từ sơ đồ Karnaugh của nó.
Ví dụ: Xét hàm bool 4 biến có sơ đồ Karnaugh như sau:
Sơ đồ này là tổng hợp của các sơ đồ sau:
- -
ABCD ABCD
- - - -
ABCD ABCD
- - -
ABCD
Vây dạng chuẩn tắc của sơ đồ này là :
- - - - - - - -
f = ABCD Ú ABCD Ú ABCD Ú ABCD Ú ABCD
3.Sơ đồ Karnaugh của một đơn thức là
Định lý 18:
Trong Fn một đơn thức do p phân tử nguy ên tố tạo thành có sơ đồ Karnaugh là một hình chữ nhật gồm 2n-p ô được tô đen. Ngược lại mỗi hình chữ
nhật được hình thành từ 2n-p ô được tô đen là sơ đồ karnaugh của mỗi một đơn thức là tích của p litteral.
Hình chữ nhật trong định lý trên được hiểu theo nghĩa rộng và thường được gọi là các cellule.
Công thức của một cellule
Khi cellule trong sơ đồ karnaugh của một đơn thức được chứa hoàn toàn trong các cột và các dộng nào thì công thức của đơn thức bằng tích của các cột và các dòng đó.
Ví dụ :
Trong F4 có 81 đơn thức, 10 đơn thức trong số đó có sơ đồ karnaugh như sau :
_
A D AC
_ _ _ _
AB BD BD
_ _ _
ABD BCD BCD
_ _
BCD
3. Tìm công thức tối tiểu bằng phương pháp Karnaugh
Chúng ta minh hoạ các bước của phương pháp này qua hạm f trong F4 có công thức như sau :
__ _ __ _ _ _ ___ __ _
f = ABCD Ú ABCD Ú ABCD Ú ABCD Ú ABCD Ú ABCD Ú ABCD Ú ABCD
Bước 1
Bước 1
B4
F
0000
0
0001
0
0010
1
0011
1
0100
0
0101
0
0110
1
0111
1
1000
1
1001
1
1010
0
1011
0
1100
0
1101
1
1110
0
1111
1
Lập bảng chân trị của f. Vẽ sơ đồ Karnaugh của f và một sơ đồ phụ mà trong đó bgười ta cần tô đen dần các ô cho đến khi giống sơ đồ Karnaugh
Sơ đồ Karnaugh
Sơ đồ phụ
Bước 2
Trong sơ đồ Karnaugh, hãy xác định các cellule lớn. Đây là những cellule mà bản than nó không bị chứa trong các cellule khác. Ta được :
_
AC BCD ABD
1 2 3
_ _ _
ACD ABC
4 5
Bước 3
Nếu một trong sơ đồ Karnaugh bị chứa trong một cellule lớn duy nhất thì tô đen sơ đồ lớn trong sơ đồ phụ. Điếu này được làm đối với m...