Chứng minh bằng mâu thuẫn

Trong logic và toán học, phép chứng minh bằng mâu thuẫn là một dạng bằng chứng xác lập sự thật hoặc tính hợp lệ của một mệnh đề, bằng cách chỉ ra rằng giả sử mệnh đề là sai dẫn đến mâu thuẫn. Chứng minh bằng mâu thuẫn còn được gọi là chứng minh gián tiếp, chứng minh phản chứng, chứng minh bằng cách giả sử ngược lại và reductio ad impossibile.^[1]

Nguyên tắc

Bản mẫu:Chú thích trong đoạn Chứng minh bằng mâu thuẫn dựa trên luật không mâu thuẫn, được chính thức hóa như một nguyên tắc siêu hình bởi Aristotle. Không mâu thuẫn cũng là một định lý trong logic mệnh đề. Điều này khẳng định rằng một khẳng định hoặc tuyên bố toán học không thể vừa là đúng vừa là sai. Điều đó có nghĩa là, một mệnh đề Q và phủ định của nó $\neg$ Q ("không- Q ") không thể cùng đúng. Trong một chứng minh bằng mâu thuẫn, người ta chỉ ra rằng việc giả định tuyên bố cần được chứng minh là sai sẽ dẫn đến một mâu thuẫn (tức là một mệnh đề Q và phủ định của nó cùng đúng). Nó có dạng của một lập luận phản chứng, và thường được tiến hành như sau:

Mệnh đề được chứng minh, P, được coi là sai. Vậy $\neg$ P đúng.
Sau đó ta chỉ ra rằng $\neg$ P dẫn đến hai khẳng định mâu thuẫn lẫn nhau, Q và $\neg$ Q.
Vì Q và $\neg$ Q không thể cả hai đều đúng, giả định rằng P là sai phải là sai, vì vậy P phải là đúng.