Chương 14: Mệnh đề, phủ định và kéo theo¶
Câu hỏi mở đầu
Suốt Phần I, ta đã nói "nếu ... thì ...", "với mọi số ...", "tồn tại số ...", và đã dùng phản chứng cho \(\sqrt2\) rồi cho \(\log_2 3\). Những câu ấy có nghĩa chính xác là gì, và khi nào một lập luận thật sự đúng?
Một lời hứa bị phá khi nào?¶
Một người cha hứa với con: "Nếu con đạt từ 8 điểm trở lên, bố sẽ thưởng." Cuối kỳ có bốn khả năng:
- con đạt 9 điểm, và được thưởng;
- con đạt 9 điểm, nhưng không được thưởng;
- con đạt 6 điểm, nhưng vẫn được thưởng;
- con đạt 6 điểm, và không được thưởng.
Trong trường hợp nào người cha thất hứa? Chỉ trường hợp 2. Trường hợp 3 có thể làm ta ngạc nhiên, nhưng lời hứa không nói gì về điểm dưới 8: thưởng thêm là rộng lượng, không phải thất hứa.
Suốt Phần I, ta đã dựa vào những câu "nếu ... thì ..." như thế: "nếu \(n^2\) chẵn thì \(n\) chẵn" ở Chương 11, "nếu \(c \neq 0\) và \(ac = bc\) thì \(a = b\)" ở Chương 9. Ta đã phủ định chúng, lật ngược chúng, xâu chúng thành chuỗi. Nhưng chưa lần nào ta nói rõ một câu như thế đúng khi nào, phủ định của nó là gì, và nó liên quan thế nào với câu lật ngược của nó. Ngôn ngữ đời thường không đủ chính xác cho việc ấy. Phần II bắt đầu bằng việc làm cho nó chính xác.
Câu có giá trị đúng sai¶
Hành động đầu tiên của Chương 3 là phân biệt. Hãy áp dụng nó cho các câu: chia mọi câu khẳng định thành hai nhóm, đúng và sai. "7 là số nguyên tố" rơi vào nhóm đúng; "\(2 + 2 = 5\)" rơi vào nhóm sai. Nhưng có những câu không rơi vào nhóm nào: câu hỏi ("Mấy giờ rồi?"), mệnh lệnh ("Đóng cửa lại"), câu mơ hồ ("Số này lớn thật"), câu chứa một biến chưa biết ("\(x + 1 = 3\)", đúng hay sai tùy \(x\)).
Một câu rơi vào đúng một trong hai nhóm gọi là một mệnh đề. Có những mệnh đề mà chưa ai biết đúng hay sai. "Mọi số chẵn lớn hơn 2 là tổng của hai số nguyên tố" là một giả thuyết nổi tiếng mà tới nay chưa ai chứng minh hay bác bỏ được; nhưng nó vẫn là một mệnh đề, vì nó hoặc đúng hoặc sai, chỉ là ta chưa biết.
Giờ ghép các câu lại. Quyết định then chốt là: giá trị đúng sai của câu ghép chỉ phụ thuộc vào giá trị đúng sai của các câu thành phần, không phụ thuộc vào nội dung của chúng. Với quyết định ấy, mỗi cách ghép chỉ là một bảng nhỏ. Với hai câu có bốn khả năng (đúng đúng, đúng sai, sai đúng, sai sai), và một cách ghép chỉ cần nói kết quả trong từng khả năng:
- "không" đổi đúng thành sai, sai thành đúng;
- "và" cho kết quả đúng khi cả hai câu đúng;
- "hoặc" cho kết quả đúng khi ít nhất một câu đúng.
Còn "nếu ... thì ..."? Đây là chỗ cần suy nghĩ, và câu trả lời hóa ra bị ép buộc. Xét câu "nếu \(n\) chia hết cho 4 thì \(n\) chẵn". Ta muốn nó là một định luật, đúng với mọi số tự nhiên \(n\). Thử vài số:
- \(n = 8\): chia hết cho 4 (đúng), chẵn (đúng). Câu phải đúng.
- \(n = 6\): chia hết cho 4 (sai), chẵn (đúng). Câu vẫn phải đúng.
- \(n = 3\): chia hết cho 4 (sai), chẵn (sai). Câu vẫn phải đúng.
Ba khả năng đúng-đúng, sai-đúng, sai-sai đều buộc phải cho kết quả đúng; nếu không, định luật hiển nhiên này sẽ sai với \(n = 6\) hay \(n = 3\). Khả năng còn lại, đúng-sai, phải cho kết quả sai: nếu nó cũng cho kết quả đúng thì "nếu ... thì ..." đúng trong mọi trường hợp và chẳng nói lên điều gì. Vậy "nếu \(P\) thì \(Q\)" sai trong đúng một khả năng: khi \(P\) đúng mà \(Q\) sai, giống hệt lời hứa của người cha. Và định luật về số chia hết cho 4 đúng chính vì không có số nào rơi vào khả năng ấy.
Ký hiệu¶
Một mệnh đề (proposition) là một câu khẳng định hoặc đúng hoặc sai, không thể vừa đúng vừa sai. Ta dùng chữ in hoa \(P\), \(Q\), \(R\) để chỉ mệnh đề, và Đ, S để chỉ hai giá trị chân lý (truth value): đúng và sai.
Chữ "mệnh đề" có hai cách dùng trong sách. Ở đây nó chỉ bất kỳ câu nào có giá trị đúng sai. Còn "Mệnh đề 1", "Mệnh đề 2" trong mục Phát biểu chặt chẽ của mỗi chương là những mệnh đề đúng đã được chứng minh; tùy tầm quan trọng, một mệnh đề đã chứng minh còn được gọi là định lý (theorem), bổ đề hay hệ quả.
Các phép nối:
- phủ định (negation) của \(P\), viết \(\lnot P\), đọc "không \(P\)"; sách giáo khoa Việt Nam viết \(\overline{P}\);
- phép hội (conjunction) \(P \land Q\), đọc "\(P\) và \(Q\)";
- phép tuyển (disjunction) \(P \lor Q\), đọc "\(P\) hoặc \(Q\)"; đây là "hoặc" bao hàm, đúng cả khi hai mệnh đề cùng đúng;
- phép kéo theo (implication) \(P \Rightarrow Q\), đọc "nếu \(P\) thì \(Q\)" hay "\(P\) kéo theo \(Q\)"; \(P\) gọi là giả thiết (hypothesis), \(Q\) là kết luận (conclusion);
- phép tương đương (biconditional) \(P \Leftrightarrow Q\), đọc "\(P\) khi và chỉ khi \(Q\)", đúng khi hai mệnh đề cùng đúng hoặc cùng sai.
Bảng liệt kê giá trị của một mệnh đề ghép trong mọi khả năng của các thành phần gọi là bảng chân trị (truth table).
Với phép kéo theo \(P \Rightarrow Q\), mệnh đề đảo (converse) của nó là \(Q \Rightarrow P\), và mệnh đề phản đảo (contrapositive) của nó là \(\lnot Q \Rightarrow \lnot P\). Khi \(P \Rightarrow Q\) đúng, ta nói \(P\) là điều kiện đủ (sufficient condition) để có \(Q\), và \(Q\) là điều kiện cần (necessary condition) để có \(P\): có \(P\) là đủ để chắc chắn có \(Q\); thiếu \(Q\) thì chắc chắn không có \(P\).
Hai mệnh đề ghép có cùng giá trị ở mọi dòng của bảng chân trị gọi là tương đương logic (logically equivalent): chúng là hai cách nói khác nhau của cùng một điều.
Làm bằng tay¶
Ví dụ 1 (một bảng chân trị). Lập bảng chân trị của \((P \Rightarrow Q) \land (Q \Rightarrow P)\).
| \(P\) | \(Q\) | \(P \Rightarrow Q\) | \(Q \Rightarrow P\) | \((P \Rightarrow Q) \land (Q \Rightarrow P)\) |
|---|---|---|---|---|
| Đ | Đ | Đ | Đ | Đ |
| Đ | S | S | Đ | S |
| S | Đ | Đ | S | S |
| S | S | Đ | Đ | Đ |
Cột cuối trùng với cột của \(P \Leftrightarrow Q\): "\(P\) khi và chỉ khi \(Q\)" chính là "nếu \(P\) thì \(Q\), và nếu \(Q\) thì \(P\)". Vì thế chứng minh một câu "khi và chỉ khi" là chứng minh cả hai chiều, như Hệ quả 6 của Chương 11 hay Mệnh đề 6 của Chương 13.
Ví dụ 2 (phủ định câu phức). (a) Phủ định của "An vừa cao vừa nặng" không phải "An vừa thấp vừa nhẹ", mà là "An không cao hoặc không nặng": câu gốc đã sai khi chỉ một trong hai điều không xảy ra.
(b) Phủ định của "\(n\) chẵn hoặc \(n\) chia hết cho 3" là "\(n\) lẻ và \(n\) không chia hết cho 3". Với \(n = 5\), câu gốc sai và câu phủ định đúng.
(c) Phủ định của "nếu trời mưa thì đường ướt" không phải "nếu trời mưa thì đường không ướt", cũng không phải "nếu trời không mưa thì đường không ướt". Câu gốc chỉ sai trong một khả năng: trời mưa mà đường không ướt. Vậy phủ định của nó là "trời mưa và đường không ướt". Phủ định một lời hứa là chỉ ra một tình huống cụ thể làm nó thất bại.
Ví dụ 3 (bốn tấm thẻ). Mỗi tấm thẻ dưới đây có một chữ cái ở một mặt và một số ở mặt kia. Quy tắc cần kiểm tra: "nếu một mặt là nguyên âm thì mặt kia là số chẵn". Phải lật những thẻ nào, và chỉ những thẻ nào, để biết quy tắc có bị vi phạm hay không? Hãy thử trả lời trước khi đọc tiếp.
Quy tắc có dạng \(P \Rightarrow Q\), với \(P\) là "có nguyên âm" và \(Q\) là "có số chẵn", và nó chỉ bị vi phạm khi \(P\) đúng mà \(Q\) sai. Thẻ E có \(P\) đúng: phải lật, xem mặt sau có phải số chẵn không. Thẻ 7 có \(Q\) sai: phải lật, xem mặt sau có phải nguyên âm không. Thẻ K có \(P\) sai: dù mặt sau là gì, quy tắc cũng không bị vi phạm. Thẻ 4 có \(Q\) đúng: dù mặt sau là gì, quy tắc cũng không bị vi phạm. Người muốn lật thẻ 4 đang kiểm tra mệnh đề đảo "nếu có số chẵn thì có nguyên âm", một quy tắc khác. Vậy phải lật E và 7.
Ví dụ 4 (mạch điện). Hai công tắc A, B nối tiếp với một bóng đèn: đèn sáng khi và chỉ khi cả A và B đều đóng. Hai công tắc nối song song: đèn sáng khi và chỉ khi A hoặc B đóng. Coi "công tắc đóng" là Đ, "mở" là S, và "đèn sáng" là Đ; bảng trạng thái của đèn trùng với bảng chân trị của phép hội và phép tuyển.
Mạch điện và logic là cùng một cấu trúc. Máy tính điện tử thực hiện các phép nối này bằng những mạch rất nhỏ, và mọi phép tính của nó rốt cuộc được ghép từ chúng.
Ví dụ 5 (điều kiện cần, điều kiện đủ). Vì "nếu \(n\) chia hết cho 4 thì \(n\) chẵn" đúng, nên chia hết cho 4 là điều kiện đủ để \(n\) chẵn, và chẵn là điều kiện cần để \(n\) chia hết cho 4. Chia hết cho 4 không phải điều kiện cần để chẵn, vì 6 chẵn mà không chia hết cho 4; chẵn cũng không phải điều kiện đủ để chia hết cho 4, cũng vì số 6.
Một ví dụ khác: "\(x = 2\)" kéo theo "\(x^2 = 4\)". Vậy \(x = 2\) là điều kiện đủ để \(x^2 = 4\), nhưng không cần, vì \(x = -2\) cũng cho \(x^2 = 4\). Còn với số nguyên \(n\), "\(n^2\) chẵn" và "\(n\) chẵn" kéo theo nhau theo cả hai chiều (Chương 11), nên mỗi điều là điều kiện cần và đủ cho điều kia.
Ranh giới¶
"Câu này sai" không phải mệnh đề. Nếu nó đúng thì điều nó nói xảy ra, tức nó sai; nếu nó sai thì điều nó nói không xảy ra, tức nó đúng. Nó không thể nằm trong nhóm nào. Ngôn ngữ cho phép nói những câu như thế; logic của các mệnh đề phải loại chúng ra.
Kéo theo không cần quan hệ nhân quả (causation). "Nếu \(2 + 2 = 5\) thì Mặt Trăng làm bằng phô mai" là một mệnh đề đúng: giả thiết sai nên lời hứa không bao giờ bị thử thách. Ta nói nó đúng một cách trống rỗng (vacuously true). "Nếu \(2 + 2 = 4\) thì Hà Nội là thủ đô của Việt Nam" cũng đúng, dù hai vế chẳng liên quan gì tới nhau. Phép kéo theo trong toán chỉ nói về giá trị đúng sai, không nói về nguyên nhân. Nghe lạ, nhưng đó là cái giá phải trả để định luật "nếu \(n\) chia hết cho 4 thì \(n\) chẵn" đúng với mọi \(n\).
"Nếu" trong đời thường thường là "khi và chỉ khi". "Nếu con ăn hết rau thì con được ăn kem": đứa trẻ hiểu rằng không ăn rau thì không có kem, tức là hiểu thêm một lời hứa nữa. Trong toán, mệnh đề đảo là một lời hứa khác, phải được nói ra và chứng minh riêng.
"Hoặc" trong đời thường thường là "hoặc loại trừ". "Anh dùng cà phê hoặc trà?" thường được hiểu là chỉ chọn một. Trong toán, "hoặc" là bao hàm: "\(n\) chia hết cho 2 hoặc cho 3" đúng với \(n = 6\). Khi cần phép hoặc loại trừ (exclusive or), phải nói rõ "hoặc ... hoặc ..., nhưng không cả hai".
Mệnh đề đảo không tương đương với mệnh đề gốc. "Nếu \(n\) chia hết cho 4 thì \(n\) chẵn" đúng, nhưng mệnh đề đảo "nếu \(n\) chẵn thì \(n\) chia hết cho 4" sai, với phản ví dụ \(n = 6\). Nhầm một câu với câu đảo của nó là một lỗi lập luận rất dễ mắc: "người giỏi toán thì chăm chỉ; anh ấy chăm chỉ; vậy anh ấy giỏi toán".
Câu có biến chưa phải mệnh đề. "\(x > 3\)" đúng hay sai tùy \(x\). Muốn biến nó thành mệnh đề, phải thay \(x\) bằng một số cụ thể, hoặc nói "với mọi \(x\)" hay "có một \(x\)". Đó là việc của Chương 15.
Phát biểu chặt chẽ¶
Định nghĩa 1. Một mệnh đề là một câu khẳng định có đúng một trong hai giá trị chân lý: đúng (Đ) hoặc sai (S).
Định nghĩa 2 (các phép nối). Với hai mệnh đề \(P\), \(Q\), các mệnh đề \(\lnot P\), \(P \land Q\), \(P \lor Q\), \(P \Rightarrow Q\) và \(P \Leftrightarrow Q\) được định nghĩa bởi bảng chân trị:
| \(P\) | \(Q\) | \(\lnot P\) | \(P \land Q\) | \(P \lor Q\) | \(P \Rightarrow Q\) | \(P \Leftrightarrow Q\) |
|---|---|---|---|---|---|---|
| Đ | Đ | S | Đ | Đ | Đ | Đ |
| Đ | S | S | S | Đ | S | S |
| S | Đ | Đ | S | Đ | Đ | S |
| S | S | Đ | S | S | Đ | Đ |
Định nghĩa 3. Hai mệnh đề ghép từ cùng các mệnh đề thành phần là tương đương logic nếu chúng có cùng giá trị ở mọi dòng của bảng chân trị. Một mệnh đề ghép đúng ở mọi dòng gọi là một hằng đúng (tautology).
Định lý 4 (phản đảo). \(P \Rightarrow Q\) tương đương logic với \(\lnot Q \Rightarrow \lnot P\), và với \(\lnot P \lor Q\). Mệnh đề đảo \(Q \Rightarrow P\) thì không tương đương với \(P \Rightarrow Q\).
Chứng minh. Lập bảng chân trị:
| \(P\) | \(Q\) | \(P \Rightarrow Q\) | \(\lnot Q \Rightarrow \lnot P\) | \(\lnot P \lor Q\) | \(Q \Rightarrow P\) |
|---|---|---|---|---|---|
| Đ | Đ | Đ | Đ | Đ | Đ |
| Đ | S | S | S | S | Đ |
| S | Đ | Đ | Đ | Đ | S |
| S | S | Đ | Đ | Đ | Đ |
Ba cột \(P \Rightarrow Q\), \(\lnot Q \Rightarrow \lnot P\) và \(\lnot P \lor Q\) giống hệt nhau. Cột \(Q \Rightarrow P\) khác cột \(P \Rightarrow Q\) ở dòng thứ hai và dòng thứ ba. \(\square\)
Vì thế, thay vì chứng minh "nếu \(n^2\) chẵn thì \(n\) chẵn", Bổ đề 1 của Chương 11 đã chứng minh "nếu \(n\) lẻ thì \(n^2\) lẻ": hai câu là một. Chương 16 sẽ khai thác kỹ cách chứng minh này.
Định lý 5 (luật De Morgan). \(\lnot(P \land Q)\) tương đương logic với \(\lnot P \lor \lnot Q\), và \(\lnot(P \lor Q)\) tương đương logic với \(\lnot P \land \lnot Q\).
Chứng minh. Với luật thứ nhất:
| \(P\) | \(Q\) | \(P \land Q\) | \(\lnot(P \land Q)\) | \(\lnot P\) | \(\lnot Q\) | \(\lnot P \lor \lnot Q\) |
|---|---|---|---|---|---|---|
| Đ | Đ | Đ | S | S | S | S |
| Đ | S | S | Đ | S | Đ | Đ |
| S | Đ | S | Đ | Đ | S | Đ |
| S | S | S | Đ | Đ | Đ | Đ |
Cột thứ tư và cột cuối giống hệt nhau. Luật thứ hai là bài C2. \(\square\)
Hai luật này mang tên luật De Morgan (De Morgan's laws). Chúng nói rằng phủ định đổi "và" thành "hoặc", "hoặc" thành "và", như Ví dụ 2 đã làm.
Hệ quả 6. \(\lnot(P \Rightarrow Q)\) tương đương logic với \(P \land \lnot Q\).
Chứng minh. Theo Định lý 4, \(P \Rightarrow Q\) tương đương với \(\lnot P \lor Q\). Theo luật De Morgan thứ hai, \(\lnot(\lnot P \lor Q)\) tương đương với \(\lnot \lnot P \land \lnot Q\), tức \(P \land \lnot Q\), vì phủ định hai lần trả lại mệnh đề ban đầu. \(\square\)
Hệ quả 6 là nền của phản ví dụ ở Chương 1: muốn bác bỏ một câu "nếu ... thì ...", chỉ cần chỉ ra một trường hợp giả thiết đúng mà kết luận sai.
Sợi chỉ
- S2. Thông tin và khả nghịch. Phép kéo theo chỉ đi một chiều: từ \(P \Rightarrow Q\) không suy ra được \(Q \Rightarrow P\). Biết kết luận đúng không cho biết gì về giả thiết (thẻ số 4 ở Ví dụ 3), giống như một phép biến đổi làm mất thông tin ở Chương 6 không cho phép đi ngược.
- S3. Thứ tự của biến đổi. "Và", "hoặc" giao hoán như phép cộng ở Chương 5; phép kéo theo thì không: \(P \Rightarrow Q\) và \(Q \Rightarrow P\) là hai câu khác nhau.
- S6. Biểu diễn khác nhau của cùng một cấu trúc. Cùng một phép nối có thể là một câu chữ, một bảng chân trị, một mạch điện, hay một cách lồng các vùng vào nhau. Mạch nối tiếp là "và", mạch song song là "hoặc"; vùng nhỏ nằm trong vùng lớn là "kéo theo".
Tóm tắt¶
- Một mệnh đề là một câu có đúng một giá trị chân lý: đúng hoặc sai; câu hỏi, mệnh lệnh, câu mơ hồ, câu chứa biến chưa biết và "câu này sai" không phải mệnh đề.
- Các phép nối \(\lnot\), \(\land\), \(\lor\), \(\Rightarrow\), \(\Leftrightarrow\) được định nghĩa bằng bảng chân trị; giá trị của câu ghép chỉ phụ thuộc vào giá trị của các thành phần.
- \(P \Rightarrow Q\) chỉ sai khi \(P\) đúng mà \(Q\) sai; định nghĩa này bị ép buộc nếu muốn các định luật như "chia hết cho 4 thì chẵn" đúng với mọi số.
- Mệnh đề phản đảo \(\lnot Q \Rightarrow \lnot P\) tương đương với \(P \Rightarrow Q\); mệnh đề đảo \(Q \Rightarrow P\) thì không.
- Luật De Morgan: phủ định đổi "và" thành "hoặc" và ngược lại; phủ định của \(P \Rightarrow Q\) là \(P \land \lnot Q\), tức một phản ví dụ.
- Khi \(P \Rightarrow Q\) đúng, \(P\) là điều kiện đủ cho \(Q\), và \(Q\) là điều kiện cần cho \(P\).
- Kéo theo trong toán không đòi quan hệ nhân quả; "nếu" và "hoặc" trong đời thường thường mang nghĩa hẹp hơn hoặc rộng hơn nghĩa trong toán.
Bài tập¶
A. Tư duy¶
A1. Một người hứa: "Nếu trời không mưa, tôi sẽ đến." Hôm ấy trời mưa và người ấy vẫn đến. Người ấy có thất hứa không? Nếu trời không mưa và người ấy không đến thì sao? Nếu trời mưa và người ấy không đến thì sao?
Lời giải
Lời hứa có dạng \(P \Rightarrow Q\), với \(P\) là "trời không mưa" và \(Q\) là "tôi đến". Nó chỉ bị phá khi \(P\) đúng mà \(Q\) sai.
Trời mưa và người ấy vẫn đến: \(P\) sai, nên lời hứa không bị phá; người ấy còn làm hơn điều đã hứa. Trời không mưa mà người ấy không đến: \(P\) đúng, \(Q\) sai, đây là thất hứa. Trời mưa và người ấy không đến: \(P\) sai, lời hứa không bị phá, vì nó không nói gì về ngày mưa.
A2. Vì sao "Câu này sai" không phải là một mệnh đề? Còn câu "Câu này đúng" thì sao?
Lời giải
Với "Câu này sai": nếu gán cho nó giá trị Đ thì điều nó nói xảy ra, nên nó sai; nếu gán S thì điều nó nói không xảy ra, nên nó đúng. Không có cách gán nào nhất quán, nên nó không có giá trị chân lý.
Với "Câu này đúng", vấn đề ngược lại: gán Đ thì nhất quán, gán S cũng nhất quán, và không có gì quyết định chọn cách nào. Một mệnh đề phải có đúng một giá trị xác định, nên câu này cũng không phải mệnh đề. Cả hai câu đều hỏng vì chúng nói về chính mình thay vì nói về một điều gì bên ngoài.
A3. "Nếu một con vật là cá voi thì nó biết bơi" là một mệnh đề đúng. Mệnh đề đảo của nó là gì, và có đúng không? Vì sao người ta hay nhầm một câu với câu đảo của nó? Cho một ví dụ về sự nhầm lẫn ấy trong đời sống.
Lời giải
Mệnh đề đảo là "nếu một con vật biết bơi thì nó là cá voi", sai: con vịt biết bơi mà không phải cá voi.
Người ta hay nhầm vì trong nhiều câu đời thường, cả hai chiều cùng đúng, hoặc người nói ngầm ý cả hai chiều ("nếu con ăn hết rau thì được ăn kem"). Nhầm lẫn trở nên nguy hiểm khi chỉ một chiều đúng. Ví dụ: "nếu trời mưa thì đường ướt; sáng nay đường ướt; vậy đêm qua trời mưa". Đường có thể ướt vì xe tưới nước chạy qua, nên kết luận không được suy ra.
B. Tính toán¶
B1. Câu nào là mệnh đề? Nếu là mệnh đề, nó đúng hay sai (nếu biết)? (a) "7 là số nguyên tố." (b) "\(x + 1 = 3\)." (c) "Hãy đóng cửa lại." (d) "Mọi số chẵn lớn hơn 2 là tổng của hai số nguyên tố." (e) "\(2 + 2 = 5\)." (f) "Số này lớn thật!"
Lời giải
(a) Mệnh đề đúng. (b) Không phải mệnh đề: đúng hay sai tùy \(x\). (c) Không phải mệnh đề: đó là một mệnh lệnh. (d) Mệnh đề; tới nay chưa ai biết nó đúng hay sai. (e) Mệnh đề sai. (f) Không phải mệnh đề: "lớn thật" không có nghĩa xác định.
B2. Lập bảng chân trị của: (a) \(P \lor \lnot P\); (b) \(P \land \lnot P\); (c) \((P \Rightarrow Q) \Rightarrow P\). Mệnh đề nào là hằng đúng?
Lời giải
(a) \(P \lor \lnot P\): với \(P\) đúng được Đ, với \(P\) sai được Đ. Đây là một hằng đúng: mỗi câu hoặc đúng hoặc sai.
(b) \(P \land \lnot P\): luôn sai. Một câu không thể vừa đúng vừa sai.
(c) Theo các dòng \((P; Q)\) = (Đ; Đ), (Đ; S), (S; Đ), (S; S): \(P \Rightarrow Q\) lần lượt là Đ, S, Đ, Đ, nên \((P \Rightarrow Q) \Rightarrow P\) lần lượt là Đ, Đ, S, S. Không phải hằng đúng.
B3. Cho \(P\): "\(3 > 2\)", \(Q\): "5 là số chẵn", \(R\): "\(\sqrt2\) là số hữu tỉ". Xác định giá trị chân lý của: (a) \(P \land \lnot Q\); (b) \(Q \lor R\); (c) \(P \Rightarrow Q\); (d) \(Q \Rightarrow R\); (e) \(\lnot P \Rightarrow R\); (f) \((P \lor Q) \Rightarrow \lnot R\).
Lời giải
\(P\) đúng; \(Q\) sai; \(R\) sai (Chương 11).
(a) Đ và Đ: đúng. (b) S hoặc S: sai. (c) Đ kéo theo S: sai. (d) S kéo theo S: đúng. (e) \(\lnot P\) sai, nên kéo theo đúng. (f) \(P \lor Q\) đúng và \(\lnot R\) đúng, nên kéo theo đúng.
B4. Viết phủ định của mỗi câu: (a) "Hôm nay trời nắng và gió." (b) "Số \(n\) chia hết cho 2 hoặc cho 5." (c) "Nếu \(n\) chia hết cho 9 thì \(n\) chia hết cho 3." (d) "\(2 < x\) và \(x \leq 5\)" (với một số \(x\) cho trước).
Lời giải
(a) "Hôm nay trời không nắng hoặc không gió."
(b) "\(n\) không chia hết cho 2 và không chia hết cho 5."
(c) "\(n\) chia hết cho 9 và \(n\) không chia hết cho 3." (Với mọi số \(n\), câu phủ định này sai, vì câu gốc là một định luật đúng.)
(d) "\(x \leq 2\) hoặc \(x > 5\)."
B5. Cho mệnh đề "nếu \(n\) chia hết cho 6 thì \(n\) chia hết cho 3". Viết mệnh đề đảo và mệnh đề phản đảo của nó. Mỗi mệnh đề đúng với mọi số tự nhiên \(n\) hay không?
Lời giải
Mệnh đề gốc đúng: \(n = 6k = 3 \cdot (2k)\).
Mệnh đề đảo: "nếu \(n\) chia hết cho 3 thì \(n\) chia hết cho 6". Sai: \(n = 3\) chia hết cho 3 mà không chia hết cho 6.
Mệnh đề phản đảo: "nếu \(n\) không chia hết cho 3 thì \(n\) không chia hết cho 6". Đúng, vì nó tương đương với mệnh đề gốc (Định lý 4).
B6. Trong mỗi cặp, điều thứ nhất là điều kiện cần, điều kiện đủ, cả hai, hay không là gì cho điều thứ hai? (a) "\(n\) chia hết cho 10" và "\(n\) chia hết cho 5". (b) "tứ giác có bốn cạnh bằng nhau" và "tứ giác là hình vuông". (c) "\(x^2 = 9\)" và "\(x = 3\)". (d) "\(n^2\) chẵn" và "\(n\) chẵn" (với \(n\) nguyên).
Lời giải
(a) Chia hết cho 10 kéo theo chia hết cho 5, nên là điều kiện đủ; không cần, vì 15 chia hết cho 5 mà không chia hết cho 10.
(b) Mọi hình vuông đều có bốn cạnh bằng nhau, nên "bốn cạnh bằng nhau" là điều kiện cần để là hình vuông; không đủ, vì có những tứ giác bốn cạnh bằng nhau mà các góc không vuông.
(c) \(x = 3\) kéo theo \(x^2 = 9\), nên "\(x^2 = 9\)" là điều kiện cần để \(x = 3\); không đủ, vì \(x = -3\).
(d) Cần và đủ: hai điều kéo theo nhau (Chương 11).
B7. Một quy định giả định: "nếu một người uống bia thì người đó phải từ 18 tuổi trở lên". Bốn tấm thẻ, mỗi thẻ ghi đồ uống ở một mặt và tuổi ở mặt kia, đang cho thấy: "uống bia", "uống nước cam", "25 tuổi", "16 tuổi". Phải lật những thẻ nào để kiểm tra quy định?
Lời giải
Quy định chỉ bị vi phạm khi một người uống bia mà dưới 18 tuổi. Phải lật "uống bia" (xem tuổi) và "16 tuổi" (xem đồ uống). "Uống nước cam" và "25 tuổi" thì dù mặt kia là gì, quy định cũng không bị vi phạm.
Đây đúng là bài bốn tấm thẻ ở Ví dụ 3, chỉ đổi nội dung. Bạn có thấy phiên bản đời thường này dễ hơn không? Cấu trúc logic của hai bài giống hệt nhau; chỉ có cách kể là khác.
B8. Đèn cầu thang có hai công tắc, một ở chân và một ở đầu cầu thang; gạt bất kỳ công tắc nào cũng đổi trạng thái của đèn. Coi \(P\) là "công tắc dưới gạt lên", \(Q\) là "công tắc trên gạt lên", và giả sử khi cả hai cùng gạt lên thì đèn sáng. Lập bảng trạng thái của đèn. Nó trùng với phép nối nào?
Lời giải
Khi cả hai lên, đèn sáng. Gạt một công tắc xuống thì đèn tắt: (Đ; S) và (S; Đ) cho đèn tắt. Gạt tiếp công tắc còn lại xuống thì đèn lại sáng: (S; S) cho đèn sáng. Bảng Đ, S, S, Đ trùng với bảng của \(P \Leftrightarrow Q\): đèn sáng khi và chỉ khi hai công tắc ở cùng một vị trí.
B9. (a) Bảng chân trị của một mệnh đề ghép từ 3 mệnh đề thành phần có bao nhiêu dòng? Từ \(n\) mệnh đề thành phần? (b) Có bao nhiêu phép nối hai mệnh đề khác nhau, tức bao nhiêu cách điền cột kết quả cho một bảng 4 dòng?
Lời giải
(a) Mỗi mệnh đề thành phần có 2 giá trị, nên 3 mệnh đề cho \(2 \cdot 2 \cdot 2 = 8\) dòng, và \(n\) mệnh đề cho \(2^n\) dòng (Chương 12).
(b) Cột kết quả có 4 ô, mỗi ô chọn Đ hoặc S độc lập: \(2^4 = 16\) phép nối. Năm phép ở Định nghĩa 2 chỉ là năm trong số đó.
B10. Lập luận nào đúng, lập luận nào sai? (a) "Nếu một số chia hết cho 6 thì nó chẵn. Số 14 chẵn. Vậy 14 chia hết cho 6." (b) "Nếu trời mưa thì đường ướt. Trời không mưa. Vậy đường không ướt." (c) "Nếu một số chia hết cho 6 thì nó chẵn. Số 15 lẻ. Vậy 15 không chia hết cho 6."
Lời giải
(a) Sai: từ \(P \Rightarrow Q\) và \(Q\) không suy ra được \(P\). Đây là nhầm câu với câu đảo; quả thật 14 không chia hết cho 6.
(b) Sai: từ \(P \Rightarrow Q\) và \(\lnot P\) không suy ra được \(\lnot Q\). Đường có thể ướt vì người ta tưới nước.
(c) Đúng: từ \(P \Rightarrow Q\) và \(\lnot Q\) suy ra được \(\lnot P\), vì \(P \Rightarrow Q\) tương đương với \(\lnot Q \Rightarrow \lnot P\) (Định lý 4).
C. Phản ví dụ và chứng minh¶
C1. Chứng minh bằng bảng chân trị rằng \(P \Leftrightarrow Q\) tương đương logic với \((P \land Q) \lor (\lnot P \land \lnot Q)\), và giải thích kết quả bằng lời.
Lời giải
Theo các dòng \((P; Q)\) = (Đ; Đ), (Đ; S), (S; Đ), (S; S): \(P \land Q\) là Đ, S, S, S; \(\lnot P \land \lnot Q\) là S, S, S, Đ; tuyển của chúng là Đ, S, S, Đ. Cột của \(P \Leftrightarrow Q\) cũng là Đ, S, S, Đ. Hai mệnh đề tương đương logic. \(\square\)
Bằng lời: "\(P\) khi và chỉ khi \(Q\)" nghĩa là hai mệnh đề cùng đúng hoặc cùng sai, đúng như câu ghép bên phải nói.
C2. Chứng minh luật De Morgan thứ hai: \(\lnot(P \lor Q)\) tương đương logic với \(\lnot P \land \lnot Q\). Giải thích bằng mạch điện song song.
Lời giải
Theo các dòng (Đ; Đ), (Đ; S), (S; Đ), (S; S): \(P \lor Q\) là Đ, Đ, Đ, S, nên \(\lnot(P \lor Q)\) là S, S, S, Đ. Còn \(\lnot P\) là S, S, Đ, Đ và \(\lnot Q\) là S, Đ, S, Đ, nên \(\lnot P \land \lnot Q\) là S, S, S, Đ. Hai cột giống hệt nhau. \(\square\)
Với mạch song song, đèn sáng khi A hoặc B đóng. Đèn tắt khi và chỉ khi không có đường nào cho dòng điện đi qua, tức A mở và B mở: phủ định của "hoặc" là "và" của các phủ định.
C3. Chứng minh rằng \(\big((P \Rightarrow Q) \land (Q \Rightarrow R)\big) \Rightarrow (P \Rightarrow R)\) là một hằng đúng. Vì sao điều này cho phép xâu các bước "kéo theo" thành một chứng minh dài?
Lời giải
Có \(2^3 = 8\) dòng. Thay vì lập cả bảng, ta tìm xem mệnh đề có thể sai ở dòng nào. Một phép kéo theo chỉ sai khi giả thiết đúng mà kết luận sai. Kết luận \(P \Rightarrow R\) sai chỉ khi \(P\) đúng và \(R\) sai. Khi đó, nếu \(Q\) đúng thì \(Q \Rightarrow R\) sai; nếu \(Q\) sai thì \(P \Rightarrow Q\) sai. Trong cả hai trường hợp, giả thiết \((P \Rightarrow Q) \land (Q \Rightarrow R)\) sai. Vậy không có dòng nào mà giả thiết đúng và kết luận sai: mệnh đề đúng ở cả 8 dòng. \(\square\)
Ý nghĩa: nếu đã chứng minh \(P \Rightarrow Q\) và \(Q \Rightarrow R\), thì \(P \Rightarrow R\) được chứng minh. Một chứng minh dài là một chuỗi \(P \Rightarrow Q_1\), \(Q_1 \Rightarrow Q_2\), ..., \(Q_k \Rightarrow R\), và hằng đúng này, áp dụng nhiều lần, nối cả chuỗi lại thành \(P \Rightarrow R\).
Câu hỏi để ngỏ¶
Câu "mọi số nguyên tố lớn hơn 2 đều lẻ" không phải một mệnh đề đơn lẻ, mà là vô số mệnh đề gộp lại: "3 lẻ", "5 lẻ", "7 lẻ", ... Làm sao nói chính xác, và phủ định chính xác, những câu về "mọi" và "có một"?