Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English
Discrete MathĐọc trong 8 phút

Chứng minh các luật logic bằng 0 và 1

Viết đúng là 1 và sai là 0, và logic trở thành đại số mà bạn đã biết. Mỗi liên từ logic trở thành một công thức nhỏ, và việc chứng minh hai mệnh đề tương đương trở thành nhân khai triển rồi so sánh. Mọi công thức trên trang này đều đã được máy tính kiểm tra với bảng chân trị của nó.

Luyện tập chủ đề này trong ứng dụng miễn phí →Tất cả bài hướng dẫn Discrete Math

Một công tắc đèn có hai vị trí#

Công tắc đèn hoặc tắt hoặc bật. Gọi tắt là 0 và bật là 1. Không có khả năng nào khác.

Một mệnh đề trong logic cũng vậy. Nó hoặc sai hoặc đúng. Vì thế hãy viết sai là 0 và đúng là 1. Giảng viên của bạn vốn đã làm vậy trong các bảng chân trị, thay vì viết T và F.

Lợi ích nằm ở đây. Khi các giá trị chân trị là số, bạn có thể làm số học với chúng. “Không”, “và”, “hoặc” và “nếu…thì” mỗi cái trở thành một công thức ngắn. Khi đó một luật logic trở thành một đẳng thức đại số, và bạn có thể chứng minh nó bằng cách nhân khai triển, giống như cách bạn kiểm tra (a + b)² = a² + 2ab + b².

Một liên từ logic (connective) chỉ là một từ nối các mệnh đề: không, và, hoặc, nếu…thì. Đó là toàn bộ thuật ngữ bạn cần cho trang này.

Bảng chuyển đổi#

Mỗi dòng cho biết một liên từ logic trở thành gì. Cột cuối là cách đọc ký hiệu thành lời.

LogicĐọc làCông thức 0/1
¬pkhông p1 − p
p ∧ qp và qpq
p ∨ qp hoặc qp + q − pq
p → qnếu p thì q1 − p + pq
p ⊕ qp hoặc q, nhưng không phải cả haip + q − 2pq
p ↔ qp nếu và chỉ nếu q1 − p − q + 2pq

Bạn không cần học thuộc sáu công thức. Bạn cần ba công thức đầu. Những công thức còn lại có thể xây dựng từ chúng, và phần tiếp theo cho thấy vì sao từng công thức đúng.

Vì sao mỗi công thức đúng#

Không. Phủ định đổi chỗ 0 và 1. Biểu thức 1 − p làm đúng việc đó: 1 − 0 = 1 và 1 − 1 = 0.

Và. p ∧ q chỉ đúng khi cả hai đều đúng. Tích của các số 0 và 1 chỉ bằng 1 khi mọi thừa số đều bằng 1. Vậy pq là phép hội. (Phép hội (conjunction) là một mệnh đề dạng “và”.)

Hoặc. Cộng p + q là đếm xem có bao nhiêu mệnh đề đúng. Số đếm đó có thể là 0, 1 hoặc 2, nhưng một giá trị chân trị phải là 0 hoặc 1. Dòng sai duy nhất là p = q = 1, nơi tổng bằng 2. Trừ đi pq sửa đúng dòng đó, vì pq bằng 1 ở đó và bằng 0 ở mọi nơi khác.

Nếu…thì. Một mệnh đề điều kiện chỉ sai ở một dòng: p = 1 và q = 0. Biểu thức p(1 − q) bằng 1 ở dòng đó và bằng 0 ở các dòng khác, nên 1 − p(1 − q) là mệnh đề điều kiện. Nhân khai triển ra và bạn được 1 − p + pq.

Hoặc loại trừ. Lại bắt đầu từ p + q. Ở dòng cả hai đều đúng, nó cho 2, nhưng hoặc loại trừ cần 0 ở đó. Hãy trừ 2pq thay vì pq, và dòng đó giảm hẳn xuống 0.

Tự kiểm tra nhanh

Thay vào cả bốn dòng (00, 01, 10, 11) và đảm bảo mọi đáp án đều là 0 hoặc 1. Một công thức mà có lúc cho ra 2 hoặc −1 thì không phải là giá trị chân trị, nên không thể đúng.

Một quy tắc bổ sung: p² = p#

Đại số thông thường có một quy tắc mà đại số 0/1 không cần, và đại số 0/1 có một quy tắc mà đại số thông thường không có:

p² = p. Các giá trị duy nhất p có thể nhận là 0 và 1, và bình phương để nguyên cả hai. Vậy bất cứ khi nào xuất hiện một bình phương, hãy thay nó bằng chính chữ cái đó.

Quy tắc này là dạng đại số của “p và p chỉ là p”. Nó cũng là điều làm cho các mâu thuẫn biến mất:

p ∧ ¬p trở thành p(1 − p) = p − p² = p − p = 0. Luôn sai. Đó là một mâu thuẫn.

p ∨ ¬p trở thành p + (1 − p) − p(1 − p) = 1 − 0 = 1. Luôn đúng. Đó là một hằng đúng (tautology), một mệnh đề đúng ở mọi dòng.

Ví dụ có lời giải: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)#

Ký hiệu ≡ nghĩa là “tương đương với”: hai vế có cùng giá trị chân trị ở mọi dòng. Đây là ví dụ trong bài giảng.

Vế trái. Trước hết p ∨ q = p + q − pq. Bây giờ lấy “hoặc” kết quả đó với r, dùng cùng công thức với (p + q − pq) thay cho p:

(p + q − pq) + r − (p + q − pq)r = p + q + r − pq − pr − qr + pqr.

Vế phải. Trước hết q ∨ r = q + r − qr. Sau đó p ∨ (kết quả đó):

p + (q + r − qr) − p(q + r − qr) = p + q + r − pq − pr − qr + pqr.

Hai biểu thức giống hệt nhau, nên hai mệnh đề tương đương. Không cần bảng chân trị. Hãy chú ý quy luật: mỗi chữ cái đơn lẻ có dấu +, mỗi cặp có dấu −, bộ ba có dấu +. Biểu thức đối xử với p, q và r như nhau, đó là lý do cách nhóm không quan trọng.

Lối tắt: viết “hoặc” thành một tích#

Nhân khai triển trở nên rối khi có bốn hoặc năm chữ cái. Có một cách gọn hơn, và nó đến từ luật De Morgan: p ∨ q có nghĩa giống ¬(¬p ∧ ¬q). Nói bằng lời, “có ít nhất một mệnh đề đúng” là điều ngược lại của “cả hai đều sai”.

Hãy chuyển đổi: ¬p là 1 − p, “và” là một tích, và “không” bên ngoài là một trừ đi toàn bộ. Vậy

p ∨ q = 1 − (1 − p)(1 − q).

Nhân khai triển ra và bạn được 1 − (1 − p − q + pq) = p + q − pq, cùng công thức như trước. Dạng tích mở rộng dễ dàng:

p ∨ q ∨ r ∨ s = 1 − (1 − p)(1 − q)(1 − r)(1 − s).

Thêm một chữ cái chỉ là thêm một thừa số. Cách nhóm không thể quan trọng, vì phép nhân không quan tâm đến cách nhóm. Đó là chứng minh một dòng cho tính kết hợp của “hoặc”, với số chữ cái bất kỳ.

Ví dụ có lời giải: mệnh đề phản đảo, bằng đại số#

Mệnh đề phản đảo của p → q là ¬q → ¬p. Khẳng định là chúng luôn có cùng giá trị. Dùng công thức điều kiện 1 − a + ab với a = 1 − q (tức là ¬q) và b = 1 − p (tức là ¬p):

1 − (1 − q) + (1 − q)(1 − p)

= q + (1 − p − q + pq)

= 1 − p + pq.

Đó chính xác là công thức của p → q. Đại số chứng minh sự tương đương trong ba dòng.

Một câu để mang vào phòng thi

Hai mệnh đề tương đương khi và chỉ khi các công thức 0/1 của chúng bằng nhau sau khi bạn thay mọi p² bằng p.

Sai ở chỗ nào#

  • Viết p ∨ q là p + q. Nó cho 2 khi cả hai đều đúng. Phần −pq không phải tùy chọn.
  • Quên p² = p. Nếu thiếu nó, p(1 − p) trông như p − p² và có vẻ không rút gọn được. Có nó, đáp án là 0.
  • Viết p → q là 1 − q + pq. Đó là mệnh đề đảo, q → p. Dòng phải bằng 0 là p = 1, q = 0, nên hãy thử dòng đó trước.
  • Dừng lại ở “trông chúng khác nhau”. Hai công thức có thể trông khác nhau mà vẫn bằng nhau sau khi bạn nhân khai triển và dùng p² = p. Luôn rút gọn hoàn toàn cả hai vế trước khi so sánh.

Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí

Luyện tập Discrete Math theo chủ đề: dùng được khi không có mạng, không quảng cáo, không cần tài khoản.

Luyện tập logic 0/1 →

Câu hỏi thường gặp#

Làm sao để biến một mệnh đề logic thành các số 0 và 1?

Viết sai là 0 và đúng là 1. Khi đó không p là 1 − p, p và q là tích pq, p hoặc q là p + q − pq, và nếu p thì q là 1 − p + pq. Hãy xây dựng các mệnh đề lớn hơn bằng cách thay các công thức này vào nhau.

Vì sao p bình phương bằng p trong đại số Boolean?

Vì p chỉ có thể là 0 hoặc 1, và cả hai giá trị này đều không đổi khi bình phương. Nên p² và p bằng nhau ở mọi dòng. Đây là dạng đại số của luật p ∧ p ≡ p.

Làm sao chứng minh hai mệnh đề logic tương đương bằng đại số?

Chuyển cả hai thành công thức 0/1, nhân khai triển mọi thứ, và thay mọi bình phương p² bằng p. Nếu hai kết quả là hai đa thức giống hệt nhau thì hai mệnh đề tương đương. Cách này thay cho bảng chân trị, vốn trở nên rất dài khi có từ bốn chữ cái trở lên.

Công thức 0/1 của phép hoặc loại trừ (exclusive or) là gì?

p + q − 2pq. Nó bằng 1 khi có đúng một trong p và q bằng 1, và bằng 0 khi chúng giống nhau. (p − q)² cho cùng các giá trị, vì nó khai triển thành p² − 2pq + q², và sau khi dùng p² = p thì bằng p + q − 2pq.

Đề xuất chỉnh sửa

Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.