Giáo trình Toán rời rạc 1 - Phạm Tiến Sơn

1 TẬP Hựp VÀ ÁNH XẠ 1

1.1 Tập hợp 1

1.1.1 Khái niệm 1

1.1.2 Các phép toán trên tập họp 3

1.1.3 Tích Descartes 5

1.2 Ánh xạ 8

1.2.1 Định nghĩa và tính chẩt 8

1.2.2 Ánh xạ hạn chế 10

1.2.3 Hợp của các ánh xạ 11

1.2.4 Ánh xạ ngược 12

1.2.5 Lực lượng cùa một tập hợp 12

2 LOGIC VÀ CÁC PHƯƠNG PHÁP CHỬNG MINH 17

2.1 Mệnh đe 17

2.2 Mệnh đề có íliều kiện và các mệnh ílề tương đương 20

2.3 Lượng hóa 23

2.4 Phương pháp chứng minh 26

i

2.5 Quy nạp toán học 31

3 THUẬT TOÁN 33

3.1 Mờ đầu 33

3.1.1 'lim số lớn nhất trong ba số 33

3.1.2 Tỉm số lớn nhất trong dãy hữu liạn các số thực 33

3.2 Thuật toán Euclid 35

3.2.1 Thuật toán Euclid 37

3.3 Thuật toán đệ quy 39

3.3.1 Tính n giai thừa 39

3.3.2 'lim ước số chung lớn nhất 10

3.3.3 Thuật toán xác định dãy Fibonacci 41

3.4 tỴ> phức tạp cùa thuật toán 43

3.5 Phân tích thuật toán Euclid 48