Tính đúng sai của công thức

Khi ghép một số mệnh đề nguyên tử thành một công thức, ta có thể thử xác định cả công thức đó đúng hay sai.

Tính đúng sai của mệnh đề

Trước hết, ta nói rõ giá trị chân lí của mệnh đề là gì. Với một mệnh đề p, ta phải xác định được nó đúng hay sai. Mệnh đề đúng có giá trị chân lí 1, mệnh đề sai có giá trị chân lí 0.

Phép gán giá trị chân lí là một quy tắc e gán cho mỗi mệnh đề giá trị 0 hoặc 1. Viết e(p) nghĩa là ta muốn biết mệnh đề p đúng hay sai. Nếu p là mệnh đề “2 nhân 2 bằng 4” thì e(p) = 1, vì đây là mệnh đề đúng. Nếu q là mệnh đề “Mặt Trời là một hành tinh” thì e(q) = 0, vì Mặt Trời là một ngôi sao. Như vậy e là một hàm số cho biết mệnh đề đúng hay sai.

Cần lưu ý rằng e không phải là một hàm số thần kì biết mọi thứ trên đời. Hàm này hoạt động đúng như ta quy định và không hề biết Mặt Trời là ngôi sao hay hành tinh. Khi bắt đầu tính toán, ta phải khai báo phép gán giá trị chân lí hoạt động thế nào. Nếu ta quy định rằng Mặt Trời là một hành tinh thì ta sẽ có e(q) = 1.

Tính đúng sai của các phép liên kết mệnh đề

Muốn xác định tính đúng sai của một công thức, ta cần biết cách đánh giá tính đúng sai của các phép liên kết mệnh đề. Tức là, khi đã biết e(p) và e(q), các công thức p ∧ q, p ⇒ q, … có giá trị chân lí bằng bao nhiêu.

Mỗi phép liên kết mệnh đề hoạt động khác nhau và dùng cho mục đích khác nhau, nên ta sẽ xét lần lượt từng phép.

Tính đúng sai của phép hội

Phép hội kí hiệu là p ∧ q, đọc là “p và q”. Ví dụ, xét công thức “Việt Nam nằm ở Đông Nam Á và thủ đô của Việt Nam là Hà Nội”. Khi nào cả câu này đúng?

Chính từ “và” giúp ta xác định tính đúng sai. Từ này đòi hỏi cả hai mệnh đề ở bên trái và bên phải đều đúng. Nếu cả hai mệnh đề p và q đều đúng, tức là e(p) = 1 và e(q) = 1, thì cả phép hội cũng đúng. Trong các trường hợp còn lại, khi một trong hai mệnh đề sai hoặc cả hai đều sai, cả công thức sai.

Ví dụ về một phép hội sai: “Sông Hồng là một con sông và sông Hồng chảy qua nước Nga”. Đúng là sông Hồng là một con sông, nhưng sông Hồng không chảy qua nước Nga, nên cả phép hội sai.

Bảng sau tóm tắt điều này:

$$\begin{array}{ccc}p& q& p\wedge q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}$$

Hai cột đầu là giá trị chân lí của các mệnh đề p và q, cột thứ ba là giá trị chân lí của công thức p ∧ q.

Tính đúng sai của phép tuyển

Phép tuyển kí hiệu là p ∨ q, đọc là “p hoặc q”. Ví dụ: “Nước Nga nằm ở châu Âu hoặc ở châu Á.” Khi nào cả câu này đúng?

Với phép tuyển, chỉ cần ít nhất một trong hai khả năng đúng. Từ “hoặc” cho ta lựa chọn: chỉ cần vế trái hoặc vế phải đúng. Điểm khác biệt nhỏ duy nhất so với lời nói hằng ngày là “hoặc” trong logic vẫn đúng khi cả hai mệnh đề cùng đúng. Trong đời thường ta không quen như vậy, ta hay dùng “hoặc” theo nghĩa loại trừ, tức là “hoặc …, hoặc … (chỉ một)”.

Có một câu chuyện cười kinh điển về điều này: một gia đình đến cửa hàng ô tô cũ để chọn xe mới. Người bố nói với người bán: “Nhà tôi quyết định lấy chiếc xe màu xanh dương hoặc chiếc màu đỏ.” Người bán liền bán cho họ cả hai chiếc. Đây là minh hoạ cho sự khác nhau giữa “hoặc” trong logic và “hoặc” trong lời nói: người bố có lẽ muốn chọn đúng một trong hai chiếc, còn người bán coi việc bán cả hai chiếc cũng là một lựa chọn hợp lệ.

Câu về nước Nga ở trên đúng, vì cả hai mệnh đề đều đúng. Câu “số 7 chia hết cho 3 hoặc số 7 là số nguyên tố” đúng, vì 7 là số nguyên tố. Số 7 không chia hết cho 3, nhưng điều đó không ảnh hưởng. Bảng chân trị:

$$\begin{array}{ccc}p& q& p\vee q\\ 1& 1& 1\\ 1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}$$

Tính đúng sai của mệnh đề kéo theo

Mệnh đề kéo theo kí hiệu là p ⇒ q, đọc là “nếu p thì q”. Ví dụ về mệnh đề kéo theo là câu “nếu ăn quá nhiều kem thì ta sẽ bị đau họng”. Khi nào câu này đúng?

Mệnh đề kéo theo là phép liên kết dễ gây nhầm lẫn nhất. Ngay cả trong lời nói hằng ngày, người ta cũng thường hiểu sai mệnh đề kéo theo và nhầm với mệnh đề tương đương. Ta thử trả lời câu hỏi: mệnh đề đảo q ⇒ p có đồng thời đúng không?

Ta biết rằng nếu ăn quá nhiều kem thì ta sẽ bị đau họng. Vậy có đúng là nếu bị đau họng thì ta đã ăn quá nhiều kem không? Chắc chắn là không. Ta có thể bị đau họng vì uống nước đá, vì cảm lạnh hoặc vì một lí do hoàn toàn khác. Mệnh đề đảo không tự động đúng. Nếu p ⇒ q đúng và đồng thời q ⇒ p cũng đúng thì ta có mệnh đề tương đương, xem phần sau.

Một ví dụ khác: “nếu ngày mai trời mưa thì Nam sẽ mang theo ô”. Giờ tôi cho bạn biết rằng Nam đã mang theo ô. Câu hỏi là: hôm đó trời có mưa không? Nhiều người có xu hướng trả lời rằng dĩ nhiên là có, vì Nam đã mang ô theo, mà Nam mang ô khi trời mưa. Nhưng câu ban đầu không nói như vậy!

Thật ra Nam có thể mang ô vì một lí do khác mà ta không hề biết. Chẳng hạn, có thể lần nào đi thăm mẹ vợ Nam cũng mang ô để che nắng cho bà. Hoặc Nam định mua ô mới và muốn đem chiếc ô cũ đi vứt. Đó đều là những lí do chính đáng để Nam mang ô theo dù trời không mưa.

Bây giờ có thể trả lời câu hỏi khi nào mệnh đề kéo theo đúng. Khi cả hai mệnh đề đều đúng, mệnh đề kéo theo chắc chắn đúng: “nếu 42 là số tự nhiên khác 0 thì số đó là số dương”. Cả hai mệnh đề đều đúng nên cả mệnh đề kéo theo đúng. Một ví dụ khác là mệnh đề kéo theo “nếu 42 là số tự nhiên khác 0 thì số đó là số âm”. Mệnh đề kéo theo này sai, vì từ một điều đúng ta lại cố suy ra một điều sai.

Cuối cùng còn các trường hợp mệnh đề thứ nhất sai. Khi đó tính đúng sai của mệnh đề thứ hai không còn quan trọng. Đã xuất phát từ một điều sai thì ta muốn nói gì tiếp cũng được. Đó là những câu kiểu “nếu 1 là số âm thì tôi là ông hoàng hài hước” hay “nếu Hà Nội là một hòn đảo giữa Thái Bình Dương thì Mặt Trời màu xanh dương.” Trong những trường hợp này, mệnh đề kéo theo tự động đúng, đơn giản vì nó xuất phát từ một điều sai. Bảng chân trị:

$$\begin{array}{ccc}p& q& p\Rightarrow q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 0& 1\end{array}$$

Tính đúng sai của mệnh đề tương đương

Mệnh đề tương đương kí hiệu là p ⇔ q, đọc là “p khi và chỉ khi q”. Ví dụ về mệnh đề tương đương: “số x chia hết cho 2 khi và chỉ khi số đó là số chẵn”. Khi nào cả câu này đúng?

Với mệnh đề tương đương, ta đòi hỏi hai mệnh đề gắn bó chặt chẽ đến mức hoặc cả hai cùng đúng, hoặc cả hai cùng sai. Tức là hoặc số x vừa chẵn vừa chia hết cho 2, hoặc không có tính chất nào trong hai tính chất đó. Không thể xảy ra trường hợp x chẵn mà không chia hết cho 2.

Ví dụ: “Minh đọc sách khi và chỉ khi ngồi trên xe buýt.” Để mệnh đề tương đương này đúng thì cứ mỗi lần ngồi trên xe buýt, Minh phải đọc sách. Đồng thời, cứ mỗi lần đọc sách, Minh phải đang ngồi trên xe buýt. Không thể có chuyện Minh đọc sách, chẳng hạn, trên giường.

Có thể diễn đạt mệnh đề tương đương bằng hai mệnh đề kéo theo: p ⇔ q có thể viết lại thành p ⇒ q và q ⇒ p. Bảng chân trị:

$$\begin{array}{ccc}p& q& p\iff q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$

Mệnh đề phủ định

Phép phủ định là phép toán một ngôi. Mệnh đề phủ định kí hiệu là $\bar{p}$ (cách viết trong sách giáo khoa) hoặc ¬p. Phép phủ định đảo ngược khẳng định ban đầu. Với mệnh đề “Lan là ca sĩ”, phép phủ định cho ta mệnh đề “Không phải Lan là ca sĩ”, hay gọn hơn là “Lan không phải là ca sĩ”. Hầu như luôn có thể lập mệnh đề phủ định bằng cách thêm “Không phải …” vào trước mệnh đề.

Phép phủ định đảo ngược giá trị chân lí, tức là biến 0 thành 1 và 1 thành 0. Có thể viết ¬0 = 1 và ¬1 = 0.

Hãy cẩn thận với một số chỗ dễ nhầm. Xét khẳng định “vôi có màu trắng”. Mệnh đề phủ định của nó là gì? Có người có thể nghĩ là “vôi có màu đen”, nhưng điều đó không đúng! Theo quy tắc ở trên, mệnh đề phủ định là “không phải vôi có màu trắng”. Điều đó có nhất thiết nghĩa là vôi phải màu đen không? Không, vôi có thể màu hồng chẳng hạn.

Bảng chân trị của mọi phép liên kết

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

Tính đúng sai của cả công thức

Giờ ta đã biết đánh giá tính đúng sai của hai mệnh đề nối với nhau bằng một phép liên kết. Cả công thức được đánh giá hoàn toàn tương tự. Với công thức (p ⇒ q) ∧ r, khi đã đánh giá được công thức (p ⇒ q), chẳng hạn bằng 1, ta được phép hội quen thuộc 1 ∧ r mà ta đã biết cách xử lí.

Lần lượt áp dụng các phép liên kết mệnh đề đơn giản nhất, ta đi đến giá trị chân lí của cả công thức. Để làm việc này, người ta thường dùng phương pháp lập bảng, trình bày ở phần sau.

Phương pháp lập bảng

Phương pháp lập bảng dùng để đánh giá các công thức phức tạp hơn. Ở n cột đầu tiên, ta ghi n biến mệnh đề có trong công thức; ở các cột tiếp theo, ta lần lượt ghi các công thức con mà công thức chứa. Qua ví dụ sẽ thấy rõ hơn.

Xét công thức (p ∨ q) ∧ (q ⇒ p). Trước hết, ta ghi vào bảng tất cả các biến mệnh đề, tức là p và q, cùng mọi tổ hợp giá trị chân lí của chúng:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Tiếp theo, ta thêm các cột cho từng công thức con p ∨ q và q ⇒ p.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Bây giờ ta đánh giá các công thức này và điền số 0 hoặc số 1 vào các cột. Bảng đã chứa mọi thông tin cần thiết. Khi đánh giá p ∨ q ở hàng thứ nhất, ta thay p bằng 1 và q cũng bằng 1. Ta được biểu thức 1 ∨ 1. Giá trị của biểu thức này là 1, nên ta ghi số 1 vào bảng:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Cứ như vậy, ta điền dần cả bảng:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

Việc còn lại là đánh giá cả công thức. Kí hiệu công thức này, chẳng hạn, là φ = (p ∨ q) ∧ (q ⇒ p). Thêm vào bảng cột φ và đánh giá nó, lúc này dùng luôn hai cột vừa tính.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

Bảng đã đầy đủ và cho biết giá trị chân lí của công thức trong mọi phép gán có thể. Chẳng hạn, nếu e(p) = 1 và e(q) = 1 thì công thức đúng. Nếu e(p) = 0 và e(q) = 1 thì công thức sai.

Lưu ý rằng ta không thể nói “công thức đúng”. Câu này vô nghĩa, vì muốn nói công thức đúng thì phải nói nó đúng trong phép gán nào. Ta có thể nói “công thức φ đúng trong phép gán e₁ và sai trong phép gán e₂”.

Trường hợp duy nhất có thể nói công thức đúng là khi nó đúng trong mọi phép gán có thể. Chẳng hạn công thức p ∨ ¬p đúng trong mọi phép gán, nên có thể nói công thức này đúng. Tương tự với trường hợp công thức sai trong mọi phép gán.

Những công thức như vậy có tên gọi riêng. Công thức đúng trong mọi phép gán gọi là hằng đúng. Công thức sai trong mọi phép gán gọi là hằng sai (mâu thuẫn).