Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc - Trần Vĩnh Đức

Bài giảng Toán rời rạc cung cấp cho người học những nội dung kiến thức như: Mệnh đề, tiên đề, và suy luận logic; phương pháp chứng minh; nguyên lý sắp thứ tự tốt; nguyên lý quy nạp; quy nạp mạnh; đồ thị và biểu diễn; một số đồ thị đặc biệt . Mời các bạn cùng tham khảo. | Phương pháp chứng minh Trần Vĩnh Đức HUST Ngày 6 tháng 9 năm 2018 CuuDuongThanCong.com https fb.com tailieudientucntt 1 37 Bài tập GS Mc Brain và vợ là bà April tới một bữa tiệc ở đó có 4 đôi vợ chồng khác. Có một vài cặp bắt tay nhau nhưng không ai bắt tay với vợ hoặc chồng mình. GS hỏi mọi người khác xem họ bắt tay bao nhiêu người và ông ấy nhận được 9 con số khác nhau. Hỏi có bao nhiêu người đã bắt tay April CuuDuongThanCong.com https fb.com tailieudientucntt 2 37 Tài liệu tham khảo Eric Lehman F Thomson Leighton amp Albert R Meyer Mathematics for Computer Science 2013 Miễn phí K. Rosen Toán học rời rạc ứng dụng trong tin học Bản dịch Tiếng Việt CuuDuongThanCong.com https fb.com tailieudientucntt 3 37 Định nghĩa Chứng minh toán học của một mệnh đề là một dãy suy luận logic dẫn đến mệnh đề này từ một tập tiên đề. CuuDuongThanCong.com https fb.com tailieudientucntt 4 37 Nội dung Mệnh đề tiên đề và suy luận logic Phương pháp chứng minh Nguyên lý sắp thứ tự tốt CuuDuongThanCong.com https fb.com tailieudientucntt Định nghĩa Mệnh đề là một khẳng định hoặc đúng hoặc sai. Mệnh đề 2 3 5 3 Mệnh đề 1 1 3 7 CuuDuongThanCong.com https fb.com tailieudientucntt 6 37 Khẳng định không phải mệnh đề Đưa tôi cái bánh Bây giờ là 5 giờ CuuDuongThanCong.com https fb.com tailieudientucntt 7 37 Mệnh đề Với mọi số nguyên dương n giá trị p n n2 n 41 là số nguyên tố. p 0 41 p 3 53 p 1 43 p 2 47 p 39 1601 nhưng p 40 402 40 41 41 41 7 CuuDuongThanCong.com https fb.com tailieudientucntt 8 37 Mệnh đề Giả thuyết Euler 1769 Phương trình a4 b4 c4 d4 không có nghiệm khi a b c d là số nguyên dương. Năm 1988 Noam Eikies đã chứng minh là sai với phản ví dụ a 95800 b 217519 c 414560 d 422481 CuuDuongThanCong.com https fb.com tailieudientucntt 9 37 Mệnh đề Phương trình 313 x3 y3 z3 không có nghiệm nguyên dương. Mệnh đề này cũng sai nhưng phản ví dụ nhỏ nhất có nhiều hơn 1000 chữ số. CuuDuongThanCong.com https fb.com tailieudientucntt 10 37 Mệnh đề Định lý bốn màu Mọi bản đồ đều có thể tô được chỉ bằng