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)

ppt35 trang | Chia sẻ: tlsuongmuoi | Lượt xem: 2122 | Lượt tải: 0download
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 Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H. Rosen Module #15: Chứng minh qui nạp Inductive 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) n0 (P(n)P(n+1)) n0 P(n) “The First Principle of Mathematical Induction” “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 nN, nếu domino #n đổ, thì domino #n+1 cũng sẽ đổ. Kết luận: Mọi dominoes đều đổ xuống! Note: this works even if there are infinitely many dominoes! Lập luận qui tắc qui nạp C/m rằng k0 P(k) là khẳng định đúng: Cho trước bất kỳ k0, áp dụng suy luận n0 (P(n)P(n+1)) dễ dàng suy ra rằng n0 (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 n2. Assume 2kn: 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:

  • pptbai_15_induction_4356.ppt
Tài liệu liên quan