พีชคณิตบูลีน

พีชคณิตบูลีน (Boolean ) เป็นเครื่องมือ ที่ช่วยในการวิเคราะห์และออกแบบระบบดิจิตอล พีชคณิตบูลีนทำให้เราสามารถอธิบายความสัมพันธ์ระหว่าง เอาต์พุตและอินพุตของลอจิกเกตในรูปของสมการพีชคณิตหรือ นิพจน์บูลีน (Boolean expression)

1. การอธิบายวงจรลอจิกในรูปพีชคณิต

วงจรลอจิกใดๆ ไม่ว่าจะมีความซับซ้อนมากเพียงใด เราก็สามารถจะอธิบายด้วยการดำเนินการบูลีนได้ เนื่องจากมีการดำเนินการ OR, AND และ NOT เป็นการดำเนินการพื้นฐานของระบบดิจิตอล ตัวอย่างในรูปที่ 1.1 แสดงการเขียนนิพจน์ที่ใช้แสดงความสัมพันธ์ระหว่าง เอาต์พุต x กับ อินพุต A, B และ C ของวงจรลอจิก จะเห็นได้ว่าแอนด์เกตทำการแอนด์ อินพุต Aและ B จากนั้นจึงถูกออร์กับ อินพุต C โดย ออร์เกต ได้ผลลัพธ์เป็นเอาต์พุต x ในที่สุด เพื่อไม่ให้เกิดความสับสน ในกรณีที่มีการออร์และแอนด์ในวงจรลอจิก จะกำหนดให้การดำเนินการแอนด์เกิดขึ้นก่อนการออร์ ยกเว้นหากมีการใส่วงเล็บกำหนดการดำเนินการไว้อย่างชัดเจน ซึ่งมีลักษณะคล้ายกับ อับดับของการดำเนินการทางพีชคณิตทั่วๆไป ที่จะทำการคูณตัวเลขก่อนทำการบวก รูปที่ 1.2 และ 1.3 แสดงตัวอย่างวงจรลอจิกและการเขียนนิพจน์ของวงจรลอจิกที่มีการดำเนินการออร์ก่อน แอนด์ และวงจรที่มีการใช้นอตเกตหรือ อินเวอร์เตอร์ ตามลำดับ รูปที่ 1.4 แสดงตัวอย่างวงจรลอจิกที่มีความซับซ้อน การใช้วงเล็บหลายแบบมาแยกการดำเนินการจะช่วยให้นิพจน์ดูง่ายไม่สับสน

2. การหาค่าเอาต์พุตของวงจรลอจิก

            เมื่อนิพจน์บูลีนของเอาต์พุตของวงจรลอจิกสามารถเขียนออกมาได้ การหาค่าเอาต์พุต สำหรับชุดอินพุตหนึ่งๆสามารถหาได้โดยการแทนค่าระดับลอจิก “0”, “1” ของอินพุตนั้นๆ ลงไปในตัวแปรภายในนิพจน์ ยกตัวอย่างการหาลอจิกเอาต์พุตของวงจรในรูปที่ 1.4 สำหรับกรณีที่อินพุตเป็น A = 0, B = 1, C = 1, D = 0 และ E = 1 จะได้ผลลัพธ์ดังนี้

กฎพื้นฐานในการแทนค่าในนิพจน์บูลีนมีดังนี้

1. แทนค่านิเสธในเทอมเดี่ยวให้หมดเสียก่อน 

2. แทนค่าภายในวงเล็บ

3. ดำเนินการแอนด์ก่อนการออร์ยกเว้นมีวงเล็บกำกับไว้

4. ถ้านิพจน์มีนิเสธคร่อมอยู่ให้ดำเนินการภายในนิพจน์ดังกล่าว แล้วจึงกลับผลลอจิก

            นอกจากนี้แล้ว เรายังสามารถหาค่าลอจิกเอาต์พุตของวงจรลอจิกได้โดยการแทนค่าลอจิกลงในวงจร ดังตัวอย่างในรูปที่ 2.1

3. การสร้างวงจรลอจิกจากนิพจน์บูลีน

            หากการดำเนินการของวงจรลอจิกเขียนอยู่ในรูปนิพจน์บูลีน เราสามารถนำมาสร้างวงจรลอจิกได้โดยตรง พิจารณานิพจน์ เราจะเห็นว่านิพจน์นี้ประกอบไปด้วยสามเทอม ที่ออร์กัน ดังนั้น เราต้องใช้ออร์เกตที่มีสามอินพุตมาใช้ในวงจร และอินพุตของออร์เกต ก็เป็นเทอมการแอนด์ ซึ่งนิยมเรียกว่า เทอมของผลคูณ (Product term) เราจะสามารถวาดรูปวงจรลอจิกสุดท้ายได้ดังรูปที่ 3.1

ในหัวข้อต่อๆไปเราจะได้ศึกษาถึงวิธีการออกแบบวงจรลอจิกที่ใช้จำนวนลอจิกเกตน้อยกว่าวิธีทางตรง แต่สามารถให้ผลของลอจิกเอาต์พุตที่เหมือนกัน

4. ทฤษฎีบทของบูลีน

            ที่ผ่านมาเราจะเห็นถึงประโยชน์ของการใช้พีชคณิตบูลีน ในการวิเคราะห์วงจรลอจิก และแทนการดำเนินการของวงจรลอจิกในรูปแบบนิพจน์คณิตศาสตร์ได้ ในหัวข้อนี้ เราจะได้เรียนรู้เกี่ยวกับทฤษฎีบทของบูลีนหรือ กฎของบูลีน ซึ่งจะสามารถช่วยให้เราลดรูปวงจรลอจิกให้มีขนาดเล็กลง ในที่นี้กำหนดให้ตัวแปร x เป็นตัวแปรบูลีนที่สามารถเป็นได้ทั้ง “0” และ “1” ในแต่ล่ะข้อจะมีรูปวงจรแสดงถึงการมีอยู่ของกฎนั้น

          1. ตัวแปร xใดๆ ถ้าแอนด์กับ “0” ผลลัพธ์ของลอจิก ต้องเป็น “0”

          2. ตัวแปร xใดๆ ถ้าแอนด์กับ “1” ผลลัพธ์ของลอจิก เท่ากับลอจิกของ x

          3. ตัวแปร xใดๆ ถ้าแอนด์กับตัวมันเอง ผลลัพธ์ของลอจิก เท่ากับลอจิกของ x พิสูจน์จาก หาก x = 0 ดังนั้น0 . 0 = 0 ; หาก 1 . 1 = 1 ดังนั้น

          4. ตัวแปร x ใด หากแอนด์กับคอมพลีเมนต์ของตัวมันเอง (  ) ผลลัพธ์ของลอจิกเป็น “0”

          5. ตัวแปร x ใดๆ หากออร์กับ “0” ผลลัพธ์ของลอจิกไม่เปลี่ยนแปลง

          6. ตัวแปร x ใดๆ หากออร์กับ “1” ผลลัพธ์ลอจิกต้องเป็น “1”

          7. ตัวแปร x ใดๆ หากออร์กับตัวมันเอง ผลลัพธ์ลอจิกเท่ากับลอจิกของ x

          8. ตัวแปร x ใดๆ หาก ออร์กับคอมพลีเมนต์ของตัวเอง ผลลัพธ์ลอจิกเท่ากับ “1”

ต่อไปนี้จะเป็นตัวอย่างการลดรูปโดยใช้ทฤษฎีบทของบูลีน เพื่อให้วงจรลอจิกใช้จำนวนเกตลดลง

5. ทฤษฎีบทของ ดีมอร์แกน

 ทฤษฎีบทที่สำคัญที่สุดสองข้อ ของทฤษฎีบทของบูลีน มาจากการคิดค้นของ นักคณิตศาสตร์เอกนามว่า ดีมอร์แกน (DeMorgan)

พิจารณา (17)

6. การสร้างลอจิกเกตต่างๆจาก แนนด์เกตและนอร์เกต

            ทุกนิพจน์ของบูลีนจะประกอบไปด้วยการผสมกันของการดำเนินการลอจิกแบบพื้นฐาน ออร์ แอนด์ และ นิเสธ ดังนั้นเราสามารถสร้างวงจรลอจิกโดยนำ ออร์เกต แอนด์เกต และอินเวอร์เตอร์เกต มาประกอบกันเป็นวงจรดิจิตอล แต่เราสามารถนำแนนด์เกตเพียงมาสร้างเป็นเกตต่างๆได้ ดังตัวอย่างในรูปที่ 6.1