Chứng minh qui nạp Inductive Proofs
Kỹ thuật mạnh dùng nhiều để chứng minh rằng vị từ P(n) là đúng đối với mỗi số tự nhiên n, không quan trọng lớn như thế nào.
ãBản chất nguyên lý “hiệu ứng domino”.
ãDựa trên luật suy diễn của logic vị từ:
P(0)
"n³0 (P(n)®P(n+1))
\"n³0 P(n)
35 trang |
Chia sẻ: tlsuongmuoi | Lượt xem: 2132 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Chứng minh qui nạp Inductive Proofs, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Module #15:Chứng minh qui nạpInductive Proofs Rosen 5th ed., §3.3 ~11 slides, ~1 lecture §3.3: Qui nạp toán học Kỹ thuật mạnh dùng nhiều để chứng minh rằng vị từ P(n) là đúng đối với mỗi số tự nhiên n, không quan trọng lớn như thế nào. Bản chất nguyên lý “hiệu ứng domino”. Dựa trên luật suy diễn của logic vị từ: P(0)n0 (P(n)P(n+1))n0 P(n) “The First Principleof MathematicalInduction” “Hiệu ứng Domino” 0 1 2 3 4 5 6 … Giả thiết #1: Domino #0 đổ. Giả thiết #2: Với mọi nN,nếu domino #n đổ, thì domino #n+1 cũng sẽ đổ. Kết luận: Mọi dominoes đều đổ xuống! Note: this workseven if thereare infinitelymany dominoes! Lập luận qui tắc qui nạp C/m rằng k0 P(k) là khẳng định đúng:Cho trước bất kỳ k0, áp dụng suy luận n0 (P(n)P(n+1)) dễ dàng suy ra rằng n0 (n0, n0, prove P(n)P(n+1). Assuming n1 can be written as a product pi = p1p2…ps of some series of s prime numbers. Let P(n)=“n has that property” Base case: n=2, let s=1, p1=2. Inductive step: Let n2. Assume 2kn: P(k). Consider n+1. If it’s prime, let s=1, p1=n+1.Else n+1=ab, where 1= 8 xu có thể dán bằng các tem 3 xu và 5 xu Chứng minh: phân trường hợp Không có nghiệm nguyên dương. G/s có:a0 nhỏ nhất là thành phần nghiệm a0 chẵn, a0 = 2a1, suy ra a1 nhỏ hơn a0, mâu thuẫn giả thuyết => không có nghiệm
Các file đính kèm theo tài liệu này:
- bai_15_induction_4356.ppt