Quy Nạp Toán Học – Wikipedia Tiếng Việt

Quy nạp toán học là một phương pháp chứng minh toán học dùng để chứng minh một mệnh đề về bất kỳ tập hợp nào được xếp theo thứ tự. Thông thường nó được dùng để chứng minh mệnh đề áp dụng cho tập hợp tất cả các số tự nhiên.

Quy nạp toán học là một hình thức chứng minh trực tiếp, thường được thực hiện theo hai bước. Khi cố gắng để chứng minh một mệnh đề là đúng cho tập hợp các số tự nhiên, bước đầu tiên, được gọi là bước cơ sở, là chứng minh mệnh đề đưa ra là đúng với số tự nhiên đầu tiên. Bước thứ hai, được gọi là bước quy nạp, là chứng minh rằng, nếu mệnh đề được giả định là đúng cho bất kỳ số tự nhiên nào đó, thế thì nó cũng đúng cho số tự nhiên tiếp theo. Sau khi chứng minh hai bước này, các quy tắc suy luận khẳng định mệnh đề là đúng cho tất cả các số tự nhiên. Trong thuật ngữ phổ biến, sử dụng phương pháp nói trên được gọi là sử dụng nguyên lý quy nạp toán học.

Phương pháp này có thể được mở rộng để chứng minh các mệnh đề về các cấu trúc được thiết lập tổng quát hơn, chẳng hạn như cây; quá trình tổng quát này, được gọi là quy nạp cấu trúc, được sử dụng trong logic toán và khoa học máy tính. Quy nạp toán học theo nghĩa mở rộng này có quan hệ chặt chẽ với đệ quy. Quy nạp toán học, trong một số hình thức, là nền tảng của tất cả các phép chứng minh tính đúng đắn của các chương trình máy tính.[1]

Mặc dù tên của nó là gần giống với lập luận quy nạp, quy nạp toán học không được nhầm lẫn như là một phương pháp của lập luận quy nạp. Quy nạp toán học là một quy tắc suy luận được sử dụng trong chứng minh. Trong toán học, chứng minh bao gồm những phép sử dụng quy nạp toán học là những ví dụ của suy diễn logic, và các lập luận quy nạp bị loại ra khỏi phép chứng minh.[2]

Mô tả

[sửa | sửa mã nguồn]

Hình thức đơn giản và phổ biến nhất của phương pháp quy nạp toán học suy luận rằng một mệnh đề liên quan đến một số tự nhiên n cũng đúng với tất cả các giá trị của n. Cách chứng minh bao gồm hai bước sau:

1. Bước cơ sở: chứng minh rằng mệnh đề đúng với số tự nhiên đầu tiên n. Thông thường, n = 0 hoặc n = 1, hiếm khi có n = -1 (mặc dù không phải là một số tự nhiên, phần mở rộng của các số tự nhiên đến -1 vẫn áp dụng được)
2. Bước quy nạp: chứng minh rằng, nếu mệnh đề được dùng cho một số số tự nhiên n, sau đó cũng đúng với n + 1. Giả thiết ở bước quy nạp rằng mệnh đề đúng với các số n được gọi là giả thiết quy nạp. Để thực hiện bước quy nạp, phải giả sử giả thiết quy nạp là đúng và sau đó sử dụng giả thiết này để chứng minh mệnh đề với n + 1.

Việc n = 0 hay n = 1 phụ thuộc vào định nghĩa của số tự nhiên. Nếu 0 được coi là một số tự nhiên, bước cơ sở được đưa ra bởi n = 0. Nếu, mặt khác, 1 được xem như là số tự nhiên đầu tiên, bước hợp cơ sở được đưa ra với n = 1.

Ví dụ

[sửa | sửa mã nguồn]

Quy nạp toán học có thể được sử dụng để chứng minh rằng mệnh đề P(n) sau, đúng với tất cả số tự nhiên n.

0 + 1 + 2 + ⋯ + n = n ( n + 1 ) 2 . {\displaystyle 0+1+2+\cdots +n={\frac {n(n+1)}{2}}\,.}

P(n) đưa ra một công thức cho tổng các số tự nhiên nhỏ hơn hoặc bằng số n. Cách chứng minh P(n) đúng với mỗi số tự nhiên n như sau.

Bước cơ sở: Chứng minh rằng mệnh đề đúng với n = 1. Ta có P(1) bằng:

1 = 1 ⋅ ( 1 + 1 ) 2 . {\displaystyle 1={\frac {1\cdot (1+1)}{2}}\,.}

Ở vế trái của phương trình, số duy nhất là 1, và do đó, phía bên tay trái là chỉ đơn giản là bằng 1. Vế phải của phương trình, 1·(1 + 1)/2 = 1. Hai vế bằng nhau, nên mệnh đề đúng với n=1. Vì vậy P(1) là đúng.

Bước quy nạp: Chứng minh rằng nếu P ( k ) đúng, P(k+1) cũng đúng. Điều này có thể được thực hiện như sau.

Giả sử P(k) đúng (với một số giá trị k). Sau đó phải chứng minh rằng P(k + 1) cũng đúng:

( 0 + 1 + 2 + ⋯ + k ) + ( k + 1 ) = ( k + 1 ) ( ( k + 1 ) + 1 ) 2 . {\displaystyle (0+1+2+\cdots +k)+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.}

Sử dụng giả thiết quy nạp rằng P(k) đúng, vế trái có thể viết thành:

k ( k + 1 ) 2 + ( k + 1 ) . {\displaystyle {\frac {k(k+1)}{2}}+(k+1)\,.}

Có thể biến đổi như sau:

k ( k + 1 ) 2 + ( k + 1 ) = k ( k + 1 ) + 2 ( k + 1 ) 2 = ( k + 1 ) ( k + 2 ) 2 = ( k + 1 ) ( ( k + 1 ) + 1 ) 2 {\displaystyle {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}\end{aligned}}}

Vì vậy P(k + 1) cũng đúng.

Vì cả bước cơ sở và bước quy nạp đã được thực hiện, mệnh đề P(n) đúng với mọi số tự nhiên n

Xem thêm

[sửa | sửa mã nguồn]

• Đệ quy
• Quy nạp cấu trúc
• Quy nạp siêu hạn

Tham khảo

[sửa | sửa mã nguồn]

1. ^ Anderson, Robert B. (1979). Proving Programs Correct. New York: John Wiley & Sons. tr. 1. ISBN 0471033952.
2. ^ Suber, Peter. "Mathematical Induction". Earlham College. Bản gốc lưu trữ ngày 24 tháng 5 năm 2011. Truy cập ngày 26 tháng 3 năm 2011.

Sách tham khảo

[sửa | sửa mã nguồn]

Giới thiệu

[sửa | sửa mã nguồn]

• Franklin, J.; A. Daoud (2011). Proof in Mathematics: An Introduction. Sydney: Kew Books. ISBN 0-646-54509-4. (Ch. 8.)
• Hazewinkel, Michiel, biên tập (2001), "Mathematical induction", Bách khoa toàn thư Toán học, Springer, ISBN 978-1-55608-010-4
• Hermes, Hans (1973). Introduction to Mathematical Logic. Hochschultext. London: Springer. ISBN 3540058192. ISSN 1431-4657.
• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (ấn bản thứ 3). Addison-Wesley. ISBN 0-201-89683-4. (Section 1.2.1: Mathematical Induction, pp. 11–21.)
• Kolmogorov, Andrey N.; Sergei V. Fomin (1975). Introductory Real Analysis. Silverman, R. A. (trans., ed.). New York: Dover. ISBN 0-486-61226-0. (Section 3.8: Transfinite induction, pp. 28–29.)

Lịch sử

[sửa | sửa mã nguồn]

• Acerbi, F. (2000). "Plato: Parmenides 149a7-c3. A Proof by Complete Induction?". Archive for History of Exact Sciences. Quyển 55. tr. 57–76. doi:10.1007/s004070000020.
• Bussey, W. H. (1917). "The Origin of Mathematical Induction". The American Mathematical Monthly. Quyển 24 số 5. tr. 199–207. doi:10.2307/2974308. JSTOR 2974308.
• Cajori, Florian (1918). "Origin of the Name "Mathematical Induction"". The American Mathematical Monthly. Quyển 25 số 5. tr. 197–201. doi:10.2307/2972638. JSTOR 2972638.
• Fowler D. (1994). "Could the Greeks Have Used Mathematical Induction? Did They Use It?". Physis. Quyển XXXI. tr. 253–265.
• Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Induction". Archives Internationales d'Histoire des Sciences. Quyển 6. tr. 17–37.
• Katz, Victor J. (1998). History of Mathematics: An Introduction. Addison-Wesley. ISBN 0-321-01618-1.
• Peirce, C. S. (1881). "On the Logic of Number". American Journal of Mathematics. Quyển 4 số 1–4. tr. 85–95. doi:10.2307/2369151. JSTOR 2369151. MR 1507856. Reprinted (CP 3.252-88), (W 4:299-309).
• Rabinovitch, Nachum L. (1970). "Rabbi Levi Ben Gershon and the origins of mathematical induction". Archive for History of Exact Sciences. Quyển 6 số 3. tr. 237–248. doi:10.1007/BF00327237.
• Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Sciences (bằng tiếng Pháp). Quyển 9 số 1. tr. 1–21. doi:10.1007/BF00348537.
• Shields, Paul (1997). "Peirce's Axiomatization of Arithmetic". Trong Houser; và đồng nghiệp (biên tập). Studies in the Logic of Charles S. Peirce.
• Unguru, S. (1991). "Greek Mathematics and Mathematical Induction". Physis. Quyển XXVIII. tr. 273–289.
• Unguru, S. (1994). "Fowling after Induction". Physis. Quyển XXXI. tr. 267–272.
• Vacca, G. (1909). "Maurolycus, the First Discoverer of the Principle of Mathematical Induction". Bulletin of the American Mathematical Society. Quyển 16 số 2. tr. 70–73. doi:10.1090/S0002-9904-1909-01860-9.
• Yadegari, Mohammad (1978). "The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)". Isis. Quyển 69 số 2. tr. 259–262. doi:10.1086/352009. JSTOR 230435.

Bài viết liên quan đến triết học này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.

• x
• t
• s

Bài viết liên quan đến toán học này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.

• x
• t
• s

x t s Logic
Tổng quan Lịch sử
Lĩnh vực	Khoa học máy tính Suy luận Triết học logic Bằng chứng Ngữ nghĩa học Cú pháp Các loại logic Cổ điển Thông thường Tư duy phản biện Lý trí Toán Phi cổ điển Triết học Lý thuyết Metalogic Metamathematics Tập hợp
Căn cứ	Bẳt chước Mâu thuẫn Nghịch lý Suy diễn logic Định nghĩa Miêu tả Hình thức Quy nạp Chứng minh Sự thật logic Tên gọi Tiền đề Xác suất Tham khảo Khẳng định Thay thế Chân lý Hợp lý
Danh sách	chủ đề Logic toán Đại số Boole Lý thuyết tập hợp khác Nhà logic học Quy tắc suy luận Nghịch lý Ngụy biện Biểu tượng logic
Cổng thông tin Triết học Thể loại

x t s Logic toán
Chung	Ngôn ngữ hình thức Formation rule Hệ hình thức Hệ suy luận Chứng minh toán học Chứng minh hình thức Ngữ nghĩa hình thức (logic) Well-formed formula Tập hợp Phần tử (toán học) Lớp (lý thuyết tập hợp) Classical logic Tiên đề Natural deduction Rule of inference Quan hệ (toán học) Định lý toán học Logical consequence Hệ tiên đề Lý thuyết hình thái Symbol (formal) Syntax (logic) Lý thuyết (logic toán)
Thuật ngữ logic	Mệnh đề toán học Suy luận Luận cứ logic Validity Cogency Tam đoạn luận Square of opposition Sơ đồ Venn
Propositional calculusĐại số Boole	Boolean functions Phép tính mệnh đề Công thức mệnh đề Logical connectives Truth tables
Logic vị từ	Logic bậc nhất Lượng từ (logic) Predicate (mathematical logic) Logic bậc hai Monadic predicate calculus
Naive set theory	Tập hợp Tập hợp rỗng Enumeration Extensionality Tập hợp hữu hạn Tập hợp vô hạn Tập hợp con Tập lũy thừa Tập hợp đếm được Tập hợp không đếm được Recursive set Tập xác định Range (mathematics) Ánh xạ Song ánh Đơn ánh Toàn ánh Hàm số Phép toán hai ngôi Cặp được sắp
Lý thuyết tập hợp	Nền tảng toán học Lý thuyết tập hợp Zermelo–Fraenkel Tiên đề chọn General set theory Lý thuyết tập hợp Kripke–Platek Lý thuyết tập hợp Von Neumann–Bernays–Gödel Lý thuyết tập hợp Morse–Kelley Lý thuyết tập hợp Tarski–Grothendieck Phép đẳng cấu
Lý thuyết mô hình	Cấu trúc (logic toán) Interpretation (logic) Non-standard model Lý thuyết mô hình hữu hạn Giá trị chân lý Validity
Lý thuyết chứng minh	Formal proof Deductive system Hệ hình thức Định lý toán học Hệ quả logic Rule of inference Syntax (logic)
Lý thuyết tính toán	Đệ quy Tập đệ quy Tập tuần tự đệ quy Bài toán quyết định Church–Turing thesis Hàm tính được Primitive recursive function

Cơ sở dữ liệu tiêu đề chuẩn
Quốc tế	GND
Quốc gia	Hoa Kỳ Israel
Khác	Encyclopedia of Modern Ukraine Yale LUX