Giáo trình toán rời rạc

lOMoARcPSD|61182002
Slide Toán rời rạc - toán rời rạc
toán rời rạc (Học viện Hành chính) Scan to open on Studeersnel
Studocu is not sponsored or endorsed by any college or university
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Giới thiệu môn học TOÁN RỜI RẠC
Tên học phần: Toán rời rạc (Discrete Mathematics)  Mã học phần: INC1002
 Số tín chỉ: 03  Số tiết: 60  Tiết lý thuyết: 30
 Tiết thảo luận, bài tập, thực hành: 30
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 1 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Giới thiệu môn học TOÁN RỜI RẠC KIỂM TRA ĐÁNH GIÁ Hoạt động Nội dung
Điều kiện dự thi Trọng kiểm tra KTHP số Kiểm tra Đánh giá sự • SV phải tham dự 10%
thường xuyên chuyên cần, tối thiểu 80% thái độ học tập; tổng số giờ của học phần • Điểm >=5 Kiểm tra Kiểm tra kiến • Điểm >=3 30%
đánh giá định thức học phần, kỳ bài tập chủ đề Thi kết thúc KT kiến thức • Điểm >=4 60% học phần toàn bộ HP
Giới thiệu môn học TOÁN RỜI RẠC
NỘI DUNG HỌC PHẦN • Chương I • LOGIC •
1.1. Mệnh đề và các phép toán • 1.1.1. Định nghĩa •
1.1.2. Bảng giá trị chân l{ các phép toán •
1.2. Sự tương đương giữa các mệnh đề • 1.2.1. Định nghĩa • 1.2.2. Tính chất • 1..2.3. Dạng chuẩn tắc •
1.3. Lượng từ và vị từ • 1.3.1. Hàm mệnh đề •
1.3.2. Phép toán trên hàm mệnh đề • 1.3.3. Lượng từ •
1.4. Một số ứng dụng trên máy tính 4
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 2 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Giới thiệu môn học TOÁN RỜI RẠC • Chương II •
LÝ THUYẾT TỔ HỢP •
2.1. Tập hợp và biểu diễn tập hợp trên máy tính •
2.1.1. Tập hợp và các phép toán •
2.1.2. Biểu diễn tập hợp trên máy tính •
2.2. Một số nguyên lý đếm cơ bản • 2.2.1. Nguyên l{ cộng • 2.2.2. Nguyên lý nhân • 2.2.3. Nguyên l{ bù trừ •
2.3. Nguyên lý Dirichlet • 2.3.1. Nguyên lý Dirichlet •
2.3.2. Một số ứng dụng của nguyên l{ Dirichlet •
2.4. Cấu hình tổ hợp •
2.4.1. Chỉnh hợp và chỉnh hợp lặp •
2.4.2. Tổ hợp và tổ hợp lặp • 2.4.3. Hoán vị •
2.4.4. Hoán vị các phần tử giống nhau 5
Giới thiệu môn học TOÁN RỜI RẠC • Chương III •
LÝ THUYẾT ĐỒ THỊ •
3.1. Các khái niệm cơ bản của lý thuyết đồ thị •
3.1.1. Khái niệm đồ thị, đường đi, chu trình, đồ thị liên thông •
3.1.2. Biểu diễn đồ thị •
3.1.3. Phân loại đồ thị •
3.2. Các thuật toán tìm kiếm trên đồ thị •
3.2.1. Thuật toán tìm kiếm theo chiều rộng •
3.2.2. Thuật toán tìm kiếm theo chiều sâu •
3.3. Đồ thị Euler và đồ thị Hamilton •
3.3.1. Đường đi Euler và Đồ thị Euler •
3.3.2. Đường đi Hamilton và Đồ thị Hamilton •
3.4. Cây và cây khung • 3.4.1. Cây • 3.4.2. Cây khung •
3.5. Bài toán tìm đường đi ngắn nhất • 3.5.1. Bài toán •
3.5.2. Thuật toán tìm đường đi ngắn nhất 6
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 3 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Giới thiệu môn học TOÁN RỜI RẠC Chương IV ĐẠI SỐ BOOLE
(Tổng số giờ: 12; lý thuyết 06, thực hành: 06)
4.1. Hàm Boole và biểu thức Boole 4.1.1. Hàm Boole 4.1.2. Biểu thức Boole
4.1.3. Dạng chuẩn tắc của hàm Boole
4.1.4. Hằng đẳng thức của đại số Boole
4.1.5. Tính đối ngẫu của đại số Boole
4.2. Các cổng logic và tổ hợp các cổng logic 4.2.1. Bộ đảo 4.2.2. Cổng hoặc (OR) 4.2.3. Cổng và (AND)
4.2.4. Tổ hợp các cổng logic
4.3. Tối thiểu hóa hàm Boole
4.3.1. Phương pháp biến đổi đại số
4.3.2. Phương pháp bảng Karnaugh 7
CHƯƠNG I: MỆNH ĐỀ TOÁN RỜI RẠC 1. Mệnh đề:
Định nghĩa: Những câu phản ánh đúng hoặc
sai thực tế khách quan được gọi là các mệnh đề.
• Đối tượng của logic mệnh đề là các mệnh đề
thoả mãn hai điều kiện sau:
• Mỗi mệnh đề đều phải hoặc đúng, hoặc sai.
• Mỗi mệnh đề không thể vừa đúng, vừa sai.
Quy ước mệnh đề có giá trị 1 nếu nó đúng, có giá trị 0 nếu nó sai.
Các giá trị 1; 0 gọi là giá trị chân lý hay chân trị của mệnh đề 8
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 4 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
CHƯƠNG I: MỆNH ĐỀ TOÁN RỜI RẠC
2. CÁC PHÉP TOÁN LOGIC TRÊN CÁC MỆNH ĐỀ
2.1. Phép phủ định
• Định nghĩa:
• Cho mệnh đề p. Khi đó, ta gọi phủ định của
mệnh đề p là mệnh đề 𝑝 (đọc là: "không p")
đúng nếu p sai, sai nếu p đúng.
Bảng giá trị chân lý của phép phủ định. 9
CHƯƠNG I: MỆNH ĐỀ TOÁN RỜI RẠC • 2.2. Phép hội 10
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 5 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
CHƯƠNG I: MỆNH ĐỀ TOÁN RỜI RẠC 2.3. Phép tuyển 11
Chương I: Logic TOÁN RỜI RẠC 2.4. Phép kéo theo
Phép kéo theo trong ngôn ngữ nói thường được phát biểu dạng nếu p thì q. 12
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 6 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC 13
Chương I: Logic TOÁN RỜI RẠC
2.5. Phép tương đương
Trong ngôn ngữ nói, phép tương đương được phát biểu
dạng “nếu và chỉ nếu”, “khi và chỉ khi”… 14
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 7 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC
• Bảng giá trị chân l{ của phép tương đương p q pq 1 1 1 1 0 0 0 0 1 0 1 0 15 Chương I: g Logic Logi TO T Á O N Á RỜI R R ẠC Ạ • Công thức 16
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 8 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC
• Sự tương đương giữa 2 công thức 17
Chương I: Logic TOÁN RỜI RẠC
• Mệnh đề tương đương
• Ví dụ: Cho 3 mệnh đề p, q, r 18
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 9 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC
Lập bảng giá trị chân lý p 1 1 1 1 0 0 0 0 q 1 1 0 0 0 0 1 1 r 1 0 1 0 1 0 0 1 p v q 1 1 (p v q)=>r 1 0 p =>r 1 1 q => r 1 0
(p =>r)^( q => r) 1 0 19
Chương I: Logic TOÁN RỜI RẠC
Ví dụ: Chứng minh các đẳng thức sau đây bằng
cách lập bảng chân l{: chú ý p.q = pΛq 20
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 10 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC Logic vị từ Ví dụ:
P(x): “x chia hết cho 2” là 1 hàm mệnh đề.
x = 4 => P(4): “4 chia hết cho 2” là 1 mệnh đề đúng
x=5 => P(5): “5 chia hết cho 2” là 1 mệnh đề sai 21
Chương I: Logic TOÁN RỜI RẠC 22
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 11 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC 23
Chương I: Logic TOÁN RỜI RẠC 24
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 12 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC
• Phép toán trên các hàm mệnh đề 25
Chương I: Logic TOÁN RỜI RẠC 26
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 13 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC 27
Chương I: Logic TOÁN RỜI RẠC 28
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 14 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC 29
Chương I: Logic TOÁN RỜI RẠC 30
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 15 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC 31
Chương I: Logic TOÁN RỜI RẠC • Ví dụ 32
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 16 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
𝐸𝐴(𝑥) = [3; +∞)? 𝐸𝐵(𝑥) = 2; 5 ?
• 𝐸𝐴 𝑥 ⋀𝐵(𝑥) = 𝐸𝐴(𝑥) ∩ 𝐸𝐵 𝑥 = = [3; +∞) ∩ 2; 5 = [3;5].
• 𝐸𝐴 𝑥 ⋁𝐵(𝑥) = 𝐸𝐴(𝑥) ∪ 𝐸𝐵 𝑥 = [2 ; +∞)
• 𝐸𝐴 𝑥 ⇒𝐵(𝑥) = (𝑅| 𝐸𝐴(𝑥)) ∪ 𝐸𝐵 𝑥 = (- ∞;3) ∪ 2; 5 = (- ∞;5].
• 𝐸𝐴 𝑥 ⟺𝐵(𝑥) = (R\(𝐸𝐴(𝑥) ∪ 𝐸𝐵 𝑥 ) ∪(𝐸𝐴(𝑥) ∩
𝐸𝐵 𝑥 ) = (- ∞;2) ∪ [3;5]. 33
Chương I: Logic TOÁN RỜI RẠC • Ví dụ 34
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 17 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023 35
Chương I: Logic TOÁN RỜI RẠC • 3. Lượng từ
• 3.1. Lượng từ tồn tại 36
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 18 lOMoARcPSD|61182002
Chương IV: Đại số Boole 05/05/2023
Chương I: Logic TOÁN RỜI RẠC 37
Chương I: Logic TOÁN RỜI RẠC
• 3.2. Lượng từ "với mọi“ 38
Downloaded by Bùi C?nhhr (canhbui948@gmail.com) 19