Chứng minh phản chứng — Phương pháp & ví dụ kinh điển

Chứng minh phản chứng chứng minh một mệnh đề bằng cách giả sử điều ngược lại và chỉ ra rằng giả sử đó dẫn đến điều không thể xảy ra. Nếu lập luận là hợp lệ và mâu thuẫn là thật, thì mệnh đề ban đầu phải đúng.

Phương pháp này hữu ích khi phủ định của mệnh đề cho bạn một dạng cụ thể để làm việc. Một trường hợp kinh điển là chứng minh $\sqrt{2}$ là số vô tỉ: khi giả sử nó là số hữu tỉ, bạn có thể viết nó dưới dạng phân số và lần theo các hệ quả.

Chứng minh phản chứng hoạt động như thế nào

Giả sử mệnh đề bạn muốn chứng minh là $P$.

Trong chứng minh phản chứng, bạn bắt đầu bằng cách giả sử $P$ là sai. Sau đó, bạn lập luận từ giả sử đó cho đến khi gặp một mâu thuẫn, chẳng hạn như:

$$1 = 0$$

hoặc xung đột với một định nghĩa đã biết, hoặc một phát biểu không thể đồng thời đúng với một bước trước đó.

Đến lúc đó, phủ định của $P$ không thể đúng, nên $P$ phải đúng.

Điều kiện then chốt là mâu thuẫn phải xuất phát từ lập luận hợp lệ và các sự thật đã được chấp nhận. Một kết quả chỉ trông có vẻ lạ là chưa đủ. Nó phải là điều không thể xảy ra theo các định nghĩa hoặc định lý bạn đang dùng.

Khi nào nên dùng chứng minh phản chứng

Chứng minh phản chứng hiệu quả nhất khi điều ngược lại của một mệnh đề có cấu trúc chặt chẽ. Điều này thường xuất hiện trong lý thuyết số, các chứng minh về tính bất khả, và một số bài toán tồn tại.

Ví dụ, nếu bạn muốn chứng minh một số là vô tỉ, thì giả sử nó là hữu tỉ sẽ cho bạn dạng phân số để làm việc. Cấu trúc bổ sung đó thường khiến việc tìm ra mâu thuẫn dễ hơn so với chứng minh trực tiếp.

Phương pháp này kém hữu ích hơn khi đã có một chứng minh trực tiếp ngắn gọn. Phản chứng là một phương pháp hợp lệ, nhưng nó nên làm sáng tỏ lập luận thay vì khiến lời giải dài hơn không cần thiết.

Ví dụ chi tiết: vì sao $\sqrt{2}$ là số vô tỉ

Một chứng minh phản chứng kinh điển cho thấy $\sqrt{2}$ là số vô tỉ.

Bắt đầu bằng cách giả sử điều ngược lại:

$$\sqrt{2} \text{ là số hữu tỉ.}$$

Nếu điều đó đúng, thì $\sqrt{2}$ có thể được viết thành

$$\sqrt{2} = \frac{a}{b}$$

trong đó $a$ và $b$ là các số nguyên, $b \neq 0$, và phân số đang ở dạng tối giản.

Bây giờ bình phương hai vế:

$$2 = \frac{a^2}{b^2}$$

nên

$$a^2 = 2b^2.$$

Điều này cho biết $a^2$ là số chẵn. Từ đó suy ra $a$ cũng là số chẵn, vì bình phương của một số nguyên lẻ là số lẻ. Vậy ta viết

$$a = 2k$$

với một số nguyên $k$ nào đó.

Thay vào $a^2 = 2b^2$:

$$(2k)^2 = 2b^2$$ $$4k^2 = 2b^2$$ $$2k^2 = b^2.$$

Bây giờ $b^2$ là số chẵn, nên $b$ cũng là số chẵn.

Nhưng khi đó cả $a$ và $b$ đều chẵn. Điều đó có nghĩa là cả hai đều chia hết cho $2$, mâu thuẫn với giả sử rằng $\frac{a}{b}$ đã ở dạng tối giản.

Vậy giả sử ban đầu là sai. Do đó $\sqrt{2}$ là số vô tỉ.

Vì sao mâu thuẫn này có tính quyết định

Mâu thuẫn ở đây không chỉ là “có gì đó sai sai”. Nó rất cụ thể:

1. Giả sử nói rằng $\sqrt{2} = \frac{a}{b}$ ở dạng tối giản.
2. Các phép biến đổi đại số cho thấy cả $a$ và $b$ đều phải chẵn.
3. Một phân số không thể vừa ở dạng tối giản vừa có cả tử số và mẫu số cùng chia hết cho $2$.

Sự xung đột trực tiếp đó chính là mâu thuẫn.

Những lỗi thường gặp trong chứng minh phản chứng

Một lỗi phổ biến là giả sử điều ngược lại quá mơ hồ. Bạn cần đúng phủ định của mệnh đề, chứ không phải một phát biểu gần giống chỉ vì nghe có vẻ tương tự.

Một lỗi khác là đi đến mâu thuẫn do một bước biến đổi đại số sai. Trong trường hợp đó, mâu thuẫn chỉ chứng minh rằng phép biến đổi đại số đã sai, chứ không chứng minh mệnh đề ban đầu là đúng.

Lỗi thứ ba là không nêu rõ sự thật nào đang bị mâu thuẫn. Một chứng minh tốt sẽ chỉ ra xung đột một cách tường minh: quy tắc chẵn lẻ, một định nghĩa, điều kiện cực tiểu, hoặc một định lý đã được chứng minh trước đó.

Cũng rất dễ che giấu lập luận yếu bằng cụm từ “đây là mâu thuẫn”. Nếu bạn không thể chỉ ra chính xác sự thật nào đã bị vi phạm, thì chứng minh đó có lẽ vẫn chưa hoàn chỉnh.

Một mẫu chứng minh phản chứng đơn giản

Với nhiều bài chứng minh nhập môn, cấu trúc thường như sau:

1. Giả sử mệnh đề là sai.
2. Chuyển giả sử đó thành một dạng cụ thể.
3. Suy ra các hệ quả từng bước một.
4. Đi đến mâu thuẫn với một sự thật đã biết.
5. Kết luận rằng giả sử ban đầu là sai, nên mệnh đề gốc phải đúng.

Nếu bước 2 yếu, thì toàn bộ chứng minh thường sẽ mơ hồ. Những chứng minh phản chứng mạnh nhất thường xuất phát từ việc biến phủ định thành một điều gì đó rất cụ thể.

Hãy thử một chứng minh phản chứng tương tự

Hãy thử mệnh đề “không tồn tại số hữu tỉ dương nhỏ nhất”. Giả sử có một số như vậy, gọi nó là $r$, rồi xét điều gì xảy ra với $\frac{r}{2}$. Nếu bạn muốn kiểm tra lập luận của mình từng bước trong một bài tương tự, hãy thử tự làm phiên bản của riêng bạn trong GPAI Solver và so sánh từng mệnh đề với mâu thuẫn mà bạn đang hướng tới.