Toán Rời Rạc Phương pháp Chứng minh 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? 2 / 37 Tài liệu tham khảo
• Eric Lehman, F Thomson Leighton & 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) 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 đề. 4 / 37 Nội dung
1 Mệnh đề, tiên đề, và suy luận logic 2 Phương pháp chứng minh
3 Nguyên lý sắp thứ tự tốt Đị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 6 / 37
Khẳng định không phải mệnh đề
• “Đưa tôi cái bánh!”
• “Bây giờ là 5 giờ” 7 / 37 • 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 Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n2 + n + 41 là số nguyên tố. 8 / 37 • p(3) = 53 ✓ • p(1) = 43 ✓ • · · · • p(2) = 47 ✓ • p(39) = 1601 ✓ nhưng
p(40) = 402 + 40 + 41 = 41 × 41 7 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 ✓ 8 / 37 • p(3) = 53 ✓ • · · · • p(2) = 47 ✓ • p(39) = 1601 ✓ nhưng
p(40) = 402 + 40 + 41 = 41 × 41 7 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(1) = 43 ✓ 8 / 37 • p(3) = 53 ✓ • · · · • p(39) = 1601 ✓ nhưng
p(40) = 402 + 40 + 41 = 41 × 41 7 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(1) = 43 ✓ • p(2) = 47 ✓ 8 / 37 • · · · • p(39) = 1601 ✓ nhưng
p(40) = 402 + 40 + 41 = 41 × 41 7 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 ✓ 8 / 37 • p(39) = 1601 ✓ nhưng
p(40) = 402 + 40 + 41 = 41 × 41 7 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 ✓ 8 / 37 nhưng
p(40) = 402 + 40 + 41 = 41 × 41 7 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 ✓ 8 / 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 8 / 37
Năm 1988, Noam Eikies đã chứng minh là sai với phản ví dụ a = 95800, b = 217519, c = 414560, d = 422481
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. 9 / 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 9 / 37
Mệnh đề này cũng sai nhưng phản ví dụ nhỏ nhất có nhiều hơn 1000 chữ số. Mệnh đề Phương trình
313(x3 + y3) = z3
không có nghiệm nguyên dương. 10 / 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ố. 10 / 37 Hình: Bản đồ tô 5 màu
Mệnh đề (Định lý bốn màu)
Mọi bản đồ đều có thể tô được chỉ bằng bốn màu sao cho hai
vùng kề nhau có màu khác nhau. 11 / 37