Bài giảng Toán rời rạc: Chương 1

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ

Chương I

KHÁI NIỆM VỀ TẬP HỢP

1.1. Định nghĩa: 1.1. Định nghĩa:

Một tập hợp là một bộ sưu tập các vật mà ta còn

gọi là các phần tử của tập hợp đó.

PHƯƠNG PHÁP PHƯƠNG PHÁP ĐẾM

25/03/2010

3

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

KHÁI NIỆM VỀ TẬP HỢP KHÁI NIỆM VỀ TẬP HỢP

1.2. Ký hiệu: Ta dùng – các chữ in: A, B, C, ..., X, Y, Z, ... để chỉ các tập hợp.

– các chữ nhỏ: a, b, c, ..., x, y, z, ... để chỉ các phần tử.

ể ầ 1.3. Biểu diễn một tập hợp: 1)Liệt kê: Các phần tử của tập hợp sẽ được liệt kê đúng một lần giữa hai dấu { }; giữa hai phần tử khác nhau sẽ có dấu ngăn cách (thường là dấu phẩy , hay chấm phẩy ;) nhưng thứ tự giữa các phần tử này là không quan trọng. Ví dụ: A = {1, 2, 3, 4},

– ký hiệu x ∈ A để chỉ x là một phần tử của tập hợp A. Ký hiệu x ∉ A để chỉ x không phải là một phần tử của tập hợp A.

N = {0, 1, 2, 3, ...}, Z = {0, ±1, ±2, ...}, ...

25/03/2010

4

5

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

KHÁI NIỆM VỀ TẬP HỢP KHÁI NIỆM VỀ TẬP HỢP

A = {x | p(x)} hay A = {x ∈ B | p(x)}.

1.3. Biểu diễn một tập hợp: 2) Nêu tính chất đặc trưng: Tập hợp sẽ được mô tả như là một bộ sưu tập gồm tất cả các phần tử x thỏa mãn tính chất đặc trưng p(x) nào đó dưới dạng:

1.4. Tập hợp rỗng: Tập hợp rỗng, ký hiệu bởi ∅, là tập hợp không chứa phần tử nào. Ví dụ: Các tập hợp

Ví dụ: Ví dụ: 1) Tập hợp A = {x ∈ R | x2 – 4x + 3 = 0} chính là tập hợp A = {1, 3}. 2) Tập hợp các số hữu tỉ được mô tả như sau:

A = {x ∈ R | x2 – 4x + 5 = 0}

và B = {x ∈ Z | 2x – 1 = 0} đều là các tập hợp rỗng.

Q = { Z, n ≠ 0}

25/03/2010

6

7

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

KHÁI NIỆM VỀ TẬP HỢP KHÁI NIỆM VỀ TẬP HỢP

A = B

⇔ (A ⊂ B) và (B ⊂ A) ⇔ (∀x ∈ A, x ∈ B) và (∀x ∈ B, x ∈ A).

1.5. Tập hợp con và tập hợp bằng nhau: 2) A bằng B, ký hiệu A = B, nếu A là tập hợp con của B và ngược lại. Như vậy, theo định nghĩa, ta có:

A ⊂ B ⇔ ∀x ∈ A, x ∈ B. A ⊂ B ⇔ ∀x ∈ A, x ∈ B. Ký hiệu A ⊄ B hay B A để chỉ A không phải là tập con của B.

Ký hiệu A ≠ B để chỉ A không bằng B. Ví d Ví dụ: Xét các tập hợp Xé á ậ h A = {x ∈ R | x2 – 4x + 3 = 0}, B = {x ∈ R | x(x –1)(x – 3) = 0}, C = {0; 1; 2}, D = {0; 1; 2; 3}. Ta thấy A ⊂ B, B ≠ C, C ⊂ D, nhưng B ⊄ A, D ⊄ C.

1.5. Tập hợp con và tập hợp bằng nhau: Cho hai tập hợp A và B. Ta nói: 1) A là tập hợp con của B, ký hiệu A ⊂ B hay B ⊃ A nếu mọi phần tử của A đều là các phần tử của B. Như vậy, theo định nghĩa, ta có:

25/03/2010

9

8

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

KHÁI NIỆM VỀ TẬP HỢP KHÁI NIỆM VỀ TẬP HỢP

1.6. Tập hợp các tập hợp con: Cho tập hợp X. Tập hợp tất cả các tập hợp con của X được ký hiệu là P(X). Như vậy:

P(X) = {A | A ⊂ B}

1.7. Số phần tử của tập hợp hữu hạn: Cho A là tập hợp hữu hạn. Số phần tử của tập A ký hiệu là |A|. Ta có: 1) |A∪B| = |A|+ |B| - |A∩B| . 2) |A×B| = |A| |B| 3) |P (A)| = 2 |A|, P(A) là tập các tập con của A. Ví dụ: Cho X = {a, b, c}. Ta có: P(X) = {∅; {a}; {b}; {c}; {a, b}; {b, c}; {a, c}; {a, b, c}}.

25/03/2010

10

11

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

CÁC PHÉP TOÁN TẬP HỢP CÁC PHÉP TOÁN TẬP HỢP

A ∪ B = {x ∈ X | x ∈ A hay x ∈ B}.

Nói cách khác Nói cách khác

1.9. Phép hợp: Phần hợp của A và B, ký hiệu bởi A ∪ B, là tập hợp tất cả các phần tử (của X) thuộc A hay thuộc B. Như vậy, theo định nghĩa, ta có:

Cho A và B là hai tập hợp con của tập hợp X. 1.8 Phép giao: Phần giao của A và B, ký hiệu bởi A ∩ B, là tập hợp tất cả các phần tử của X vừa thuộc A vừa thuộc B. Như vậy, theo định nghĩa, ta có: {x ∈ X | x ∈ A và x ∈ B}. A ∩ B = {x ∈ X | x ∈ A và x ∈ B}. A ∩ B

Nói cách khác

∀x ∈ X, x ∈ A ∪ B ⇔ x ∈ A hay x ∈ B.

Suy ra

∀x ∈ X, x ∈ A ∩ B ⇔ x ∈ A và x ∈ B.

Suy ra

∀x ∈ X, x ∉ A ∪ B ⇔ x ∉ A và x ∉ B.

∀x ∈ X, x ∉ A ∩ B ⇔ x ∉ A hay x ∉ B.

25/03/2010

12

13

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

CÁC PHÉP TOÁN TẬP HỢP CÁC PHÉP TOÁN TẬP HỢP

A \ B = {x ∈ X | x ∈ A và x ∉ B}.

= X\A = {x ∈ X | x ∉ A}.

Nói cách khác Nói cách khác

A Nói cách khác Nói cách khác

∀x ∈ X, x ∈ A \ B ⇔ x ∈ A và x ∉ B.

∀x ∈ X, x ∈ ⇔ x ∉ A.

Suy ra

∀x ∈ X, x ∉ A \ B ⇔ x ∉ A hay x ∈ B.

∀x ∈ X, x ∉ ⇔ x ∈ A.

1.10. Phép hiệu: Phần hiệu của A và B, ký hiệu bởi A \ B, là tập hợp tất cả các phần tử (của X) thuộc A nhưng không thuộc B. Như vậy, theo định nghĩa, ta có: 1.11. Phép bù: Với A là một tập con của X, phần bù của A trong X, ký hiệu bởi hay CX(A), là tập hợp X\A. Như vậy, theo định nghĩa, ta có:

25/03/2010

14

15

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

CÁC PHÉP TOÁN TẬP HỢP CÁC PHÉP TOÁN TẬP HỢP

Ví dụ: Xét các tập hợp

X = {0; 1; 2; 3; 4; 5; 6}; A = {0; 1; 2; 3}; B = {1; 2; 4; 5}.

A ∩ A = A và A ∪ A = A

2) Tính giao hoán:

A ∩ B = B ∩ A và A ∪ B = B ∪ A.

3) Tính kết hợp:

Ta có: A ∩ B = {1 2}; A ∩ B = {1, 2}; A ∪ B = {0; 1; 2; 3; 4; 5}; A \ B = {0; 3}; B \ A = {4; 5}; CX(A) = {4; 5; 6}; CX(B) = {0; 3; 6}.

(A ∩ B) ∩ C = A ∩ (B ∩ C) và (A ∪ B) ∪ C = A ∪ (B ∪ C)

1.12. Định lý (tính chất của các phép toán): Cho A, B, C là các tập hợp con của tập hợp X. Khi đó ta có: 1) Tính lũy đẳng:

25/03/2010

16

17

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

CÁC PHÉP TOÁN TẬP HỢP CÁC PHÉP TOÁN TẬP HỢP

1.12. Định lý (tính chất của các phép toán): 4) Tính phân phối:

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) và A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

{

}

x = ∀ ∈

A i

I x A , ∈ i

i I ∈

A A

B B

A A

& &

A A

B B

A A

B B

5) Công thức De Morgan: B B = =

∩ ∩

∪ ∪

= =

∩ ∩

{

x i

}

∃ ∈

A i

I x A , ∈ i

6) Các công thức

i I ∈

A B \

∩

1.13. Mở rộng: Cho {Ai}i∈I là một họ các tập hợp. Ta định nghĩa phần giao và phần hợp của họ {Ai}i∈I như sau:

25/03/2010

18

19

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

CÁC PHÉP TOÁN TẬP HỢP TÍCH DESCARTRES

A i

i I ∈

1.13. Mở rộng: Khi đó ta có công thức De Morgan suy rộng như sau:

A × B = {(x, y) | x ∈ A và y ∈ B}.

A A i

Nói cách khác

i I ∈

(x, y) ∈ A × B ⇔ x ∈ A và y ∈ B.

Suy ra

(x, y) ∉ A × B ⇔ x ∉ A hay y ∉ B.

1.14. Định nghĩa: Cho hai tập hợp A và B. Tích Descartes của A và B, ký hiệu bởi A × B, là tập hợp tất cả các cặp (x, y) có thứ tự x trước, y sau, trong đó x thuộc A và y thuộc B. Như vậy, theo định nghĩa, ta có:

25/03/2010

20

21

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

là một dãy gồm n tập hợp. Ta định nghĩa tích

như sau:

n { } 1 A i i =

TÍCH DESCARTRES TÍCH DESCARTRES

(x, y) = (x', y') ⇔ x = x' và y = y'. (x, y) ≠ (x', y') ⇔ x ≠ x' hay y ≠ y'.

A i

n ∏ 1 i =

A à

{(

Ký hiệu A2 để chỉ tích Descartes A × A. Tức là: ) |

A2 = {(x, y) | x ∈ A và y ∈ A} A2 A}

1.14. Định nghĩa: Ta có: Do đó:

An = {(x1, x2, ..., xn) | ∀1 ≤ i ≤ n, xi ∈ A}

1.15. Tích Descartes của n tập hợp: n { } 1 Cho A i i = Descartres của A1 × A2 × ... × An = {(x1, x2, ..., xn) | ∀1 ≤ i ≤ n, xi ∈ Ai} n { } 1 bởi Ta còn ký hiệu tích Descartes của bởi A i i = Ký hiệu An để chỉ tích Descartes A × A × Ký hiệu A để chỉ tích Descartes A × A × ... × A (n lần). × A (n lần) Tức là:

25/03/2010

22

23

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

là một họ các tập hợp. Ta định nghĩa tích

TÍCH DESCARTRES VỊ TỪ VÀ LƯỢNG TỪ

như sau:

n { } 1 A i i =

)

i ∀ ∈

∈

A i

x i

I x , i

A i

i I ∈

{ (

}

∏ i I ∈

1.16. Mở rộng: n { } 1 Cho A i i = Descartes của họ

1.17. Định nghĩa: Cho A là một tập hợp khác rỗng. Giả sử, ứng với mỗi x = a ∈ A ta có một mệnh đề p(a). Khi đó, ta nói p = p(x) là một vị từ theo một biến (xác định trên A). Tổng quát, cho A1, A2, A3…là n tập hợp khác rỗng. Giả sử rằng ứng với mỗi (x1,x2,...,xn) = (a1,a2,...,an) n ∈A1×A2× ... ×An, ta có một mệnh đề p(a1,a2,.,an). Khi đó ta nói p = p(x1,x2,.,xn) là một vị từ theo n biến (xác định trên A1×A2× ... ×An)

25/03/2010

24

25

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

VỊ TỪ VÀ LƯỢNG TỪ VỊ TỪ VÀ LƯỢNG TỪ

1.18. Định nghĩa: Cho trước các vị từ p(x), q(x) theo một biến x ∈ A. Khi ấy, i. Phủ định của vị từ p(x) ký hiệu là ¬p(x) là vị từ mà khi thay x bởi 1 phần tử cố định của A thì ta được mệnh đề ¬(p(a)).

Ví dụ 1: Xét p(n) = “n > 2” là một vị từ một biến xác định trên tập các số tự nhiên N. Ta thấy với n = 3, 4 ta được các mệnh đề đúng p(3), p(4), còn với n = 0, 1 ta được mệnh đề sai p(0), p(1). Ví dụ 2:ụ Xét p(x,y) = “x2 + y = 1” là một vị từ theo hai biến xác định trên R2, ta thấy p(0,1) là một mệnh đề đúng, trong khi p(1,1) là một mệnh đề sai.

ii. Phép nối liền (tương ứng nối rời, kéo theo…) của p(x) và q(x) được ký hiệu bởi p(x)∧q(x) (tương ứng là p(x)∨q(x), p(x)→q(x)) là vị từ theo biến x mà khi thay x bởi phần tử cố định a ∈ A ta được mệnh đề p(a)∧q(a) ( tương ứng là p(a) ∨q(a), p(a)→q(a)).

25/03/2010

26

27

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

VỊ TỪ VÀ LƯỢNG TỪ VỊ TỪ VÀ LƯỢNG TỪ

[∀x ∈A,∀y ∈B, p(x, y)] ↔ [∀y ∈B, ∀x ∈A, p(x, y)]

i. Mệnh đề “Với mọi x thuộc A, p(x)”, ký hiệu bởi “∀x ∈ là mệnh đề được định bởi “∀x ∈ A, p(x)” A, p(x)”, đúng khi và chỉ khi p(a) luôn đúng với mọi giá trị a ∈A.

ii. ii

)]

[∃x ∈A, ∃y ∈B, p(x, y)] ↔ [∃y ∈B, ∃x ∈A, p(x, y)] [∃ A ∃ B ( )]

[∃ B ∃ A (

iii. [∃x ∈A, ∀y ∈B, p(x, y)] →[∀y ∈B, ∃x ∈A, p(x, y)]

ii. Mệnh đề “Tồn tại (ít nhất) (hay có (ít nhất)) một x thuộc A, p(x))” ký hiệu bởi “∃x ∈A, p(x)”, là mệnh đề được định bởi “∃x ∈A, p(x)” đúng khi và chỉ khi có ít nhất một giá trị x = a0 nào đó sao cho mệnh đề p(a0) đúng.

1.19. Định nghĩa: Cho p(x) là một vị từ theo một biến xác định trên A. Ta định nghĩa các mệnh đề lượng từ hóa của p(x) như sau: 1.20. Định lý: Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A×B, các mệnh đề sau là đúng:

25/03/2010

28

29

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

VỊ TỪ VÀ LƯỢNG TỪ VỊ TỪ VÀ LƯỢNG TỪ

ta có:

∀ ∈

⇔ ∃ ∈

( ) x A p x ,

1.22. Định lý: i. Với p(x) là một vị từ theo một biến xác định trên A,

∃ ∈

⇔ ∀ ∈

( ) x A p x ,

i. Mệnh đề mới vẫn còn tương đương logic với mệnh

ạ

ợ g đề cũ nếu hai lượng từ này cùng loại.

, . .. ,

(

)

( ) x A p x , ii Phủ định của mệnh đề lượng từ hóa từ vị từ p(x x ii. Phủ định của mệnh đề lượng từ hóa từ vị từ p(x1, x2, ..., xn) có được bằng cách thay lượng từ ∀ bằng lượng từ ∃ và ngược lại, và thay vị từ p(x1, x2, ..., xn) bằng vị từ x

ii. Mệnh đề mới này sẽ là một hệ quả logic của mệnh đề cũ nếu hai lượng từ trước khi hoán vị có dạng ∃ ∀

1.21. Định lý: Trong một mệnh đề lượng từ hoá từ một vị từ theo nhiều biến độc lập, nếu ta hoán vị hai lượng từ đứng cạnh nhau thì:

25/03/2010

30

31

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

VỊ TỪ VÀ LƯỢNG TỪ VỊ TỪ VÀ LƯỢNG TỪ

Nếu một mệnh đề đúng có dạng lượng từ hóa trong đó

Nếu trong một mệnh đề lượng từ hóa, khi thay một biến

một biến x ∈ A bị buộc bởi lượng từ phổ dụng ∀, khi ấy

buộc bởi lượng từ ∀ bằng một phần tử cố định nhưng

tùy ý của tập hợp tương ứng mà mệnh đề nhận được có tùy ý của tập hợp tương ứng mà mệnh đề nhận được có

nếu thay thế x bởi a ∈ A ta sẽ được một mệnh đề đúng. nếu thay thế x bởi a ∈ A ta sẽ được một mệnh đề đúng

chân trị 1 thì bản thân mệnh đề lượng từ hoá ban đầu

cũng có chân trị 1.

1.23. Quy tắc đặc biệt hóa phổ dụng: 1.24. Quy tắc tổng quát hóa phổ dụng:

25/03/2010

32

33

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ

f(A) = {y ∈ Y | ∃x ∈ A, y = f(x)}

1.27. Ảnh và ảnh ngược: Cho ánh xạ f từ X vào Y và A ⊂ X, B ⊂ Y. Ta định nghĩa: 1) Ảnh của A qua f là tập hợp:

Ta cũng viết:

f : X → Y

{f(x) | x ∈ A} f(A) = {f(x) | x ∈ A} f(A)

x f(x)

Như vậy theo định nghĩa, ta có:

1.25. Định nghĩa: Cho hai tập hợp X, Y ≠ ∅. Một ánh xạ f từ X vào Y là quy tắc cho ứng với mỗi phần tử x của X một phần tử duy nhất y của Y mà ta ký hiệu là f(x) và gọi là ảnh của x qua ánh xạ f. Ta viết:

∀y ∈ Y, y ∈ f(A) ⇔ ∃x ∈ A, y = f(x); ∀y ∈ Y, y ∉ f(A) ⇔ ∀x ∈ A, y ≠ f(x).

∀x ∈ X, f(x) = g(x)

1.26. Định nghĩa: Hai ánh xạ f và g từ X vào Y được gọi là bằng nhau nếu:

25/03/2010

34

35

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ

f–1(B) = {x ∈ X | f(x) ∈ B}

Như vậy theo định nghĩa, ta có:

∀x ∈ X, x ∈ f–1(B) ⇔ f(x) ∈ B; ∀x ∈ X, x ∉ f–1(B) ⇔ f(x) ∉ B. (B) ⇔ f(x) ∉ B. ∀x ∈ X, x ∉ f

ấ

1.27. Ảnh và ảnh ngược: 2) Ảnh ngược hay tạo ảnh của B bởi f là tập hợp:

1.27. Ảnh và ảnh ngược: Chú ý: 1) Ta thường dùng ký hiệu Imf để chỉ tập hợp f(X) và còn gọi là ảnh của f. 2) Với y ∈ B ta dùng ký hiệu f–1(y) thay cho f–1({y}). Đó chính là tập hợp các phần tử x ∈ X thỏa f(x) = y (ta thường gọi đây là tập hợp tất cả các nghiệm x trong X của phương trình f(x) = y). Lưu ý rằng tập hợp f–1(y) có thể rỗng hay khác rỗng (gồm một hay nhiều phần tử).

25/03/2010

36

37

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

Xét ánh xạ f : X → Y.

ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ PHÂN LOẠI ÁNH XẠ

∀x, x' ∈ X, x ≠ x' ⇒ f(x) ≠ f(x')

Những tính chất sau được suy trực tiếp từ định nghĩa.

1. 2. 3. 4. 5. 6.

f(A1 ∪ A2) = f(A1) ∪ f(A2); f(A1 ∩ A2) ⊂ f(A1) ∩ f(A2); f(A1 \ A2) ⊃ f(A1) \ f(A2); f–1(B1 ∪ B2) = f–1(B1) ∪ f–1(B2); f–1(B1 ∩ B2) = f–1(B1) ∩ f–1(B2); f–1(B1 \ B2) = f–1(B1) \ f–1(B2).

f : X → Y là một đơn ánh f : X → Y là một đơn ánh ⇔ (∀x, x' ∈ X, f(x) = f(x') ⇒ x = x'). ⇔ (∀y ∈ Y, f–1(y) có nhiều nhất một phần tử). ⇔ (∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) có nhiều nhất một nghiệm x ∈ X.

1.29. Đơn ánh: 1 29 Đơn ánh: Ta nói f : X → Y là một đơn ánh nếu hai phần tử khác nhau bất kỳ của X đều có ảnh khác nhau, nghĩa là: 1.28 Định lý: Giả sử f là một ánh xạ từ X vào Y. Với A1 và A2 là hai tập hợp con tùy ý của X, B1 và B2 là hai tập con tùy ý của Y. Ta có:

25/03/2010

38

39

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

Xét ánh xạ f : X → Y.

PHÂN LOẠI ÁNH XẠ PHÂN LOẠI ÁNH XẠ

f : X → Y không là một đơn ánh ⇔ (∃x, x' ∈ X, x ≠ x' và f(x) = f(x')). ⇔ (∃y ∈ Y, phương trình f(x) = y (y được xem như tham số) có ít nhất hai nghiệm x ∈ X.

f : X → Y là một toàn ánh ⇔ (∀y ∈ Y, ∃x ∈ X, y = f(x)) ⇔ (∀y ∈ Y, f–1(y) ≠ ∅); ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) có nghiệm x ∈ X.

1.29. Đơn ánh: á h 1 29 Suy ra: 1.30. Toàn ánh: à á h 1 30 Ta nói f : X → Y là một toàn ánh nếu Imf = Y. Những tính chất sau được suy trực tiếp từ định nghĩa.

25/03/2010

40

41

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

Xét ánh xạ f : X → Y.

PHÂN LOẠI ÁNH XẠ PHÂN LOẠI ÁNH XẠ

f : X → Y không là một toàn ánh

1.30. Toàn ánh: à á h 1 30 Suy ra:

Xét ánh xạ f : X → Y. 1.31. Song ánh và ánh xạ ngược: á h à á h 1 31 S Ta nói f : X → Y là một song ánh hay là một tương ứng 1-1 nếu f vừa là đơn ánh vừa là toàn ánh. Những tính chất sau được suy trực tiếp từ định nghĩa.

f : X → Y là một song ánh

⇔ (∃y ∈ Y, ∀x ∈ X, y ≠ f(x)); ⇔ (∃y ∈ Y, f–1(y) = ∅); ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) vô nghiệm trong X.

⇔ (∀y ∈ Y, ∃!x ∈ X, y = f(x)); ⇔ (∀y ∈ Y, f–1(y) có đúng một phần tử); ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) có duy nhất một nghiệm x ∈ X.

25/03/2010

42

43

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

PHÂN LOẠI ÁNH XẠ PHÂN LOẠI ÁNH XẠ

Xét ánh xạ f : X → Y. 1.31. Song ánh và ánh xạ ngược: á h à á h 1 31 S Suy ra:

f : X → Y không là một song ánh

Xét ánh xạ f : X → Y. 1.31. Song ánh và ánh xạ ngược: á h à á h 1 31 S Xét f : X → Y là một song ánh. Khi đó, theo tính chất trên, với mọi y ∈ Y, tồn tại duy nhất một phần tử x ∈ X thỏa f(x) = y. Do đó tương ứng y x là một ánh xạ từ Y vào X. Ta gọi đây là ánh xạ ngược của f và ký hiệu f–1. Như vậy:

f 1 : Y → X f–1 : Y → X

⇔ f không là một đơn ánh hay không là một toàn ánh; ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) vô nghiệm hoặc có ít nhất hai nghiệm x ∈ X.

f–1(y) = x với f(x) = y.

25/03/2010

44

45

25/03/2010

1. Nhắc lại về tập hợp và ánh xạ 1. Nhắc lại về tập hợp và ánh xạ

TÍCH CÁC ÁNH XẠ TÍCH CÁC ÁNH XẠ

f : X → Y và g : Y' → Z trong đó Y ⊂ Y'. Ánh xạ tích h của f và g là ánh xạ từ X vào Z xác định bởi: h : X → Z

1.32. Định nghĩa: Cho hai ánh xạ

x x h(x) = g(f(x)) h(x) = g(f(x)) Ta viết: h = g o f : X → Y → Z

x f(x) h(x) = g(f(x))

1.33. Định lý: Xét f : X → Y là một song ánh. Khi đó: f o f–1 = IdY f–1 o f = IdX trong đó ký hiệu IdX để chỉ ánh xạ đồng nhất X → X định bởi Id (x) = x ∀x ∈ X; ta gọi Id là ánh xạ đồng định bởi IdX(x) = x, ∀x ∈ X; ta gọi IdX là ánh xạ đồng nhất trên X, tương tự IdY là ánh xạ đồng nhất trên Y.

25/03/2010

46

47

2. Phép đếm 2. Phép đếm

NGUYÊN LÝ CỘNG & NGUYÊN LÝ NHÂN NGUYÊN LÝ CỘNG & NGUYÊN LÝ NHÂN

2.1. Nguyên lý Cộng: Giả sử để một hiện tượng xảy ra, có k trường hợp lớn loại trừ lẫn nhau. Biết rằng ở mỗi trường hợp lớn thứ j lại có nj trường hợp nhỏ. Khi đó, số trường hợp nhỏ nói chung để hiện tượng trên xảy ra là: ra là:

n = n1 + n2 + … + nk.

2.2. Nguyên lý Nhân: Giả sử để hoàn thành một công việc ta phải tiến hành theo trình tự k bước có tác dụng độc lập. Biết rằng: – Có n1 cách thực hiện buớc 1. – Sau khi thực hiện bước 1 xong, dù bằng bất cứ cách nào, luôn luôn có một số lượng không đổi n2 cách để thực hiện bước 2. – ………… – Cuối cùng, sau khi thực hiện xong bước thứ k-1, luôn luôn có một số lượng không đổi nk cách để thực hiện bước thứ k. Khi đó, số cách để hoàn thành công việc đã cho là: n = n1n2… nk.

25/03/2010

48

49

25/03/2010

2. Phép đếm 2. Phép đếm

GIẢI TÍCH TỔ HỢP GIẢI TÍCH TỔ HỢP

2.4. Chỉnh hợp:

Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k

phần tử (1 ≤ k ≤n) sắp thứ tự của tập hợp A được 2.3. Hoán vị: Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử ký hiệu là Pn

gọi là một chỉnh hợp chập k của n phần tử. Số

các chỉnh hợp chập k của n ký hiệu là

Pn = n! Định lý. Số hoán vị của n phần tử, trong đó có n1 phần Định lý. Số hoán vị của n phần tử, trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc loại 2,…, nk phần tử giống nhau thuộc loại k, là:

k n

! k

n −

)

(

n ! !...

n n ! 1

25/03/2010

50

51

2. Phép đếm 2. Phép đếm

GIẢI TÍCH TỔ HỢP GIẢI TÍCH TỔ HỢP

2.5. Tổ hợp:

Cho tập hợp A gồm n phần tử. Mỗi tập con gồm

với mọi 0 ≤ k ≤ n;

k phần tử của A được gọi là một tổ hợp chập k

với mọi 1 ≤ k ≤ n với mọi 1 ≤ k ≤ n

k C n 1 1 C− =

k k C n

k k n 1 +

của n phần tử. Số các tổ hợp chập k của n phần 2.5. Tổ hợp: Nhận xét: Từ kết quả trên ta suy ra số tập con gồm k phần tử của tập hợp gồm n phần tử là Định lý: n k a) − = C n

k n

tử đựơc ký hiệu là

b) b) Công thức nhị thức Newton: Với x, y ∈ R và n là số nguyên dương ta có: x

n k y−

)

(

n n

! −

k C x n

(

)

= ∑

25/03/2010

52

53

25/03/2010

2. Phép đếm 2. Phép đếm

GIẢI TÍCH TỔ HỢP GIẢI TÍCH TỔ HỢP

a2,…, an là một nhóm không thứ tự gồm k phần tử có

(mỗi xi đều nguyên không âm) của phương trình

x1+ x2+…+ xn= k

thể trùng nhau được rút ra từ tập {a1, a2,…, an}. kKGọi nK Gọi

là số tổ hợp lặp chập k của n loại phần tử. Ta có là số tổ hợp lặp chập k của n loại phần tử Ta có

là:là:

công thức:

k n

k n k

C + −

k n

k n k

C + −

2.6. Tổ hợp lặp: Có thể xem một tổ hợp lặp chập k của n loại phần tử a1, 2.6. Tổ hợp lặp: Hệ quả: Số nghiệm nguyên không âm (x1,x2,…,xn)

25/03/2010

54

55

2. Phép đếm 3. Hệ thức đệ quy

2.7. Nguyên lý Dirichlet

Một hệ thức đệ quy tuyến tính cấp k là một hệ thức có dạng: ạ g

⎤ ⎥

(1) xn = a1xn-1 +… + akxn-k + fn

⎤ ⎥

⎡ ⎢

/n ⎡ ⎢ n/k. Hơn nữa, tính chất trên.

trong đó: Giả sử có n vật cần đặt vào k hộp. Khi đó tồn tại vật trở lên, trong đó ít nhất một hộp chứa từ /n ⎤ ⎡ ⎥ ⎢ là số nguyên nhỏ nhất lớn hơn hay bằng là số nguyên lớn nhất thỏa

ự ộ { n}

– ak ≠ 0, a1,…, ak-1 là các hệ số thực – {fn} là một dãy số thực cho trước y – {xn} là dãy ẩn nhận các giá trị thực.

25/03/2010

57 25/03/2010

56

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Nghiệm tổng quát • Mỗi dãy {xn} thỏa (1) được gọi là một nghiệm Trường hợp dãy fn= 0 với mọi n thì (1) trở thành: của (1).

(2) xn = a1xn-1 +… +akxn-k

• Nhận xét rằng mỗi nghiệm {xn} của (1) được hoàn toàn xác định bởi k giá trị ban đầu x0, x1,…, xk-1. ệ q y y ệ Ta nói (2) là một hệ thức đệ quy tuyến tính ộ ( ) thuần nhất cấp k.

• Họ dãy số {xn = xn(C1, C2,…,Ck)} phụ thuộc • Họ dãy số {x = x (C C C )} phụ thuộc vào k họ tham số C1, C2,…, Ck được gọi là nghiệm tổng quát của (1) nếu mọi dãy của họ này đều là nghiệm của (1).

25/03/2010

58

59

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Mục đích giải hệ thức đệ quy • Giải một hệ thức đệ quy là đi tìm nghiệm tổng ồ quát của nó.

Nghiệm riêng • Cho {xn} là nghiệm tổng quát của (1) và với mọi k giá trị ban đầu y0, y1,…, yk-1, tồn tại ầ duy nhất các giá trị của k tham số C1, C2,…,Ck sao cho nghiệm {xn} tương ứng thỏa:

( ) (*) x0 y0, x1 y1,…, xk-1 x0 = y0 x1 = y1 yk-1 xk 1 = yk 1 • Nếu hệ thức đệ quy có kèm theo điều kiện ban đầu, ta phải tìm nghiệm riêng thỏa điều kiện ban đầu đó. kiện ban đầu đó

• Khi đó, nghiệm {xn} tương ứng được gọi nghiệm riêng ứng với điều kiện ban đầu (*).

25/03/2010

60

61

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Với n = 1, ta có x1 = 1.

Với n = 2, ta có x2 = 2 Ví dụ: Một cầu thang có n bậc. Mỗi bước đi gồm 1 Một cầu thang có n bậc. Mỗi bước đi gồm 1 hoặc 2 bậc. Gọi xn là số cách đi hết cầu thang. Tìm một hệ thức đệ quy cho xn.

Với n > 2, để khảo sát xn ta chia thành hai trường hợp loại trừ lẫn nhau: Trường hợp 1: Bước đầu tiên gồm 1 bậc Trường hợp 1: Bước đầu tiên gồm 1 bậc. Khi đó, cầu thang còn n-1 bậc nên số cách đi hết cầu thang trong trường hợp này là xn-1.

25/03/2010

62

63

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Vậy ta có hệ thức đệ quy tuyến tính thuần nhất cấp 2: p

x n − 2.

x n x 1

x 1 n − 21, x

⎧ ⎨ ⎩

Trường hợp 2: Bước đầu tiên gồm 2 bậc. Khi đó, cầu thang còn n 2 bậc nên số cách đi Khi đó, cầu thang còn n-2 bậc nên số cách đi hết cầu thang trong trường hợp này là xn-2. Theo nguyên lý cộng, số cách đi hết cầu thang là xn-1 + xn-2 . Do đó ta có:

xn = xn-1 + xn-2

25/03/2010

64

65

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hanoi Tower 264= 18446744073709551615 (500 billion years)

y ọ g ặ

Bài toán Tháp Hà Nội Có 3 cọc A, B, C và n đĩa (có lỗ để đặt vào cọc) với đường kính đôi một khác nhau. Nguyên tắc ắ đặt đĩa vào cọc là: mỗi đĩa chỉ được chồng lên đĩa lớn hơn nó. Ban đầu, cả n đĩa được đặt chồng lên nhau ở cọc A, hai cọc B và C để trống. Vấn đề đặt ra là chuyển cả n đĩa ở cọc A sang cọc C (có thể qua trung gian cọc B), mỗi lần chỉ chuyển một đĩa. Gọi xn là số lần chuyển đĩa. Tìm một hệ thức đệ quy cho xn.

25/03/2010

66

67

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Với n = 1 ta có x1 = 1.

Như vậy số lần chuyển toàn bộ n đĩa từ A sang C là: C là:

xn-1+ 1 + xn-1 = 2xn-1 + 1. Nghĩa là xn = 2xn-1 + 1, ta có hệ thức đệ quy tuyến tính không thuần nhất cấp 1:

1 −

x = ⎧ ⎨ x =⎩ 1

C C ối ù h ể A

Với n >1, trước hết ta chuyển n-1 đĩa bên trên sang cọc B qua trung gian cọc C (giữ nguyên đĩa thứ n dưới cùng ở cọc A). Số lần chuyển n- 1 đĩa đó là xn-1. Sau đó ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng ta chuyển n-1 đĩa 1 đĩ từ cọc B sang cọc C. Số lần chuyển n-1 đĩa đó lại là xn-1.

25/03/2010

68

69

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất

Trường hợp k = 1

Xét hệ thức đệ quy tuyến tính thuần nhất (2) xn = a1xn-1 +… + akxn-k Phương trình đặc trưng (*) trở thành

λ - a1 = 0

n Cλ= 0

Phương trình đặc trưng của (2) là phương trình bậc k định bởi: nên có nghiệm là λ0 = a1 Khi đó, (2) có nghiệm tổng quát là: ( ) (*) λk - a1λk-1 - λ a1λ … ak 0 - ak = 0

25/03/2010

70

71

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất

−

Ví dụ: Hệ thức đệ quy

1 −

2 x ⎧ ⎨ x =⎩ 1

Phương trình đặc trưng: 2λ - 3 = 0 có nghiệm Phương trình đặc trưng: 2λ 3 = 0 có nghiệm là λ0 = 3/2

n n

Do đó nghiệm tổng quát là:

⎛ ⎛ C = ⎜ ⎝

⎞3 ⎞ ⎟ 2 ⎠

là một hệ thức đệ quy tuyến tính thuần nhất cấp 1

25/03/2010

72

73

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính thuần nhất

Hệ thức đệ quy tuyến tính thuần nhất Trường hợp k = 2: ệ , Từ điều kiện ban đầu x1 = 1, ta có : Phương trình đặc trưng (*) trở thành: (*) λ2 - a1λ - a2 = 0

C =

Suy ra:

3 C ∗ = 2 2 3 Do đó nghiệm của hệ thức đệ quy đã cho là:

n Bλ λ A + 2

n 1

1 −

3 2

⎛ = ⎜ ⎝

⎞ ⎟ ⎠

a) Nếu (*) có hai nghiệm thực phân biệt λ1 và λ2 thì (2) có nghiệm tổng quát là :

25/03/2010

74

75

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất

c) Nếu (*) có hai nghiệm phức liên hợp được viết dưới dạng lượng giác : ế

(cos

sin ) ϕ

b) Nếu (*) có nghiệm kép thực λ0 thì (2) có nghiệm tổng quát là:

(

) n A nB λ 0

n r A

( cos

sin

n ϕ

n ) ϕ

thì (2) có nghiệm tổng quát là:

25/03/2010

76

77

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất

Giải các hệ thức đệ quy sau:

( ) 0 1

1 −

−

1 −

−

Ví dụ 1: x 2 − Ví dụ 1

1 −

Phương trình đặc trưng của (1) là:

4. 4

n = =

x x 0

12 − 1 n + x x 12; 2; = =

⎧ ⎨ ⎩ ⎩

(*) 2λ2 - 3λ + 1 = 0 Ví dụ 2

−

có hai nghiệm thực là λ1 = 1 và λ2 = 1/2. Do đó nghiệm tổng quát của (1) là:

x =

2 + =

1 + =

x 1

⎧ ⎨ ⎩

1 2

⎛ ⎜ ⎝

⎞ ⎟ ⎠

Ví dụ 3

25/03/2010

78

79

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính thuần nhất Hệ thức đệ quy tuyến tính thuần nhất

−

1 −

( ) 2

1 n + 2; =

n =

x 1

Từ điều kiện ban đầu x0 = 2; x1 = 4 ta suy ra:

(

)

A B +

Ví dụ 2: 4 ⎧ ⎨ ⎩

B =

A =⎧ ⎪ ⎨ 3 ⎪⎩ 2 Suy ra A = 2 và

Phương trình đặc trưng của (2) là:

3 2 2

4λ2 - 12λ + 9 = 0

−

Vậy nghiệm của (2) là:

)

(

n B

)

x =

3 2

⎛ ⎜ ⎝

⎞ ⎟ ⎠

3 2

⎛ ⎜ ⎝

⎞ ⎟ ⎠

có nghiệm thực kép là λ0 = 3/2. Do đó nghiệm tổng quát của (2) là:

25/03/2010

80

81

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính thuần nhất

−

sin

cos

n 2 (

x n

C 1

( ) 3

n π ) 3

2 + =

1 + =

x 1

Hệ thức đệ quy tuyến tính thuần nhất Do đó nghiệm tổng quát của (3) là

Ví dụ 3: ⎧ ⎧ ⎨ ⎩ Phương trình đặc trưng của (3) là:

2( 2(

C C

4 4

) )

+ +

= =

C C 1

(*) λ2 - 2λ + 4 = 0

C 1

C= 21,

1 λ= ±

)

C 1

1 2

2 (cos

3 sin

n π 3 Từ điều kiện ban đầu x1 = 4; x2 = 4 ta suy ra: ⎧ 3 1 ⎪⎪ ⎪⎪ 2 2 ⎨ 3 ⎪ − 4( ⎪⎩ 2 Vậy nghiệm của (3) là : x n

2(cos

λ=

n π 3

n π ) 3

Suy ra: có hai nghiệm phức liên hợp là

25/03/2010

83

82

π sin ) 3

Ta viết hai nghiệm trên dưới dạng lượng giác: π 3

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất

Xét hệ thức đệ quy tuyến tính không thuần nhất

(1) xn = a1xn-1 +… + akxn-k + fn

Nghiệm tổng quát của (1) =

Hệ thức đệ quy tuyến tính thuần nhất tương ứng là:

+ (2) (2) Nghiệm tổng quát ổ của (2) + Một nghiệm riêng của (1) của (1) xn x = a x a1xn-1 +… + akxn-k + akx k

Phương trình đặc trưng của (2) là:

(*) λk - a1λk-1 -… - ak = 0

25/03/2010

84

85

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất

Dạng 1: f = βnP (n) Dạng 1: fn βPr(n) Cách tìm một nghiệm riêng của (1) khi vế phải fn của (1) có dạng đặc biệt như sau: Khi đó ta xét λ0 = β. Có 3 trường hợp nhỏ:

Dạng 1: fn = βnPr(n), trong đó Pr(n) là một đa thức bậc r theo n; βlà một hằng số

Trường hợp 1: β không là nghiệm của phương trình đặc trưng

ầ

Dạng 2: fn = Pm(n)cosnϕ + Ql(n)sinnϕ, trong đó Pm(n), Ql(n) lần lượt là các đa thức bậc m, l theo n; ϕlà hằng số (ϕ≠kπ).

Trường hợp 2: β là nghiệm đơn của phương trình đặc trưng

fn = fn1 + fn2 +…+ fns, trong đó các fn1,

Dạng 3: fn2,…, fns thuộc 2 dạng đã xét ở trên.

Trường hợp 3: β là nghiệm kép của phương trình đặc trưng

25/03/2010

86

87

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất

Dạng 1: f = βnP (n) Dạng 1: fn βPr(n) Trường hợp 2

Dạng 1: f = βnP (n) Dạng 1: fn βPr(n) Trường hợp 1 Nếu λ0 = β không là nghiệm của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: ạ g Nếu λ0 = β là nghiệm đơn của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: dạng:

xn = βnQr(n)

xn = nβnQr(n)

25/03/2010

88

89

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất

Qr(n) = Arnr + Ar-1nr-1 +…+ A0 là đa thức tổng quát có cùng bậc r với Pr(n), trong đó Ar, Ar-1,…, A0 là r+1 hệ số cần xác định.

n 1

ý Chú ý:

Dạng 1: f = βnP (n) Dạng 1: fn βPr(n) Trường hợp 3 Nếu λ0 = β là nghiệm kép của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: ạ g

xn = n2βnQr(n)

Để xác định các hệ số trên ta cần thế xn, xn-1,…, xn-k n k vào (1) và cho n nhận r + 1 giá trị nguyên nào đó hoặc đồng nhất các hệ số tương ứng ở hai vế để được một hệ phương trình. Các hệ số trên là nghiệm của hệ phương trình này

25/03/2010

90

91

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất

Dạng 2: fn Pm(n)cosnϕ+ Ql(n)sinnϕ Dạng 2: f = P (n)cosnϕ+ Ql(n)sinnϕ Dạng 2: fn Pm(n)cosnϕ+ Ql(n)sinnϕ Dạng 2: f = P (n)cosnϕ+ Ql(n)sinnϕ

Khi đó ta xét λ0 = cosϕ ± isinϕ. Có 2 trường hợp nhỏ:

Trường hợp 1: λ0 = cosϕ ± isinϕ không là nghiệm của phương trình đặc trưng.

Trường hợp 1 Nếu λ0 = cosϕ ± isinϕ không là nghiệm của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: nghiệm riêng dạng:

xn = Rk(n)cosnϕ + Sk(n)sinnϕ

Trường hợp 2: λ0 = cosϕ ± isinϕ là nghiệm của phương trình đặc trưng.

25/03/2010

92

93

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất

Chú ý: ý Dạng 2: fn Pm(n)cosnϕ+ Ql(n)sinnϕ Dạng 2: f = P (n)cosnϕ+ Ql(n)sinnϕ

Rk(n), Sk(n) là các đa thức tổng quát theo n có bậc k = max{m,l} với 2k+2 hệ số cần xác định:

Rk(n) = Aknk + Ak-1nk-1 +…+ A0 Trường hợp 2 Nếu λ0 = cosϕ ± isinϕ là nghiệm của phương trình đặc trưng (*) thì (1) có một nghiệm riêng dạng: dạng:

Sk(n) = Bknk + Bk-1nk-1 +…+ B0

xn = n(Rk(n)cosnϕ + Sk(n)sinnϕ)

25/03/2010

94

95

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính không thuần nhất

2 2

3 3

x x

4 4

n n

1 1

−

+ +

(2) (2)

x x n

1 −

−

Hệ thức đệ quy tuyến tính không thuần nhất Ví dụ Dạng 3: fn Dạng 3: f = f 1 + f 2 + + f fn1 + fn2 +…+ fns

−

Hệ thức đệ quy tuyến tính thuần nhất là:

1 −

−

Bằng cách như trên ta tìm được nghiệm riêng xni (1≤ i ≤ s) của hệ thức đệ quy:

Phương trình đặc trưng của (2) là: Phương trình đặc trưng của (2) là: fni a0xn + a1xn 1 +… + akxn k = fni a0xn a1xn-1 … akxn-k

(*)

Khi đó xn = xn1 + xn2+…+ xns là một nghiệm riêng của (1). 2λ2 - 3λ + 1 = 0 có hai nghiệm thực là λ1 = 1 và λ2 = 1/2

25/03/2010

96

97

25/03/2010

3. Hệ thức đệ quy 3. Hệ thức đệ quy

Hệ thức đệ quy tuyến tính không thuần nhất Hệ thức đệ quy tuyến tính không thuần nhất

nx C C

2n(an+b) -3(n-1)[a(n-1)+b] + (n-2)[a(n-2) + b] = 4n + 1

1 1 2

⎛ ⎛ ⎜ ⎝

⎞ ⎞ ⎟ ⎠

Do đó nghiệm tổng quát của (2) là: Thế (4) vào (1) ta được: ( ) ( ) ợ

Bây giờ ta tìm một nghiệm riêng của (1).

1; a b + = a b 3 + =

⎧ ⎨ ⎩

Cho n lần lượt nhận hai giá trị n = 0; n = 1 ta được hệ: ệ ợ 1 h

Vế phải của (1) là fn = 4n+1 có dạng Pr(n) là đ hứ bậ đa thức bậc r = 1 theo n. Vì λ0 = 1 là nghiệm đơn của phương trình đặc trưng (*) nên (1) có một nghiệm riêng dạng:

(4) xn = n(an + b)

25/03/2010

98

99

3. Hệ thức đệ quy 4. Nguyên lý bù trừ

Hệ thức đệ quy tuyến tính không thuần nhất

2; b Trong một số bài toán đếm phức tạp hơn, nếu không có giả thiết gì về sự rời nhau giữa hai tập A và B thì |A(cid:1515)B| = |A| + |B| – |A∩B|. 1. Thế vào (4) ta Giải hệ trên ta được a = 2; b = -1 Thế vào (4) ta Giải hệ trên ta được a tìm được một nghiệm riêng của (1) là:

(5) xn = n(2n – 1)

A A∩B A A∩B

B B

n n (2

−

x C C

1 2

⎛ ⎜ ⎝

⎞ ⎟ ⎠

Từ (3) và (5) ta suy ra nghiệm tổng quát của (1) làlà:

25/03/2010

100

101

25/03/2010

4. Nguyên lý bù trừ 4. Nguyên lý bù trừ

ạ ọ g

Ví dụ Lớp toán học rời rạc có 25 sinh viên giỏi tin học, ọ , p 13 sinh viên giỏi toán và 8 sinh viên giỏi cả toán và tin học. Hỏi lớp có bao nhiêu sinh viên nếu mỗi sinh viên hoặc giỏi toán hoặc học giỏi tin học hoặc giỏi cả hai môn?

Gọi A tập là tập các sinh viên giỏi Tin học, B là tập các sinh viên giỏi toán. Khi đó A∩B là tập sinh viên giỏi cả toán học và tin học. Vì mỗi sinh viên trong lớp hoặc giỏi toán, hoặc giỏi tin học hoặc giỏi cả hai nên ta có tổng số sinh viên trong lớp là |A(cid:1515)B|. Do vậy ta có: lớp là |A(cid:1515)B|. Do vậy ta có: |A(cid:1515)B| = |A| + |B| – |A∩B| = 25 + 13 – 8 = 30.

25/03/2010

102

103

4. Nguyên lý bù trừ 5. Nguyên lý quy nạp

Giả sử A1, A2,.., An là những tập hữu hạn. Khi đó:

...

∪ ∪ ∪ 2

1 n +

minh quy nạp như sau: Giả sử ta phải chứng minh mệnh

...

∩ ∩ − +

( 1) −

∩ + j

∩ ∩ ∩ 2

∑

A A ∑ A =

A A A

A A

1 i n ≤ ≤

− 1 j n i ≤ < ≤

1 j k n i ≤ < < ≤

đề∀n∈N, p(n), khi đó ta sẽ thực hiện các bước sau:

Bước 1. Kiểm tra p(0) là mệnh đề đúng (trong thực tế, ta

có thể bắt đầu bằng giá trị nhỏ nhất có thể được của n, không có thể bắt đầu bằng giá trị nhỏ nhất có thể được của n không

nhất thiết phải bắt đầu từ 0)

Bước 2. Với n bất kỳ, giả sử p(n) là mệnh đề đúng, ta sẽ

phải chứng minh p(n+1) cũng là mệnh đề đúng.

Mệnh đề “∀n∈N, p(n)” là hệ quả logic của “p(0)∧[∀n∈N, p(n) →p(n+1)]” Nguyên lý quy nạp được cụ thể hóa thành phương pháp chứng ể

25/03/2010

104

105

25/03/2010

5. Nguyên lý quy nạp 5. Nguyên lý quy nạp

Xét n là số tự nhiên bất kỳ, giả sử p(n) là mệnh đề đúng, nghĩa là

n n (

1 )

, 0

. . .

n ∀ ∈

ta có:

Ví dụ

n n ( (

1 )+ 1 ) +

. . .

n n (

1 )

" 0

. . .

2 2 "

g Chứng minh

Ta sẽ chứng minh p(n+1) cũng đúng. Thật vậy, ta có:

Ta xét vị từ p(n) =

n n (

1 )

. . .

(

1 )

(

1 )

" 0

Ta có:

0 . 1 2 2

( (

n n

1 ) [ ( 1 ) [ (

1 ) 1 )

1 ] 1 ]

+ +

n n 2

p(0)= , đây rõ ràng là một mệnh đề

suy ra p(n+1) là mệnh đề đúng.

Theo nguyên lý quy nạp ta có điều phải chứng minh.

đúng.

25/03/2010

106

107

dã đã ế l ô tì

i h ằ

à tổ

3 đ

6. Phương pháp phản chứng 6. Phương pháp phản chứng

Một trong những cách giải bài toán tồn tại là dùng lập luận phản chứng: giả thiết điều chứng minh là sai, từ đó dẫn đến mâu thuẫn. minh là sai từ đó dẫn đến mâu thuẫn

Điều kiện cần và đủ để 3 đoạn là cạnh của một tam giác là tổng của hai cạnh phải lớn hơn một cạnh. Ta sắp các đoạn thẳng theo thứ tự tăng dần của độ dài a1, a2,..., a7 và chứng minh rằng dãy đã xếp luôn tìm được 3 đoạn mà tổng của hai ủ h i đoạn đầu lớn hơn đoạn cuối. Để chứng minh, ta giả sử không tìm được ba đoạn nào mà tổng của hai đoạn nhỏ hơn một đoạn, nghĩa là các bất đẳng thức sau đồng thời xảy ra:

Ví dụ

, a2 ≥ 10 )

Cho 7 đoạn thẳng có độ dài lớn hơn 10 và nhỏ

hơn 100. Chứng minh rằng ta luôn luôn tìm hơn 100 Chứng minh rằng ta luôn luôn tìm

a1 + a2 ≤ a3 (cid:1436) a3 ≥ 20 (vì a1 a2 + a3 ≤ a4 (cid:1436) a4 ≥ 30 (vì a2 ≥ 10 a3 ≥ 20) a2 + a3 ≤ a4 (cid:1436) a4 ≥ 30 (vì a2 ≥ 10, a3 ≥ 20) a3 + a4 ≤ a5 (cid:1436) a5 ≥ 50 (vì a3 ≥ 20, a4 ≥ 30 ) a4 + a5 ≤ a6 (cid:1436) a6 ≥ 80 (vì a4 ≥ 30, a5 ≥ 50) a5 + a6 ≤ a7 (cid:1436) a7 ≥ 130 (vì a5 ≥ 50, a6 ≥ 80)

được 3 đoạn để có thể ghép lại thành một tam

(cid:1436) Mâu thuẫn (bài toán được giải quyết).

giác.

Bài giảng Toán rời rạc: Chương 1 - Phương pháp đếm

Chương I

PHƯƠNG PHÁP PHƯƠNG PHÁP ĐẾM

25/03/2010

3

N = {0, 1, 2, 3, ...}, Z = {0, ±1, ±2, ...}, ...

25/03/2010

25/03/2010

4

5

Q = { Z, n ≠ 0}

25/03/2010

25/03/2010

6

7

25/03/2010

25/03/2010

9

8

25/03/2010

25/03/2010

10

11

25/03/2010

25/03/2010

12

13

25/03/2010

25/03/2010

14

15

Ví dụ: Xét các tập hợp

25/03/2010

25/03/2010

16

17

25/03/2010

25/03/2010

18

19

25/03/2010

25/03/2010

20

21

25/03/2010

25/03/2010

22

23

25/03/2010

25/03/2010

24

25

25/03/2010

25/03/2010

26

27

25/03/2010

25/03/2010

28

29

25/03/2010

25/03/2010

30

31

25/03/2010

25/03/2010

32

33

25/03/2010

25/03/2010

34

35

25/03/2010

25/03/2010

36

37

25/03/2010

25/03/2010

38

39