Bài tập logic mệnh đề

Bài này trình bày một số công thức và các phép gán giá trị chân lí có thể có của chúng bằng phương pháp lập bảng.

Ví dụ thứ nhất

Ta tìm xem khi nào công thức sau đúng: ϕ = (p ∧ q) ∨ ¬q. Ghi vào bảng các biến mệnh đề p và q:

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

Tiếp theo, thêm vào bảng phần thứ nhất của công thức (p ∧ q), mệnh đề phủ định ¬q và sau đó là cả công thức:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Bây giờ ta tính các giá trị ở cột thứ ba, đó là một phép hội đơn giản, và đồng thời ở cột phủ định, chỉ cần ghi giá trị ngược với giá trị ở cột thứ hai:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Cuối cùng, ta tính các giá trị ở cột cuối, tức là cả công thức. Theo bảng của ta, đó là phép tuyển “giữa cột thứ ba và cột thứ tư”. Kết quả:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Ví dụ thứ hai

Cùng yêu cầu, công thức khác: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Ta thấy công thức chứa các biến mệnh đề p, q và mệnh đề phủ định của chúng. Vì vậy, trước hết ta lập bảng gồm hai biến và các mệnh đề phủ định của chúng:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Tiếp theo, ta thêm các công thức p ∧ ¬q và ¬p ⇒ q. Đánh giá chúng không khó, vì bảng đã có giá trị chân lí của từng mệnh đề lẫn mệnh đề phủ định của chúng. Bảng có dạng:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Cuối cùng còn phải đánh giá cả công thức, tức là mệnh đề tương đương giữa hai cột cuối:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Ví dụ thứ ba

Ví dụ thứ ba phức tạp hơn một chút: có ba biến mệnh đề, nên bảng dài hơn. Công thức như sau: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Vì có ba biến mệnh đề nên có tất cả 8 phép gán giá trị chân lí:

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

Tiếp theo, ta làm giống như ví dụ trước: đánh giá từng cột ở cả 8 hàng. Bảng đầy đủ có dạng:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Ví dụ thứ tư

Lần này đề bài không phải là một công thức có sẵn mà là một bài toán có lời văn. Ba người bạn được mời đến một bữa tiệc sinh nhật. Họ không ưa nhau lắm nên đặt ra điều kiện để chịu đi dự tiệc. Tên của họ là Minh, Hùng và Nam. Các quy tắc như sau:

1. Nếu Minh đi thì Hùng cũng đi.
2. Nam đến dự tiệc, hoặc nếu Minh đến thì Hùng không đến.
3. Nam đến khi và chỉ khi Minh không đến hoặc Hùng không đến.

Câu hỏi: cả ba người có thể cùng đến dự tiệc không? Nếu không thì những ai có thể đến mà không vi phạm quy tắc nào?

Trước hết, ta phải viết các mệnh đề bằng lời ở trên thành biến mệnh đề và công thức. Kí hiệu các biến mệnh đề là M, H và N (Minh, Hùng, Nam); mỗi biến ứng với một mệnh đề kiểu “Minh đi dự tiệc”. Quy tắc thứ nhất có thể viết lại thành: M ⇒ H, tức là “nếu M thì H”, hay “nếu Minh đi dự tiệc thì Hùng đi dự tiệc”.

Quy tắc thứ hai viết lại như sau. Quy tắc bắt đầu bằng “Nam đến dự tiệc, hoặc…”, nên rõ ràng ta cần phép tuyển. Tạm thời ta viết: N ∨ … Phần tiếp theo của câu nói: “nếu Minh đến thì Hùng không đến”. Đó là mệnh đề kéo theo, trong đó ở vế phải còn phải dùng phép phủ định: “Hùng không đến” = ¬H. Cả mệnh đề kéo theo có dạng: M ⇒ ¬H. Ghép mệnh đề này vào phép tuyển ở trên: N ∨ (M ⇒ ¬H).

Quy tắc thứ ba viết lại như sau: bắt đầu bằng “Nam đến khi và chỉ khi”. Đó là mệnh đề tương đương: N ⇔ … Tiếp theo là “Minh không đến hoặc Hùng không đến”, viết thành: ¬M ∨ ¬H. Ghép lại: (N ⇔ (¬M ∨ ¬H)).

Bây giờ ghi tất cả các công thức vào bảng và tính giá trị:

$$\begin{array}{cccccc}M& H& N& (M\Rightarrow H)& (N\vee (M\Rightarrow \mathrm{\neg }H))& (N\iff (\mathrm{\neg }M\vee \mathrm{\neg }H))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

Câu hỏi là cả ba bạn có thể cùng đến bữa tiệc không. Câu trả lời nằm ở hàng thứ nhất. Hàng này ứng với trường hợp cả ba bạn cùng đi, thể hiện bằng ba số 1 ở ba cột đầu. Mọi điều kiện có được thoả mãn không? Điều kiện thứ nhất được thoả mãn (cột thứ tư), điều kiện thứ hai cũng vậy (cột thứ năm), nhưng điều kiện cuối thì không (cột cuối), ở đó là số 0. Nghĩa là nếu cả ba cùng đi thì điều kiện thứ ba không được thoả mãn.

Vậy ta tìm những hàng mà ở các vị trí ứng với điều kiện (tức là ba cột cuối) toàn là số 1. Số 1 nghĩa là điều kiện được thoả mãn. Ta thấy điều này xảy ra trong hai trường hợp: khi Hùng và Nam đi còn Minh không đi, và khi chỉ có Nam đi.

Cũng có thể tính bằng cách thêm vào bảng công thức ϕ là phép hội của cả ba điều kiện. Công thức có dạng: ϕ = ((M ⇒ H) ∧ (N ∨ (M ⇒ ¬H)) ∧ (N ⇔ (¬M ∨ ¬H))). Công thức này diễn tả đúng điều ta muốn: mọi công thức (mọi điều kiện) đều được thoả mãn. Khi đó bảng có dạng:

$$\begin{array}{ccccccc}M& H& N& (M\Rightarrow H)& (N\vee (M\Rightarrow \mathrm{\neg }H))& (N\iff (\mathrm{\neg }M\vee \mathrm{\neg }H))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Thêm một số bài tập về phương pháp lập bảng

Tôi đã viết một chương trình tự động lập cả bảng cho một công thức bất kì, nên phải tận dụng nó cho đáng. Dưới đây là thêm một số công thức đã giải:

Công thức: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Bảng chân trị:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Công thức: (a ∨ ¬a) ⇔ (b ∧ ¬b). Bảng chân trị:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Công thức: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Bảng chân trị:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Công thức: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Bảng chân trị:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Công thức: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Bảng chân trị:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$