So sánh Biểu thức Boolean
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| equivalent/ɪˈkwɪvələnt/ | tương đương |
| De Morgan's Laws/də ˈmɔːɡənz lɔːz/ | Định luật De Morgan |
Một ví dụ phản chứng đủ để bác bỏ phép biến đổi Boolean
- Một phép biến đổi đề xuất chuyển !(a && b) thành !a && !b. Đặt a = true và b = false.
- Giá trị ban đầu là true, trong khi phép biến đổi đề xuất là false. Định lý De Morgan yêu cầu !a || !b, điều này phù hợp với giá trị ban đầu.
Khi hai điều kiện có nghĩa giống nhau
- Hai biểu thức Boolean được gọi là tương đương nếu chúng trả về kết quả giống hệt nhau cho mọi đầu vào. Đối với số nguyên
x,x >= 5và!(x < 5)là tương đương — cả hai đều là true chính xác khixlớn hơn hoặc bằng5. - Đối với các biến Boolean không có tác dụng phụ, các biểu thức tương đương sẽ có kết quả giống nhau. Ngoài ra, hãy kiểm tra thứ tự đánh giá nếu biểu thức gọi các phương pháp hoặc thay đổi trạng thái. Một bảng chân lý chứng minh sự tương đương: cùng một đầu ra ở mỗi hàng.
Định luật De Morgan
- Định lý De Morgan viết lại một NOT phủ định trên AND/OR:
!(a && b)bằng!a || !b. !(a || b)bằng!a && !b. Quy tắc: đẩy!vào bên trong, và đảo ngược&&↔||.
Rút gọn điều kiện
- Sử dụng Định lý De Morgan và quy tắc logic để viết một biểu thức tương đương ngắn gọn, rõ ràng hơn. Đối với điểm số là số nguyên,
!(score < 60)trở thànhscore >= 60— cùng ý nghĩa nhưng dễ đọc hơn. - Việc loại bỏ phép phủ định kép hoặc
!bao ngoài thường làm rõ ý đồ. Hãy kiểm tra miền đầu vào và hành vi đánh giá chính xác; ít ký tự hơn không đảm bảo ít lỗi hơn.
Theo Định lý De Morgan, !(a && b) tương đương với...
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Đẩy ! vào trong và đổi && thành ||.
Theo Định lý De Morgan, !(a || b) tương đương với...
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Đẩy ! vào trong và đổi || thành &&.
Đối với một điểm số nguyên, biểu thức nào tương đương với !(score < 60)?
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
not-less-than-60 có nghĩa at-least-60.
Hai biểu thức Boolean tương đương nếu chúng cho cùng một kết quả với mọi đầu vào.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Cùng một đầu ra trong mỗi hàng bảng chân lý = tương đương.
Áp dụng Định lý De Morgan, !(a && b) trở thành !a && !b.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Nó trở thành !a || !b — toán tử phải đổi.
Kiểm tra với bảng chân lý
- Để kiểm tra xem hai biểu thức có tương đương hay không, hãy lập bảng cho tất cả các đầu vào. Nếu mọi hàng khớp nhau, chúng tương đương; một sự không khớp bất kỳ nghĩa là chúng không tương đương.
- Đối với hai biến Boolean thuần túy, có bốn hàng đầu vào, điều này hoàn toàn xác định hàm chân lý. Điều này không liệt kê hết các tác động của các cuộc gọi phương thức tùy ý hay chứng minh mọi việc chuyển đổi so sánh số thực (floating-point).
Khi áp dụng Định luật De Morgan, bạn phải đảo ngược toán tử, không chỉ phân phối !. !(a && b) là !a || !b (AND thành OR) — viết !a && !b là sai. Mẹo ghi nhớ: đẩy NOT vào trong và hoán đổi && ↔ ||. Khi không chắc chắn, bảng chân lý sẽ giải quyết vấn đề này trong bốn hàng.
Với a=true và b=false, giá trị của !(a && b), !a && !b, và !a || !b là gì, theo thứ tự đó?
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
The mismatching middle expression is a counterexample to the proposed equivalence.
Đối với một điểm số double bằng NaN, !(score < 60) and score >= 60 return có tạo ra kết quả Boolean giống nhau không?
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Các phép so sánh score < 60 and score >= 60 đều trả về false đối với NaN, do đó biểu thức phủ định đầu tiên là true và biểu thức thứ hai là false.
Nếu f() trả về false, g() được thực thi bao nhiêu lần khi đánh giá !(f() && g())?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Tham số đầu tiên là false sẽ làm ngắt vòng lặp ngắn (short-circuit) của toán tử &&, nên g() không được gọi. Biểu thức tương đương !f() || !g() cũng bỏ qua g().
Viết lại !(a && b):
- Sai:
!a && !b. - Đúng (De Morgan):
!a || !b— AND đảo thành OR. - Kiểm tra: nếu
a = true, b = false, thì!(true && false) = !false = true, và!a || !b = false || true = true. ✓
Mở rộng suy luận sang trường hợp mới
- Đối với các biến Boolean thuần túy, cả bốn cặp đầu vào đều chứng minh tính tương đương. Các dạng De Morgan bảo toàn thứ tự đánh giá ngắn gọn từ trái sang phải:
!(f() && g())và!f() || !g()đều bỏ qua g khi f là false. - Hoán đổi các toán tử là một phép biến đổi khác. Mặc dù
a && bvàb && acó cùng bảng chân lý cho các biến thuần túy, nhưngf() && g()vàg() && f()có thể gọi các phương thức khác nhau. Đối với double score=NaN, biểu thức!(score < 60)là đúng nhưngscore >= 60là sai; quy tắc so sánh số nguyên không mở rộng sang NaN.
Hai biểu thức Boolean tương đương nếu chúng cho kết quả giống nhau với mọi đầu vào (có thể chứng minh bằng bảng chân lý). Định luật De Morgan: !(a && b) = !a || !b và !(a || b) = !a && !b — đẩy ! vào trong và đảo && ↔ ||. Sử dụng các định luật này để đơn giản hóa điều kiện thành các dạng tương đương rõ ràng hơn.