Mục lục:
Chương1: Tổng quan
I - Lời mở đầu
II - Mục tiêu
III - Hướng giải quyết
Chương 2: Nội dung
I - Lý thuyết
II - Ứng dụng
Ch ư ơng 3: Kết luận và hướng phát triển
I - Kết quả đạt được
II - Hạn chế
III - Hướng phát triển

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

Trang 1

trang 5
trang 5
trang 5
trang 5
trang 6
trang 6
trang 12
trang17
trang 17
trang 17

trang 17


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:
•
•
•
•
•

Chương 2
Trang 2

Tìm hiểu lý thuyết
Xây dựng giải thuật
Viết chương trình
Thiết kế giao diện
Viết báo cáo và hoàn chỉnh chương trình

1 tuần
2 tuần
2 tuần
1 tuần
1 tuần



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

C

1010

1110

0110


0010

D

C

1011

1111

0111

0011

D

1001

1101

0101

0001

D

1000

1100


0100

0000

-

C
-

C

-

-

B

D

-

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:
Trang 3


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

C
D
C D
- CD
B

Định lý 17:

Trang 4

B

B

B

D


1) 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.
2) 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.
3) Sơ đồ Karnaugh của tích fg là phần giao của sơ đồ Karnaugh cuả f và của g.
4) 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

Trang 5

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 :

Trang 6


A

Trang 7

_
D

AC

_

_

__

AB

BD


BD


_
BCD

ABD

__
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 F 4 có
công thức như sau :
__

_

__

_

_

_


___

__

_

f = ABCD ∨ ABCD ∨ ABCD ∨ ABCD ∨ ABCD ∨ ABCD ∨ ABCD ∨
ABCD
Bước 1
Bước 1
4
Lập bảng chân trị của f. Vẽ sơ đồ
B
F
Karnaugh của f và một sơ đồ phụ mà
0000 0
trong đó bgười ta cần tô đen dần các ô
0001 0
cho đến khi giống sơ đồ Karnaugh
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
Trang 8
1111 1


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
_
ACD

Trang 9

2
__
ABC

3



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ụ.
Trang 10



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:

Trang 11


3.
BẮT ĐẦU

S

SỐ BIẾN = 4

Đ


S

NHẬP GIÁ
TRỊ ÔVUÔNG
Đ

IN RA SƠ ĐỒ
CÔNG THỨC

KẾT THÚC

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");
Trang 12


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 .
Trang 13


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:

Trang 14


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

Trang 15


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.

Trang 16