Bài giảng Toán ứng dụng trong tin học - Chương 1: Quan hệ & suy luận toán học - Nguyễn Thanh Chuyên

yen@gmail.com 
 QUAN HỆ & 
SUY LUẬN TOÁN HỌC 
Chương 1 
Bài giảng TOÁN ỨNG DỤNG TRONG TIN HỌC 
(Tài liệu cập nhật – 2009) 
TRƯỜNG CAO ĐẲNG NGHỀ iSPACE 
137C Nguyễn Chí Thanh, P 9, Q 5, TP. Hồ Chí Minh 
Web: ispace.edu.vn - Tel: 08.6.261.0303 - Fax: 08.6.261.0304 
1.1 Tập hợp và Quan hệ 
1.2 Suy luận toán học 
1.3 Quan hệ hai ngôi 
1- Khái niệm về tập hợp 
2- Quan hệ giữa các tập hợp 
3- Các phép toán về tập hợp 
4- Quy nạp toán học 
5- Định nghĩa bằng đệ quy 
6- Các thuật toán đệ quy 
7- Tính đúng đắn của chương trình 
8- Quan hệ tương đương 
9- Quan hệ thứ tự 
Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
1.1- TẬP HỢP - QUAN HỆ 
1- Khái niệm về Tập hợp 
+ TẬP HỢP; một số các phần tử cùng tính chất 
Tập hợp các SV lớp A, trường B 
Tập hợp các số nguyên 
Tập hợp các điểm trên một đường tròn 
+ Tập hợp A , B, C --- các phần tử x, y, z... 
phần tử x thuộc tập hợp A, 
 x không thuộc tập hợp B 
A 
B 
X 
Y 
Z 
C 
C là tập hợp rỗng 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
1.1- TẬP HỢP - QUAN HỆ (tt) 
+ CÁCH DIỄN TẢ MỘT TẬP HỢP; 
L 
N 
R 
+ Liệt kê 
+ Đặc trưng 
A =  x  x có tính chất p  
+ THCS tự nhiên N 
+ THCS nguyên Z 
+ THCS hữu tỷ Q 
+ THCS vô tỷ 
+ Tập hợp các số thực R 
+ THCS nguyên tố NT 
+ THCS chẵn C 
+ THCS lẻ L.... 
+ THCS phức P 
+ THCS ảo A 
1- Khái niệm về Tập hợp 
B = {x  x=n 2 +1; n  N và 1<n≤5} 
A = {5, 10, 17, 26 } 
Ví dụ 1.1: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
2- Quan hệ giữa các tập hợp; 
+ Tập hợp CON 
B 
A 
X 
Y 
Z 
B 
C 
Tính bắc cầu: 
t 
n 
Quy ước: 
+ Sự bằng nhau của 2 tập hợp 
1.1- TẬP HỢP - QUAN HỆ (tt) 
E 
X 
Y 
Z 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
3- Các phép toán về tập hợp 
a. Phép hợp 
b. Phép giao 
c. Hiệu của 2 tập hợp 
d. Tập bù 
e. Tích của 2 tập hợp 
f. Phân hoạch 
1.1- TẬP HỢP - QUAN HỆ (tt) 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
3- Các phép toán về tập hợp 
a. Phép H Ợ P 
1.1- TẬP HỢP - QUAN HỆ (tt) 
B 
A 
1 
3 
2 
4 
b 
3 
2 
a 
B 
A 
1 
3 
2 
4 
b 
3 
2 
a 
Tính chất (hợp) 
T.lũy đẳng 
T.kết hợp 
T. rỗng 
T.giao hoán 
Ví dụ 1.2: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
3- Các phép toán về tập hợp 
b. Phép GIAO 
1.1- TẬP HỢP - QUAN HỆ (tt) 
B 
A 
1 
3 
2 
4 
b 
3 
2 
a 
T.lũy đẳng 
T.kết hợp 
T.rỗng 
T.giao hoán 
Tính chất (GIAO ) 
E r ời B 
E 
f 
Ví dụ 1.3: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
3- Các phép toán về tập hợp 
c. HiỆ U của 2 tập hợp 
1.1- TẬP HỢP - QUAN HỆ (tt) 
F 
E 
1 
3 
2 
4 
b 
3 
2 
a 
E 
3 
2 
4 
3 
2 
F 
b 
a 
1 
3 
2 
Ví dụ 1.4: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
3- Các phép toán về tập hợp 
d/ Tập BÙ 
1.1- TẬP HỢP - QUAN HỆ (tt) 
Bù của A trong E 
E 
A 
E 
A 
Luật De Morgan 
Ví dụ 1.5: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
3- Các phép toán về tập hợp 
d/ TÍCH của 2 tập hợp 
1.1- TẬP HỢP - QUAN HỆ (tt) 
Không có tính giao hóan 
AxB 
A 
B 
Ví dụ 1.6: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
3- Các phép toán về tập hợp 
e/ PHÂN HOẠCH 
1.1- TẬP HỢP - QUAN HỆ (tt) 
Các tập con A 1 , A 2 , A 3 của tập X tạo nên một PHÂN HOẠCH của X, nếu: 
Ví dụ 1.7: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
3- Các phép toán về tập hợp 
V í dụ 1.8- (Hệ nhị phân) 
1.1- TẬP HỢP - QUAN HỆ (tt) 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Bài tập 1.1: 
Biết 
Hãy tính: 
Bài tập về nhà DẠNG 1 (Homework-1): 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Cho A = {x  x=n 2 +1; n  N và 1<n≤9} 
 và B = {y  y=5n; n=2, 5, 8, 10, 13} Xác định: 
trong A 
trong B 
trong A  B 
Bài tập 1.2: 
Bài tập về nhà DẠNG 1 (Homework-1): 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
1.2 Suy luận toán học 
4- Quy nạp toán học 
5- Định nghĩa bằng đệ quy 
6- Các thuật toán đệ quy 
7- Tính đúng đắn của chương trình 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Phương pháp 
 Với những bài toán chứng minh tính đúng đắn của một biểu thức mệnh đề có chứa tham số n, như P(n). Quy nạp toán học là một kỹ thuật chứng minh P(n) đúng với mọi số tự nhiên n ≥N 0 . 
 - Quá trình chứng minh quy nạp bao gồm 2 bước: 
 Bước cơ sở: Chỉ ra P(N 0 ) đúng. 
 Bước quy nạp: Chứng minh nếu P(k) đúng thì P(k+1) đúng. Trong đó P(k) được gọi là giả thiết quy nạp. 
Chứng minh 1 + 3 + 5 + 7 + + (2n-1)= n 2 với n ≥ 1 
4- Quy nạp toán học 
1.2 Suy luận toán học 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Bước 1 : Chỉ ra n=1 (*) đúng: 
Bước 2 : Giả sử (*) đúng với n= k : 
Chứng minh 
Giải: 
 Chứng minh (*) đúng với n =k+1: 
 Bài toán đã được c hứng minh đúng với n=k+1) : 
Ví dụ 1.9: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
5- Định nghĩa bằng đệ quy 
(Định nghĩa quy nạp) 
1.2 Suy luận toán học 
Biết 
Tính f(3) 
Giải: 
Ví dụ 1.10: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Bài tập 2.1: 
Biết 
Tính f(4) 
Bài tập 2.2: 
Biết 
Tính f(3) 
Bài tập 2.3: 
Biết 
Tính f(5) 
Bài tập về nhà DẠNG 2 (Homework-2): 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
6- Các thuật toán đệ quy 
Ví dụ 1.11- Thuật toán đệ quy tính a n 
Hàm lũy thừa 
(a  R và a  0; n  N và n  0 ) 
if n=0 then luythua(a,n) : =1 
else luythua(a,n)=a*luythua(a,n-1) 
1.2 Suy luận toán học 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
7- Tính đúng đắn của chương trình 
Chương trình đúng đắn  Mọi đầu vào khả dĩ  đầu ra đúng 
Chương trình (Đọan CT) S là đúng đắn bộ phận đối với khẳng định đầu p và khẳng định cuối q 
If điều_kiện then 
 S1 
else 
 S2 
 Câu lệnh điều kiện 
While điều_kiện 
 S 
 Bất biến vòng lập While 
1.2 Suy luận toán học 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Định nghĩa 
Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích Đề các R  A x B . 
Chúng ta sẽ viết a R b thay cho ( a , b )  R 
Quan hệ từ A đến chính nó được gọi là quan hệ trên A 
R = { ( a 1 , b 1 ), ( a 1 , b 3 ), ( a 3 , b 3 ) } 
23 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Ví dụ. A = tập sinh viên; B = các lớp học. 
	 R = {( a , b ) | sinh viên a học lớp b } 
24 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Ví dụ. Cho A = {1, 2, 3, 4}, và 
R = {( a , b ) | a là ước của b } 
Khi đó 
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)} 
1 
2 
3 
4 
1 
2 
3 
4 
25 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu: 	  a  A, a R a 
Ví dụ. Trên tập A = {1, 2, 3, 4}, quan hệ: 
R 1 = {(1,1), (1,2), (2,1), (2, 2), (3, 4), (4, 1), (4, 4)} không phản xạ vì (3, 3)  R 1 
R 2 = {(1,1), (1,2), (1,4), (2, 2), (3, 3), (4, 1), (4, 4)} phản xạ vì (1,1), (2, 2), (3, 3), (4, 4)  R 2 
26 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Quan hệ  trên Z phản xạ vì a  a với mọi a  Z 
Quan hệ > trên Z không phản xạ vì 1 > 1 
1 
2 
3 
4 
1 
2 
3 
4 
Quan hệ“ | ” (“ước số”) trên Z + là phản xạ vì mọi số nguyên a là ước của chính nó . 
Chú ý. Quan hệ R trên tập A là phản xạ nếu nó chứa đường chéo của A × A : 
 = {( a , a ); a  A } 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Định nghĩa. Quan hệ R trên A được gọi là đối xứng nếu: 
 a  A  b  A ( a R b )  ( b R a ) 
Quan hệ R được gọi là phản xứng nếu 
 a  A  b  A ( a R b )  ( b R a )  ( a = b ) 
Ví dụ. 
Quan hệ R 1 = {(1,1), (1,2), (2,1)} trên tập 
 A = {1, 2, 3, 4} là đối xứng 
Quan hệ  trên Z không đối xứng. 
Tuy nhiên nó phản xứng vì 
 ( a  b )  ( b  a )  ( a = b ) 
28 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Định nghĩa. Quan hệ R trên A có tính bắc cầu (truyền) nếu 
 a  A  b  A  c  A ( a R b )  ( b R c )  ( a R c ) 
Ví dụ. 
Quan hệ R = {(1,1), (1,2), (2,1), (2, 2), (1, 3), (2, 3)} 
trên tập A = {1, 2, 3, 4} có tính bắc cầu. 
Quan hệ  và “|”trên Z có tính bắc cầu 
( a  b )  ( b  c )  ( a  c ) 
( a | b )  ( b | c )  ( a | c ) 
29 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
1.3 Quan hệ hai ngôi 
a  b 
a  c 
 a  e 
Phản xạ 
a b 
c d e 
f 
Bắc cầu 
Phản đối xứng 
Đối xứng 
Tính chất của Quan hệ hai ngôi 
Ví dụ 1.12: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
1.3 Quan hệ hai ngôi 
8- Quan hệ tương đương 
Phản xạ 
Bắc cầu 
Phản đối xứng –xx-- 
Đối xứng 
Tính chất của Quan hệ tương đương 
Ví dụ 1.13: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Ví dụ. 
Cho S = {sinh viên của lớp}, gọi 
 R = {( a,b ): a có cùng họ với b} 
Hỏi 
Yes 
Yes 
Yes 
Mọi sinh viên 
có cùng họ 
thuộc cùng một nhóm . 
 R phản xạ? 
 R đối xứng? 
 R bắc cầu? 
32 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
8- Quan hệ tương đương 
Định nghĩa. Quan hệ R trên tập A được gọi là tương đương nếu nó có tính chất phản xạ, đối xứng và bắc cầu : 
Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb nếu a và b có cùng độ dài. Khi đó R là quan hệ tương đương. 
Ví dụ. Cho R là quan hệ trên R sao cho aRb nếu a – b nguyên. Khi đó R là quan hệ tương đương 
33 
1.3 Quan hệ hai ngôi 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
1.3 Quan hệ hai ngôi 
9- Quan hệ thứ tự 
Tính chất của Quan hệ thứ tự 
Phản xạ--xx-- 
Bắc cầu 
Đối xứng—xx-- 
Phản xạ 
Phản đối xứng 
Ví dụ 1.14: 
TOÁN ỨNG DỤNG Chương 1: QUAN HỆ - SUY LUẬN TOÁN HỌC 
Quan hệ >= trên tập số thực 
CÁM ƠN CÁC EM 
ĐÃ CHÚ Ý LẮNG NGHE ! 
TRƯỜNG CAO ĐẲNG NGHỀ iSPACE 
137C Nguyễn Chí Thanh, P 9, Q 5, TP. Hồ Chí Minh 
Web: ispace.edu.vn - Tel: 08.6.261.0303 - Fax: 08.6.261.0304 
TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT 
Kết thúc Chương 1: 
QUAN HỆ & SUY LUẬN TOÁN HỌC