Bài giảng môn học Toán rời rạc

Toán học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành toán học có đối tượng nghiên cứu là các tập hợp rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy tính.
Nội dung trích xuất từ tài liệu:
Bài giảng môn học Toán rời rạc TOÁN RỜI RẠC(Discrete Mathematics) Chương 1 Cơ sở Logic mệnh đềLogicLogic vị từNội dung chính Khái niệm mệnh đề  Các phép toán logic  Dạng mệnh đề  Các quy tắc suy diễn  Các phương pháp chứng minh  Vị từ và lượng từ hóa 1. Định nghĩa mệnh đề: Mệnh đề (Proposition): là một diễn đạt có giá trị chân lý (chân trị) xác định (đúng hoặc sai nhưng không thể vừa đúng lại vừa sai). Ví dụ 1.1: Các diễn đạt sau, diễn đạt nào là mệnh đề? Mặt trời quay quanh trái đất  3+1 = 5  Trái đất quay quanh mặt trời,…  x+2=8  Mấy giờ rồi?  phải hiểu kỹ điều này.  Hà nội là thủ đô của Việt Nam  Sài gòn nằm ở miền bắc việt nam  x+1=5 nếu x=1 Mệnh đề (tt)Kí hiệu: 1 (hoặc T): Chân trị đúng. 0 (hoặc F): Chân trị sai. P, Q, R,… dùng cho kí hiệu các mệnh đề.Ví dụ 1.2: P: Hà Nội là Thủ Đô của Việt Nam Q: Quy Nhơn thuộc tỉnh Bình Định R: Việt Nam thuộc châu Á S: Long An là tỉnh thuộc khu vực miền trung của Việt Nam. …2. Các phép toán logicPhépphủđịnh(Negationoperator)Phépnốiliền(Conjunctionoperator)Phépnốirời(Disjunctionoperator)Phépkéotheo(Implicationoperator)Phépkéotheohaichiều(Biconditionaloperator)2.1. Phép phủ định (Negation operator) Phủ định của mệnh đề P (kí hiệu ¬P: đọc là “Không P”) là mệnh đề có chân trị 1 nếu P có chân trị 0 và có chân trị 0 nếu P có chân trị 1.◊Bảngchântrị P ¬P 0 1 1 0◊Vídụ2.1: P: ≡ “HànộilàthủđôcủaViệtNam” ¬P:≡ “HànộikhôngphảilàthủđôcủaViệtNam” Q:≡ “14=8” ¬Q:≡ ”14 ≠ 8”2.2. Phép nối liền (ConjunctionOperator) Phép nối liền hai mệnh đề P và Q (kí hiệu P ∧ đọc là “P Q: và Q”) là mệnh đề có chân trị 1 nếu cả P và Q có chân trị 1 hoặc có chân trị 0 nếu ít nhất một trong 2 mệnh đề P hay Q có chân trị 0. Bảng chân trị: P∧ P Q Q 0 0 0 0 1 0 1 0 0 1 1 1Ví dụ về phép nối liềnVí dụ 2.2: “Hôm nay là chủ nhật và ngày mai là thứ 7” là một mệnh đề có chân trị 0.Ví dụ 2.2: “Tổng các góc trong một tam giác bằng 180o và trong tam giác vuông có một góc 90o” là mệnh đề có chân trị 1Ví dụ 2.3: “Trong một tam giác cân có 2 cạnh bằng nhau và mặt trời quay quanh trái đất” là một mệnh đề có chân trị 0.2.3. Phép nối rời (Disjunction Operator) Phép nối rời kết hợp hai mệnh đề P,Q (kí hiệu P ∨Q: đọc là “P hay Q”) là mệnh đề có chân trị 0 nếu cả P và Q có chân trị 0 hoặc có chân trị 1 nếu P có chân trị 1 hay Q có chân trị 1. Bảng chân trị: P∨ P Q Q 0 0 0 0 1 1 1 0 1 1 1 12.4 Phép kéo theo (Implication Operator) Mệnh đề “Nếu P thì Q” (kí hiệu P → Q: đọc là P kéo theo Q, hay P là điều kiện đủ của Q hay Q là điều cần của P) là mệnh đề có chân trị 0 nếu P có chân trị 1 và Q có chân trị 0, có chân trị 1 trong các trường hợp còn lại. Bảng chân trị: P→Q P Q 0 0 1 0 1 1 1 0 0 1 1 1Ví dụ về phép kéo theo Ví dụ 2.4: P:≡ “Nếu 32.5. Phép kéo theo 2 chiều Mệnh đề “Nếu P thì Q và ngược lại”, kí hiệu P ↔ Q (còn đọc là “P nếu và chỉ nếu Q” hoặc “P khi và chỉ khi Q” hoặc “P là điều kiện cần và đủ để có Q”) có chân trị 1 nếu cả 2 mệnh đề P và Q có cùng chân trị, có chân trị 0 trong các trường hợp còn lại. Bảng chân trị: P↔Q P Q 0 0 1 0 1 0 1 0 0 1 1 13. Dạng mệnh đề Tóm tắt: Định nghĩa   Bảng chân trị  Tương đương Logic  Hệ quả Logic  Các quy tắc thay thế  Các luật logic  Các phương pháp chứng minh3.1. Dạng mệnh đề Định nghĩa: Dạng ...