428 trang 89 lượt tải

Tổng hợp bài giảng môn Toán rời rạc| Bài giảng môn Toán rời rạc| Trường Đại học Bách Khoa Hà Nội

177

Tổng hợp bài giảng môn Toán rời rạc| Bài giảng môn Toán rời rạc| Trường Đại học Bách Khoa Hà Nội. Tài liệu gồm 428 trang giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem.

Môn: Toán rời rạc (BKHN) 53 tài liệu

Trường: Đại học Bách Khoa Hà Nội 2.8 K tài liệu

Tác giả:

Profile

Trịnh Thảo Anh

7 tháng trước
Danh sách Quiz
/428
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
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
là số nguyên tố.
•
p(0) = 41 ✓
•
p(1) = 43 ✓
•
p(2) = 47 ✓
•
p(3) = 53 ✓
•
···
•
p(39) = 1601 ✓
nhưng
p(40) = 40
2
+ 40 + 41 = 41 × 41 7
8 / 37
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
là số nguyên tố.
•
p(0) = 41 ✓
•
p(1) = 43 ✓
•
p(2) = 47 ✓
•
p(3) = 53 ✓
•
···
•
p(39) = 1601 ✓
nhưng
p(40) = 40
2
+ 40 + 41 = 41 × 41 7
8 / 37
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
là số nguyên tố.
•
p(0) = 41 ✓
•
p(1) = 43 ✓
•
p(2) = 47 ✓
•
p(3) = 53 ✓
•
···
•
p(39) = 1601 ✓
nhưng
p(40) = 40
2
+ 40 + 41 = 41 × 41 7
8 / 37
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
là số nguyên tố.
•
p(0) = 41 ✓
•
p(1) = 43 ✓
•
p(2) = 47 ✓
•
p(3) = 53 ✓
•
···
•
p(39) = 1601 ✓
nhưng
p(40) = 40
2
+ 40 + 41 = 41 × 41 7
8 / 37
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
là số nguyên tố.
•
p(0) = 41 ✓
•
p(1) = 43 ✓
•
p(2) = 47 ✓
•
p(3) = 53 ✓
•
···
•
p(39) = 1601 ✓
nhưng
p(40) = 40
2
+ 40 + 41 = 41 × 41 7
8 / 37
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
là số nguyên tố.
•
p(0) = 41 ✓
•
p(1) = 43 ✓
•
p(2) = 47 ✓
•
p(3) = 53 ✓
•
···
•
p(39) = 1601 ✓
nhưng
p(40) = 40
2
+ 40 + 41 = 41 × 41 7
8 / 37
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
là số nguyên tố.
•
p(0) = 41 ✓
•
p(1) = 43 ✓
•
p(2) = 47 ✓
•
p(3) = 53 ✓
•
···
•
p(39) = 1601 ✓
nhưng
p(40) = 40
2
+ 40 + 41 = 41 × 41 7
8 / 37
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
là số nguyên tố.
•
p(0) = 41 ✓
•
p(1) = 43 ✓
•
p(2) = 47 ✓
•
p(3) = 53 ✓
•
···
•
p(39) = 1601 ✓
nhưng
p(40) = 40
2
+ 40 + 41 = 41 × 41 7
8 / 37
Mệnh đề (Giả thuyết Euler, 1769)
Phương trình
a
4
+ b
4
+ c
4
= d
4
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 đề (Giả thuyết Euler, 1769)
Phương trình
a
4
+ b
4
+ c
4
= d
4
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 đề
Phương trình
313(x
3
+ y
3
) = z
3
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
Mệnh đề
Phương trình
313(x
3
+ y
3
) = z
3
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
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.
Hình: Bản đồ tô 5 màu
11 / 37

Tài liệu khác của Đại học Bách Khoa Hà Nội

Preview text:

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

Tài liệu liên quan: