Mệnh đề và suy luận

"Không phải cả hai" luôn tách thành hai trường hợp đầy đủ — ít nhất một cái sai — và đó chính là tuyển của các phủ định; đây là bộ khung logic đằng sau việc phủ định mệnh đề "với mọi" và đằng sau các mạch số biến cổng AND thành cổng OR của các đầu vào đã đảo (tương đương NAND/NOR).

Ta chứng minh $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ bằng cách xét đầy đủ bốn trường hợp giá trị chân lý của $P$ và $Q$, vì một công thức mệnh đề được xác định hoàn toàn bởi bảng chân trị của nó.

Trường hợp $P=1, Q=1$: $P \wedge Q = 1$, nên $\neg(P\wedge Q)=0$. Đồng thời $\neg P=0$ và $\neg Q=0$, nên $(\neg P)\vee(\neg Q)=0$. Hai vế bằng nhau, cùng là $0$.

Trường hợp $P=1, Q=0$: $P\wedge Q=0$, nên $\neg(P\wedge Q)=1$. Đồng thời $\neg P=0$, $\neg Q=1$, nên $(\neg P)\vee(\neg Q)=1$. Hai vế bằng nhau, cùng là $1$.

Trường hợp $P=0, Q=1$: theo tính đối xứng với trường hợp trên, $\neg(P\wedge Q)=1$ và $(\neg P)\vee(\neg Q)=1$. Hai vế khớp nhau.

Trường hợp $P=0, Q=0$: $P\wedge Q=0$, nên $\neg(P\wedge Q)=1$. Đồng thời $\neg P=1$, $\neg Q=1$, nên $(\neg P)\vee(\neg Q)=1$. Hai vế khớp nhau.

Cả bốn dòng của bảng chân trị đều khớp, vậy $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ là một hằng đúng (tautology, đúng với mọi phép gán). Luật thứ hai $\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$ suy ra bằng cách kiểm bốn dòng tương tự, hoặc bằng đại số: thay $P, Q$ trong luật thứ nhất bởi $\neg P, \neg Q$ rồi phủ định hai vế, dùng $\neg\neg X \equiv X$.

Một mệnh đề kéo theo và mệnh đề phản đảo của nó luôn mang cùng lượng thông tin — "nếu trời mưa thì mặt đất ướt" đúng y hệt như "nếu mặt đất không ướt thì trời không mưa". Sự tương đương này là cơ sở logic cho phép chứng minh phản đảo, một trong hai kỹ thuật chứng minh gián tiếp phổ biến nhất (kỹ thuật kia là phản chứng).

Ta chứng minh $(P \to Q) \equiv (\neg Q \to \neg P)$ bằng cách so sánh bảng chân trị của $P\to Q$ và $\neg Q\to\neg P$ trên cả bốn phép gán.

Trường hợp $P=1, Q=1$: $P\to Q=1$ (giả thiết đúng, kết luận đúng). Đồng thời $\neg Q=0$, nên $\neg Q\to\neg P$ có giả thiết sai, khiến cả mệnh đề kéo theo bằng $1$ bất kể $\neg P$. Hai vế đều bằng $1$.

Trường hợp $P=1, Q=0$: $P\to Q=0$ (giả thiết đúng, kết luận sai là trường hợp duy nhất khiến kéo theo sai). Đồng thời $\neg Q=1$, $\neg P=0$, nên $\neg Q\to\neg P$ có giả thiết đúng, kết luận sai, cho ra $0$. Hai vế đều bằng $0$.

Trường hợp $P=0, Q=1$: $P\to Q=1$ (giả thiết sai khiến kéo theo luôn đúng). Đồng thời $\neg Q=0$, nên $\neg Q\to\neg P=1$ tự động. Hai vế đều bằng $1$.

Trường hợp $P=0, Q=0$: $P\to Q=1$ (giả thiết sai). Đồng thời $\neg Q=1$, $\neg P=1$, nên $\neg Q\to\neg P=1$ (giả thiết đúng, kết luận đúng). Hai vế đều bằng $1$.

Cả bốn dòng khớp nhau, nên $P\to Q$ và $\neg Q\to\neg P$ có cùng bảng chân trị và tương đương logic. Lưu ý điều này khác với đảo $Q\to P$ và phản $\neg P\to\neg Q$, hai mệnh đề này tương đương nhau nhưng nói chung KHÔNG tương đương với kéo theo gốc — một nguồn lỗi lập luận rất hay gặp.