พีชคณิตบูลีนและแผนที่คาร์โน
| English | ไทย |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | พีชคณิตบูลีน |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | กฎของเด摩根 |
| Karnaugh map/ˈkɑːnɔː mæp/ | แผนที่คาร์นัฟ |
| truth table/truːθ ˈteɪbl/ | ตารางความจริง |
| absorption/əbˈsɔːpʃn/ | การดูดซับ |
| Gray code/ɡreɪ kəʊd/ | โค้ดเกรย์ |
วิทยานิพนธ์ระดับปริญญาเอกที่สร้างยุคดิจิทัล
- ในปี 1937 นักเรียนอายุ 21 ปีชื่อ Claude Shannon สังเกตว่ารีเลย์โทรศัพท์ที่เขาศึกษาทำงานเหมือนกับพีชคณิตที่ George Boole คิดค้นไว้ก่อนหน้าแปดสิบปี เพื่อใช้เหตุผลเกี่ยวกับค่าจริงและค่าเท็จ
- หากสวิตช์เป็นตัวแปร Boolean วงจรจะเป็นนิพจน์ และการลดทอนนิพจน์จะ กำจัดเกตออกจากวงจร เกตน้อยลงหมายความว่าถูกกว่า เร็วขึ้น และใช้พลังงานน้อยลง
- วิทยานิพนธ์ของเขาถูกเรียกว่าสำคัญที่สุดของศตวรรษ สิ่งทั้งหมดในหน้านี้คือไอเดียหนึ่งนั้นที่ถูกใช้เป็นเครื่องมือ
- บทเรียนนี้คือ Boolean algebra, กฎของ De Morgan และ Karnaugh map ที่ทำหน้าที่เดียวกันด้วยการมองด้วยตาเปล่า
สัญลักษณ์และกฎ
+หมายถึง OR,·หมายถึง AND และมักถูกละไว้, และเส้นบนหมายถึง NOT. Truth table อธิบายสิ่งเดียวกันอย่างครบถ้วน- Identity: $A + 0 = A$ และ $A \cdot 1 = A$. Null: $A + 1 = 1$ และ $A \cdot 0 = 0$.
- Idempotent: $A + A = A$. Inverse: $A + \overline{A} = 1$ และ $A \cdot \overline{A} = 0$.
- Absorption: $A + A\cdot B = A$, เพราะถ้า $A$ เป็นจริง นิพจน์ทั้งหมดจะเป็นจริงไม่ว่า $B$ จะเป็นอย่างไรก็ตาม
จับคู่กฎ布尔每个到它所表达的内容。
กฎเหล่านี้ช่วยให้คุณสามารถลดรูปนิพจน์ Boolean แบบพีชคณิตก่อนสร้างวงจร
ตามกฎการดูดกลืน, A + A·B จะลดรูปเป็น ____.
ถ้า A เป็นจริง expression ทั้งหมดยิ่งเป็นจริงไม่ว่า B จะเป็นอะไร และถ้า A เป็นเท็จ พจน์ทั้งสองจะเป็นเท็จ Both B ไม่สามารถส่งผลต่อผลลัพธ์ได้
กฎของเดอ มอร์แกน
- De Morgan's laws คือกฎสองข้อที่ข้อสอบขอให้ใช้โดยระบุชื่อ:
- สูตรคำพูด: ลบทอนทั้ง-expression, สลับ AND และ OR, ลบทอนแต่ละ operand
- มีความสำคัญทางปฏิบัติเพราะช่วยให้สามารถเขียนนิพจน์ใดๆ ใหม่โดยใช้เพียง NAND gates หรือเพียง NOR gates เท่านั้น, และชิปที่สร้างจากเกตซ้ำๆ ตัวเดียวจะมีต้นทุนการผลิตต่ำกว่า
สองนิพจน์, ตารางความจริงหนึ่ง,
พีชคณิตบูลีน
A·B, A+B, Ā …
พีชคณิตบูลีนก็คือเกตเหล่านี้เขียนเป็นนิพจน์ — เปรียบเทียบตารางความจริง
ตามกฎของเดมอร์แกน, $\overline{A \cdot B}$ เท่ากับ:
ลบออกทั้ง-expression, สลับ AND→OR, ลบออกแต่ละ operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$
การประยุกต์ใช้กฎเดมอร์แกนกับนิพจน์ใด ๆ ต้องผ่านขั้นตอนใด? เลือก ทุก ข้อที่ถูกต้อง
ลบออกทั้ง-expression, สลับ operator, ลบออกแต่ละส่วน ลำดับไม่สำคัญ เพราะ AND และ OR มีสมบัติการสับเปลี่ยน
ตัวอย่างวิธีทำ: ลดทอน และนับจำนวนเกต
- ลดทอน $Z = A\cdot B + A\cdot\overline{B}$ และบอกว่าจะประหยัดอะไร
- ดึง $A$ ออกมา: $Z = A\cdot(B + \overline{B})$. ตามกฎ Inverse $B + \overline{B} = 1$, ดังนั้น $Z = A \cdot 1 = A$
- expresion เดิมต้องใช้ AND gate สองตัว, NOT หนึ่งตัว และ OR หนึ่งตัว: รวมสี่เกต นิพจน์ที่ลดทอนแล้วต้องการ ไม่มีเลย มีเพียงอินพุต $A$
- ต้องจบเสมอด้วยการบอกว่าผลจากการลดทอน ได้มาอะไร: เกตน้อยลง ดังนั้นวงจรที่ถูกกว่า เร็วกว่า และใช้พลังงานน้อยกว่า
ลดรูป $A\cdot B + A\cdot\overline{B}$
ดึง A ออกมา: $A(B + \overline{B}) = A \cdot 1 = A$
A·B + A·NOT B ต้องการ AND สองตัว, NOT หนึ่งตัว และ OR หนึ่งตัว รูปแบบที่ลดรูปแล้วต้องการ gate จำนวนเท่าไร?
มันลดรูปเหลือเพียง A ดังนั้น output คือ input โดยไม่ต้องใช้ gate เลย ประหยัดไปสี่ gates
Karnaugh map
- Karnaugh map ช่วยลดทอนนิพจน์ bằngการ จัดกลุ่ม 1s ที่อยู่ติดกัน จากตารางความจริง
- แถวและหลักมีป้ายกำกับตามลำดับ Gray code,
00, 01, 11, 10, เพื่อให้ เซลล์ที่อยู่ติดกันต่างกันเพียงตัวแปรเดียวเท่านั้น นั่นคือเทคนิคทั้งหมด: ทำให้พีชคณิตมองเห็นได้ผ่านความ毗邻 - วาง 1 ในแต่ละเซลล์ที่ผลลัพธ์เป็น 1, จากนั้นหากลุ่มสี่เหลี่ยมผืนผ้าของ 1s ที่มีด้านเป็นเลขยกกำลังสอง: 1, 2, 4, 8. กลุ่มอาจ ม้วนรอบขอบ ได้
สี่เหลี่ยมใหญ่เท่าไร พจน์ก็ยิ่งง่ายขึ้นเท่านั้น
ตาราง Karnaugh ลดรูปนิพจน์ Boolean bằng cách:
คุณจัดกลุ่ม 1 ที่ติดกัน (ในลำดับ Gray-code) เป็นสี่เหลี่ยมขนาดกำลังสอง; แต่ละกลุ่มกลายเป็นพจน์ที่ลดรูปแล้ว
ทำไมแถวและหลักของตาราง Karnaugh จึงติดป้ายว่า 00, 01, 11, 10 แทนที่จะเป็น 00, 01, 10, 11?
ลำดับ Gray-code ทำให้ความติดกันในทางพีชคณิตกลายเป็นความติดกันในทางกายภาพ ในลำดับการนับกฎการจัดกลุ่มจะทำงานไม่ได้เลย
อ่านกลุ่ม
- ภายในกลุ่ม ตัวแปรที่ คงที่ จะคงอยู่ในพจน์; ตัวแปรที่ เปลี่ยนแปลง จะหายไป
- ดังนั้นกลุ่มขนาด 2 จะตัดตัวแปรหนึ่งออก, กลุ่มขนาด 4 ตัดสองตัว, และกลุ่มขนาด 8 ตัดสามตัว. กลุ่มยิ่งใหญ่ พจน์ยิ่งง่ายขึ้น
- ครอบคลุม 1 ทั้งหมดโดยใช้กลุ่มที่ น้อยที่สุด และ ใหญ่ที่สุด เท่าที่จะเป็นไปได้, แล้วนำพจน์ของกลุ่มมา OR เข้าด้วยกัน กลุ่มอาจซ้อนทับกันได้ และการซ้อนทับมักเป็นสิ่งที่ทำให้สามารถสร้างกลุ่มที่ใหญ่ขึ้นได้
ในตาราง Karnaugh กลุ่ม 1 ที่ติดกันขนาดใหญ่ขึ้นจะกำจัดตัวแปรได้มากกว่า ให้พจน์ที่ง่ายขึ้น (กลุ่ม 2 ตัดตัวแปรหนึ่งตัว, กลุ่ม 4 ตัดตัวแปรสองตัว)
คุณจัดกลุ่ม 1 ที่ติดกันเป็นสี่เหลี่ยมขนาดกำลังสองตามลำดับ Gray-code; กลุ่มยิ่งใหญ่ พจน์ที่ได้ยิ่งง่ายขึ้น
เรียงลำดับขั้นตอนการลดรูปด้วยตาราง Karnaugh
Gray code, หนึ่ง, กลุ่มที่ใหญ่ที่สุด, ตัดสิ่งที่เปลี่ยน, OR พจน์ ใช้กลุ่มน้อยที่สุดและใหญ่ที่สุดที่จะครอบคลุม 1 ทั้งหมด
ตัวอย่างวิธีทำ: อ่าน K-map สองตัวแปร
- Karnaugh map สำหรับ $A$ และ $B$ มี 1s ในเซลล์ $\overline{A}B$ และ $AB$. ลดทอน
- 1s ทั้งสองอยู่毗邻กัน: ониแบ่งหลัก $B = 1$ ร่วมกัน, ดังนั้นจึงจัดกลุ่มเป็นสี่เหลี่ยมผืนผ้าขนาด 2
- ภายในกลุ่มนั้น $B$ คงเป็น 1 ตลอดเวลา, ในขณะที่ $A$ เปลี่ยนจาก 0 เป็น 1 ตัวแปรที่เปลี่ยนแปลงจะหายไป
- ดังนั้นนิพจน์ทั้งหมดจึงเป็นเพียง $Z = B$ เปรียบเทียบกับผลบวกของผลคูณที่ไม่ได้ลดทอน, $\overline{A}B + AB$, ซึ่งต้องใช้ NOT, AND สองตัว และ OR หนึ่งตัว
ควรใช้วิธีใด
- Boolean algebra แม่นยำและใช้ได้กับตัวแปรจำนวนเท่าใดก็ได้, แต่คุณต้องสังเกตว่ากฎใดใช้ได้นะ
- Karnaugh map เป็นกระบวนการเชิงกลและยากที่จะผิดสำหรับ สองถึงสี่ตัวแปร, ซึ่งเป็นสิ่งที่ข้อสอบกำหนด, และมันแสดงให้ดูว่าจัดกลุ่มที่ใหญ่ที่สุดได้อย่างไรโดยตรง
- ทั้งสองวิธีให้คำตอบเหมือนกัน ประโยชน์ของ K-map คือการลดทอนกลายเป็น การมอง, ไม่ใช่การค้นหากฎ
คะแนนที่หลุดหายไป
- De Morgan คือ ลบทอนทั้ง-expression, สลับ operator, ลบทอนแต่ละส่วน การเปลี่ยนเพียง operator เท่านั้นคือคำตอบครึ่งหนึ่งแบบคลาสสิก
- แถวของ K-map ต้องเรียงตามลำดับ Gray code,
00, 01, 11, 10. ในลำดับนับแบบ binary ความ毗邻จะผิดและการจัดกลุ่มจะล้มเหลว - ขนาดกลุ่มคือ เลขยกกำลังสอง และสามารถม้วนรอบขอบได้ กลุ่มขนาดสามไม่ใช่กลุ่ม
- บอกว่าการลดทอนมี เพื่ออะไร: เกตน้อยลง ดังนั้นถูกกว่า เร็วกว่า และใช้พลังงานต่ำ
คุณเข้าใจแล้ว
- Boolean algebra เขียนนิพจน์ใหม่ให้เป็นพจน์ที่น้อยลง, ดังนั้นวงจรจึงต้องการ เกตน้อยลง
- De Morgan: $\overline{A + B} = \overline{A} \cdot \overline{B}$ และ $\overline{A \cdot B} = \overline{A} + \overline{B}$; absorption: $A + AB = A$; $A\cdot B + A\cdot\overline{B} = A$
- Karnaugh map จัดกลุ่ม 1s ที่อยู่毗邻กันจากตารางความจริง, โดยมีแถวและหลักเรียงตามลำดับ Gray code เพื่อนบ้านต่างกันในตัวแปรเดียว
- ตัวแปรที่เปลี่ยนแปลงภายในกลุ่มจะหายไป, ดังนั้น กลุ่มใหญ่กว่าให้พจน์ที่ง่ายขึ้น: ครอบคลุม 1 ทุกตัวโดยใช้กลุ่มที่น้อยที่สุด ใหญ่ที่สุด เท่าที่จะทำได้