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ổ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.

Toán Rời Rạc
Phương pháp Chứng minh
1 / 37
Bài tập
GS Mc Brain vợ April tới một bữa tiệc đó 4 đôi
vợ chồng khá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
ông y nhận được 9 con số khác nhau.
Hỏi 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 đề một dãy suy luận logic
dẫn đến mệnh đề y từ một tập tiên đề.
4 / 37
Nội dung
1 Mệnh đề, tiên đề, suy luận logic
2 Phương pháp chứng minh
3 Nguyên sắp thứ tự tốt
Định nghĩa
Mệnh đề 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ờ 5 giờ”
7 / 37
Mệnh đề
Với mọi số nguyên dương n, giá trị
p(n) ::= n
2
+ n + 41
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
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
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
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
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
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
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
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 nghiệm khi a, b, c, d số nguyên dương.
Năm 1988, Noam Eikies đã chứng minh sai với phản 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 nghiệm khi a, b, c, d số nguyên dương.
Năm 1988, Noam Eikies đã chứng minh sai với phản 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 nghiệm nguyên dương.
Mệnh đề y cũng sai nhưng phản dụ nhỏ nhất nhiều hơn
1000 chữ số.
10 / 37
Mệnh đề
Phương trình
313(x
3
+ y
3
) = z
3
không nghiệm nguyên dương.
Mệnh đề y cũng sai nhưng phản dụ nhỏ nhất nhiều hơn
1000 chữ số.
10 / 37
Mệnh đề (Định bốn màu)
Mọi bản đồ đều thể được chỉ bằng bốn màu sao cho hai
vùng k nhau màu khác nhau.
Hình: Bản đồ 5 màu
11 / 37
| 1/428

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