Toán thi và Giải toán

Phản chứng

Kỹ thuật chứng minh giả sử điều trái với kết luận cần chứng minh rồi suy ra mâu thuẫn.

Trực giácGiả sử điều trái, rồi xem nó sụp đổ

Giả sử một thám tử muốn chứng minh nghi phạm đã có mặt tại hiện trường vụ án. Thay vì tìm bằng chứng trực tiếp, thám tử nói: "Giả sử nghi phạm không có mặt ở đó. Khi đó anh ta không thể để lại dấu chân này, thứ chỉ mình anh ta mới có thể tạo ra. Nhưng dấu chân lại ở ngay đây — mâu thuẫn. Vậy nghi phạm phải đã có mặt ở đó." Đây chính xác là hình dạng của phản chứng: để chứng minh một mệnh đề $P$ , giả sử điều trái $\neg P$ , theo đúng các hệ quả logic, rồi chỉ ra chúng va chạm với điều đã biết là đúng. Vì giả thiết sai là cách duy nhất dẫn tới kết luận vô lý, $\neg P$ phải sai, nên $P$ đúng.

Đường cong

y=x^2-2

cắt trục hoành đúng tại

x=\sqrt{2}

; chứng minh phản chứng bên dưới cho thấy điểm cắt này không bao giờ có thể là tỉ số của hai số nguyên.

Phổ thôngHình dạng logic của chứng minh phản chứng

Định nghĩa: Phản chứng

Để chứng minh một mệnh đề $P$ bằng phản chứng, giả sử $\neg P$ (điều trái với $P$ ), rồi từ đó, chỉ dùng các bước logic hợp lệ và sự kiện đã được thiết lập, suy ra một mệnh đề $Q$ cùng với phủ định của nó $\neg Q$ . Vì $Q \wedge \neg Q$ luôn sai, giả thiết $\neg P$ dẫn tới nó phải sai, nên $P$ đúng.

\neg P \Rightarrow (Q \wedge \neg Q)

Ở đây $P$ là mệnh đề ta muốn chứng minh, và $Q$ là mệnh đề bất kỳ mà cả tính đúng lẫn tính sai của nó ta đều suy ra được từ $\neg P$ — thường $Q$ là một sự kiện đã biết là đúng (như " $\gcd(p,q)=1$ ") mà ta vô tình suy ra phủ định của nó. Một khi $\neg P \Rightarrow (Q \wedge \neg Q)$ được thiết lập và $Q \wedge \neg Q$ là bất khả, logic buộc chính $\neg P$ phải là bất khả, tức $P$ đúng.

\sqrt{2} = \frac{p}{q}, \quad \gcd(p,q)=1

Dòng thứ hai này là giả thiết cụ thể dùng để mở đầu chứng minh kinh điển rằng $\sqrt{2}$ vô tỉ: ở đây $p$ và $q$ là các số nguyên với $q \neq 0$ , và yêu cầu $\gcd(p,q)=1$ nghĩa là phân số $\frac{p}{q}$ đã được viết ở dạng tối giản. Chứng minh (nêu đầy đủ bên dưới) cho thấy giả thiết này buộc cả $p$ và $q$ đều chẵn, mâu thuẫn với $\gcd(p,q)=1$ .

So sánh các chiến lược chứng minh
Phương pháp	Giả thiết	Mục tiêu
Chứng minh trực tiếp	$P$	Suy ra $Q$ trực tiếp từ $P$ bằng các sự kiện đã biết
Phản chứng	$\neg P$	Suy ra cả $Q$ và $\neg Q$ từ $\neg P$
Xuống thang vô hạn	Tồn tại một phản ví dụ nhỏ nhất	Xây một phản ví dụ nhỏ hơn thực sự, mâu thuẫn với tính nhỏ nhất

Đại họcHai chứng minh phản chứng kinh điển

Định lý: Tính vô tỉ của

\sqrt{2}

$\sqrt{2}$ là số vô tỉ, tức không tồn tại các số nguyên $p,q$ với $q \neq 0$ sao cho $\sqrt{2} = \frac{p}{q}$ .

Vì sao đúng?

Không có cách đại số trực tiếp nào để chỉ ra một số không phải là tỉ số của các số nguyên, vì điều đó có nghĩa phải kiểm tra vô hạn phân số; phản chứng né tránh điều này bằng cách giả sử tồn tại một phân số như vậy ở dạng tối giản rồi khai thác đúng giả thiết đó để tìm ra một sự kiện chẵn lẻ bất khả.

Chứng minh

Giả sử, để phản chứng, rằng $\sqrt{2}$ là số hữu tỉ. Khi đó ta có thể viết $\sqrt{2} = \frac{p}{q}$ với các số nguyên $p,q$ và $q \neq 0$ , và bằng cách rút gọn thừa số chung ta có thể giả sử $\gcd(p,q)=1$ (phân số ở dạng tối giản).

Bình phương hai vế cho $2 = \frac{p^2}{q^2}$ , nên $p^2 = 2q^2$ . Điều này có nghĩa $p^2$ là số chẵn. Vì bình phương của số lẻ là số lẻ, nên $p$ phải là số chẵn; viết $p = 2k$ với số nguyên $k$ nào đó.

Thay lại, $(2k)^2 = 2q^2$ , nên $4k^2 = 2q^2$ , rút gọn thành $q^2 = 2k^2$ . Điều này có nghĩa $q^2$ là số chẵn, nên bằng cùng lập luận $q$ cũng phải là số chẵn.

Nhưng giờ cả $p$ và $q$ đều chẵn, nên $2$ chia hết cả hai, mâu thuẫn với giả thiết $\gcd(p,q)=1$ . Mâu thuẫn này cho thấy giả thiết ban đầu — rằng $\sqrt{2}$ có thể viết thành $\frac{p}{q}$ — phải sai. Do đó $\sqrt{2}$ là số vô tỉ.

Định lý: Chứng minh của Euclid về vô hạn số nguyên tố

Có vô hạn số nguyên tố.

Vì sao đúng?

Không thể liệt kê trực tiếp vô hạn số nguyên tố để kiểm tra khẳng định, nên phản chứng thay vào đó giả sử tồn tại một danh sách hữu hạn đầy đủ, rồi từ chính danh sách đó tạo ra một số vạch trần danh sách là chưa đầy đủ.

Chứng minh

Giả sử, để phản chứng, rằng chỉ có hữu hạn số nguyên tố, và cho $p_1, p_2, \dots, p_n$ là danh sách đầy đủ tất cả chúng.

Xét số $N = p_1 p_2 \cdots p_n + 1$ . Vì $N > 1$ , nó phải có ít nhất một ước nguyên tố; gọi là $p$ (mọi số nguyên lớn hơn $1$ đều có một ước nguyên tố).

Theo giả thiết, $p_1, \dots, p_n$ là danh sách tất cả số nguyên tố, nên $p$ phải bằng $p_i$ với $i$ nào đó. Đặc biệt, $p$ chia hết tích $p_1 p_2 \cdots p_n$ .

Nhưng $p$ cũng chia hết $N = p_1 p_2 \cdots p_n + 1$ . Nếu $p$ chia hết cả $p_1 p_2 \cdots p_n$ và $N$ , thì $p$ chia hết hiệu của chúng: $p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1$ .

Không số nguyên tố nào chia hết $1$ , vì mọi số nguyên tố đều lớn hơn $1$ . Đây là mâu thuẫn. Do đó giả thiết ban đầu — rằng chỉ có hữu hạn số nguyên tố — phải sai, nên có vô hạn số nguyên tố.

Đại họcỨng dụng thực tiễn và Ví dụ minh họa

Phản chứng là công cụ làm việc vượt xa toán thi đấu: các nhà khoa học máy tính dùng nó để chứng minh các kết quả bất khả thi (không thuật toán nào giải được bài toán dừng, không thuật toán sắp xếp so sánh nào vượt $n\log n$ trong trường hợp xấu nhất), các nhà mật mã học dựa vào nó để lập luận rằng phá vỡ một lược đồ sẽ kéo theo giải được một bài toán được tin là khó, và các kỹ sư dùng nó để lập luận các khẳng định bất khả thi liên quan an toàn ("nếu áp suất vượt quá giá trị này, con dấu sẽ hỏng, nhưng con dấu vẫn nguyên vẹn, nên áp suất chưa bao giờ vượt quá"). Xuống thang vô hạn, một biến thể giả sử tồn tại một phản ví dụ nhỏ nhất rồi thu nhỏ nó, đặc biệt phổ biến trong lý thuyết số và các lập luận về tính dừng của thuật toán. Hai ví dụ dưới đây cho thấy phản chứng và xuống thang vô hạn áp dụng vào các bài toán tổ hợp cụ thể.

Ví dụ: Bàn cờ khuyết: một phản chứng trong lát gạch

Một bàn cờ $8 \times 8$ bị cắt bỏ hai ô góc đối diện, còn lại $62$ ô. Chứng minh bàn cờ này không thể được phủ kín hoàn toàn bởi $31$ quân domino, mỗi quân phủ đúng $2$ ô kề nhau.

Lời giải

Giả sử, để phản chứng, rằng tồn tại một cách lát như vậy bằng $31$ quân domino.

Tô màu bàn cờ theo kiểu xen kẽ đen trắng thông thường, nên nó có $32$ ô đen và $32$ ô trắng. Mỗi quân domino, vì phủ hai ô kề nhau, luôn phủ đúng một ô đen và một ô trắng (các ô kề nhau luôn khác màu).

Do đó, một cách lát dùng $31$ quân domino sẽ phủ đúng $31$ ô đen và $31$ ô trắng — tổng $62$ ô, chia đều theo màu.

Tuy nhiên, hai góc đối diện của một bàn cờ chuẩn luôn cùng màu (đây là tính chất của cách tô màu chuẩn). Xóa chúng đi làm mất $2$ ô của một màu, còn lại $30$ ô màu đó và $32$ ô màu kia.

Điều này có nghĩa bàn cờ thực tế có $30$ ô một màu và $32$ ô màu kia, không thể chia thành $31$ -và- $31$ bởi bất kỳ cách lát nào. Điều này mâu thuẫn với số đếm ở Bước 3 (đúng $31$ mỗi màu), nên cách lát giả sử không thể tồn tại.

Ví dụ: Xuống thang vô hạn: không có nghiệm không tầm thường của $a^2=2b^2$

Dùng xuống thang vô hạn để chứng minh phương trình $a^2 = 2b^2$ không có nghiệm nguyên dương $a,b$ .

Lời giải

Giả sử, để phản chứng, tồn tại một nghiệm nguyên dương. Trong tất cả các nghiệm nguyên dương $(a,b)$ , chọn một nghiệm có $b$ nhỏ nhất có thể — điều này khả thi vì các số nguyên dương được sắp thứ tự tốt (mọi tập khác rỗng các số nguyên dương đều có phần tử nhỏ nhất).

Từ $a^2 = 2b^2$ , vế phải là số chẵn, nên $a^2$ chẵn, và do đó $a$ phải chẵn (bình phương của số lẻ là số lẻ). Viết $a = 2a_1$ với $a_1$ là số nguyên dương nào đó.

Thay vào, $(2a_1)^2 = 2b^2$ cho $4a_1^2 = 2b^2$ , nên $b^2 = 2a_1^2$ . Bằng lập luận tương tự như trên, $b^2$ chẵn, nên $b$ chẵn; viết $b = 2b_1$ .

Thay tiếp, $2a_1^2 = (2b_1)^2 = 4b_1^2$ , nên $a_1^2 = 2b_1^2$ . Điều này có nghĩa $(a_1,b_1)$ cũng là một nghiệm nguyên dương của cùng phương trình $a_1^2=2b_1^2$ , và vì $b = 2b_1$ , ta có $b_1 = b/2 < b$ .

Điều này mâu thuẫn với việc chọn $(a,b)$ là nghiệm có $b$ nhỏ nhất có thể, vì $(a_1,b_1)$ là nghiệm có tọa độ thứ hai còn nhỏ hơn. Mâu thuẫn này cho thấy không thể tồn tại nghiệm nguyên dương nào của $a^2=2b^2$ .

Phản chứng chứng minh một mệnh đề $P$ bằng cách giả sử $\neg P$ rồi suy ra mâu thuẫn dạng:

Trong chứng minh kinh điển rằng $\sqrt{2}$ vô tỉ, giả sử $\sqrt{2} = \frac{p}{q}$ ở dạng tối giản rồi bình phương cho $p^2 = 2q^2$ . Kết luận tức thì về $p$ là gì?

Trong chứng minh của Euclid, giả sử số nguyên tố $p_1,\dots,p_n$ là tất cả số nguyên tố, số $N=p_1p_2\cdots p_n+1$ dẫn tới mâu thuẫn vì:

Với bàn cờ khuyết bị bỏ hai góc đối diện, mâu thuẫn trong chứng minh lát domino xảy ra vì một cách lát cần: