Định lý: trong Fn, một đơn thức do p nhân tử nguyên tố tạo thành, sơ đồ karnaugh của nó có 2n-p ô được tô. Sơ đồ karnaugh có hình chữ nhật gồm 2n-p ô được tô là sơ đồ karnaugh của một đơn thức là tích của p literals (được gọi là cell) | 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 | 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
