Bai giang toan ung dung

GV. Nguyễn Thanh Chuyên Email: [email protected]
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)
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=n2+1; nN và 1A = {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 A1, A2, A3 …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=n2+1; nN và 1 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 ≥N0.
- Quá trình chứng minh quy nạp bao gồm 2 bước:
Bước cơ sở: Chỉ ra P(N0) đú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)= n2 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 chứ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 an
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 = { (a1, b1), (a1, b3), (a3, b3) }
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)}
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ệ:

R1 = {(1,1), (1,2), (2,1), (2, 2), (3, 4), (4, 1), (4, 4)} không phản xạ vì (3, 3)  R1

R2 = {(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)  R2
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ệ R1 = {(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
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