- Tập hợp. - Định nghĩa, định lý và chứng minh. - Mô tả đặc tính D = {x| x là một ngày trong tháng 9}. - Hàm: là một ánh xạ từ miền xác định sang miền giá trị f: D → R. - Quan hệ. - Nếu R là một quan hệ hai ngôi ⇔ aRb = True. - Tương tự, Nếu R là một quan hệ k ngôi ⇔ R(a 1 , a 2. - Quan hệ "bằng". - Quan hệ "chẵn hoặc lẻ". - Các tính chất của quan hệ. - Quan hệ tương đương phải thỏa mãn:. - Phản xạ (reflexive): nếu aRa là đúng với ∀a ∈ S. - L không là quan hệ. - E là quan hệ. - P là quan hệ. - Đồ thị (Graphs). - Chu trình: là một đường đi mà đỉnh bắt đầu ≡ đỉnh kết thúc. - Quan hệ hai ngôi ≡ Đồ thị có hướng. - Cây (Trees) là một đồ thi - Không có chu trình - Có một nút gốc. - Chuỗi (xâu): là một dãy hữu hạn các ký tự của bộ chữ, được viết liền và không bị ngăn cách bởi dấu phẩy. - baccada là một xâu trên Σ 2. - Ngôn ngữ: là một tập các xâu L 1 = {ab,bc,ca,da}. - Định nghĩa: là một mô tả về các đối tượng và khái niệm mà chúng ta sử dụng. - Mệnh đề toán học: là một mệnh đề được biểu diễn bằng các đối tượng toán học. - Chứng minh: là sự lập luận logic có sức thuyết phục rằng mệnh đề là đúng. - Định lý: là mệnh đề toán học đã được chứng minh là đúng. - Bổ đề: là một mệnh đề đúng có thể suy ra từ một định lý nào đó. - Hệ quả: Được suy ra khi chứng minh một định lý nào đó. - Phỏng đoán: là một mệnh đề có khả năng là đúng nhưng chưa được chứng minh. - Khi và chỉ khi: là một mệnh đề tương đương P ⇔ Q - Cần chứng minh chiều thuận: P ⇒ Q. - Chứng minh chiều ngược: Q ⇒ P. - Các cách chứng minh. - Chứng minh bằng việc xây dựng. - Định lý. - x đặc biệt nào đó là nghiệm của bài toán Chứng minh: Chỉ ra cách xây dựng x. - Chứng minh bằng phản chứng Định lý: “Mệnh đề P là đúng”. - Chứng minh:. - Chứng minh bằng quy nạp. - Định lý: “Mệnh đề P là đúng ∀ i ≥ 0”. - Chỉ ra P(0) là đúng Bước quy nạp:. - Giả sử P(i) là đúng → Giả thiết quy nạp. - Thực hiện biến đổi logic để chỉ ra P(i+1) là đúng Kết luận là P đúng ∀ i ≥ 0. - Ví dụ về các cách chứng minh. - Định lý: Nếu a và b là 2 số nguyên liên tiếp thì a+b là một số lẻ. - Vì a và b là 2 số nguyên liên tiếp → b = a + 1 - a + b = a + a + 1 = 2a + 1. - Mà 2a là số chẵn → 2a + 1 là số lẻ → a + b là số lẻ. - Chứng minh bằng phản chứng. - Giả sử a + b không phải là số lẻ. - Vì a và b là 2 số nguyên liên tiếp → a + b = 2a + 1 (2. - Vậy giả thiết trên là sai → Định lý đã được chứng minh. - Định lý: Nếu a và b là 2 số nguyên liên tiếp thì a+b là một số lẻ Chứng minh:. - Giả sử P(x) đúng khi tổng của x và số nguyên liên tiếp sau x là số lẻ. - 1 + 2 = 3 là số lẻ → P(x. - Giả sử P(x) là đúng → P(x. - x + x + 1 là số lẻ Tăng x và x + 1 lên 1 đơn vị: (x+1. - Vì vậy P(x) là số lẻ → P(x+1) là số lẻ. - Kết luận là P đúng ∀ x ≥ 1
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt