Giáo trình Toán rời rạc - Bài 1: Phương pháp chứng minh - Trần Vĩnh Đức
Phương pháp chứng minh
Trần Vĩnh Đức
HUST
Ngày 6 tháng 9 năm 2018
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,
▶
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
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
Định nghĩa
Mệnh đề là một khẳng định hoặc đúng hoặc sai.
▶
Mệnh đề
Mệnh đề
2 + 3 = 5
1 + 1 = 3
ꢀ
ꢁ
▶
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) ::= n2 + n + 41
là số nguyên tố.
▶
▶
▶
▶
p(0) = 41 ✓
p(3) = 53 ✓
· · ·
p(39) = 1601 ✓
▶
p(1) = 43 ✓
▶
p(2) = 47 ✓
nhưng
p(40) = 402 + 40 + 41 = 41 × 41
ꢁ
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,
c = 414560,
b = 217519,
d = 422481
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ố.
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
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.
Appel & Hakel đã phân loại các bản đồ và dùng máy tính để kiểm
tra xem chúng có tô được bằng 4 màu. Họ đã hoàn tất chứng
minh năm 1976. Tuy nhiên
▶
Chứng minh quá dài để có thể kiểm tra mà không dùng máy
tính.
▶
Không ai đảm bảo rằng chương trình máy tính này chạy đúng.
Không ai đủ nhiệt tình để kiểm tra hết hàng nghìn trường hợp
đã được chứng minh.
▶
12 / 37
Mệnh đề (Định lý cuối cùng của Fermat)
Phương trình
xn + yn = zn
không có nghiệm nguyên với n ≥ 3.
▶
Bài toán được viết trong một quyển sách Fermat đọc năm
1630.
▶
Andrew Wiles chứng minh là đúng năm 1994.
13 / 37
Mệnh đề (Giả thuyết Goldbach)
Mọi số nguyên chẵn lớn hơn 2 đều là tổng của hai số nguyên tố.
▶
Được giả thuyết năm 1742
Đã được khẳng định là đúng với mọi số không lớn hơn 1016.
▶
▶
ꢀ hay ꢁ ?
14 / 37
Định nghĩa
Vị từ là một mệnh đề mà giá trị chân lý phụ thuộc vào một hoặc
nhiều biến.
p(n) :: = “n là số bình phương hoàn hảo”
p(4) = “4 là số bình phương hoàn hảo”
p(4) = ꢀ
p(5) = ꢁ
15 / 37
Phương pháp tiên đề
▶
Thủ tục chuẩn để thiết lập các giá trị chân lý trong toán học
đã được phát triển khoảng từ 300 BC bởi Euclid.
▶
Bắt đầu từ 5 “giả sử” để xây dựng hình học Euclid. Ví dụ:
Qua một điểm nằm ngoài một đường thẳng ta vẽ được
một và chỉ một đường thẳng song song với đường thẳng
đã cho.
▶
▶
▶
Các mệnh đề như thế này được thừa nhận là đúng được gọi là
tiên đề.
Bắt đầu từ các tiên đề này, Euclid thiết lập giá trị chân lý của
các mệnh đề khác bằng cách đưa ra “chứng minh”.
Chứng minh là một dãy các lập luận logic từ tập tiên đề dẫn
đến mệnh đề cần chứng minh.
16 / 37
Một số thuật ngữ cho mệnh đề
▶
Mệnh đề đúng và quan trọng gọi là định lý.
Bổ đề là mệnh đề chuẩn bị có ích để chứng minh các mệnh
đề khác.
Hệ quả là một mệnh đề mà chứng minh nó chỉ cần vài bước
từ một định lý.
▶
▶
17 / 37
Hệ tiên đề của chúng ta
▶
Về cơ bản, toán học hiện đại dựa trên hệ tiên đề ZFC
(Zermelo-Fraekel with Choice) cùng với một vài quy tắc suy
luận logic.
▶
▶
Tuy nhiên, chúng quá tối giản. Ví dụ, một chứng minh hình
thức trong ZFC cho 2 + 2 = 4 cần nhiều hơn 20, 000 bước lập
luận!
Trong môn học này, ta thừa nhận mọi sự kiện trong toán
“phổ thông” như tiên đề.
18 / 37
Suy luận logic
▶
Luật Modus Ponens:
P, P ⇒ Q
Q
(Một chứng minh của P và một chứng minh P suy ra Q là
một chứng minh của Q)
▶
▶
Luật
P ⇒ Q, Q ⇒ R
P ⇒ R
Luật
¬P ⇒ ¬Q
Q ⇒ P
19 / 37
Không phải luật
¬P ⇒ ¬Q
P ⇒ Q
ꢁ
Ví dụ
▶
Nếu 4 là số nguyên tố, thì “tôi không biết bay”.
Nếu 4 không phải số nguyên tố, thì “tôi biết bay”.
ꢀ
▶
ꢁ.
20 / 37
Tải về để xem bản đầy đủ
37 trang
26/04/2022
3940
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 1: Phương pháp chứng minh - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_bai_phuong_phap_chung_minh_tran_vinh.pdf
