Comparing Boolean Expressions
แนะนำใหม่| English | ความหมาย |
|---|---|
| equivalent/ɪˈkwɪvələnt/ | เทียบเท่า |
| De Morgan's Laws/də ˈmɔːɡənz lɔːz/ | กฎเด摩根 |
ตัวอย่างเดียวที่ขัดแย้งสามารถล้มล้างการเขียนใหม่แบบ Boolean ได้
- การเขียนใหม่ที่ถูกเสนอให้เปลี่ยน !(a && b) เป็น !a && !b ให้ a = true และ b = false
- ค่าเริ่มต้นเป็นจริง แต่การเขียนใหม่ที่เป็นจริงนั้นเป็นเท็จ De Morgan ต้องการ !a || !b ซึ่งสอดคล้องกับค่าเริ่มต้น
เมื่อเงื่อนไขสองอย่างมีความหมายเหมือนกัน
- นิพจน์ Boolean สองนิพจน์จะ เทียบเท่ากัน ก็ต่อเมื่อให้ ผลลัพธ์เดียวกันสำหรับทุกอินพุต สำหรับจำนวนเต็ม
x,x >= 5และ!(x < 5)นั้นเทียบเท่ากัน — ทั้งสองเป็นจริงก็ต่อเมื่อxมีค่าอย่างน้อย5 - สำหรับตัวแปร Boolean ที่ไม่มีผลข้างเคียง นิพจน์ที่เทียบเท่ากันจะให้ผลลัพธ์เหมือนกัน นอกจากนี้ควรตรวจสอบลำดับการประเมินหากนิพจน์เรียกใช้เมทโธดหรือเปลี่ยนแปลงสถานะ ตารางความจริง ใช้พิสูจน์ความเทียบเท่า: ผลลัพธ์ในแถวเดียวกันทั้งหมดต้องตรงกัน
กฎของเดอ摩根
- กฎของเด摩根 (De Morgan's Laws) ช่วยเขียนใหม่ NOT ที่ครอบคลุม AND/OR:
!(a && b)เทียบเท่ากับ!a || !b !(a || b)เทียบเท่ากับ!a && !bรูปแบบคือ: ดัน!เข้าไปด้านใน และ สลับ&&↔||
การลดรูปเงื่อนไข
- ใช้กฎของเด摩根และกฎตรรกะเพื่อเขียนนิพจน์ที่ สั้นลงและชัดเจนขึ้น ที่มีนัยยะเทียบเท่ากัน สำหรับคะแนน integer
!(score < 60)จะกลายเป็นscore >= 60— นัยยะเดิมแต่อ่านง่ายขึ้น - การลบเครื่องหมายลบซ้อนหรือ
!ด้านนอกมักทำให้เจตนารมณ์ชัดเจนขึ้น ตรวจสอบโดเมนอินพุตและพฤติกรรมการประเมินอย่างละเอียด; ตัวอักษรที่น้อยลงไม่จำเป็นต้องหมายความว่ามีความผิดพลาดน้อยกว่า
ตาม De Morgan's Law, !(a && b) สมมูลกับ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Push the ! in and flip && to ||.
ตาม De Morgan's Law, !(a || b) สมมูลกับ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Push the ! in and flip || to &&.
สำหรับคะแนนจำนวนเต็ม Which เป็นสมมูลกับ !(score < 60)?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
not-less-than-60 means at-least-60
Two Boolean expressions are equivalent if they give the same result for every input
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Same output in every truth-table row = equivalent
การ applying De Morgan's Law, !(a && b)会变成 !a && !b
Difficulty 1/5 · 100 coins + a small bonus on first completion today
会变成 !a || !b — the operator must flip
การทดสอบด้วยตารางความจริง
- เพื่อตรวจสอบว่านิพจน์สองนิพจน์เทียบเท่ากันหรือไม่ ให้สร้างตารางสำหรับทั้งสองนิพจน์สำหรับทุกอินพุต หากทุกแถวตรงกัน แสดงว่าเทียบเท่ากัน; หากมีช่องใดช่องหนึ่งไม่ตรง แสดงว่าไม่เทียบเท่ากัน
- สำหรับตัวแปร Boolean ล้วนมีแถวอินพุตสี่แถว ซึ่งกำหนดฟังก์ชันความจริงได้อย่างสมบูรณ์ สิ่งนี้ไม่ได้ระบุผลกระทบจากการเรียกใช้เมทโธดตามใจหรือพิสูจน์ว่าการเขียนใหม่นิพจน์เปรียบเทียบ floating-point ทุกชนิดถูกต้อง
เมื่อใช้กฎของเด摩根 คุณต้องกลับด้านตัวดำเนินการด้วย ไม่ใช่แค่กระจาย ! !(a && b) คือ !a || !b (AND เปลี่ยนเป็น OR) — การเขียน !a && !b เป็น ผิด คำจำ: ดัน NOT เข้าไปและสลับ && ↔ || เมื่อไม่แน่ใจ ใช้ตารางความจริงเพื่อสรุปผลในสี่บรรทัด
สำหรับ a=true และ b=false ค่าของ !(a && b), !a && !b และ !a || !b ตามลำดับคืออะไร?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The mismatching middle expression is a counterexample to the proposed equivalence.
สำหรับคะแนน double เท่ากับ NaN !(score < 60) and score >= 60 return ให้ผลลัพธ์ Boolean เดียวกันหรือไม่
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การเปรียบเทียบ score < 60 and score >= 60 ทั้งคู่เป็น false สำหรับ NaN ดังนั้นนิพจน์แรกที่ถูกปฏิเสธจึงเป็น true และนิพจน์ที่สองเป็น false
ถ้า f() ส่งคืนค่า false g() จะถูกเรียก多少次ในการประเมิน !(f() && g())?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
operand แรกที่เป็น false ทำให้ AND ตัดวงจร (short-circuits) จึงไม่มีการเรียก g นิพจน์สมมูล !f() || !g() ก็ข้าม g เช่นกัน
การเขียนใหม่ !(a && b):
- ผิด:
!a && !b - ถูก (ตามกฎเด摩根):
!a || !b— AND สลับเป็น OR - ตรวจสอบ: ถ้า
a = true, b = false, แล้ว!(true && false) = !false = true, และ!a || !b = false || true = true. ✓
ขยายเหตุผลไปยังกรณีใหม่
- สำหรับตัวแปร Boolean ล้วน คู่ input ทั้งสี่คู่พิสูจน์ความเทียบเท่าได้ รูปแบบ De Morgan รักษาการประเมินแบบ short-circuit จากซ้ายไปขวา:
!(f() && g())และ!f() || !g()จะข้าม g เมื่อ f เป็น false - การสลับ operands เป็นการแปลงรูปแบบที่แตกต่างกัน แม้
a && bและb && aจะมีตารางความจริงเหมือนกันสำหรับตัวแปรล้วน แต่f() && g()และg() && f()อาจเรียกใช้เมทโธดต่างกัน สำหรับ double score=NaN,!(score < 60)เป็นจริงแต่score >= 60เป็นเท็จ; กฎการเปรียบเทียบจำนวนเต็มไม่ขยาย用到 NaN
นิพจน์บูลีนสองรูปจะ เทียบเท่ากัน หากให้ผลลัพธ์ตรงกันสำหรับทุกอินพุต (พิสูจน์ได้ด้วย ตารางความจริง) กฎของเด摩根: !(a && b) = !a || !b และ !(a || b) = !a && !b — ดัน ! เข้าไปภายในและ กลับด้าน && ↔ || ใช้สิ่งเหล่านี้เพื่อ ลดรูป เงื่อนไขให้อยู่ในรูปแบบที่เทียบเท่ากันและชัดเจนยิ่งขึ้น