หน่วยที่ 3 พีชคณิตบูลีน

115 ใบความรู้ เรื่อง พชี คณติ บูลนี     บทนํา พีชคณิตบูลีนเป็ นศาสตร์อีกแขนงหน่ึงที่นาํ เอาเคร่ืองหมาย สัญลกั ษณ์ หรือสมการ มาแทนการทํางานของลอจิกเกต วงจรลอจิกเกต หรื อวงจรดิจิตอล ซ่ึงมีความสอดคล้อง และเกี่ยวขอ้ งซ่ึงกนั และกนั ถูกคิดคน้ โดยนกั คณิตศาสตร์ชาวองั กฤษชื่อ จอร์จ บูล เมื่อปี พ.ศ.2390 เรียกสมการน้ีว่า “สมการลอจิก” หรือ “สมการบูลีน” ทฤษฎีพีชคณิตบูลีนน้ีถูกนํามาใช้ลดรูป สมการ วิเคราะห์ ออกแบบ และแกไ้ ขวงจรดิจิตอลเบ้ืองตน้ อยา่ งแพร่หลายจนถึงปัจจุบนั 3.1 ทฤษฎพี ชี คณติ บูลนี และการพสิ ูจน์เปรียบเทยี บ ทฤษฎีพีชคณิตบูลีนไดก้ าํ หนดกฎและสูตรต่าง เพ่ือนาํ ไวใ้ ช้แกป้ ัญหา พอท่ีจะแยก หมวดหม่ไู ดด้ งั น้ี 1. กฎของแอนด์ ตารางท่ี 3.1 พชี คณิตบูลีนกฎของแอนดแ์ ละการพิสูจน์เปรียบเทียบ กฎของแอนด์ การพิสูจนเ์ ปรียบเทียบ 1. A.0 = 0 A0 2. A.1 = A AA

116 ตารางที่ 3.1 พชี คณิตบลู ีนกฎของแอนดแ์ ละการพสิ ูจน์เปรียบเทียบ (ตอ่ ) กฎของแอนด์ การพสิ ูจน์เปรียบเทียบ 3. A.A = A AA A 4. A.A = 0 A 0 A 2. กฎของออร์ ตารางที่ 3.2 พชี คณิตบลู ีนกฎของออร์และการพิสูจน์เปรียบเทียบ กฎของออร์ การพสิ ูจน์เปรียบเทียบ 1. A + 0 = A AA 2. A + 1 = A 1 A

117 ตารางที่ 3.2 พชี คณิตบลู ีนกฎของออร์และการพสิ ูจน์เปรียบเทียบ (ต่อ) กฎของออร์ การพสิ ูจน์เปรียบเทียบ 3. A + A = A AA A 4. A + A = 1 A 1 A 3. กฎของนอต ตารางท่ี 3.3 พชี คณิตบลู ีนกฎของนอตและการพิสูจนเ์ ปรียบเทียบ กฎของนอต การพสิ ูจนเ์ ปรียบเทียบ 1. 0 = 1 1 2. 1 = 0 0 3. A = A AA

118 ตารางท่ี 3.3 พชี คณิตบูลีนกฎของนอตและการพสิ ูจนเ์ ปรียบเทียบ (ต่อ) กฎของนอต การพิสูจนเ์ ปรียบเทียบ A1 4. ถา้ กาํ หนดให้ A = 0 จะได้ A = 1 5. ถา้ กาํ หนดให้ A = 1     จะได้ A = 0 A  0   4. กฎของการสลบั ท่ี (Commutative law) ตารางท่ี 3.4 พชี คณิตบูลีนกฎของการสลบั ที่และการพสิ ูจน์เปรียบเทียบ กฎของการสลบั ท่ี การพสิ ูจนเ์ ปรียบเทียบ A A+B B 1. A + B = B + A B B+A A 2. A.B = B.A A A+B B B B+A A

119 5. กฎของการรวมกนั (Association law) ตารางท่ี 3.5 พชี คณิตบลู ีนกฎของการรวมกนั และการพสิ ูจนเ์ ปรียบเทียบ กฎของการรวมกนั การพิสูจนเ์ ปรียบเทียบ 1. (A + B) + C = A + (B + C) A (A+B)+C B A+(B+C) C A B C 2. (A . B) . C = A . (B . C) A (A.B).C B A.(B.C) C A B C 6. กฎของการกระจาย (Distributive law) 1. A + AB = A + B สามารถพิสูจน์ไดจ้ ากตารางความจริง โดยใชค้ ุณสมบตั ิการ ทาํ งานของออร์เกต แอนดเ์ กต และนอตเกตจะไดด้ งั น้ี ตารางที่ 3.6 กฎของการกระจายขอ้ ท่ี 1 และการพสิ ูจนเ์ ปรียบเทียบ A B A AB A + AB A+B 001000 011111 100011 110011

120 2. A + AB = A + B สามารถพสิ ูจนไ์ ดจ้ ากตารางความจริง โดยใชค้ ุณสมบตั ิการ ทาํ งานของนอตเกต แอนดเ์ กต และออร์เกตจะไดด้ งั น้ี ตารางท่ี 3.7 กฎของการกระจายขอ้ ที่ 2 และการพิสูจนเ์ ปรียบเทียบ A B A AB A+AB A+B 001011 011011 100000 110111 3. A (B + C) = (AB) + (AC) สามารถพิสูจนไ์ ดจ้ ากตารางความจริง โดยใชค้ ุณสมบตั ิการทาํ งานของแอนดเ์ กตและออร์เกตจะไดด้ งั น้ี ตารางที่ 3.8 กฎของการกระจายขอ้ ท่ี 3 และการพิสูจนเ์ ปรียบเทียบ A B C AB AC B + C A(B+C) (AB)+(AC) 000000 0 0 001001 0 0 010001 0 0 011001 0 0 100000 0 0 101011 1 1 110101 1 1 111111 1 1

121 4. A + (BC) = (A + B) (A + C) สามารถพสิ ูจนไ์ ดจ้ ากตารางความจริง โดยใชค้ ุณสมบตั ิการทาํ งานของแอนดเ์ กต และออร์เกตจะไดด้ งั น้ี ตารางที่ 3.9 กฎของการกระจายขอ้ ท่ี 4 และการพสิ ูจนเ์ ปรียบเทียบ A B C BC A+B A+C A+(BC) (A+B)(A+C) 000000 0 0 001001 0 0 010010 0 0 011111 1 1 100011 1 1 101011 1 1 110011 1 1 111111 1 1 3.2 การใช้พชี คณติ บูลนี ลดรูปสมการลอจกิ สมการลอจิกที่ยาวทําให้วงจรลอจิกใหญ่ จึงไม่เป็ นการประหยัดในการสร้างวงจร แต่เรามีวิธีในการลดรูปของสมการลอจิกได้ โดยใช้ทฤษฎีพีชคณิตบูลีนท่ีได้ศึกษามาตอนตน้ ดงั ตวั อยา่ งต่อไปน้ี ตวั อย่างที่ 3.1 จงลดรูปสมการต่อไปน้ีใหส้ ้นั ท่ีสุด ก. Y = BC + BC + BC ข. Y = ABC + ABC + BC ค. Y = ABC + ABC + ABC + ABC

122 วธิ ีทาํ ขอ้ (ก) Y = BC + BC + BC = C(B + B) + BC ตอบ = C . 1 + BC วธิ ีทาํ ขอ้ (ข) = C + BC = C+B ตอบ วธิ ีทาํ ขอ้ (ค) Y = ABC + ABC + BC = BC(A + A + 1) ตอบ = BC Y = ABC + ABC + ABC + ABC = AB(C + C) + AB(C + C) = AB + AB = A(B + B) =A

123 3.3 ทฤษฎขี องเดอร์มอร์แกนและการพสิ ูจน์เปรียบเทยี บ ทฤษฎีเดอร์มอร์แกน (DeMorgan's Theorems) คิดคน้ จากนกั คณิตศาสตร์อีกผหู้ น่ึง ที่มีช่ือว่า “เดอร์มอร์แกน” ทฤษฎีน้ีใชเ้ ป็ นวิธีที่นาํ มาช่วยในการแกป้ ัญหาพีชคณิตบูลี โดยมีคาํ นิยามว่า สามารถเปล่ียนรูปของสมการลอจิกจากคอมพลีเมนต์ของแอนด์ เป็ นการออร์กัน ของคอมพลีเมนตต์ วั แปร และเปล่ียนรูปของสมการลอจิกจากคอมพลีเมนตข์ องออร์ เป็นการแอนด์ กนั ของคอมพลีเมนตต์ วั แปร หรือเรียกให้จาํ ไดง้ ่ายว่า บฟั เบิลออร์แทนแนนด์ และบฟั เบิลแอนด์ แทนนอร์ พิสูจน์ไดด้ งั น้ี 1. A . B = A + B ตารางท่ี 3.10 พิสูจน์ทฤษฎีเดอร์มอร์แกน บฟั เบิลออร์แทนแนนด์ A B A B A.B A+B 0011 1 1 0110 1 1 1001 1 1 1100 0 0 2. A + B = A . B ตารางท่ี 3.11 พิสูจน์ทฤษฎีเดอร์มอร์แกน บฟั เบิลแอนดแ์ ทนนอร์ A B A B A+B A.B 1 0011 1 0 0 0110 0 0 1001 0 1100 0

124 3.4 การใช้ทฤษฎขี องเดอร์มอร์แกนออกแบบวงจรลอจกิ โดยใช้แนนด์เกตหรือนอร์เกต เพยี งชนิดเดยี ว วธิ ีการท่ีจะใชแ้ นนดเ์ กตหรือนอร์เกตเพียงชนิดเดียวในวงจรที่เราออกแบบน้นั มีวธิ ีการดงั น้ี 1. ใส่เครื่องหมายบาร์ (BAR) ตลอดท้งั สมการลอจิกจาํ นวน 2 คร้ัง 2. ใชท้ ฤษฎีเดอร์มอร์แกน เพื่อเปลี่ยนสถานะของตวั แปรและทาํ ใหเ้ หลือบาร์ เพยี งอนั เดียว 3. นาํ สมการลอจิกที่ไดไ้ ปเขียนวงจรลอจิก ตวั อย่างท่ี 3.2 จากสมการ Y = A + BC จงออกแบบวงจรโดยใชแ้ นนดเ์ กตเพยี งชนิดเดียว วธิ ีทาํ Y = AB + C ขอ้ (1) = AB . C ขอ้ (2) ขอ้ (3) A Y B C ตวั อย่างที่ 3.3 จากสมการ Y = (A + B)(B + C) จงออกแบบวงจรโดยใชน้ อร์เกตเพยี งชนิดเดียว วธิ ีทาํ Y = (A + B)(B + C) ขอ้ (1) = (A + B) + (B + C) ขอ้ (2) ขอ้ (3) A Y B C