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 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ọi ô như vậy. Ô ( 1 , 4 ) nằm duy nhất trong cellule lớn 1 Ô ( 4 , 1 ) nằm duy nhất trong cellule lớn 5 Vậy 2 cellule lớn 1 và 5 được tô đen trong sơ đồ phụ Bước 4 Nếu sơ đồ phụ giống sơ đồ Karnaugh thì sang bước 6 Nếu không thì sang bước 5 Trong ví dụ này ta sang bước 5 Bước 5 Trong số những cellule lớn chưa có mặt trong sơ đồ phụ ta chọn cellule lớn chứa nhiều ô chưa được tô đen nhất. Nếu có nhiều cellule lớn thoả điều kiện thì ta chọn cellule lớn lớn nhất. Nếu lại có nhiều ô lớn lớn nhất thì lần lược chọn một trong số đó. Sau cùng, tô đen cellule lớn đã chọn trên sơ đồ phụ và trở lại bước 4. Trong ví dụ này cellule lớn 3 được chọn. Bước 6 Chúng ta đi điến bước này khi sơ đồ phụ giống hoàn toàn sơ đồ Karnaugh. Một số cellule lớn đã được chọn để tô sơ đồ phụ . Công thức tối tiểu của hàm f là tổng ( Ú ) của các công thức của các cellule lớn đã được sử dụng để tô sơ đồ phụ. Trong ví dụ này các cellule lớn đa được chọn là 1 , 3 và 5 nên ta được công thức tói tiểu : _ _ _ f = AC Ú ABD Ú ABC Bước 7 Sau cùng chúng ta so sánh công thức tìm được ở bước 6 để tìm công thức tốt nhất. Đó là công thức có ít phép toán nhất. Có thể có nhiều công thức tốt như nhau. II - ỨNG DỤNG 1. Yêu cầu của đề tài Người lập trình phải tìm ra công thức tối tiểu của một hàm bool từ một công thức tổng quát được nhập từ bàn phím. 2. Lưu đồ Các hoạt động của chưong trình được thể hiện tổng quát bằng lưu đồ sau: BẮT ĐẦU SỐ BIẾN = 4 NHẬP GIÁ TRỊ ÔVUÔNG IN RA SƠ ĐỒ CÔNG THỨC KẾT THÚC Đ Đ S S 3.Giới thiệu chương trình A)Nhập vào số biến của hàm bool void ct(){ textcolor(1); setbkcolor(1); int sobien; int ovuong[16]; int a,b,c; char bien[10]; strcpy(bien,"ABCDRSXYZ"); printf("nhap vao bieu do karnaugh 4 bien.\n\n"); cout << "vui long nhap so bien ham bool: "; cin >> sobien; /* trong khi so bien lon hon 4 hoac nho hon 4 thong bao loi*/ do { if(sobien>4) { printf("\n Xin loi so bien khong dung \n"); printf("\n vui long nhap lai cho dung: "); cin >> sobien; } if(sobien<4) { printf("\n Xin loi so bien khong dung \n"); printf("\n Vui long nhap lai cho dung: "); cin >> sobien; } }while(sobien>4 || sobien<4&&getch()!=27); B)Xuất bảng đồ ra màn hình Chúng ta phải nhập giá trị vào các ô vuông của bảng đồ Karnaugh. do { printf("\nnhap vao: %c %c %c %c\n",bien[0],bien[1],bien[2],bien[3]); printf("\n Vui long nhap gia tri vao o vuong") ; for(c=0;c<16;c++) { printf("\nNhap vao o vuong thu %d: ",c); cin >> ovuong[c]; while(ovuong[c]!=0 && ovuong[c]!=1&&getch()!=27) { printf("\n gia tri cua o vuong chi la 1 hoac 0 \n",c); printf("\nNhap so o vuong thu %d: ",c); cin >> ovuong[c]; } } Nếu tất cả giá trị trong ô vuông đều bằng 0 thì in ra thông báo. Sơ đồ không có công thức . if(ovuong[0]==0 && ovuong[1]==0 && ovuong[2]==0 && ovuong[3]==0 && ovuong[4]==0 && ovuong[5]==0) if(ovuong[6]==0 && ovuong[7]==0 && ovuong[8]==0 && ovuong[9]==0 && ovuong[10]==0) if(ovuong[11]==0 && ovuong[12]==0 && ovuong[13]==0 && ovuong[14]==0 && ovuong[15]==0) { printf("\nSo do karnaugh khong co cong thuc\n\n"); return; } 4.Giới thiệu chương trình Demo Chương trình Demo sau khi thực thi sẽ có dạng như sau: Nếu ta ấn phím 1 chương trình sẽ thực thi như sau: Nếu chọn phím 2 thi chương trình thực thi là: Chúng ta ấn phím Esc để quay lại chương trình ban đầu.Từ chương trình ban ta chọn phím 3 để thoát khỏi Demo. Chương 3 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN I - KẾT QUẢ ĐẠT ĐƯỢC Sau bảy tuần nghiên cứu và tìm hiểu đề tài, cùng với sự hướng dẫn tận tình của thầy cô và sự giúp đỡ của bạn bè. Hôm nay, Niên Luận cơ bản đã được hoàn thành và đạt được một số kết quả như sau: Hiểu và cài đặt được một số thuật toán đã yêu cầu bằng ngôn ngữ C++ biết cách sử dụng các thao tác. Chương trình chạy ổn định, giao diện thân thiện với người dùng và dễ sử dụng, có thể nhập dữ liệu trực tiếp từ bàn phím. II - HẠN CHẾ Mặc dù có cố gắng để hoàn thành Niên Luận 1, nhưng đây là lần đầu tiên viết một chương trình hoàn chỉnh nên vẫn còn thiếu nhiều kinh nghiệm trong kỹ thuật lập trình cũng như trong cách tổ chức dữ liệu. Mặt khác, do thời gian và trình độ còn hạn chế nên chương trình vẫn còn nhiều sai xót ngoài ý muốn. III - HƯỚNG PHÁT TRIỂN Thiết kế giao diện thân thiện với người sử dụng Cải tiến chương trình đầy đủ và hoàn thiện hơn Phát triển chương trình sang các ngôn ngữ khác như Visua Basic, Java,…để được hổ trợ nhiều hơn.