tailieunhanh - Phần 1: Toán rời rạc
Trình bày các vấn đề của lý thuyết tổ hợp xoay quanh 4 bài toán cơ bản : Bài toán đêm, Bài toán tồn tại, Bài toán liệt kê và Bài toán tới ưu tổ hợp. Nội dung cảu phần I không những giúp nâng cao tư duy toán, mà còn làm quen với tư duy thuật toán trong việc giải quyết các vấn đề thực tế, đồng thời cũng rèn luyện kỹ thuật lập trình các bài toán tổ hợp | TOÁN HỌC RỜI RẠC PHẦN 1 DISCRETE MATHEMATICS PART ONE NỘI DUNG ÔN TẬP PHẦN 1 CƠ SỞ LOGIC Phép tính mệnh đề & vị từ Quy tắc suy luận. Quy nạp ĐẠI SỐ BOOL Quan hệ thứ tự & tập hợp được sắp Dàn và đại số bool Hàm bool Phương trình bool & hệ phủ tối tiểu Công thức tối tiểu của hàm bool PHẦN 2 PHÉP ĐẾM Nguyên lý cộng, nhân & bù trừ Giải tích tổ hợp Nguyên lý Dirichlet Công thức đệ quy NỘI DUNG ÔN TẬP (cont.) LÝ THUYẾT ĐỒ THỊ Đại cương Đồ thị liên thông Đường đi ngắn nhất Cây khung trọng lượng tối tiểu Luồng cực đại SỐ HỌC Lý thuyết chia hết Lý thuyết đồng dư CƠ SỞ LOGIC (1) PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ Mệnh đề Chân trị của mệnh đề: đúng, sai (true, false) Các phép toán mệnh đề Phép phủ định (NOT, ¬, ) Phép hội (AND, ) Phép tuyển: (OR, ) Phép tuyển loại trừ (XOR, ) Phép toán trên bit Phép kéo theo: Phép tương đương: Biểu thức mệnh đề Mệnh đề hệ quả & mệnh đề tương đương Hằng đúng (tautology), hằng sai Tiếp liên Mệnh đề hệ quả: P Q hằng đúng Tương đương logic: P Q hằng đúng | TOÁN HỌC RỜI RẠC PHẦN 1 DISCRETE MATHEMATICS PART ONE NỘI DUNG ÔN TẬP PHẦN 1 CƠ SỞ LOGIC Phép tính mệnh đề & vị từ Quy tắc suy luận. Quy nạp ĐẠI SỐ BOOL Quan hệ thứ tự & tập hợp được sắp Dàn và đại số bool Hàm bool Phương trình bool & hệ phủ tối tiểu Công thức tối tiểu của hàm bool PHẦN 2 PHÉP ĐẾM Nguyên lý cộng, nhân & bù trừ Giải tích tổ hợp Nguyên lý Dirichlet Công thức đệ quy NỘI DUNG ÔN TẬP (cont.) LÝ THUYẾT ĐỒ THỊ Đại cương Đồ thị liên thông Đường đi ngắn nhất Cây khung trọng lượng tối tiểu Luồng cực đại SỐ HỌC Lý thuyết chia hết Lý thuyết đồng dư CƠ SỞ LOGIC (1) PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ Mệnh đề Chân trị của mệnh đề: đúng, sai (true, false) Các phép toán mệnh đề Phép phủ định (NOT, ¬, ) Phép hội (AND, ) Phép tuyển: (OR, ) Phép tuyển loại trừ (XOR, ) Phép toán trên bit Phép kéo theo: Phép tương đương: Biểu thức mệnh đề Mệnh đề hệ quả & mệnh đề tương đương Hằng đúng (tautology), hằng sai Tiếp liên Mệnh đề hệ quả: P Q hằng đúng Tương đương logic: P Q hằng đúng CƠ SỞ LOGIC (2) Các tương đương thường dùng (T=hằng đúng, F=hằng sai) P T = T Domination laws (P Q) R=P (Q R) = P Q R Associative laws P F = F (P Q) R = P (Q R) = P Q R P F = P Identity laws P (Q R)=(P Q) (P R) Distributive laws P T = P P (Q R)=(P Q) (P R) P P = P Idempotent laws ¬(P Q) = ¬P ¬Q De Morgan’s laws P P = P ¬(P Q) = ¬P ¬Q ¬(¬P)=P Double negation laws P (P Q) = P Absortion laws P ¬P = T Comlement laws P (P Q) = P P ¬P = F P Q = ¬P Q P Q = Q P Commutative laws P Q = Q P CƠ SỞ LOGIC (3) Vị từ Vị từ P: E {0, 1} Không gian của một vị từ: E = E1xE2x xEn Trọng lượng của một vị từ: n Các phép toán vị từ: , , , Các lượng tử ¬ ( X: P(X)) = X: ¬P(X) ¬ ( X: P(X)) = X: ¬P(X) CƠ SỞ LOGIC (4) QUY TẮC SUY LUẬN Các quy tắc suy luận: Quy tắc Hằng đúng Tên P (P Q) Cộng P Q P Rút gọn (P (P Q)) Q Modus ponens (¬Q (P Q)) ¬P Modus tollens ((P Q) (Q R)) (P R) Tam đoạn
đang nạp các trang xem trước
