tailieunhanh - 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 https 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 https 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 https 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 đề. https 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 https 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 https 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ờ https 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 https 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 https 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ố. https tailieudientucntt 10 37 Mệnh đề Định lý bốn màu Mọi bản đồ đều có thể tô được chỉ bằng