TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
BÀI TẬP THẢO LUẬN MÔN HỌC
TOÁN HỌC RỜI RẠC
Số tín chỉ : 03
Hệ: Đại học chính qui
Ngành: Nhóm ngành Công nghệ thông tin
Khoa : Công nghệ thông tin
Nhóm giảng viên biên soạn :
1. ThS Nguyễn Hiền Trinh
2. ThS Ngô Thúy Ngân
3. ThS Nguyễn Thu Huyền
4. ThS Đào Thị Thu
5. KS Nguyễn Thị Thanh Tâm
Đơn vị : Bộ môn Khoa học máy tính
Năm : 2012
1
MỤC LỤC
STT Nội dung Trang
1
Thảo luận 1: Cấu trúc tập hợp, Đại số mệnh đề
3
2 Thảo luận 2: Qui tắc suy luận, các phương pháp chứng minh
toán học
6
3 Thảo luận 3: Thuật toán, cách biểu diễn, thuật toán đệ qui,
thuật toán quay lui
9
4 Thảo luận 4: Kỹ thuật đếm cơ bản & cao cấp 16
5 Thảo luận 5:Khái niệm cơ bản về đồ thị, các đồ thị đặc biệt 20
6 Thảo luận 6: Thuật toán tìm đường đi ngắn nhất, xây dựng
cây khung ngắn nhất trên đồ thị, bài toán luồng cực đại trên

a/ Chứng minh T là quan hệ tương đương trên R
b/ Xác định lớp tương đương [a], a ∈ R
Bài 5: Trên R xét 2 quan hệ
xSy nếu x
3
≤ y
3
xTy nếu x
2
≤ y
2
Chứng minh rằng T là quan hệ thứ tự toàn phần trên R ; T không phải là quan hệ thứ tự trên R
1.3 Bài tập về logic mệnh đề và các dạng chuẩn tắc, tân từ và vị từ
Bài 6: Tìm chính tắc hội của biểu thức sau:
( )
( )
( )
( ) ( )
yxzxyxzxzyxE ∨∧∧⇔→∧∨=,,
( )( )( )
zzyxzyyxxzzyyx ∨∨∨∨∨∨⇔
( )( )( )( )( )( )( )
zyxzyxzyxzyxzyxzyxzyx ∨∨∨∨∨∨∨∨∨∨∨∨∨∨⇔
( )( )( )( )
zyxzyxzyxzyx ∨∨∨∨∨∨∨∨
3
( )( )( )( )( )( )
zyxzyxzyxzyxzyxzyx ∨∨∨∨∨∨∨∨∨∨∨∨⇔
Bài 7: Tìm chính tắc tuyển của biểu thức :
( ) ( )

zzyxzyxxzyyx ∨∨∨∨∨
⇔
zyxyzxzyxzyxzyxzyx ∨∨∨∨∨
⇔
yzxzyxzyxzyx ∨∨∨
Bài 9: Liệt kê các phần tử của các tập sau:
a/ A={ x ∈ R  (x-1)(2x
2
+ 3x + 1)=0}
b/ B={ x ∈ N  x là ước của 24}
Bài 10:Phát biểu nào sau đây là mệnh đề trong Logic mệnh đề:
a. 5 không phải là số nguyên tố
b. Tam giác đều là tam giác có các cạnh bằng nhau
c. 1 + 1 = 0
d. Phương trình 5x+4=0 có nghiệm bằng bao nhiêu?
e. 6 là số chia hết cho 2 và 3
Bài 11: Kiểm tra 3 lô hàng. Ký hiệu p
i
là mệnh đề: ”Lô hàng i đạt yêu cầu” i=1,2,3. Sử dụng p
i
và
các phép toán mệnh đề hãy biểu diễn các mệnh đề:
a. Lô hàng 1 và lô hàng 2 đạt yêu cầu
b. Không lô hàng nào đạt yêu cầu
c. Có ít nhất một lô hàng đạt yêu cầu
Bài 12: Chứng minh các đẳng thức sau:
a.
)()( rpqrqp →→⇔→→
b.
rqprqp →∧⇔→→ )(

các dấu kéo theo; không kể các dấu lượng từ thì nó là tuyển của các thành phần mà mỗi thành phần
này lại là hội của các biểu thức không chứa các dấu tuyển và hội.
Bài 15: Cho biểu thức E=
))()(())()(( xxFxxRxxQxxP ∃∨∃¬→∀∧∀
Thực hiện các phép biến đổi tương đương sau đối với E:
1. Khử phép kéo theo
2. Đưa phép phủ định về trực tiếp liên quan tới các vị từ P, Q, R, F
3. Đưa các lượng từ lên trước biểu thức
5
Thảo luận 2
Qui tắc suy luận, các phương pháp chứng minh toán học
2.1 Tổng hợp kiến thức về qui tắc lập luận, các phương pháp chứng minh toán học, các vấn đề
liên quan đại số Bool.
2.2Bài tập về các quy tắc suy diễn, chứng minh toán học.
Bài 1: Chứng minh qui tắc suy luận
rp
rqqp
→
→→ ,
Cách 1: Lập bảng giá trị chân lý
p q r
p→q q→r p→r
0 0 0 1 1 1
0 0 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1
1 0 0 0 1 0
1 0 1 0 1 1
1 1 0 1 0 0
1 1 1 1 1 1

↔
→→ ,
3/
rqp
rqrp
→∨
→→ ,
4/
rqp
rpqp
∧→
→→ ,
5/
rp
rqp
→
→∨
6/
q
qpqp →→ ,
Bài 3: Chứng minh rằng S
n
= 1 + 3 + 5 + + (2n-1) = n
2
với mọi số tự nhiên n ≥1
Chứng minh:
6
1. Khi n=1, ta có S
1
=1=1

+3
2
- + (-1)
n+1
n
2
= (-1)
n+1
n(n+1)/2 với ∀n≥1, n
∈
N
c/
1
1
+n
≥
)2 (6.4.2
)12 (5.3.1
n
n −
với ∀n=1,2,
d/ 1
3
+ 2
3
+ + n
3
= (1+2+ +n)
2
=

6/ f =
zyxzyxyzxzyxzyx ++++

7/ f = xyz +
zyxzyxyzxzyxzyxzxy +++++
8/ f =
zyxwyzxwzyxwzyxwzyxwyzxwzywxzwxywxyz ++++++++
Bài 6: Dùng thủ tục Quine-Cluskey cực tiểu hóa các hàm Bool sau (Thiết kế mạch tối thiểu biểu
diễn hàm Bool vừa tìm được)
1/ f =
zyxyzxzyxzxy +++

2/ f =
zyxyzx +
zyxzyxxyz +++
3/ f =
zyxyzxzxyxyz +++
4/ f =
zyxyzxzyxzyxzxy ++++
7
5/ f =
tzyxwtzyxwtzyxwztyxwtyzxwyztxwtzxywztyxw +++++++
8
Thảo luận 3
Thuật toán, cách biểu diễn, thuật toán đệ qui, thuật toán quay lui
3.1 Tổng hợp kiến thức về khái niệm thuật toán, các phương pháp biểu diễn thuật toán. Các
thuật toán đệ qui, quay lui.
3.2 Bài tập về thuật toán, thuật toán đệ qui, quay lui
Bài 1: Cho 2 số tự nhiên a, b. Tìm ước số chung lớn nhất của chúng.
Xác định bài toán:

1. Phải quyết định xem tại mỗi bước duyệt và so sánh giá trị nào là lớn hơn để chọn.
Bài 3: Tìm USCLN của 2 số tự nhiên a, b.
Input : Hai số tự nhiên a, b
Outputt: Số tự nhiên d là ước của a và d là ước của b; d lớn nhất trong tập các ước chung của a và
b.
Thuật toán giả mã:
Begin
9
1. Read(a,b)
2. While a<>b Do
if a>b then a:=a-b
Else b:=b-a
3.d:=a
4. Write(d)
End;
Hoặc có thể xây dựng thành thủ tục sau:
Function USCLN1(a,b:word):word;
Begin
While a<>b Do
If a> b then a:= a-b
Else b:=b-a;
USCLN:=a;
End;
Function USCLN2(a,b:word):word;
Var r: word;
Begin
While b<>0 Do
Begin
r:= a mod b;
a:= b; b:= r;

∈ {0, 1}. Cần xây dựng thành phần thứ i của cấu hình tức là xây dựng a
i
(a
i
∈ {0, 1})
• a
i
có tập giá trị đề cử là {0, 1}
• a
i
có điều kiện chấp nhận: Không có điều kiện chấp nhận
Thủ tục quay lui xây dựng thành phần a
i
Procedure Try(i: integer);
Var j: integer;
Begin
For j: = 0 to 1 do
Begin
a[i]: = j;
If i = n then ghi nhận
else Try (i+1);
End;
End;
Trong thủ tục trên cần xây dựng thêm các thủ tục: ghi nhận, khởi tạo. Chương trình liệt kê
dãy nhị phân
Program Daynhiphan;
Uses crt;
var n,d:integer;
a:array[1 20] of integer;
procedure KHOITAO;

2
, ,a
n
) trong đó a
i
∈ A,
i = 1,2, ,n và a
i
, a
j
đôi một khác nhau. Ta đi xây dựng thành phần thứ i của cấu hình a
i

• a
i
có tập giá trị đề cử là 1, 2,…,n
• a
i
có điều kiện chấp nhận: Giá trị chưa được dùng và để kiểm soát người ta dùng
mảng logic b: array[1 n] of Boolean;
- Nếu b[j] = True thì j chưa dùng
- Nếu b[j] = False thì j đã được dùng
Với mỗi giá trị đề cử j nếu b[j] = True thì j được chấp nhận và ta đi xác định a
i
theo j và sau
đó đặt b[j] = False (để xác định rằng j đã được dùng rồi)
Thủ tục quay lui xây dựng thành phần thứ i của cấu hình
Procedure Try(i: integer);
Var j: integer;
Begin

for i:=1 to n do write(a[i]:3);
writeln;
end;
procedure Try(i:integer);
var j:integer;
14
begin
for j:=1 to n do
if b[j]= true then {chap nhan j}
begin
a[i]:=j; {xac dinh a[i] theo j}
b[j]:=false; {ghi nhan trang thai moi}
if i=n then GHINHAN else Try(i+1);
b[j]:=true; {tra lai trang thai cu}
end;
end;
BEGIN
khoitao;Try(1);
readln;
END.
15
Thảo luận 4
Kỹ thuật đếm cơ bản & cao cấp
4.1 Tổng hợp kiến thức về các kỹ thuật đếm cơ bản và cao cấp.
4.2 Bài tập về các nguyên lý đếm
Bài 1:(Lý thuyết Ramsay–giải quyết các bài toán phân chia các tập con của một tập các phần tử).
Giả sử trong nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm
có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau.
Giải: Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất 3 người là bạn của
A hoặc có ít nhất 3 người là thù của A ( Vì theo nguyên lý Dirrichlet

B
∪
C) = N(A) + N(B) + N(C) - N(A
∩
B) - N(A
∩
C) - N(B
∩
C) + N(A
∩
B
∩
C )
mà N(A) = 100 , N(B) = 70 , N(C) = 50 , N(A
∩
B) =40 , N(A
∩
C) =20
N(B
∩
C) = 12 , N(A
∪
B
∪
C) =500
Suy ra N(A
∩
B
∩
C )= 500 – 100 – 70 -50 +40 + 20 + 12 = 352

N
m
( nguyên lý bù trừ)
Trong đó N
k
là tổng các phần tử của X thoả mãn k tính chất lấy từ m tính chất đã cho
16
Bài 4: Hỏi trong tập X = {1, 2, …, 10000} có bao nhiêu số không chia hết cho bất cứ số nào trong
các số 3,4,7?
Giải: Gọi A
i
= {xє X x chia hết cho i}, i = 3, 4, 7
Khi đó A
3
∪
A
4
∪
A
7
là các số trong X chia hết cho ít nhất một trong 3 số 3, 4, 7.
Vậy theo nguyên lý bù trừ, số lượng các số cần đếm sẽ là:
N(X) – N(A
3
∪
A
4
∪
A
7

7
) + N(A
4

∩
A
7
)
= [10000/(3.4)] + [10000/(3.7)] + [10000/(4.7)]
= 833 + 476 + 357 = 1666
N
3
= N(A
3
∩
A
4
∩
A
7
) = [10000/(3.4.7)] = 119
(ở đây kí hiệu [r] để chỉ số nguyên lớn nhất không vượt quá r)
Vậy số lượng các số cần đếm là: 10000 – 7261 + 1666 – 119 = 4286.
Bài 5: Nhập vào một chuỗi ký tự S. Xuất ra màn hình tất cả các hoán vị khác nhau của các ký tự
trong chuỗi S (Các ký tự trong S không nhất thiết khác nhau)
Program hoanvilap;
uses crt;
Var s:string;
KT:Array[1 255] of Boolean;
B:Array[1 255] of Char;

end;
end;
BEGIN
clrscr; Write('S=');readln(S);
n:=Length(S); dem:=0;
Fillchar(KT,Sizeof(KT),0);
Fillchar(B,Sizeof(B),0);
Try(1);
readln;
END.
Bài 6. Có bao nhiêu xâu nhị phân có dộ dài nhỏ hơn hoặc bằng 8.
Bài 7. Có bao nhiêu xâu nhị phân có độ dài là 80 hoặc bắt đầu bởi 111 hoặc kết thúc bởi 000
Bài 8. Có bao nhiêu số nguyên dương gồm đúng 3 chữ số:
a/ Chia hết cho 4
18
b/ Chia hết cho 4 hoặc cho 3
c/ Chia hết cho 4 và chia hết cho 3
4.3 Bài tập về tổ hợp và hoán vị
Bài 9 Cho tập A={1, 3, 5}. Có bao nhiêu số gồm 3 chữ số khác nhau được thành lập từ A.
Giải: Số gồm 3 chữ số khác nhau được thành lập từ A chính là một hoán vị của A, do đó số các số
theo yêu cầu là P
3
=3!=1.2.3=6 (số theo yêu cầu)
Liệt kê các số đó là: 135; 153; 315; 351; 513; 531
Bài 10. Cho A={0,1, , 9}, có thể lập được bao nhiêu số chẵn có 4 chữ số mà các chữ số đó đều
khác nhau.
19
Thảo luận 5
Khái niệm cơ bản về đồ thị, các đồ thị đặc biệt
5.1 Tổng hợp kiến thức về cấu trúc đồ thị, các phương pháp duyệt đồ thị, đồ thị Euler, đồ thị

6
7
2
5
1
4
K
Bài 2. Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề sau:
a)
1 2 3
2 0 4
3 4 0










, b)
1 2 0 1
2 0 3 0
0 3 1 1
1 0 1 0





.
Bài 3. Nêu ý nghĩa của tổng các phần tử trên một hàng (cột) của một ma trận liền kề đối với một đồ
thị vô hướng ? Đối với đồ thị có hướng ?
Bài 4: Chỉ ra thứ tự duyệt đồ thị theo BFS hoặc DFS trên các đồ thị G
1
, G
2
(bài 1); đồ thị a,b,c (bài2)
Bài 5. Tìm ma trận liền kề cho các đồ thị sau:
a) K
n
, b) C
n
, c) W
n
, d) K
m,n
, e) Q
n
.
Bài 6. Cho V={2,3,4,5,6,7,8} và E là tập hợp các cặp phần tử (u,v) của V sao cho u<v và u,v
nguyên tố cùng nhau. Hãy vẽ đồ thị có hướng G=(V,E). Tìm số các đường đi phân biệt độ dài 3 từ
đỉnh 2 tới đỉnh 8.
Bài 7. Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư. không liền kề) tùy ý trong K
3,3
với
mỗi giá trị của n sau:
a) n=2, b) n=3, c) n=4, d) n=5.
5.3 Bài tập về đồ thị Euler, Hamilton, đồ thị phẳng, vấn đề tô màu đồ thị.

Bài 1. Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 8 trên đồ thị G được
biểu diễn bởi ma trận trọng số sau:
a/ C=


























∞∞∞∞













∞∞∞∞
∞∞∞
∞∞∞∞
∞∞∞
∞∞∞∞
∞∞
∞∞∞∞
∞∞∞∞
0276
20551
7508
68047
5012
141014
7102
2420
Bài 2. Cho đồ thị với trọng số dương như hình vẽ. Hãy xác định đường đi ngắn nhất từ đỉnh 1 đến
đỉnh 7 ( xác định giá và vết của đường đi).

4
6
7
5
3
1
6
1
2
2
1
7
3
2
1
5
Bài 7. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị:
6.3 Bài tập về các thuật toán xây dựng cây khung nhỏ nhất, các phương pháp duyệt trên cây,
luồng cực đại trên mạng
Bài 8. Cho đồ thị được biễu diễn bằng ma trận trọng số (C
1
), (C
2
) :
a/ Dùng thuật toán Kruskal tìm cây khung với giá nhỏ nhất trên G
1
, G
2
b/ Dùng thuật toán Prim tìm cây khung với giá nhỏ nhất trên G
1

C=


























∞∞∞∞
∞∞∞
∞∞∞

2
5
3
7
6
4
3
3
2