71 ภาพท่ี 3.11 แผนภาพเวลาของนอรเกตภาพที่ 3.12 แผนภาพเวลาของเอกซค ลูซีพออรเ กต
72 • แผนภาพเวลาของเอกซคลซู พี นอรเกต จากคุณสมบัติของเอกซคลูซีพนอรเกต ณ ชวงเวลาหน่ึง เมื่ออินพุตที่มีคา 1 เปนจํานวนคู จะไดคาเอาตพุตออกมาเปนคา 1 แตถามีอินพุตท่ีเปนคา 1 เปนจํานวนคี่ จะไดคาเอาตพุตออกมาเปนคา 0 ซึ่งคาเอาตพุตจะเปนคาคอมพลีเมนตกับเอกซคลูซีฟออรเกต ดงั นั้นแผนภาพเวลาจึงเปนไปดังภาพท่ี 3.13 ภาพท่ี 3.13 แผนภาพเวลาของเอกซค ลูซีฟนอรเกต จากแผนภาพเวลาของลอจิกเกตท่ีกลาวไปขางตน จะเห็นไดวาคาเวลาจะดําเนินจากซายไปขวา และสัญญาณเอาตพุตนน้ั จะเปลย่ี นแปลง ณ เวลาเดยี วกันกบั ท่ีสัญญาณอนิ พตุ เปลี่ยนแปลงคา ที่เปน เชนนเ้ี พราะวา กําหนดใหลอจิกเกตในวงจรนั้นทํางานไดท ันทีโดยไมเสยี เวลาประมวลผล เชน จากภาพท่ี 3.13 ระหวางชว งเวลา 0 ถงึ 15 นาโนวินาที สัญญาณ x และสญั ญาณ y อยใู นเงือ่ นไขท่ีทําใหเอกซคลูซีฟนอรใหสัญญาณเอาตพุตออกมาเปนคา 1 แตเมื่อเวลาดําเนินพนชวงนาโนวินาทีท่ี 15 ไปจนถึงนาโนวินาทีที่ 25 สัญญาณ x และสัญญาณ y อยูในเงื่อนไขที่ทําใหเอกซคลูซีฟนอรใหสัญญาณเอาตพุตออกมาเปนคา 0 จะเห็นไดวาชวงเวลานาโนวินาทีที่ 15 น้ัน เกิดการเปลี่ยนแปลงระดับสัญญาณของเอาตพุตอยางฉับพลันตามการเปล่ียนแปลงคาของสัญญาณอินพุต ดังน้ันแผนภาพเวลาดังกลาวจึงเปนแผนภาพเวลาทางอุดมคติ เพราะในความเปนจริงแลวแตละลอจิกเกตน้ันจะมีคาเวลาการหนวงเวลา ซงึ่ แตกตางกันขนึ้ อยูก บั ชนดิ ของลอจกิ เกต
73 หากสมมุตวาในภาพที่ 3.14 นอตเกตมีเวลาหนวง 5 นาโนวินาทีออรเกตและนอรเกตมีเวลาหนวง 10 นาโนวินาที แผนภาพเวลาท่ีไดจ ะเปน ดงั ภาพท่ี 3.15 เน่ืองจากแตละลอจิกเกตมีเวลาหนวงที่ตางกัน สัญญาณเอาตพุตที่ไดจึงตองพิจารณาเวลาหนวงนี้ดวย ยกตัวอยางเชน สัญญาณ B ซ่ึงเปนเอาตพุตของนอตเกตท่ีมีเวลาหนวง 5 นาโนวินาที ดังนั้น ชวงเวลาระหวาง 0 ถึง 5 นาโนวินาทีของสัญญาณ B จะถูกแรเงา เพื่อระบุวาชวงเวลาดังกลาวคือชวงเวลาที่ลอจิกเกตกําลังประมวลผลและไมสามารถระบุไดวาสัญญาณมีคาเปน 0 หรือ 1 หรือไมมีสัญญาณก็เปนได ชวงเวลาระหวาง 0 ถึง 5นาโนวินาทีท่ีมีอินพุต z มีคาเปน 0 สัญญาณ B = ������������̅ จะมีคาเปน 1 ท่ีชวงเวลาระหวาง 5 ถึง 10นาโนวนิ าที กลา วคือสัญญาณ B ในภาพท่ี 3.15 คอื สญั ญาณ B ในภาพท่ี 3.14 ที่เกิดการหนวงเวลาไป5 นาโนวินาทีน่นั เอง และสญั ญาณที่จดุ A ในภาพที่ 3.15 คอื สัญญาณทจี่ ุด A ในภาพท่ี 3.14 ท่ีหนว งเวลาไป 10 นาโนวนิ าที เพราะนอรเกตมีเวลาหนว ง 10 นาโนวนิ าที ภาพที่ 3.14 วงจรดิจทิ ลั ลอจิกและแผนภาพเวลาการทํางานของวงจร
74 ภาพท่ี 3.15 แผนภาพเวลาทว่ี ิเคราะหถ ึงคาหนวงเวลาของวงจรดิจิทลั ลอจกิ ในภาพท่ี 3.14 สัญญาณท่ีจุด F ในภาพที่ 3.15 เกิดจากการนอรกันของสัญญาณท่ี A และ B ในภาพที่ 3.15และมีเวลาหนวงอีก 10 นาโนวินาทีจากออรเกต ทําใหสัญญาณที่จุดF มีเวลาหนวงท้ังหมด 20 นาโนวินาที (พ้ืนท่ีแรเงาตั้งแต 0 ถึง 20 นาโนวินาที) และหยุดท่ีเวลา 65 นาโนวินาที เพราะสัญญาณ B ที่นํามาประมวลผลมีถึงนาโนวินาทีที่ 55 ซึ่งชวงนาโนวินาทีท่ี 55 ถึง 60 จะไมสามารถใชสัญญาณ Aเพียงสัญญาณเดียวเพื่อประมวลผลได และจะเห็นไดวาสัญญาณท่ีจุด B ระหวางเวลา 5 ถึง 10 นาโนวนิ าทนี ัน้ จะไมถูกนํามาประมวลผลในการหาสัญญาณ F เพราะวาสัญญาณท่ีจดุ A ระหวา งเวลา 5 ถงึ10 นาโนวนิ าทนี ้ันไมอ าจระบคุ าได
75สรุป ในบทน้ีเราไดศึกษาการใชเครื่องมือเพื่อการวิเคราะหเหตุการณของระบบหรือวงจรดิจิทัลไดแก ตารางความจริงและแผนภาพเวลา ซึ่งมีความสําคัญตอการนําไปอธิบายการทํางานของวงจรดิจิทัลหรือระบบตาง ๆ ได โดยเฉพาะระบบท่ีมีความซับซอนยิ่งขึ้นในบทตอ ๆ ไป เพราะระบบหรือวงจรดิจิทัลลอจิกหลาย ๆ วงจรถึงแมจะมีโครงสรางของวงจรที่แตกตางกัน แตอาจจะใหคาเอาตพุตท่ีเหมือนกันไดในทุกเหตุการณของคาอินพุต ดังนั้นในบทตอไปเราจะศึกษาทฤษฎีบทของบูลลีนซึ่งเปนทฤษฎีทส่ี าํ คญั สาํ หรับใชในการลดรูปฟง กช ันเพ่ือใหใชจ าํ นวนลอจกิ เกตนอ ยทสี่ ดุ ในการสรา งวงจร
76แบบฝกหดั ทา ยบท3.1 จงสรา งตารางความจริงของฟงกชนั ������������ = ������������������������������������ + ������������������������� + ���������������������������� + ������������������������3.2 จงสรา งตารางความจรงิ ของฟงกชนั ������������ = ������������������������������������ + ���������������������������������������� + �������������������������3.3 จงสรางตารางความจรงิ ของฟงกชัน ������������ = ������������(������������ + ������������) + �������������������������������������3.4 จงสรา งตารางความจริงของฟงกชัน ������������ = ����������������������������(������������⨁������������) + ������������������������������������������3.5 จงสรา งตารางความจริงของฟงกชนั ������������ = ������������������������������+������������������������������������������������ ������������จากแผนภาพเวลาตอไปน้ี จงสรา งแผนภาพเวลาของฟง กชันทก่ี ําหนด3.6 ������������ = ������������������������������������ + ������������������������� + ���������������������������� + ������������������������3.7 ������������ = ������������������������������������ + ���������������������������������������� + �������������������������3.8 ������������ = ������������������������������+������������������������������������������������ ������������
77 เอกสารอา งอิงทรงยศ นาคอริยกุล. (2560). การวเิ คราะหและออกแบบวงจรดจิ ิทลั . กรุงเทพมหานคร: สาํ นกั พมิ พแ หงจุฬาลงกรณมหาวทิ ยาลัย.สมศกั ดิ์ มติ ะถา. (2543). การออกแบบวงจรดจิ ติ อลและวงจรตรรก. กรงุ เทพมหานคร: ภาควิชาวิศวกรรมคอมพวิ เตอร คณะวิศวกรรมศาสตร สถาบันเทคโนโลยพี ระจอมเกลา เจาคณุ ทหารลาดกระบัง.
78
แผนการสอนประจาํ สปั ดาหที่ 4 และ 5หัวขอเรอ่ื ง บทที่ 4 พชี คณิตบูลลนีเน้อื หา/รายละเอียด 4.1 พ้ืนฐานของพีชคณิตบูลลีน 4.2 ทฤษฎีบทบูลลีน 4.3 การเขียนฟง กชนั บูลลีนในรูปแบบมาตรฐาน 4.4 การลดรูปฟง กชนั บลู ลนี 4.5 การหาคอมพลเี มนตข องฟงกชันจาํ นวนชัว่ โมงทส่ี อน 4 ช่ัวโมงวัตถุประสงคเชิงพฤติกรรม เมือ่ ศึกษาจบบทเรยี น ผูเรยี นมคี วามรูความเขาใจในเนอ้ื หาและสามารถทาํ สิ่งตอไปน้ีได 1. สามารถอธิบายความหมายและความสาํ คัญของพชี คณิตบลู ลนี ได 2. สามารถจดจาํ อธิบาย และพิสจู นท ฤษฎบี ทบลู ลนี และทฤษฏขี องเดอมอรแ กนได 3. สามารถเขยี นฟงกช นั บูลลนี ในรปู แบบมาตรฐานได 4. สามารถเขยี นรปู วงจรลอจิกจากสมการบลู ลีนหรือฟง กชันบลู ลนี ได 5. สามารถใชพีชคณิตบูลลนี ในการลดรูปฟงกชันบลู ลนี และวงจรดจิ ิทัลได 6. สามารถแปลงวงจรดจิ ิทัลดวยวงจรรูปแบบอนื่ ซึ่งเทียบเทา กันทางพีชคณิตบลู ลีนไดวธิ สี อนและกิจกรรมการเรยี นการสอน 1. ผสู อนตง้ั คําถามเพื่อดึงดูดความสนใจของผูเรยี น และกระตุนผูเ รียนใหเ กดิ ความพรอมในการเรียนรูเ นอื้ หาทเี่ รยี น 2. ผูสอนเนนใหผูเรียนจดบันทึกหรือถายภาพเนื้อหาที่สอนจากสื่ออิเล็กทรอนิกสแลวสรุปเนอ้ื หาเปน สวนตัว ไมแนะนําใหคดั ลอกกนั เพ่อื สง เสริมจรยิ ธรรม และฝก ความรับผิดชอบในตนเอง 3. ผูสอนมอบหมายใหผูเรียนคนใดคนหน่ึงเปนตัวแทนในการรวบรวมงานท่ีมอบหมายจากเพ่อื นรวมชน้ั เรียน เพอื่ ฝก ความเปนผนู าํ และความมีจติ สาธารณะ 4. ผูสอนใหผูเรียนแบงกลุมเพื่อเตรยี มทํากิจกรรมแบบกลุม โดยตองเปนกลุมที่ไมซ ํา้ กับสัปดาหทีผ่ านมา สาํ หรบั การระดมสมองแกโจทยปญหา 5. ผูสอนบรรยายเน้ือหาเกี่ยวกับพื้นฐานของพีชคณิตบูลลีน ทฤษฎีบทบูลลีน การเขียนฟงกช ันบูลลีนในรูปแบบมาตรฐาน การลดรปู ฟงกชนั บลู ลีนและการหาคอมพลีเมนตของฟงกช ัน
80 6. ผูสอนใชการยกตัวอยา งโจทยป ญหาและการระดมสมองของผเู รยี นเพอ่ื แกโ จทยปญหา 7. ผูสอนใหโจทยปญหาที่เกี่ยวของกับบทเรียนเพ่ิมเติม เพ่ือใหผูเรียนไปคนควา และสบื เสาะหาความรเู พม่ิ เตมิ เพือ่ แกโจทยปญ หาเสรมิ จากผสู อน 8. ผูสอนสรุปเนื้อหาสาระสําคัญประจําบทเรียนและมอบหมายงานประจําสัปดาห โดยกําหนดสงงานในสัปดาหถดั ไปสอ่ื การสอน 1. แนวการสอนรายวชิ าดิจิทลั อเิ ลก็ ทรอนิกส 2. เอกสารประกอบการสอนรายวิชาดจิ ทิ ัลอิเล็กทรอนกิ ส 3. ส่อื อเิ ลก็ ทรอนิกส 4. โจทยป ญหาหรอื ตวั อยางสถานการณจ าํ ลองแผนการประเมนิ ผลการเรียนรู 1. ผลการเรยี นรู 1.1 ดา นคุณธรรม จรยิ ธรรม 1.1.1 มจี ติ สํานึก ตระหนักในการปฏิบตั ติ ามจรรยาบรรณทางวชิ าการและวิชาชีพ 1.1.2 มจี ิตสาธารณะ 1.2 ดา นความรู 1.2.1 ผเู รยี นมคี วามรูใ นหลกั การและทฤษฏี ทางดา นคอมพิวเตอรอ เิ ล็กทรอนิกส 1.2.2 มีความรูพ้ืนฐานทางวิทยาศาสตรและคณิตศาสตร และสามารถนํามาบูรณาการในดานคอมพวิ เตอรอเิ ลก็ ทรอนกิ สไ ด 1.3 ดา นทกั ษะทางปญ ญา 1.3.1 ผูเรียนมีความสามารถในการคิดวิเคราะหอยางเปนระบบ และมีเหตุมีผลตามหลกั การทางวทิ ยาศาสตร 1.3.2 ผูเรียนสามารถนําความรูทางดานคอมพิวเตอรอิเล็กทรอนิกสไปประยุกตกับสถานการณต าง ๆ ไดอ ยา งถูกตอ งเหมาะสม 1.4 ดานทักษะความสมั พนั ธระหวา งบุคคลและความรบั ผิดชอบ 1.4.1 ผเู รยี นมีความรับผดิ ชอบตอสงั คมและองคกร 1.5 ทกั ษะในการวิเคราะหเชิงตวั เลข การส่ือสารและการใชเ ทคโนโลยสี ารสนเทศ 1.5.1 ผูเรียนสามารถประยุกตความรูทางคณิตศาสตรและสถิติ เพื่อการวิเคราะหประมวลผล การแกป ญหา และนาํ เสนอขอ มลู ไดอยา งเหมาะสม
81 1.5.2 ผูเรียนสามารถใชเทคโนโลยีสารสนเทศในการสบื คน เก็บรวบรวมขอมูล และนาํ เสนอขอมลู ไดอยางมีประสิทธภิ าพและเหมาะสมกบั สถานการณ 2. วิธปี ระเมินผลการเรยี นรู 2.1 ดา นคุณธรรม จรยิ ธรรม 2.1.1 ประเมินจากการเขาชั้นเรียนท่ีตรงเวลาของผูเรียน สงงานท่ีไดรับมอบหมายตรงตอ เวลา 2.1.2 ประเมินจากความซื่อสัตยสุจริตในการทํางานที่ไดรับมอบหมาย ไมคัดลอกงานเพื่อน และไมท จุ ริตในการสอบ 2.1.3 ประเมินจากพฤติกรรมการทํากิจกรรมแบบกลุม มีการเสียสละ หรือชวยเหลืองานเพ่อื สว นรวม 2.2 ดา นความรู 2.2.1 ประเมินจากการตอบคําถามและแสดงความคดิ เห็นในชน้ั เรยี น 2.2.2 ประเมินจากการทาํ แบบฝก หัดทบทวนท่สี ง ในแตละสัปดาห 2.2.3 ประเมนิ จากการนําเสนอรายงานในช้นั เรยี น 2.2.4 ประเมนิ จากผลการสอบ 2.3 ดานทักษะทางปญ ญา 2.3.1 ประเมินจากความสามารถทางปญญาของผูเรียน ที่มีความสามารถในการวิเคราะห สังเคราะห และแสดงความรู ความคิดเห็นที่เกี่ยวของกับเน้ือที่เรียนในช้ันเรียน เชนการต้งั คําถาม การตอบคําถาม 2.3.2 ประเมินจากผลงาน และการปฏิบัติของนักศึกษา เชน การนําเสนอรายงานการทดสอบโดยใชแ บบทดสอบหรอื สัมภาษณ 2.4 ดา นทักษะความสัมพันธร ะหวา งบุคคลและความรบั ผิดชอบ 2.4.1 ประเมินจากการความรับผิดชอบตอตนเองและผูอ่ืนในการทํางานกลุมมีความใสใจชว ยเหลือเก้ือกลู เพอ่ื นรว มงานมน่ั ใจในการเปนผนู ํา และรบั ฟง ความคิดเหน็ ของผูอื่น 2.5 ทักษะในการวิเคราะหเชิงตัวเลข การสื่อสารและการใชเ ทคโนโลยสี ารสนเทศ 2.5.1 ประเมินจากความสามารถในการคํานวณ โจทยตัวอยาง แบบฝกหัดในชนั้ เรียน และแบบฝก หัดประจําสัปดาห 2.5.2 ประเมินจากเทคนิคการนําเสนอโดยใชทฤษฎี การเลือกใชเคร่ืองมือทางเทคโนโลยสี ารสนเทศ หรอื การใชท ฤษฎีทางคณติ ศาสตร
82 3. สดั สว นการประเมิน 3.1 ดานคณุ ธรรม จริยธรรม รอ ยละ 0.88 3.1.1 มีจิตสํานึก ตระหนักในการปฏิบัติตามจรรยาบรรณทางวิชาการและวิชาชีพ รอยละ 0.44 3.1.2 มีจิตสาธารณะ รอยละ 0.44 3.2 ดานความรู รอยละ 4.44 3.2.1 ผูเรียนมคี วามรูในหลกั การและทฤษฏี ทางดานคอมพิวเตอรอิเล็กทรอนกิ ส รอยละ 2.67 3.2.2 มีความรูพื้นฐานทางวิทยาศาสตรและคณิตศาสตร และสามารถนํามาบูรณาการ ในดานคอมพวิ เตอรอ ิเลก็ ทรอนิกสได รอยละ 1.77 3.3 ดา นทกั ษะทางปญ ญา รอยละ 1.77 3.3.1 ผูเรียนมีความสามารถในการคิดวิเคราะหอยางเปนระบบ และมีเหตุมีผลตามหลักการทางวิทยาศาสตร รอยละ 0.88 3.3.2 ผูเรียนสามารถนําความรูทางดานคอมพิวเตอรอิเล็กทรอนิกสไปประยุกตกับสถานการณตาง ๆ ไดอยางถูกตองเหมาะสม รอ ยละ 0.89 3.4 ดา นทกั ษะความสัมพนั ธร ะหวางบคุ คลและความรบั ผิดชอบ รอยละ 0.88 ผูเรียนมีความรับผิดชอบตอตนเองและสวนรวม มีความสัมพันธระหวางกลุมและสามารถทํางานรว มกับผอู ่ืน 3.5 ทกั ษะในการวิเคราะหเชงิ ตวั เลข การส่อื สารและการใชเ ทคโนโลยีสารสนเทศ รอ ยละ 0.88 3.5.1 ผูเรียนสามารถประยุกตความรูทางคณิตศาสตรและสถิติ เพื่อการวิเคราะหประมวลผล การแกปญหา และนาํ เสนอขอมลู ไดอยา งเหมาะสม รอยละ 0.44 3.5.2 ผูเรียนสามารถใชเทคโนโลยีสารสนเทศในการสืบคน เก็บรวบรวมขอมูลและนําเสนอขอมลู ไดอยางมีประสทิ ธภิ าพและเหมาะสมกับสถานการณ รอยละ 0.44
บทที่ 4 พชี คณิตบูลลีน (Boolean Algebra) พชี คณติ บลู ลีนเปนทฤษฎีทางคณติ ศาสตรที่ใชทําการวิเคราะหขอมูลเชงิ ตรรกะ ซึ่งเปนขอมูลที่ใชในวงจรดิจิกทัล ช่ือของทฤษฎีบูลลีนน้ันตั้งชื่อตามนักคณิตศาตรชาวอังกฤษท่ีช่ือนาย จอรจ บูล(George Boole) ซึ่งเปนผูเขียนตําราเกี่ยวกับทฤษฎีทางดานตรรกะข้ึนใน ค.ศ. 1854 โดยพีชคณิตบลู ลีนนัน้ จะแสดงขอมลู ตรรกะหรือขอ มลู ฐานสองใหอยูใ นรูปของฟง กชนั บูลลีน (Boolean function)ซงึ่ ฟงกช ันบูลลนี หนึ่งประกอบไปดว ยตัวแปรฐานสอง (binary variable) เคร่ืองหมายเทา กับ (=) และการประมวลผลทางตรรกะข้ันพื้นฐานท้ัง 3 ชนิดคือ การแอนด การออร และการนอต ลําดับขั้นความสําคัญของการประมวลผลทางตรรกะคือใหทําคําสั่งในวงเล็บกอน จากน้ันจึงทําการนอต การแอนด และการออรตามลําดับ โดยที่คาของฟงกชันบูลลีนนัน้ สามารถมีคาเปนไดแค 0 หรือ 1 เทานั้นดังนัน้ บางครั้งจงึ ถกู เรยี กวาพชี คณิตสวิตชิ่ง (switching algebra)4.1 พืน้ ฐานของพชี คณติ บูลลนี ในพิชคณิตท่ีเรารูจักกันจะแสดงคาดวยจํานวนเลขอาจอยูในรูปของเลขจํานวนเต็ม เศษสวนจํานวนลบ สแควรรูท ฯลฯ ประกอบกันเปนสมการ ตัวอยางเชน 10 + (20 ÷ 5) x 2 = 28 แตสําหรับพชิ คณติ บูลลนี จะแสดงคาดวยสัญลักษณท่ีเปนสมการเชน เดียวกัน แตค า เหลา นั้นจะมีเพียง 2คาเทาน้นั เชน จรงิ /เทจ็ สงู /ต่ํา 1/0 ใหพ ิจารณาจากตวั อยางดา นลา ง ������������ = ������������ . ������������ + ������������̅จากสมการขางตน ฟงกชันบูลลีน F ประกอบดวย 3 อินพุตคือ x, y และ z ซึ่งทุกการประมวลผลทางตรรกะดวยการแอนด การออร และการนอต ตารางความจริงของฟงกชัน F เปนดังตารางที่ 4.1 ซ่ึงแสดงเหตุการณที่เปนไปไดท้ังหมด 23 = 8 กรณีจากอินพุตท้ังหมด 3 ตัว โดยสดมภหรือแนวตั้ง(column) ท่ี 4 ของตารางแสดงคาตรรกะของ ������������̅ เพราะการนอตมีลําดับความสําคัญสูงสุดในฟงกชันสดมภท่ี 5 แสดงคาตรรกะของ x•y ซ่ึงมีลําดับความสําคัญเปนอันดับสองในสมการ และ สดมภท่ี 6แสดงคาตรรกะของฟงกชัน F ที่ไดจากการออรกันของสดมภที่ 4 และ 5 ในตารางความจริง ดังน้ันการนําตัวแปรหลายตัวมารวมกันในรูปแบบสมการนี้เราจึงเรียกวาสมการบูลลีนหรือฟงกชันบูลลีนหรอื สวทิ ชิ่งฟงกชัน (switching function) ฟงกชันบูลลีนนี้สามารถนําไปไชสรางวงจรลอจิกไดดังภาพท่ี 4.1 สําหรับวงจรลอจิก ตัวแปร x, y และ z จะถูกเขียนทางดานซายของวงจรแทนอินพุตของฟง กชัน สวนฟงกชน่ั F นัน้ เปนเอาตพุตของวงจร
84ตารางที่ 4.1 ตาราความจรงิ ของฟงกช นั ������������ = ������������ ⋅ ������������ + ������������� ������������ ������������ ������������ ������������� ������������ ⋅ ������������ ������������ = ������������ ⋅ ������������ + ������������� 00010 1 00100 0 01010 1 01100 0 10010 1 10100 0 11011 1 11101 1 ภาพที่ 4.1 วงจรลอจิกของฟงกช นั ������������ = ������������ ⋅ ������������ + �������������จากภาพท่ี 4.1 นอตเกตทําหนาท่ีหาคอมพลีเมนตของอินพุต z เพ่ือสรางเทอม z̅ และแอนดเกตมี 2อินพุต คือ x และ y เพื่อสรางเทอม x•y เอาตพุตของแอนตเกตและนอตเกตถูกเช่ือมตอโดยสายสญั ญาณเขากบั อินพุตของออรเกตเพือ่ ทาํ การออรทัง้ 2 เทอม จึงไดเ อาตพ ตุ คือฟงกช ัน F ดังกลา วการสรางวงจรลอจกิ ประเภทนีเ้ รียกวา วงจรเชิงผสม (combinational logic circuits)4.2 ทฤษฎีบทบูลลนี ฟงกชันบูลลีนหลายฟงกชันถึงแมจะมีสมการไมเหมือนกัน แตวาใหเอาตพุตเหมือนกันสําหรับแตละกรณีของคาอินพุต การเขียนฟงกชันบูลลีนท่ีแตกตางกันจะเปนตัวกําหนดการเขียนวงจรลอจิกท่ีแตกตางกันดวย ดังน้ันฟงกชันบูลลีนท่ีใหเอาตพุตเหมือนกับอีกฟงกชันแตวามีจํานวนเทอมนอยกวาน้ัน ยอมใชจํานวนลอจิกเกตที่นอยกวา จึงเปนการเขียนฟงกชันท่ีดีกวา เพราะทําใหสามารถสรา งวงจรลอจกิ ท่ีมขี นาดเลก็ และทาํ งานรวดเร็วกวา อีกฟง กช นั หน่งึ
85 การลดรูปฟงกชันบูลลีนท่ีซับซอนจึงเปนส่ิงจําเปนอยางยิ่งในการออกแบบวงจรดิจิทัล โดยหน่ึงในวิธีลดรูปฟงกชันบูลลีนน้ีทําไดดวยการใชทฤษฎีบทบูลลีน ซ่ึงประกอบไปดวย 27 ทฤษฎี และรวมกับอกี 2 ทฤษฎีบทของเดอมอรแ กน ดงั ตารางท่ี 4.2ตารางท่ี 4.2 คณุ สมบตั ิและทฤษฎบี ทของบลู ลีนและเดอมอรแกนคุณสมบตั ิ การแอนด การออร การนอต 7. 1� = 0 คณุ สมบตั ิ 1. 0 ⋅ 0 = 0 4. 0 + 0 = 0 8. 0� = 1เบ้ืองตน เกยี่ วกบั 2. 0 ⋅ 1 = 0 5. 1 + 0 = 1การกระทําบน 3. 1 ⋅ 1 = 1 6. 1 + 1 = 1 17. A� = A คา คงท่ี 13. A + 0 = A 14. A + 1 = 1คณุ สมบัติ 9. A ⋅ 0 = 0 15. A + A = A 16. A + A� = 1เบอื้ งตน เกีย่ วกบั 10. A ⋅ 1 = Aการกระทาํ บนตวั 11. A ⋅ A = A 21. A+B = B+A 12. A ⋅ A� = 0 22. (A+B)+C=A+(B+C)=A+B+C แปร 1 ตัว 23. (A⋅B)+(A⋅C) = A⋅(B+C) 18. A⋅B = B⋅A คณุ สมบัติ 26. A + AB = A เก่ียวกับการ 27. A + A�B = A + Bกระทาํ บนตัว 19. (A⋅B)⋅C = A⋅(B⋅C) = A⋅B⋅Cแปรมากกวา 1 20. (A+B) ⋅(A+C) = A+(B⋅C) 29. ���������������+����������������� = ������������̅ ∙ ������������� ตัวคุณสมบตั ิการ 24. A⋅(A+B) = A ดูดกลนื 25. A ⋅ (A� + B) = ABทฤษฎขี องเดอ 28. ���������������⋅���������������� = ������������� + ������������� มอรแกน ทฤษฎบี ทขอที่ 1 ถงึ 8 แสดงความสมั พันธตามเกตพน้ื ฐาน การแอนด การออร และการนอตของคาอินพตุ และเอาตพตุ ทฤษฎีบทขอท่ี 9 ถึง 17 แสดงความสัมพันธระหวางตัวแปร 1 ตัว การคอมพลีเมนตและคาฐานสอง 0 และ 1 โดยท่ีทฤษฎบี ทท้ัง 9 ขอสามารถพิสจู นไ ดโ ดยงา ยโดยการแทนคาเปน ไปไดท้ัง 2 คา(0 และ 1 ) ของตัวแปร x ในสมการ ยกตัวอยางเชน หากตองการพิสูจนทฤษฎีบทขอที่ 6 วาเปนจริงใหแทนคา x = 0 ในสมการจะไดวา 0 + 1 = 1 และเมื่อแทนคา x = 1 ในสมการจะไดวา 1 + 1 = 1ซึง่ เปนจรงิ ทง้ั 2 กรณจี ากตารางความจริงของการออร
86 ทฤษฎีบทขอที่ 18 ถึง 29 เปนการแสดงความสัมพันธระหวางตัวแปร 2 ตัว ข้ึนไปกับการดาํ เนินการทางตรรกะ สามารถสรุปไดด ังตอไปน้ี ทฤษฎีบทขอท่ี 18 และ 21 คือการสลับท่ี (commutative) ท่ีระบุวาการสลับที่ของตัวแปรในการออรแ ละแอนดน้ันใหผ ลลพั เหมือนเดิม ทฤษฎีบทขอท่ี 19 และ 22 คือการเปล่ียนกลุม (associative) ท่ีระบุวาผลลัพธท่ีไดจากการเปลี่ยนกลุมระหวาง 3 ตัวแปรท่ีทําการออรหรือการแอนด ไมวาจะเปลี่ยนกลุมแบบใดจะไดผลลัพธเหมือนกัน ทฤษฎีบทขอที่ 20 และ 23 คือการกระจายหรือการแจกแจง (distributive) ใชในการแจกแจงตวั แปรเขาไปในกลุมทม่ี เี ครอ่ื งหมายตรรกะตา งกัน ทฤษฎีบอขอท่ี 24 ถึง 27 คือการดูดกลืน (absorption) เปนทฤษฎีบทท่ีใชในการลดรูปตัวแปรทีไ่ มจ ําเปน ในฟงกช นั บูลลนี ทฤษฎีบทขอที่ 28 และ 29 คือทฤษฎีบทของเดอรมอรแกน (DeMorgan’s theorem) ที่คิดคนขึ้นโดยนักคณิตศาตรท่ีมีช่ือเดอมอรแกน (DeMorgan) ซึ่งมีความสําคัญอยางมากในพีชคณิตบูลลนี โดยใชในการหาคอมพลีเมนตข องฟง กช ันบลู ลนี และเปลี่ยนรปู ฟงกชนั บลู ลีนตวั อยางที่ 4.1 จงพิสูจนท ฤษฎบี ทของเดอมอรแกนทีร่ ะบุวา �x��y� = ������������̅ + �������������วธิ ีทาํ วิธีที่หน่ึงในการที่จะพิสูจนวา �x��y� = ������������̅ + ������������� คือการใชตารางความจริงเพื่อแสดงวาฟงกชันทางซายของสมการเทา กับฟงกช นั ทางขวาของสมการในทุกกรณีของคา อนิ พตุ ดงั แสดงในตารางที่ 4.3ซึ่งจะไดเห็นไดวาคาตรรกะของเทอม x���y� ในสดมภท่ี 4 ของตารางนั้นเทากับคาของเทอม ������������̅ + ������������� ในสดมภท่ี 7 ของตารางในทุกเหตกุ ารณทีเ่ ปน ไปไดท้ังหมดของอินพตุ x และ y เพราะฉะนน้ั จึงสรปุ ไดวาx���y� = ������������̅ + �������������ตารางที่ 4.3 ตารางความจรงิ ของตวั อยา งท่ี 4.1 ������������ ������������ ������������������������ ���������������������������� ������������� ������������� ������������� + ������������� 000111 1 010110 1 100101 1 111000 0
87 ทฤษฎบี ทของเดอมอรแกนนน้ั สามารถเขียนในรูปแบบท่ัวไปทมี่ ีมากกวา 2 ตวั แปรไดด งั นี้ 28. ��������������1��+�����������������2��+���⋯���+������������������������������ = ��������������1� ∙ ��������������2� ∙ … ∙ ���������������������������� 29. ��������������1���∙���������������2��∙��…���∙���������������������������� = ��������������1� + ��������������2� + ⋯ + ����������������������������โดยทฤษฎีบทเดอมอรแกนน้ันสามารถจดจําไดโดยงายคือ ในการเขยี นเทอมทางขวาของสมการ ใหท าํการเปลี่ยนเครื่องหมายตรรกะของเทอมทางซายของสมการจากการออรเปนการแอนด หรือจากการแอนดเปนการออร จากน้ันใหเปล่ียนคอมพลีเมนตของทั้งเทอมมาเปนคอมพลีเมนตของแตละตัวแปรแทน (แยกเคร่อื งหมายบารแ ลวเปล่ยี นเครอ่ื งหมายดําเนนิ การ)4.3 การเขียนฟง กชันบูลลีนในรูปแบบมาตรฐาน การเขียนฟงกชันบูลลีนหน่ึงนั้นสามารถเขียนไดหลายรูปแบบโดยใชทฤษฎีบทบูลลีน แตวิธีการเขียนฟงกชันบูลลีนในรูปแบบมาตรฐานน้ันนิยมเขียนใน 2 รูปแบบคือการเขียนฟงกชันในรูปผลบวกของผลคูณ (sum-of-products (SOP) form) และรูปผลคูณของผลบวก (product of sums(POS) form) กําหนดใหสัญพจณ (literal) คือตัวแปรอินพุตหน่ึงท่ีเขียนอยูในรูปปกติ (เชน x) หรือรูปคอมพลีเมนต (เชน x�) การเขียนฟงกชันบูลลีนใหอยูในรูปผลบวกของผลคูณคือการเขียนฟงกชันในรูปสัญพจน 1 ตัวหรือมากกวาท่ีอยูในรูปการแอนดกันกอนแลวคอยนําแตละเทอม (ผลคูณ) มาทําการออรกัน ซ่ึงการแอนดน้ันมีการประมวลผลและใชสัญลักษณทางคณิตศาสตรแบบเดียวกันกับการคูณและการออรก็ใชสัญลักษณทางคณิตศาสตรแบบเดียวกันกับการบวก การเขียนรูปแบบนี้จึงเรียกวาการเขียนในรูปผลบวกของผลคูณ ตัวอยา งฟง กช ันบลู ลีนที่อยูในรูปผลบวกของผลคณู เชน ������������ = ������������̅ + ������������������������� + �������������������������ซ่ึงฟงกชัน F ประกอบไปดวย 4 สัญพจนท่ีไมซ้ํากัน (w, ������������̅, ������������� และ z) และ 3 ผลคูณ (������������̅, ������������������������� และ �������������������������)โดยแตละผลคูณมีจํานวนสัญพจนต้ังแต 1 สัญพจนข้ึนไป ตัวอยางฟงกชันที่ไมอยูในรูปผลบวกของผลคูณเชน ������������ = ������������������������� + ������������̅ ( ������������ + ������������ )ฟงกชัน G ไมอยูในรูปผลบวกของผลคูณเพราะวาเทอมที่ 2 มีการนําอินพุต b และ c มาออรกันกอนทําการแอนดซ่ึงทําใหผิดรูปแบบ เราสามารถใชทฤษฎีบทบูลลีนขอท่ี 14 คือ การแจกแจง เพื่อเขียนฟงกช นั G ใหอยูในรปู ผลบวกของผลคณู ไดด งั นี้ ������������ = ������������������������� + ������������̅ ( ������������ + ������������ ) = ������������������������� + ������������̅������������ + ������������̅������������
88 ประโยชนของการเขยี นฟง กช นั ในรปู ผลบวกของผลคณู คือเมื่อนาํ ไปสรางวงจรลอจกิ จะมีเวลาหนว งท่ีเกิดจาก Propagation delay time นอยท่ีสุด Propagation delay time ของว งจรประกอบดวยเวลาหนวงที่แตละลอจิกเกตใชในการประมวลสัญญาณและเวลาการแพรกระจายของสัญญาณผานสายไฟเชื่อมตอแตละลอจิกเกต ในการสรางวงจรลอจิกสําหรับฟงกชัน G ขางตน เมื่อสรางจากฟงกชันบูลลีนท่ีไมไดอยูในผลบวกของผลคูณจะไดวงจรลอจิกดังภาพที่ 4.2 (ก) โดยกาํ หนดใหใ ชอินพุตท่ีอยใู นรูปปกติและรูปคอมพลีเมนตในการสราง วงจรลอจกิ ทส่ี รางใช 2 แอนดเกตและ 2 ออรเกต และเปนวงจรแบบ 3 ระดับ ขณะที่ภาพที่ 4.2 (ข) แสดงวงจรลอจิกที่สรางจากฟงกชันบูลลีนท่ีอยูในรูปผลบวกของผลคูณ ซ่ึงจะเปนการสรางวงจรแบบ 2 ระดับ และมีเวลาหนวงประมาณ 2 ลอจิกเกต จงึ ประมวลผลสญั ญาณไดเ ร็วกวา วงจรลอจิกในภาพท่ี 4.2 (ก) ภาพที่ 4.2 การสรางวงจรลอจิก (ก) แบบ 3 ระดับ และ (ข) แบบ 2 ระดับ วิธีการเขียนฟงกชันในรูปแบบมาตรฐานอีกวิธีหนึ่งคือ การเขียนในรูปผลคูณของผลบวกโดยเขียนใหสัญพจน 1 ตัวหรือมากกวาอยูในรูปการออรกันกอนแลวคอยนําแตละเทอม (ผลบวก) มาทําการแอนดกัน ตัวอยา งฟงกชนั ที่อยใู นรูปผลคูณของผลบวก เชน ������������ = ������������(������������� + ������������)(������������� + ������������ + ������������)
89ซ่ึงฟงกชัน H ประกอบไปดวย 5 สัญพจนท่ีไมซ้ํากัน (������������, �������������, ������������, ������������� และ ������������) และ 3 พจนผลบวก(������������, �������������� + ������������� และ (������������� + ������������ + ������������)) โดยท่ีเรียกวาผลคูณของผลบวกก็เพราะวาแตละเทอมนั้นอยูในรปู การออร กันของสญั พจนตั้งแต 1 สัญพจนข ึ้นไป แลว จึงนาํ มาทําการแอนดกัน การสรางวงจรลอจิกจากฟงกชันบูลลีนท่ีเขียนอยูในรูปผลคูณของผลบวกเปนการสรางวงจรแบบ 2 ระดับ ซึ่งจะประมวลผลไดร วดเรว็ เชน เดยี วกันกับรูปผลบวกของผลคณู ดงั แสดงในภาพที่ 4.3 ภาพที่ 4.3 การสรา งลอจกิ ของฟง กช ันบลู ลีน ������������ = ������������(������������� + ������������)(������������� + ������������ + ������������)4.4 การลดรปู ฟง กช ันบลู ลนี ( Simplification of Boolean Functions) เนื่องจากฟงกชันบูลลีนหนงึ่ สามารถเขียนไดหลายรปู แบบโดยใชทฤษฎีบทบูลลีน การเปล่ียนรูปฟงกชันบูลลีนใหอยูในรูปใดนั้นจึงข้ึนอยูกับวัตถุประสงคของผูออกแบบวงจรดิจิทัล โดยทั่วไปแลวผูออกแบบวงจรตองการใชจํานวนลอจิกเกตใหนอยท่ีสุดเพื่อความสะดวกในการสรางวงจรและทําใหวงจรมีขนาดเล็กและราคาตํ่า นอกจากนี้ผูออกแบบยังตองการใหวงจรท่ีออกแบบทํางานรวดเร็วที่สุดดวย ดังน้ันวัตถุประสงคของการลดรูปฟงกชันบูลลีนคือการลดจํานวนสัญพจนของฟงกชันใหเหลือนอยท่ีสุดและทําใหฟงกชันอยูในรูปผลบวกของผลคูณหรือในรูปผลคูณของผลบวก ดังแสดงในรูปตัวอยางตอไปนี้ตัวอยา งท่ี 4.2 จงทําการลดรูปฟงกชันบูลลีน ������������ = ������������ + ������������̅ ������������ ������������ + ������������̅ ������������ ������������̅ ใหเหลือจํานวนสัญพจนนอยที่สดุและอยใู นรูปผลบวกของผลคณูวิธีทํา การลดรปู ฟงกช ันบุลนี F โดยใชทฤษฎีบทบลู ลีนในตารางท่ี 2.10 ทําไดดงั น้ี F = x + ( x̅ y ) ( z + z�) จากทฤษฎบี ทขอที่ 23
90 F = x + ( x̅ y ) ( 1 ) จากทฤษฎีบทขอ ท่ี 16 F = x + x̅ y จากทฤษฎีบทขอ ท่ี 10 F=x+ y จากทฤษฎีบทขอ ที่ 27น้ันคือฟงกชัน ������������ = ������������ + ������������̅ ������������ ������������ + ������������̅ ������������ ������������̅ ท่ีมีจํานวนสัญพจนทั้งหมด 7 สัญพจนนั้นใหคาเอาตพุตเทากันกับฟงกชัน ������������ = ������������ + ������������ ท่ีมีจํานวนสัญพจนท ้ังหมด 2 สัญพจนและไมขึ้นอยูกับคาของอนิ พุตz เลย แตหากเปรียบเทียบวงจรลอจิกของฟงกชัน ������������ = ������������ + ������������̅ ������������ ������������ + ������������̅ ������������ ������������̅ (ภาพที่ 4.4 (ก)) และวงจรลอจิกของฟงกชัน ������������ = ������������ + ������������ (ภาพที่ 4.4 (ข)) เราจะเห็นไดวาวงจรลอจิกใน ภาพท่ี 4.4 (ข)นัน้ เปนวงจรทีอ่ อกแบบไดดกี วาเพราะใชออรเ กตแค 1 เกตในการสรา งเทา นนั้ ภาพที่ 4.4 วงจรลอจิกของฟงกช นั ในตวั อยา งท่ี 4.2 (ก) กอนลดรปู และ (ข) หลงั ลดรปูตัวอยา งที่ 4.3 จงทําการลดรูปฟงกชนั บูลลนี ������������ = ������������ ( ������������ + ������������̅ ) + ������������̅ ������������ ใหเหลือจํานวนสัญพจนนอยท่สี ดุและอยูในรปู ผลบวกของผลคณูวิธที ํา จากทฤษฎีบทขอท่ี 23 จากทฤษฎีบทขอ ที่ 21 F = x y + x z̅ + x̅ y จากทฤษฎีบทขอ ท่ี 23 F = x y + x̅ y + x z̅ F = (x + x̅ ) y + x z̅
91 F = (1) y + x z̅ จากทฤษฎีบทขอ ที่ 16 F = y + x z̅ จากทฤษฎีบทขอ ที่ 10 จากฟง กช นั บลู ลนี ������������ = ������������ ( ������������ + ������������̅ ) + ������������̅ ������������ ถาสรางวงจรลอจกิ โดยไมทําการลดรปู ฟงกชันกอน จะตองสรางวงจรแบบ 4 ระดับ ซ่ึงมีคาหนวงเวลามากกวาวงจรแบบ 3 ระดับ ดังนั้นการลดรูปสมการใหเหลือเพียง ������������ = ������������ + ������������ ������������̅ จึงเปนการลดตนทุนและเพิ่มประสิทธภิ าพใหระบบ ดังแสดงในภาพท่ี 4.5 ภาพท่ี 4.5 วงจรลอจิกของฟงกชนั ในตวั อยางท่ี 4.3 (ก) กอ นลดรปู และ (ข) หลงั ลดรูปตัวอยางที่ 4.4 จงทําการลดรูปฟงกชันบูลลีน ������������ = ( ������������̅ + ������������ ) ( ������������ + ������������ + ������������ ) ใหเหลือจํานวนสัญพจนนอ ยท่สี ุดและอยูในรปู ผลคณู ของผลบวกวิธีทํา F = ( y + x̅ ) ( y + ( x + z ) ) จากทฤษฎีบทขอ ท่ี 21 และ 22
92กําหนดให y เปน A, ให x� เปน B และให (x + z) เปน C แลว จะไดวาเทอม (������������ + ������������̅ )( ������������ + (������������ + ������������))นั้นอยูในรูปของ (A+B)(A+C) ซึ่งเทากับ A+BC จากทฤษฎีบทขอที่ 20 เพราะฉะนั้นจึงสรุปไดวา( ������������ + ������������̅ ) ( ������������ + ( ������������ + ������������ ) ) = ������������ + ������������̅ ( ������������ + ������������ ) F = y + x̅ ( x + z ) จากทฤษฎีบทขอ ท่ี 20 F = y + x̅ x + x̅ z จากทฤษฎีบทขอท่ี 23 F = y + x̅ z จากทฤษฎีบทขอ ที่ 12 F = ( y + x̅ ) ( y + z ) จากทฤษฎีบทขอ ท่ี 20ตวั อยางท่ี 4.5 จงทําการลดรูปฟงกชันบูลลีน ������������ = ������������������������������������ + (�������������������������)(���������������������������̅) ใหเหลือจํานวนสัญพจนนอยที่สุดและอยใู นรปู ผลคูณของผลบวกวธิ ีทํา จากทฤษฎีบทขอ ที่ 28 จากทฤษฎีบทขอที่ 17 F = xyz + (xy�)(x� + z�) จากทฤษฎีบทขอท่ี 23 F = xyz + (xy�)(x� + ������������) จากทฤษฎีบทขอท่ี 19 F = xyz + (xy�)(x�) + (xy�)(z) จากทฤษฎีบทขอ ท่ี 12 F = xyz + (xx�)(y�) + (xy�)(z) จากทฤษฎีบทขอท่ี 9 F = xyz + (0)(y�) + xy�z จากทฤษฎีบทขอท่ี 13 F = xyz + (0) + xy�z จากทฤษฎีบทขอ ที่ 23 F = xyz + xy�z จากทฤษฎีบทขอที่ 16 จากทฤษฎีบทขอ ที่ 10 F = xz(y + y�) F = xz(1) F = xzโดยฟงกชัน ������������ = ������������������������ เขียนอยูในรูปผลคูณของผลบวก (ผลบวก x และ z) และอยูในรูปผลบวกของผลคูณ (ผลคณู xz) ดวย4.5 การหาคอมพลีเมนตข องฟง กช ัน (Complement of a Function) การหาคอมพลีเมนตของฟงกชัน F นั้นทําไดโดยการเปล่ียนคาของ F จาก 0 เปน 1 และจาก1 เปน 0 ในตารางความจริง สัญลัษณของคอมพลีเมนตของฟงกชัน F คือ F� โดยเขียนเปนฟง กช ันบูลลีนไดจากการหาคอมพลเี มนตของฟง กช ันบูลลีน F ท้ัง 2 ดา นของสมการ แลวใชท ฤษฎีบทเดอมอรแกนเพ่ือลดรูปฟงกชัน F� ใหอยูในรูปผลบวกของผลคูณหรือในรูปผลคูณของผลบวกตอไปดังตวั อยา งท่ี 4.6
93ตวั อยา งท่ี 4.6 จงหาคอมพลีเมนตของฟงกช นั F = x ( y̅ z� + y z ) โดยใชจ าํ นวนสัญพจนใหนอยที่สุดและอยใู นรูปผลบวกของผลคณุวิธที าํ ใหนําฟง กช นั F ใสเครือ่ งหมายบาร เพอ่ื ทําใหเปน คอมพลีเมนต F� จะไดว า F� = x���(��y�̅ �z���+���y���z��)F� = ������������̅ + (��y��̅ �z���+���y��z���) จากทฤษฎบี ทขอ ท่ี 28F� = ������������̅ + (�y��̅ �z�) ∙ (���������������������������) จากทฤษฎีบทขอ ท่ี 29F� = ������������̅ + (������������� + ������������̿) ∙ (������������� + ������������̅) จากทฤษฎบี ทขอที่ 28F� = ������������̅ + (������������ + ������������) ∙ (������������� + ������������̅) จากทฤษฎบี ทขอที่ 17F� = ������������̅ + (������������������������� + ������������������������̅ + ������������������������� + ������������������������̅) จากทฤษฎบี ทขอท่ี 23F� = ������������̅ + (0 + ������������������������̅ + ������������������������� + 0) จากทฤษฎีบทขอที่ 12F� = ������������̅ + ������������������������̅ + ������������������������� จากทฤษฎบี ทขอ ที่ 13 จะไดค อมพลเี มนตของฟงกช ัน F หรือ F� = ������������̅ + ������������������������̅ + ������������������������� โดยเราสามารถลดรูปสมการไดอีกถา ใชลอจกิ เกตท่นี อกเหนือจากลอจิกเกต แอนด ออร และนอต นั่นคอื เอกซคลซู ฟี ออรเกต เพราะจากสมการบูลลีนของเอกซคลูซีฟออรเกตท่ีเราไดศึกษาไปในบทที่ 2 คือ ������������ ⊕ ������������ = ������������������������� + ������������̅������������ ดังน้ันในตวั อยา งนีฟ้ งกช ัน F� อาจมคี าเทากบั ������������̅ + (������������⨁������������) ไดตัวอยา งท่ี 4.7 กําหนดใหใชค าปกติของอนิ พุตไดเ ทานน้ั จงวาดวงจรลอจิกของฟงกชันบูลลีน ������������ = ������������̅ ������������ + ������������̅ ������������ โดย (ก) ใชแนนดเกตอยางเดยี วเทาน้ัน (ข) ใชนอรเ กตอยางเดียวเทา นน้ัวธิ ีทาํ (ก) ใชแนนดเ กตอยา งเดียวเทาน้นั วธิ กี ารสรา งวงจรลอจกิ โดยใชจํานวนแนนดเ กตเทา ทจ่ี าํ เปนใหท าํ ตามข้ันตอนตอไปนี้ ข้นั ท่ี 1 ทาํ การลดรูปฟงกชันบลู ลีน F ใหอ ยใู นรูปผลบวกของผลคณู และใชจํานวนสัญพจนใหนอยที่สุดโดนใชทฤษฎีบทบูลลีน จากตัวอยางน้ี ������������ = ������������������ ������������ + ������������������ ������������ อยูในรูปท่ีมีจํานวนสัญพจนนอยที่สดุ ในรูปของผลบวกของผลคูณแลว เราจึงไมต อ งทาํ การลดรปู อีก ขั้นท่ี 2 วาดฟงกชันบูลลีน F ท่ีไดจากขั้นที่ 1 โดยใชแอนดเกต ออรเกต และนอตเกตไดดังภาพที่ 4.6
94 ภาพที่ 4.6 วงจรลอจิก F ในข้ันที่ 1 ทใี่ ชนอตเกต ออรเกต และแอนดเ กตในการสราง ขน้ั ที่ 3 ใชห ลักการแปลงเกตในบทท่ี 2 ชว ยในการเปล่ยี นนอตเกต แอนดเ กต และออรเ กตในภาพที่ 4.6 ใหเ ปน แนนดเกต ซงึ่ จะไดวงจรลอจกิ ดังภาพที่ 4.7 ภาพท่ี 4.7 วงจรลอจกิ F ทีใ่ ชแนนดเกตในการสรา ง ขั้นท่ี 4 กําจัดแนนดเกตท่ีไมจําเปนในวงจรลอจิกที่ไดในขั้นที่ 3 จากรูปท่ี 4.7 แนนดเกตที่ 1ถงึ 4 น้ันทําหนา ท่แี ทนนอตเกต แตวา แนนดเกตที่ 1 และ 2 นนั้ เปนการหาคอมพลีเมนต 2 คร้งั ซึ่งจะไดผลลัพเดิม (x� = x) เพราะฉะนั้นเราสามารถกําจัดแนนดเกตท่ี1 และ 2 ได สําหรับแนนดเกตท่ี 3และ 4 กส็ ามารถกําจดั ไดด ว ยเหตุผลเดยี วกัน วงจรลอจิกสดุ ทายท่ไี ดจ งึ เปน ดงั ภาพท่ี 4.8 ภาพที่ 4.8 วงจรลอจกิ ������������ = ������������̅ ������������ + ������������̅ ������������ โดยใชแ นนดเ กตในการสราง
95 (ข) ใชน อรเกตอยา งเดียวเทานน้ั วิธกี ารวาดวงจรลอจิกโดยจาํ นวนนอรเ กตเทาทจี่ าํ เปน ใหตามข้ันตอนตอ ไปน้ี ขัน้ ท่ี 1 ทาํ การลดรปู ฟงกช ันบูลลีน F ใหอ ยใู นรปู ผลคณู ของผลบวกและใชจ ํานวนสัญพจนใหนอ ยที่สดุ โดยใชทฤษฎบี ทบูลลีน จากตวั อยา งนี้จะไดว า������������ = ������������̅ ������������ + ������������̅ ������������ = ������������̅ ( ������������ + ������������ ) จากทฤษฎบี ทขอ ที่ 23ซ่งึ อยูในรูปผลคูณของผลบวก ข้ันท่ี 2 วาดฟงกชันบูลลีน F ท่ีไดจากข้ันท่ี 1 โดยใชแอนดเกต ออรเกต และนอตเกตไดดังภาพที่ 4.9 ภาพท่ี 4.9 วงจรลอจกิ F ในข้ันที่ 1 ท่ีใชน อตเกต ออรเกต และแอนดเกตในการสราง ข้ันที่ 3 ใชห ลกั การแปลงเกตในบทที่ 2 ชวยในการเปลยี่ นนอตเกต แอนดเ กต และออรเกตในภาพท่ี 4.9 ใหเปน นอรเกต ซ่ึงจะไดว งจรลอจกิ ดังภาพที่ 4.10ภาพท่ี 4.10 วงจรลอจกิ F ทใี่ ชน อรเกตในการสรา ง
96 ข้ันท่ี 4 กําจัดนอรเกตที่ไมจําเปนในวงจรลอจิกท่ีไดในขั้นท่ี 3 จากภาพที่ 4.10 นอรเกตท่ี 1ถึง 4 นั้นทําหนาท่ีแทนนอตเกต โดยนอรเกตที่ 1 และ 2 น้ันเปนการหาคอมพลีเมนต 2 คร้ังซึ่งจะไดผลลพั ธเ ดิม เราจึงกาํ จัดนอรเ กตที่ 1 และ 2 ได สาํ หรับนอรเ กตท่ี 3 และ 4 กส็ ามารถถูกกําจัดไดดวยเหตผุ ลเดียวกัน วงจรลอจิกสุดทา ยทไ่ี ดจงึ เปนดงั ภาพที่ 4.11 ภาพท่ี 4.11 วงจรลอจิก ������������ = ������������̅ ������������ + ������������̅ ������������ โดยใชน อรเ กตในการสรา งสรุป ในบทนี้เราไดศึกษาทฤษฎีบทบูลลีนซึ่งเปนทฤษฎีท่ีสําคัญสําหรับใชในการลดรูปฟงกชันบลู ลนี เพ่อื ใหใชจํานวนลอจิกเกตนอยท่สี ุดในการสรางวงจร โดยเรม่ิ จากคุณสมบัติเกยี่ วกับการกระทําบนตัวคงที่ คุณสมบัติของการกระทําบนตัวแปร 1 ตัว คุณสมบัติเก่ียวกับการกระทําบนตัวแปรมากกวา 1 ตัวขน้ึ ไป คณุ สมบตั กิ ารดดู กลืน และทฤษฎเี ดอ มอร แกน เน่ืองจากสมการไมซับซอนและงา ยตอการเขาใจ เพราะวงจรท่ีใชจาํ นวนลอจิกเกตนอยกวา ยอมทํางานไดรวดเรว็ กวา มขี นาดเล็กกวาและมีราคาถูกกวา ท้ังนี้ทฤษฎีบทบูลลีนยังสามารถนํามาประยุกตใชในการสรา งวงจรลอจิกใด ๆ โดยใชแนนดเกตหรือนอรเกตเทาน้ัน โดยทั้งหมดนี้มีประโยชนอยางมากในการสรางวงจร เพราะวาเราตองการวงจรลอจิกท่ีมีประสิทธิภาพและประหยัดตนทุนใหมากที่สุด ในบทตอไปจะเปนการเรียนรูวิธกี ารลดรปู ฟง กชนั หรอื วงจรลอจกิ อีกวิธีหนึ่งซ่ึงไดป ระสิทธผิ ลเชนเดียวกันกบั ทฤษฎีบทบูลลนี
97แบบฝกหดั ทา ยบท4.1 จากวงจรลอจกิ ตอไปนจ้ี งสรา งบูลลนี ฟงกช ันของ A, B C และ D และหาคา เอาตพตุ X4.2 จงใชพชี คณิตบูลลนี พสิ ูจนว า ������������������������������������ + ������������������������������������� = ������������������������4.3 จงใชพีชคณติ บูลลีนพสิ ูจนวา ������������������������ + �������������(������������������������� + ������������������������) = ������������������������ + �������������������������4.4 จงใชพีชคณิตบูลลนี พิสจู นวา �������������������������������������� + �������������������������������������̅ + ������������������������������������ + �������������������������������������̅ = ������������⨁������������⨁������������4.5 จงลดทอนสมการลอจกิ โดยใชพ ชี คณติ บลู ลนี ของสมการ ������������ = (������������ + ������������)(������������������������ + �������������������������) + ������������������������ + ������������4.6 จงลดทอนสมการลอจกิ โดยใชพีชคณิตบูลลีน ของสมการ ������������ = (������������ + ������������̅ + �������������)(������������̅ + ������������� + �������������)(������������ + ������������̅)4.7 จงใชส มการตอ ไปน้เี พอ่ื สรางวงจรลอจกิ ที่ประกอบไปดวยนอรเกตเพยี งชนิดเดียว และใชจ าํ นวนเกตนอ ยที่สดุ ������������ = ������������̅������������̅ + �������������������������̅ + ������������������������̅ + ������������������������4.8 จงใชส มการตอไปน้ีเพ่ือสรา งวงจรลอจกิ ทป่ี ระกอบไปดวยแนนดเ กตเพียงชนดิ เดียว และใชจํานวนเกตนอยทส่ี ุด ������������ = ������������������������̅(������������� + ������������) + (��������������̅ �+�����������������+����������������̅)
98 เอกสารอา งองิทรงยศ นาคอริยกุล. (2560). การวเิ คราะหและออกแบบวงจรดิจิทัล. กรุงเทพมหานคร: สาํ นักพมิ พแ หง จุฬาลงกรณม หาวทิ ยาลยั .สมศกั ด์ิ มิตะถา. (2543). การออกแบบวงจรดจิ ิตอลและวงจรตรรก. กรุงเทพมหานคร: ภาควชิ าวศิ วกรรมคอมพวิ เตอร คณะวิศวกรรมศาสตร สถาบันเทคโนโลยีพระจอมเกลาเจา คุณทหารลาดกระบัง.
แผนการสอนประจําสปั ดาหท่ี 6 และ 7หวั ขอเร่อื ง บทท่ี 5 แผนภาพคารนอหเนื้อหา/รายละเอียด 5.1 มินเทอมและแมกซเทอม 5.2 การลดรปู ฟงกช ันโดยใชแ ผนภาพคารน อห 5.3 การลดรูปฟงกชันบูลลีนในรปู แบบใด ๆ โดยใชแ ผนภาพคารนอห 5.4 การลดรปู ฟง กชันใหอ ยใู นรปู ผลคูณของผลบวก 5.5 กรณที ่ไี มสนใจ 5.6 การลดรปู วงจรที่มีหลายเอาตพ ุตจํานวนช่วั โมงทีส่ อน 6 ชวั่ โมงวตั ถปุ ระสงคเ ชิงพฤติกรรม เมอ่ื ศึกษาจบบทเรียน ผเู รียนมคี วามรูค วามเขาใจในเน้ือหาและสามารถทําส่งิ ตอไปน้ีได 1. สามารถอธิบายความหมายและลกั ษณะของมนิ เทอมและแมกซเทอมได 2. สามารถสรางแผนภาพคารน อหส ําหรบั ฟง กชนั ลอจิกแบบตาง ๆ ได 3. สามารถลดรปู ฟงกชนั โดยการใชแ ผนภาพคารน อหได 4. สามารถอธิบายเหตุการณกรณีทไ่ี มสนใจได 5. สามารถลดรปู วงจรดิจิทลั ท่มี ีจํานวนเอาตพ ตุ มากกวาหนึง่ เอาตพุตได 6. สามารถใชแผนภาพคารนอหเพ่ือวเิ คราะหท างลัดหรอื บทสรุปของเหตุการณใด ๆ ไดวธิ ีสอนและกิจกรรมการเรยี นการสอน 1. ผูส อนตั้งคําถามเพือ่ ดงึ ดูดความสนใจของผูเรยี น และกระตนุ ผเู รียนใหเกดิ ความพรอมในการเรียนรเู น้ือหาทเี่ รียน 2. ผูสอนเนนใหผูเรียนจดบันทึกหรือถายภาพเน้ือหาท่ีสอนจากสื่ออิเล็กทรอนิกสแลวสรุปเนื้อหาเปน สวนตวั ไมแ นะนาํ ใหค ดั ลอกกัน เพอื่ สงเสรมิ จรยิ ธรรม และฝกความรับผิดชอบในตนเอง 3. ผูสอนมอบหมายใหผูเรียนคนใดคนหน่ึงเปนตัวแทนในการรวบรวมงานที่มอบหมายจากเพื่อนรวมชนั้ เรยี น เพือ่ ฝก ความเปนผนู ําและความมีจิตสาธารณะ 4. ผสู อนใหผ เู รียนแบงกลุมเพ่ือเตรียมทํากจิ กรรมแบบกลุม โดยตอ งเปน กลุมที่ไมซํ้ากับสัปดาหท่ีผานมา สําหรับการระดมสมองแกโจทยปญหา
100 5. ผูสอนบรรยายเนื้อหาเกี่ยวกับมินเทอมและแมกซเทอม การลดรูปฟงกชันโดยใชแผนภาพคารนอห การลดรปู ฟง กช ันบูลลีนในรปู แบบใด ๆ โดยใชแผนภาพคารนอห การลดรปู ฟงกชนัใหอยูในรูปผลคูณของผลบวก วิธีการกระทําเมื่อเจอกรณีท่ีไมสนใจ และการลดรูปวงจรท่ีมีหลายเอาตพุต 6. ผูสอนใชก ารยกตัวอยา งโจทยปญ หาและการระดมสมองของผูเรยี นเพือ่ แกโจทยป ญหา 7. ผูสอนใหโจทยปญหาท่ีเกี่ยวของกับบทเรียนเพ่ิมเติม เพื่อใหผูเรียนไปคนควา และสบื เสาะหาความรเู พม่ิ เติม เพอ่ื แกโ จทยป ญหาเสริมจากผสู อน 8. ผูสอนสรุปเนื้อหาสาระสําคัญประจําบทเรียนและมอบหมายงานประจําสัปดาห และอธิบายรายละเอยี ดเรอ่ื งการสอบกลางภาคและกําหนดสงงานในสัปดาหถัดไปสื่อการสอน 1. แนวการสอนรายวิชาดิจทิ ลั อเิ ลก็ ทรอนิกส 2. เอกสารประกอบการสอนรายวชิ าดิจิทลั อเิ ล็กทรอนกิ ส 3. สือ่ อเิ ล็กทรอนิกส 4. โจทยปญหาหรือตัวอยา งสถานการณจําลองแผนการประเมินผลการเรยี นรู 1. ผลการเรียนรู 1.1 ดานคุณธรรม จริยธรรม 1.1.1 มจี ติ สาํ นึก ตระหนักในการปฏบิ ัตติ ามจรรยาบรรณทางวชิ าการและวิชาชีพ 1.1.2 มจี ิตสาธารณะ 1.2 ดานความรู 1.2.1 ผเู รยี นมีความรูในหลกั การและทฤษฏี ทางดา นคอมพิวเตอรอิเล็กทรอนกิ ส 1.2.2 มีความรูพ้ืนฐานทางวิทยาศาสตรและคณิตศาสตร และสามารถนํามาบูรณาการในดา นคอมพวิ เตอรอเิ ลก็ ทรอนิกสได 1.3 ดานทักษะทางปญ ญา 1.3.1 ผูเรียนมีความสามารถในการคิดวิเคราะหอยางเปนระบบ และมีเหตุมีผลตามหลกั การทางวทิ ยาศาสตร 1.3.2 ผูเรียนสามารถนําความรูทางดานคอมพิวเตอรอิเล็กทรอนิกสไปประยุกตกับสถานการณต า ง ๆ ไดอยางถูกตอ งเหมาะสม
101 1.4 ดา นทกั ษะความสมั พันธร ะหวางบคุ คลและความรบั ผิดชอบ 1.4.1 ผเู รยี นมคี วามรบั ผิดชอบตอสังคมและองคกร 1.5 ทกั ษะในการวเิ คราะหเชิงตัวเลข การสื่อสารและการใชเทคโนโลยีสารสนเทศ 1.5.1 ผูเรียนสามารถประยุกตความรูทางคณิตศาสตรและสถิติ เพ่ือการวิเคราะหประมวลผล การแกปญ หา และนาํ เสนอขอ มูลไดอ ยางเหมาะสม 1.5.2 ผูเรียนสามารถใชเ ทคโนโลยีสารสนเทศในการสืบคน เก็บรวบรวมขอมูล และนําเสนอขอ มลู ไดอ ยางมีประสิทธิภาพและเหมาะสมกบั สถานการณ 2. วธิ ีประเมินผลการเรยี นรู 2.1 ดานคณุ ธรรม จรยิ ธรรม 2.1.1 ประเมินจากการเขาช้ันเรียนที่ตรงเวลาของผูเรียน สงงานท่ีไดรับมอบหมายตรงตอเวลา 2.1.2 ประเมินจากความซื่อสัตยสุจริตในการทํางานที่ไดรับมอบหมาย ไมคัดลอกงานเพื่อน และไมท ุจรติ ในการสอบ 2.1.3 ประเมินจากพฤติกรรมการทํากิจกรรมแบบกลุม มีการเสียสละ หรือชวยเหลืองานเพอ่ื สวนรวม 2.2 ดานความรู 2.2.1 ประเมนิ จากการตอบคาํ ถามและแสดงความคิดเหน็ ในช้ันเรียน 2.2.2 ประเมนิ จากการทาํ แบบฝก หดั ทบทวนที่สงในแตละสัปดาห 2.2.3 ประเมนิ จากการนาํ เสนอรายงานในชนั้ เรียน 2.2.4 ประเมนิ จากผลการสอบ 2.3 ดา นทักษะทางปญ ญา 2.3.1 ประเมินจากความสามารถทางปญญาของผูเรียน ที่มีความสามารถในการวิเคราะห สังเคราะห และแสดงความรู ความคิดเห็นที่เกี่ยวของกับเนื้อท่ีเรียนในช้ันเรียน เชนการต้ังคําถาม การตอบคาํ ถาม 2.3.2 ประเมินจากผลงาน และการปฏิบัติของนักศึกษา เชน การนําเสนอรายงานการทดสอบโดยใชแบบทดสอบหรอื สมั ภาษณ 2.4 ดานทักษะความสัมพันธระหวางบคุ คลและความรบั ผิดชอบ 2.4.1 ประเมินจากการความรับผิดชอบตอตนเองและผูอ่ืนในการทํางานกลุมมคี วามใสใ จชวยเหลือเกือ้ กูลเพือ่ นรว มงานมัน่ ใจในการเปน ผนู าํ และรบั ฟง ความคดิ เห็นของผูอืน่
102 2.5 ทกั ษะในการวเิ คราะหเ ชิงตัวเลข การสื่อสารและการใชเ ทคโนโลยสี ารสนเทศ 2.5.1 ประเมินจากความสามารถในการคํานวณ โจทยตัวอยาง แบบฝกหัดในชนั้ เรียน และแบบฝก หดั ประจาํ สัปดาห 2.5.2 ประเมินจากเทคนิคการนําเสนอโดยใชทฤษฎี การเลือกใชเคร่ืองมือทางเทคโนโลยีสารสนเทศ หรือการใชท ฤษฎีทางคณติ ศาสตร 3. สัดสวนการประเมนิ 3.1 ดานคุณธรรม จรยิ ธรรม รอยละ 1.33 3.1.1 มีจิตสํานึก ตระหนักในการปฏิบัติตามจรรยาบรรณทางวิชาการและวิชาชีพ รอยละ 0.66 3.1.2 มีจติ สาธารณะ รอยละ 0.67 3.2 ดา นความรู รอยละ 6.67 3.2.1 ผเู รียนมคี วามรใู นหลกั การและทฤษฏี ทางดา นคอมพวิ เตอรอเิ ลก็ ทรอนิกส รอ ยละ 4.00 3.2.2 มีความรูพ้ืนฐานทางวิทยาศาสตรและคณิตศาสตร และสามารถนํามาบูรณาการ ในดานคอมพิวเตอรอิเลก็ ทรอนกิ สได รอยละ 2.67 3.3 ดานทกั ษะทางปญ ญา รอยละ 2.67 3.3.1 ผูเรียนมีความสามารถในการคิดวิเคราะหอยางเปนระบบ และมีเหตุมีผลตามหลกั การทางวทิ ยาศาสตร รอ ยละ 1.33 3.3.2 ผูเรียนสามารถนําความรูทางดานคอมพิวเตอรอิเล็กทรอนิกสไปประยุกตกับสถานการณตา ง ๆ ไดอยางถกู ตองเหมาะสม รอยละ 1.34 3.4 ดานทักษะความสัมพนั ธร ะหวา งบุคคลและความรบั ผิดชอบ รอยละ 1.33 ผูเรียนมีความรับผิดชอบตอตนเองและสวนรวม มีความสัมพันธระหวางกลุมและสามารถทาํ งานรวมกับผอู ืน่ 3.5 ทักษะในการวเิ คราะหเ ชงิ ตวั เลข การสอ่ื สารและการใชเ ทคโนโลยีสารสนเทศ รอ ยละ 1.33 3.5.1 ผูเรียนสามารถประยุกตความรูทางคณิตศาสตรและสถิติ เพ่ือการวิเคราะหประมวลผล การแกปญ หา และนําเสนอขอ มลู ไดอ ยางเหมาะสม รอ ยละ 0.66 3.5.2 ผูเรียนสามารถใชเทคโนโลยีสารสนเทศในการสืบคน เก็บรวบรวมขอมูลและนาํ เสนอขอ มูลไดอยา งมีประสทิ ธิภาพและเหมาะสมกบั สถานการณ รอ ยละ 0.67
บทที่ 5 แผนภาพคารน อห (Karnaugh Maps) การใชทฤษฎีบทบูลลีนในการลดรูปฟงกชันบูลลีนใหจํานวนสัญพจนเหลือนอยที่สุด เพ่ือใหงายตอการสรางและออกแบบวงจรนั้นคอนขางยุงยากเพราะนักศึกษาตองจดจําทฤษฎีบทบูลลีนท้ังหมด และตัดสินใจวาตองนําทฤษฎีบทขอใดบางไปใชลดรูป นอกจากน้ียังเปนการยากท่ีจะตรวจสอบวาผลลัพธท่ีไดเปนคําตอบที่ดีท่ีสุดแลวหรือไม และเปนการยากในกรณีท่ีมีหลาย ๆ ตัวแปรบทนี้จะนําเสนออีกวิธีหนึ่งท่ีเปนท่ีนิยมใชในการลดรูปฟงกชัน น่ันคือการใชแผนภาพคารนอห(Karnaugh map) ซ่ึงเปนแผนภาพที่งายตอ การเชาใจและงา ยตอการตรวจสอบวา ฟง กชนั ท่ีไดน้ันเปนคําตอบที่ดีที่สุดแลวหรือไม การใชแผนภาพคารนอหในการลดรูปฟงกชันบูลลีนจึงเปนพื้นฐานสําคัญสําหรบั การออกแบบวงจรดจิ ิทลั ท่จี ะถกู นาํ ไปใชในบทตอ ๆ ไป5.1 มินเทอมและแมกซเทอม (Minterm and Maxterm) เราไดเ รียนรูว าฟงกช ันบลูลีนหรือสมการบูลลนี หรือวงจรลอจิกใด ๆ กต็ าม สามารถมีรูปแบบพื้นฐานไดเพียง 2 รูปแบบ นั้นคือรูปแบบพ้ืนฐานผลบวกของผลคูณ (canonical sum of productform) และรูปแบบพ้ืนฐานผลคูณของผลบวก (canonical product of sum form) ซ่ึงท้ังสองรูปแบบน้ีจะตองประกอบไปดวยสัญพจนที่สําคัญ 2 แบบ น้ันคือพจนในรูปแบบของการแอนดกัน(การคูณ) และพจนในรูปแบบของการออรกัน (การบวก) โดยท้ังสองพจนนี้มีชื่อเรียกเฉพาะคือมินเทอมและแมกซเทอมตามลําดับ เราสามารถใชมินเทอมและแมกซเทอมแทนเหตุการณที่สังเกตไดทงั้ หมดจากตารางความจรงิ มินเทอม คือ เทอมหรือพจนผลคูณท่ีแสดงการแอนดกันของสัญพจนของตัวแปรอินทุตท้ังหมดของฟงกชัน ยกตัวอยางเชน ฟงกชันบูลลีนหน่ึงประกอบดวย 2 อินพุตคือ x และ y ตังน้ันฟงกชันน้ีจึงมีจํานวนมินเทอมทั้งหมด 4 มินเทอมคือ x�y�, x�y, xy� และ xy ซึ่งแตละมินเทอมประกอบดวย 2 สัญพจน ถาหากฟงกชันบูลลีนมีตัวแปรฐานสอง n ตัว จํานวนมินเทอมท่ีเปนไปไดท้งั หมดคือ 2n มนิ เทอม ตารางท่ี 5.1 แสดงจํานวนมินเทอมท้ังหมดในกรณีท่ีฟง กช ันมีตวั แปรอินพุต 3ตัว คือ x, y และ z เราใชสญลักษณ mj สําหรบแตละมินเทอม โดยคา j คือคาตัวเลขฐานสิบท่ีมีฅาเทา กบั เลขฐานสองของตวั แปร xyz เชน กรณี xyz = 110 (x = 1, y = 1 และ z = 0) คือคา มนิ เทอมm6 เพราะวา 110 ในระบบจํานวนฐานสองมคี า เทา กบั 6 ในระบบจาํ นวนฐานสิบนัน่ เอง
104 แตละมินเทอมสามารถเขียนในรูปตัวแปรอินพุตไดโดยกรณีท่ีตัวแปรอินพุตมีคาเปน 0 ใหเขียนในรูปคอมพลีเมนต และตัวแปรอินพุตที่มีคาเปน 1 ใหเขียนในรูปปกติ ยกตัวอยางเชน กรณีคาอินพตุ xyz = 010 จะเปล่ยี นเปนคามินเทอมไดคอื m2 = x�yz� ตังแสดงในตารางที่ 5.1 แมกชเทอม คือ เทอมหรือพจนผลบวกท่ีแสดงการออรกันของสัญพจนของตัวแปร อินพุตท้ังหมดของฟงกชัน โดยแมกชเทอมท้ัง 8 เทอมสําหรับฟงกชันท่ีมี 3 ตัวแปร เปนตังตารางที่ 5.1สัญลักษณสําหรับแมกชเทอมคือ Mj โดยแตละแมกชเทอมเขียนในรูปตัวแปรไดโดยตัวแปรที่มีคาเปน0 ใหเขียนในรูปปกติและตัวแปรท่ีมีคาเปน 1 ใหเขียนในรูปคอมพลีเมนต เชน ถาคา xyz = 010 จะเปลยี่ นเปนคาแมกซเทอมไดคือ M2 = x + y� + zตารางที่ 5.1 มินเทอมและแมกซเ ทอมสาํ หรับฟง กช นั ทมี่ ี 3 อนิ พตุ xyz มินเทอม แมกซเทอม 000 001 m0 = x� y� z� M0 = x + y + z 010 m1 = x� y� z M1 = x + y + z� 011 m2 = x� y z� M2 = x + y� + z 100 m3 = x� y z M3 = x + y� + z� 101 m4 = x y� z� M4 = x� + y + z 110 m5 = x y� z M5 = x� + y + z� 111 m6 = x y z� M6 = x� + y� + z M7 = x� + y� + z� m7 = x y z การเขียนเอาตพุตในรูปผลบวกของมินเทอม จากตารางความจริงนั้น ทําไดโดยการออรมินเทอมทง้ั หมดในตารางความจริงท่ีทําใหค า เอาตพตุ เปน 1 ยกตวั อยางเชน ฟง กช ันบูลลีน F มีคาเปน ดังตารางท่ี 5.2 ซึ่งมีคาเปน 1 เมื่ออินพุต xyz มีคาเปน 000, 010 และ 101 หรือมินเทอม x� y� z�, x� y z�และ x y� z ตามลําดับ เพราะฉะน้ันฟงกชัน F สามารถเขียนใหอยูในรูปการออรกันของมินเทอมทีมีคาเปน 1 ไต F(x, y, z) = x� y� z� + x� y z� + x y� z = ������������0 + ������������0 + ������������0 = ∑ ������������(0,2,5) ตัวอักษรที่อยูในวงเล็บหลังฟงกชัน F แสดงลําตับของตัวแปรท่ีถูกแปลงเปนมินเทอมจากตัวอยางน้ีตัวแปร x เปนตัวแปรที่มีนัยสําคัญสูงสุด (MSB) และตัวแปร z เปนตัวแปรที่มีนัยสาํ คญัต่ําสุด (LSB) โดยตัวเลขในวงเล็บแสตงคาตัวเลขฐานสิบของแตละมินเทอมที่ถูกออรกัน และใชสัญลักษณ ∑ แทนการหาผลบวก โดยคําวาบวกในที่นี้มีความหมายคือการออรกันในทางตรรกะ เราสามารถตรวจสอบวา ฟงกชันบลู ลีน F ใหค า เปน ตงั ตารางท่ี 5.2
105 โดยการแทนคา อินพตุ ท่เี ปนไปไดท ั้ง 8 เหตุการณในสมการ F(x, y, z) ขางตน และพิสูจนวาฟงกช ัน F มคี าตังตารางความจรงิ ท่ีกําหนดให ตังนน้ั ฟงกชนั บลู ลีนใด ๆ กต็ าม สามารถเขยี นใหอยใู นรปู ผลบวกของมนิ เทอมหรอื รูปแบบมาตรฐานผลบวกของผลคูณไดดวยวธิ ีการตังทกี่ ลาวมานี้ตารางท่ี 5.2 ตารางความจริงของฟง กช ัน F(x, y, z) = ∑ ������������(0,2,5)xyz F000 1001 0010 1011 0100 0101 1110 0111 0 ในการหาคอมพลีเมนตของฟงกชัน F ก็ทําไดดวยการออรมินเทอมในตารางความจริงท่ีใหค าเอาตพุตเปน 0 ซงึ่ จะได F�(x, y, z) = x� y� z + x� y z + x y� z� + x y z� + x y z = ������������1 + ������������3 + ������������4 + ������������6 + ������������7 = ∑ ������������(1,3,4,6,7)นน่ั กค็ ือการหาคอมพลเี มนตของฟง กชนั F คอื ผลบวกของมินเทอมที่ไมรวมอยูในผลบวกของมินเทอมของฟง กชนั F น่ันเอง ฟงกชันเอาตพุตใด ๆ สามารถเขียนใหอยูในรูปของการแอนดกันของแมกซเทอมไดเชนกันโดยการเลอื กแอนดแมกซเ ทอมทั้งหมดในตารางความจริงท่ีใหคาเอาตพุตเปน 0 เชน ฟง กชันบลู ลีน Fในตารางที่ 5.2 มคี า เปน 0 เมือ่ อนิ พุต xyz มคี าเปน 001, 011, 100, 110 และ 111 หรือแมกซเทอมx + y + z�, x + y� + z�, x� + y + z, x� + y� + z และ x� + y� + z� ตามลําดับ เมื่อนําแมกซเทอมเหลานี้มาแอนดกันจะไดสมการF(x, y, z) = (x + y + z�)(x + y� + z�)(x� + y + z)(x� + y� + z)(x� + y� + z�) = ������������1 + ������������3 + ������������4 + ������������6 + ������������7 = ∏ ������������(1,3,4,6,7)
106การเขียนฟงกชันบูลลีนในรูปการแอนดกันของแมกซเทอมที่ใหคาเอาตพุตในตารางความจริงเปน 0นั้นเรียกวาการเขียนในรูปผลคูณของแมกซเทอม และใชสัญลักษณ ∏ แทนการหาผลคูณ โดยคําวาคูณในที่นี้หมายถึงการแอนดทางตรรกะ การเขียนคอมพลีเมนตของฟงกชัน F ในรูปผลคูณของแมกซเทอม ก็ทําไดดวยการแอนดกันของแมกซเทอมในตารางความจริงท่ีใหคาเอาตพุตเปน 1 ซ่ึงจะไดสมการ F�(x, y, z) = (x + y + ������������)(x + y� + z)(x� + y + z�) = ������������0 + ������������2 + ������������5 = ∏ ������������(0,2,5)หากเราหาคอมพลีเมนตข องฟงกช ัน F เราจะไดฟ งกช ัน F โดยใช'ทฤษฎขี องเดอมอรแ กนซ่ึงจะได F�(x, y, z) = �(�x��+���y��+����������������)��(�x��+���y���+���z��)�(�x���+���y��+���z���) = (��x��+���y��+�����������������) + (��x��+���y���+���z��) + �(�x���+���y��+���z���) = x� y� z� + x� y z� + x y� z = ∑ ������������(0,2,5)ผลลัพธที่ไดแสดงความสัมพันธกันระหวางผลบวกของมินเทอมและผลคูณของแมกซเทอม ชึ่งจากฟงกชัน F ในตารางท่ี 5.2 สรุปไดว า F(x, y, z) = ∑ ������������(0,2,5) = ∏ ������������(1,3,4,6,7) F�(x, y, z) = ∑ ������������(1,3,4,6,7) = ∏ ������������(0,2,5)ตวั อยางท่ี 5.1 จงเขียนฟง กชัน ������������ = ������������ + ������������������������̅ ในรูปผลบวกของมินเทอมและผลคณู ของแมกซเทอมวิธีทํา วิธีที่งายที่สุดในการแกปญหาขอน้ีคือการเขียนตารางความจริงของฟงกชันกอน ตารางความจริงของฟงกชัน ������������ = ������������ + ������������������������̅ เปนดังตารางท่ี 5.3 โดยสดมภท่ี 4 ของตารางแสดงคาตรรกะของเทอมผลคูณ ������������������������̅ ท่ีใหคาเปน1 ก็ตอเมื่ออินพุต y = 1 และ Z = 0 และสดมภท่ี 5 แสดงคาตรรกะของ������������ = ������������ + ������������������������̅ ซงึ่ หาไดจ ากการออรกันของสดมภท ี่ 1 และ 4 นน่ั เอง จากตารางความจริงท่ีได เราสามารถเขียนฟงกชันบูลีนใหอยูในรูปผลบวฦของมินเทอมและผลคูณของแมกชเทอมไดโดยงาย การเขียนฟงกชัน F ในรูปผลบวกของมินเทอมใหพิจารณากรณีของคา อินพตุ ที่ทําใหฟ งกช ัน F มคี าเปน 1 จะไดว า F(x, y, z) = x� y z� + x y� z� + x y� z + x y z� + x y z = ∑ m(2,4,5,6,7)
107และเขียนในรูปผลคูณของแมกซเทอมโดยพิจารณากรณีของคาอินพุตที่ทําใหฟงกชัน F มีคาเปน 0จะไดวา F(x, y, z) = (x + y + ������������)(x + y� + ������������)(x + y� + z�) = ∏ ������������(0,1,3)โดยตวั เลขทั้ง 3 ตวั ของผลคณู ฃองแมกซเ ทอมคือตัวเลขที่ไมไดร วมอยูในผลบวกของมินเทอมน่ันเองตารางที่ 5.3 ตารางความจริงของฟง กชัน ������������ = ������������ + ������������������������̅xyz ������������������������̅ ������������ = ������������ + ������������������������̅000 0 0 0001 0 1 0010 1 1 1011 0 1 1100 0101 0110 1111 05.2 การลดรปู ฟงกชันโดยใชแ ผนภาพคารนอห ขอดอยของการใชทฤษฏีบทบูลลีนในการลดรูปฟงกชันบูลลีนคือไมสามารถกําหนดไดวาสมควรใชท ฤษฎบี ทขอใดกอนหรือหลัง และยากตอการตรวจสอบวาผลลัพธท่ีไดมจี ํานวนสัญพจนนอยท่ีสุดแลวหรือไม การใชแผนภาพคารนอหเปนวิธีการลดรูปฟงกชันบูลลีนโดยใชแผนภาพตารางซง่ึ เขาใจไดงายกวา และตรวจสอบไดง า ยวา คาํ ตอบท่ไี ดนน้ั ดีทส่ี ุดแลว หรอื ไม แผนภาพคารนอหคือแผนภาพตารางโดยท่ีแตละชองส่ีเหลี่ยมจัตุรัสของตาราง (ชอง) แสดงคามินเทอมของฟงกชัน เพราะวาฟงกชันบูลลีนใด ๆ สามารถเขียนใหอยูในรปู ผลบวกของมินเทอมไดแผนภาพคารนฺอหจึงแสดงฟงกชันน้ันในรูปผลบวกของมินเทอม จากนั้นจึงทําการลดรูปฟงกชันจากการจดจํารูปแบบท่ีเกิดข้ึนในแผนภาพคารนอห ผลลัพธที่ไดจากการลดรูปโดยใชแผนภาพคารนอหจะอยูใ นรปู แบบมาตรฐานผลบวกของผลคูณ
108 5.2.1 แผนภาพคารนอหแบบ 1 ตวั แปร เราสามารถทราบจาํ นวนชองของแผนภาพคารนอห ชนิด 1 ตัวแปร ไดจากความสัมพันธ คือ2n โดยท่ี n เปนจํานวนตัวแปร นั่นแสดงวาแผนภาพคารนอห ชนิด 1 ตัวแปร จะมีจํานวนชองเทากบั21= 2 ชอง แสดงดังภาพที่ 5.1 ภาพท่ี 5.1 แผนภาพคารน อหชนดิ 1 ตัวแปรจากภาพที่ 5.1 แสดงใหเห็นวาถาฟงกชัน F = A เราจะไมสามารถทําการลดรูปฟงกชันใหต่ํากวาน้ีไดอีก เน่ืองจากในแผนภาพคารนอหมี “1” เพียงตัวเดียว และถูกวางอยูในชองที่ A=1 ซึ่งมีคากํากับตาํ แหนง เทา กบั “1” (A=1) ทําใหผลลัพธทเ่ี ราได คือ F = A แสดงดงั ภาพที่ 5.2ภาพที่ 5.2 แผนภาพคารน อหชนดิ 1 ตวั แปรของฟง กชัน F = Aแตถ าฟงกชัน F มตี ารางความจริงเปนไปดังตารางท่ี 5.4ตารางท่ี 5.4 ตารางความจริงของฟงกชนั F ������������ A 1 0 1 1
109จะทาํ ใหเ ราสามารถสรางแผนภาพคารนอหไดดงั ภาพท่ี 5.3 ภาพท่ี 5.3 การใชแผนผังคารนอหลดรปู ฟง กชัน 1 ตัวแปร จากภาพที่ 5.3 จะประกอบดวยมินเทอม = 1 จาํ นวน 2 เทอมดว ยกนั ซง่ึ ถูกวางอยใู นชอง A= 0 และชอง A = 1 การลดรูปฟงกชันในลักษณะน้ี ทําใหเราสามารถสรุปไดวาผลลัพธเทากับ “1”เพราะทกุ ชอ งของแผนภาพคารน อหมคี า มนิ เทอมเปน “1” ผลลัพธท่ีไดจากการลดรูปฟงกชันนั้น บางครั้งไมไดสิ้นสุดอยูที่การใชแผนภาพคารนอหเพราะ เราจะตองนาผลลัพธแตล ะวงรอบมาพิจารณา เพ่ือจัดใหอยูในรูปแบบมาตรฐานผลบวกของผลคูณ แตการลดรูปฟงกชันดังแสดงในภาพท่ี 5.3 เราจะไดผลลัพธการลดรูปโดยการใชแผนภาพคารนอหอยางแทจริง เพราะฉะน้ันการวงรอบนั้นเราจําเปนอยางยิ่งที่จะตองวงรอบในคร้ังหนึ่ง ๆ ใหสามารถครอบคลุมมนิ เทอมไดจาํ นวนมากทีส่ ดุ และอยใู นกฎการวงรอบท่ีถูกตอง 5.2.2 แผนภาพคารนอหแบบ 2 ตัวแปร แผนภาพคารนอหน้ันเปรียบเสมือนตารางความจริงไนแบบรูปภาพท่ีประกอบดวยชองส่ีเหลี่ยมจัตุรัส ช่ึงแตละชองใชแสดง 1 มินเทอม เนื่องจากฟงกชันที่มี 2 ตัวแปรน้ันมีมินเทอมไดทั้งหมด 4 มินเทอม แผนภาพคารนอหแบบ 2 ตัวแปรจึงเปนดังภาพท่ี 5.4 โดยภาพที่ 5.4 (ก) แสดงตําแหนงของแตละมินเทอมบนแผนภาพคารนอหแบบ 2 ตัวแปร และภาพท่ี 5.4 (ข) แสดงความสมั พนั ธร ะหวางมนิ เทอมและตัวแปรอนิ พุต x และ y โดยตวั เลข 0 และ 1 ท่ีกาํ กับแตละแถวและสดมภใชระบุวาตัวแปรน้ันอยูในรูปคอมพลีเมนตและรูปปกติตามลําดับ ซึ่งแผนภาพคารนอหมีการเขียนตัวแปรกํากับเฉพาะแถวหรือสดมภที่อยูในรูปปกติ เพราะฉะน้ันชองส่ีเหลี่ยมที่อยูแถวที่ 1 (ตัวแปร x เทา กบั 0) และสดมภที่ 1 (ตัวแปร y เทา กบั 0) จงึ แสดงคามินเทอม x�������������� นน่ั เอง
110 ภาพที่ 5.4 แผนภาพคารน อหแบบ 2 ตัวแปร (ก) แทนมนิ เทอม และ (ข) แทนตัวแปร วิธีการใชแผนภาพคารนอหในการลดรูปฟงกชันสามารถอธิบายไดตังนี้ สมมุติใหตารางความจริงของฟงกชันบูลลีน F ฟงกชันหน่ึงเปนดังตารางท่ี 5.5 ฟงกชันน้ีสามารถเขียนในรูปผลบวกของมนิเทอมไดคือ ������������(������������, ������������) = ������������̅������������� + ������������̅������������ + ������������������������ = ∑ ������������ (0,1,3) การแสดงฟงกชัน F บนแผนภาพคารนอหทาํ ไดโดยนาํ คามนิ เทอมของ F ทีไ่ ดใ นตารางความจริงไปเขียนลงบนแผนภาพคารน อหแบบ 2 ตัวแปรในภาพท่ี 5.4 ไดตังภาพที่ 5.5 น่ันคือมินเทอม m0, m1 และ m3 ท่ีอยูในผลบวกของมินเทอมท่ีใชแสดงฟงกชัน F มีคาเปน 1 บนแผนภาพคารนอห และมินเทอม m2 ที่ไมอยูในผลบวกของมินเทอมท่ีใชแสดงฟงกชัน F จะมีคาเปน 0 บนแผนภาพคารนอห การลดรูปฟงกชันนี้โดยใชแผนภาพคารนอหทําไดโดยการจับกลุมคา 1 ท่ีอยูติดกันบนแผนภาพ แถวที่ 1 ของแผนภาพคารนอหในภาพท่ี 5.5แสดงคามินเทอมทั้งหมดที่อินพุต x มีคาเปน 0 หรือ x� การจับคูมินเทอม m0 และ m1 ของฟงกชัน Fในแถวท่ี 1 จึงแสดงเทอมผลคูณ X โดยไมข้ึนอยูกับคา y วาจะเปน 0 หรือ 1 ดังแสดง ไตจากทฤษฏีบทบลู ลีน ������������̅������������� + ������������̅������������ = ������������̅ (������������� + ������������) = ������������̅ สวนสดมภที่ 2 ของแผนภาพใชแ สดงมินเทอมทั้งหมดท่ีอินพุตy เปน 1 หรือ y การจับคูมินเทอม m1 และ m3 ของฟงกชัน F ที่อยูติดกันในสดมภท่ี 2 จึงแสดงผลคูณ y โดยไมข้ึนอยูกับอินพุต x เพราะวา ������������̅������������ + ������������������������ = (������������̅ + ������������)������������ = ������������ การจับกลุมมินเทอมของฟงกช ัน F บนแผนภาพคารนอหจงึ ลดรูปเหลอื F = ������������̅ + y ดงั พิสจู นไดจ ากทฤษฏบี ทบูลลีนดงั น้ี ������������(������������, ������������) = ∑ ������������ (0,1,3) = ������������̅������������� + ������������̅������������ + ������������������������ = ������������̅(������������� + ������������) + ������������������������ = ������������̅(1) + ������������������������ = ������������̅ + ������������������������ = ������������̅ + ������������
111ตารางที่ 5.5 ตารางความจริงของฟง กช ัน ������������(������������, ������������) = ∑ ������������ (0,1,3)xy F00 101 110 011 1 ภาพที่ 5.5 การใชแ ผนภาพคารนอหในการลดรูปฟง กช ัน ������������(������������, ������������) = ∑ ������������ (0,1,3) การลดรูปโดยใชแ ผนภาพคารน อหจะไดผ ลลัพธในรูปผลบวกของผลคูณ การจับกลุมมินเทอมของฟงกชัน F บนแผนภาพจะลดจํานวนมินเทอมและจํานวนสัญพจนของฟงกชัน จากตวั อยางขางตนมินเทอม m1 ของฟงกชัน F ถูกจับกลุมมากกวา 1 ครั้ง โดยใชทฤษฎีบทบูลลีนที่ระบุวา A + A = Aและมินเทอมท้ังหมดของฟงกชัน F ถูกจับกลุมและลดรูปจนเหลือท้ังหมดแค 2 สัญพจนเทาน้ันในรูปผลบวกของผลคูณคือ ������������ = ������������̅ + ������������ 5.2.3 แผนภาพคารนอหแบบ 3 ตัวแปร ภาพที่ 5.6 แสดงแผนภาพคารนอหแบบ 3 ตวั แปร โดยมี 8 ชองตารางสําหรับทง้ั 8 มนิ เทอมโดยการเปลี่ยนคาของตัวแปร yz ตามสดมภไมไดเปล่ียนแบบการนับเลขฐานสองตามปกติแบบ00011011 แตเปนการเปล่ียนคาของตัวแปรแบบ 00011110 เพ่ือใหคาบิตของตัวแปร yz เปล่ียนคาแค 1 ตําแหนงเทานั้นในการเปลี่ยนจากสดมภหนึ่งไปสดมภถัดไปยกตวั อยางเชน สดมภท ่ี 2 และ 3 มีแคต ัวแปร y เทานน้ั ที่เปลย่ี นคา และสดมภท ่ี 3 และ 4 จะมแี คตวัแปร z เทานั้นท่ีเปลี่ยนคา ในการอานคามินเทอมจากแผนภาพท่ีทําไดดวยการนําตัวเลขประจําแถวและสดมภมารวมกัน เชน ชอ งสเี หลีย่ มของแผนภาพท่ตี าํ แหนง แถว x = 1 และสดมภ yz = 01 คอื คาฐานสอง xyz = 101 หรือ 510 ในระบบจํานวนฐานสิบ จึงใชแทนคามินเทอม m5 หรือ xyz̅ โดย
112แผนภาพคารนอหในภาพที่ 5.7 มีการเขียนตัวแปรกํากับ 4 ชองติดกันที่ตัวแปรมีคาเปน 1 และอีก 4ชอ งทเ่ี หลือท่ีมคี าเปน 0 จะไมมีการเขยี นตวั แปรกํากบั ไวแ ละถกู ละไวใ นฐานท่เี ขา ใจ ภาพท่ี 5.6 แผนภาพคารน อหแบบ 3 ตัวแปรการจบั กลุมสําหรับแผนภาพคารนอหแ บบ 3 ตัวแปรทําไดด ังตอไปนี้การจบั กลุมแบบ 2 มนิ เทอม ชองสี่เหล่ียม (มินเทอม) ในแผนภาพคารนอหท่ีอยูติดกันไมวาจะแนวนอนหรือแนวตั้งจะมีคาตัวแปรที่ตางกันแค 1 ตัวเทานั้น โดยที่ตางกันคือชองหน่ึงตัวแปรอยูในรูปปกติและอีกชองหน่ึงตัวแปรนั้นอยูใ นรูปคอมพลีเมนต ยกตัวอยา งเชน ฟงกชัน ������������(������������, ������������, ������������) ที่ประกอบดว ยผลบวกของมินเทอม������������1(������������̅�������������������������) และ ������������5(�������������������������������������) นั้นมีตัวแปร x ท่ีแตกตางกันคือ x� ในมินเทอม m1 และ x ในมินเทอม m5ขณะท่ีตัวแปรอ่ืนอีก 2 ตัวมีคาเทากัน (�������������������������) ผลบวกของ 2 มินเทอมน้ีจะสามารถลดรูปตัวแปร x ไดเพราะวา ������������(������������, ������������, ������������) = ������������1 + ������������5 = ������������̅������������������������� + ������������������������������������� = �������������������������(������������̅ + ������������) = �������������������������การลดรปู ฟง กช ัน F นโี้ ดยใชแผนภาพคารน อหท ําไดโ ดยการจบั กลุมมนิ เทอม ������������1และ ������������5 ทีอ่ ยตู ิดกันในแนวตั้ง (สดมภท่ี 2) ซ่ึงท้ัง 2 มินเทอมเติมเต็มสดมภที่ 2 ซ่ึงใชแทนคา yz = 01 หรือ ������������������������� นั่นเองดงั แสดงในภาพที่ 5.7 จึงลดรปู เหลือผลคณู ������������������������� โดยผลลัพธที่ไดนไี้ มขึน้ อยูกบั ตวั แปร x ภาพท่ี 5.7 การจบั กลุมมนิ เทอม ������������1และ ������������5 โดยใชแผนภาพคารนอหแ บบ 3 ตัวแปร
113การบวกกนั ของ 2 มนิ เทอมทอ่ี ยูติดกัน (ในแนวตั้งหรือแนวนอน) ในแผนภาพคารน อหแบบ 3 ตัวแปรจะสามารถลดรูปตัวแปรที่แตกตางกันได 1 ตัวแปร โดยมีกรณีพิเศษคือสดมภที่ 1 และ 4 มีตัวแปรที่ตางกัน 1 ตัวเชนเดียวกัน น่ันคึอตัวแปร y เชนผลบวกของมินเทอม ������������0 และ ������������2 มีตัวแปร yทีแ่ ตกตา งกันคอื y� ในมนิ เทอม ������������0 และ y ในมินเทอม ������������2 จึงลดรูปไดตังน้ี ������������0 + ������������2 = ������������̅�������������������������̅ + ������������̅������������������������̅ = ������������̅������������̅(������������� + ������������) = ������������̅������������̅การจับกลุมของ m0 และ m2 โดยใชแผนภาพคารน อหท ําไดด ังภาพที่ 5.8 เนืองจากคาของสดมภที่ 1และ 4 จะมีแคตัวแปร y เทานั้นท่ีตางกัน เพราะฉะนั้นเราจึงจินตนาการไดวาขอบทางซายและขอบทางขวาของแผนภาพคารนอหนั้นเสมือนอยูตดิ กัน โดยสดมภที่ 1 และ 4 ใชแสดงกรณีตัวแปร z เปน0 หรือ z� นั่นเอง และมินเทอม m0 และ m2 อยูในแถวท่ี 1 ซ่ึงคาตัวแปร x เปน 0 หรือ x� ตังนั้น การจับกลุมของ m0 และ m2 โดยใชแผนภาพคารนอห จึงทําไดโดยการแอนดกันของแถวท่ี 1 หรือ x� กับสดมภที่ 1 และ 4 หรือ z� ไดผลลัพธคือผลคูณ x�z� เชนเดียวกับการใชทฤษฎีบทบูลลีนน่ันเองภาพท่ี 5.10 แสดงตัวอยา งการจับกลุม 2 มินเทอมแบบอ่นื ๆ และผลลัพธท ่ีไดโ ดยใชแผนภาพ คารนอหเ พอื่ ใหนักศึกษาไดเขา ใจการใชแผนภาพคารนอหมากขน้ึ ภาพที่ 5.8 การจับกลุมมินเทอม m0 และ m2 โดยใชแ ผนภาพคารน อหแบบ 3 ตวั แปร ภาพที่ 5.9 ตัวอยางการจบั กลุม 2 มนิ เทอมโดยใชแ ผนภาพคารน อหแบบ 3 ตัวแปร
114การจบั กลมุ แบบ 4 มินเทอม ชองสี่เหล่ียมจัตุรัสท่ีติดกัน 4 ชอง (4 มินเทอม) บนแผนภาพคารนอหแบบ 3 ตัวแปรเมื่อรวมกันแลวจะลดรูปเหลือแค 1 สัญพจน ช่ึงสัญพจนนี้เปนสัญพจนที่เหมือนกันทั้ง 4 มินเทอมยกตัวอยางเชน ฟงกชัน ������������(������������, ������������, ������������) ท่ีเขียนในรูปผลบวกของมินเทอม m0, m1, m4 และ m5 จะมีสญั พจนท ่ีเหมอื นกันคือ ������������� จงึ ลดรูปเหลือเพียงผลคณู ������������� ไดโ ดยใชท ฤษฎีบทบลู ลนี ตังนี้ ������������(������������, ������������, ������������) = ������������0 + ������������1 + ������������4 + ������������5 = ������������̅�������������������������̅ + ������������̅������������������������� + �������������������������������������̅ + ������������������������������������� = ������������̅�������������(������������̅ + ������������) + �������������������������(������������̅ + ������������) = ������������̅������������� + ������������������������� = �������������(������������̅ + ������������) = �������������การจับกลุมของ 4 มินเทอมน้ีโดยใชแผนภาพคารนอหทําไดดังภาพท่ี 5.10 ซ่ึงสดมภท่ี 3 และ 4 ของแผนภาพคารนอหใชแทนคาตัวแปร y = 1 หรือ y ตังนั้น สดมภท่ี 1 และ 2 จึงแทนคาตัวแปร y = 0หรือ ������������� การจับกลุมของมินเทอมทั้งหมด (m0, m1, m4 และ m5) ท่ีอยูในสดมภ 1 และ 2 จึงลดรูปเหลือสญั พจน ������������� นน่ั เอง ภาพท่ี 5.10 การจบั กลมุ มินเทอม m0, m1, m4 และ m5 โดยใชแผนภาพคารน อหแ บบ 3 ตัวแปรโดยภาพท่ี 5.11 แสดงตัวอยางเพ่ิมเติมของการจับกลุม 4 มินเทอมและผลลัพธที่ได โดยใชแผนภาพคารนอหแบบ 3 ตัวแปร ซ่ึงจะเห็นวาการจับกลุม 4 มินเทอมน้ีจะใหผลลัพธเหลือเพียง 1 สัญพจนซึ่งลดรูปไดมากกวาการจับกลุม 2 มินเทอม ดังนั้นเราจึงควรจับกลุมใหไดขนาดใหญท่ีสุดในลักษณะความสัมพันธข นาดกลมุ เทากบั 2n โดย n คือเลขจํานวนเตม็ 0, 1, 2, ... , n
115 ภาพท่ี 5.11 ตวั อยา งการจับกลุม 4 มนิ เทอมโดยใชแผนภาพคารน อหแบบ 3 ตัวแปรการจับกลุมแบบ 8 มินเทอม กลุม 8 มินเทอมน้ันเปนมินเทอมท้ังหมดท่ีอยูในแผนภาพคารนอหแบบ 3 ตัวแปร ฟงกชัน������������(������������, ������������, ������������) แบบ 3 ตวั แปรทีอ่ ยใู นรูปผลบวกกันของมนิ เทอมทง้ั 8 มนิ เทอมจะใหคาเปน 1 เสมอ ไมวาตัวแปรอนิ พุต x, y และ z จะเปนคา ใดตวั อยางท่ี 5.2 จงลดรูปฟงกชัน ������������(������������, ������������, ������������) = ∑ ������������ (0,2,3,4,6) ใหเหลือจํานวนสัญพจนนอยที่สุดและอยูในรูปผลบวกของผลคูณโดยใชแผนภาพคารนอหวิธีทาํ ข้ันแรกคือการเขียนทั้ง 5 มินเทอมของฟงกชัน F ลงบนแผนภาพคารนอหแบบ 3 ตัวแปรกอน จากนั้นจึงทากรจับกลุมมินเทอมเพื่อทําการลดรูป ซึ่งเราจับกลุมมินเทอมขนาดใหญกอนเพราะวาจะใชจํานวนมินเทอมของฟงกชัน F มากที่สุด และลดรูปใหฟงกชันมีจํานวนสัญพจนนอยทส่ี ุดเพื่องายตอ การสรา งวงจร แลว จึงจบั กลุมมนิ เทอมท่เี หลอื ท้ังหมดของฟง กชัน
116ภาพท่ี 5.12 แสดงการลดรูปฟงกชัน F นี้โดยเริ่มจากการจับกลุม 4 มินเทอมท่ีอยูติดกันกอนในสดมภท่ี 1 และ 4 (มินเทอม m0, m2, m3, m4 และ m6) ซึ่งลดรูปเหลือเทอม z� จากน้ันเราจะเห็นวายังเหลือมินเทอม m3 ที่ยังไมไดถูกจับกลุม เราจึงจับกลุม 2 มีนเทอม m2 และ m3 เนื่องจากอยูติดกัน(แตละมินเทอมสามารถถูกจับกลุมไดมากกวา 1 คร้ัง) และลดรูปเหลือผลคูณ ������������̅������������ ดังน้ันฟงกชัน Fจึงสามารถลดรูปโดยใชแผนภาพคารนอหไดโดยการนําผลคูณท้ัง 2 เทอมมาออรกัน และเขียนอยูในรูปผลบวกของผลคณู ไดค ือ ������������(������������, ������������, ������������) = ∑ ������������ (0,2,3,4,6) = ������������̅ + ������������̅������������ ภาพที่ 5.12 แผนภาพคารนอหสําหรับฟง กช นั F ในตวั อยางท่ี 5.2ตวั อยางที่ 5.3 จงลดรูปฟงกชัน ������������(������������, ������������, ������������) = ∑ ������������ (0, 1, 2, 7) ใหเหลือจํานวนสัญพจนนอยท่ีสุดและอยูในรูปผลบวกของผลคณู โดยใชแ ผนภาพคารน อหวิธที าํ การจบั กลมุ มินเทอมของฟง กชนั F ในตัวอยางนี้บนแผนภาพคารน อหถูกแสดงในภาพที่ 5.13จะเห็นไดวาตวั อยางนี้ไมมีกลุม 4 มินเทอมที่อยูติดกนั เราจึงทําการจับกลมุ 2 มนิ เทอมแทน โดยกลุมแรกคือกลุมมินเทอม m0 และ m1 ที่อยูติดกันและลดรูปเหลือผลคูณ ������������̅������������� จากนั้นมินเทอม m0 จะถูกจับกลุมอีกคร้ังกับมินเทอม m2 ท่ีอยูติดกันเพ่ือทําการลดรูปเหลือผลคูณ ������������̅������������̅ หลังการจับกลุม 2 มินเทอมทอี ยูติดกนั แลว จะเห็นไดว า ยังเหลือมินเทอม m7 ท่ยี งั ไมไ ดถูกจับกลุม ซ่ึงเราไมส ามารถจับกลุมมินเทอมนี้กับมินเทอมอื่นได เพราะไมอยูติดกบั มินเทอมอน่ื บนแผนภาพ มินเทอม m7 (������������, ������������, ������������) จงึ ไมถูกลดรูปในฟง กชัน F ผลลัพธท่ไี ดจากการลดรปู ผลบวกของผลคณู คือ ������������(������������, ������������, ������������) = ∑ ������������ (0, 1, 2, 7) = ������������̅������������� + ������������̅������������̅ + ������������������������������������
117 ภาพที่ 5.13 แผนภาพคารนอหสําหรับฟงกช นั F ในตัวอยางที่ 5.3 ในกรณีท่ีปญหามีความซับซอน ขั้นตอนวิธีท่ีมีรูปแบบในการลดรูปโดยการใชแผนภาพคารนอหอยางมีประสิทธิภาพและเขียนเปนโปรแกรมคอมพิวเตอรไดจึงมีความสําคัญอยางมาก ซึ่งมีงานวิจัยที่เก่ียวของในดานน้ีเปนจํานวนมากและไดถูกตีพิมพผลงานวิจัยในวารสารวิชาการหลายเลมกอนท่เี ราจะศึกษาข้ันตอนวิธีทเ่ี ปนท่นี ิยมมากทสี่ ุด เราควรเขา ใจคําจาํ กดั ความทีเ่ กยี่ วของกอ นดงั น้ี อิมพลิแคนท (implicant) คือ เทอมผลคูณท่ีมีสวนทําใหฟงกชันที่ตองการลดรูปมีคาเปน 1โดยอิมพลิแคนทพื้นฐานก็คือมินเทอมของฟงกชันน้ัน ตัวอยางการหาอิมพลแคนททั้งหมดของฟง กช ัน������������(������������, ������������, ������������) = ∑ ������������ (2, 3, 5, 7) ทําไดโดยการเขียนฟงกชันนี้ลงบนแผนภาพคารนอหดังภาพที่ 5.14และทําการจับกลมุ 1 ที่เปนไปไดท ง้ั หมดของฟงกช ัน F ซึ่งมีท้ังหมด 7 กลมุ หรือ 7 อมิ พลิแคนทดังนี้ กลมุ 1 มนิ เทอมมีทง้ั หมด 4 อิมพลิแคนท คอื ������������̅������������������������̅, ������������̅������������������������, ������������������������������������� และ ������������������������������������ กลมุ 2 มินเทอมมที ง้ั หมด 3 อิมพลแิ คนท คอื ������������̅������������, ������������������������ และ yz ภาพที่ 5.14 แผนภาพคารนอหส าํ หรบั ฟงกชนั ������������(������������, ������������, ������������) = ∑ ������������ (2, 3, 5, 7)
118 อิมพลิแคนทเฉพาะ (prime implicant) คือ อิมพลิแคนทที่ไมสามารถรวมกับอิมพลิแคนทอื่นเพื่อลดรูปหรือลดจํานวนสัญพจนตอไปไดอีก กลาวอีกนัยหน่ึงคือ อิมพลิแคนทเฉพาะของฟงกชันคอื อิมพลแิ คนทท ไี่ มเ ปน เซตยอยของอิมพลิแคนทอืน่ จากตัวอยางฟงกชัน F ในภาพที่ 5.14 เราตองการหาวาจากอิมพลิแคนททั้งหมด 7อิมพลิแคนท มีอิมพลิแคนทใดบางเปนอิมพลิแคนทเฉพาะ จากคํานิยามขางตนเราจะเห็นวาอิมพลิแคนท ������������̅������������������������̅ ไมใชอิมพลิแคนทเฉพาะ เพราะอิมพลิแคนท ������������̅������������������������̅ สามารถรวมกลุมกับอิมพลิแคนท ������������̅������������������������ แลวลดรูปเหลืออิมพลิแคนท ������������̅������������ ดังแสดงในภาพที่ 5.15 ดวยเหตุผลดังกลาว ฟงกชัน Fในภาพที่ 5.16 มีอิมพลิแคนทเ ฉพาะแค 3 เทอมเทานนั้ คอื ������������̅������������, ������������������������ และ yz ภาพที่ 5.15 อิมพลิแคนท ������������̅������������������������̅ เปน เซตยอยของอมิ พลแิ คนท ������������̅������������ อิมพลิแคนทเฉพาะท่ีจําเปน (essential prime implicant) คือ อิมพลิแคนทเฉพาะที่มีมนิ เทอมอยางนอ ย 1 มนิ เทอมทีไ่ มเ ปนมนิ เทอมในอิมพลแิ คนทเ ฉพาะอื่น ๆ จากตัวอยางฟงกช นั F ในภาพที่ 5.14 เราตองการหาวาจากอินพลิแคนทเฉพาะท้ังหมด 3 เทอมของฟงกชันดังแสดงในภาพท่ี5.15 มีอมิ พลิแคนฑเฉพาะใดบางเปน อิมพลิแคนทเฉพาะท่จี าํ เปน ซง่ึ จะเห็นไดวา อมิ พลิแคนทเฉพาะ������������̅������������ และ ������������������������ เปนอิมพลิแคนฑเฉพาะท่ีจําเปน เพราะอิมพลิแคนทเฉพาะ ������������̅������������ มีมินเทอม m2 ที่ไมเปนมินเทอมของอิมพลิแคนทเฉพาะ ������������������������ และ yz และอิมพลิแคนทเฉพาะ ������������������������ มีมินเทอม m5 ท่ีไมเปนมนิ เทอมของอมิ พลิแคนทเ ฉพาะ ������������̅������������ และ yz สว นอิมพลแิ คนทเฉพาะ yz ไมเปน อิมพลิแคนทเฉพาะที่จําเปน เพราะวามินเทอม m3 และ m7 ที่อยูในอิมพลิแคนทเฉพาะ yz ลวนเปนมินเทอมท่ีอยูในอิมพลแิ คนทเฉพาะอืน่ ๆ (������������̅������������ และ ������������������������) โดยจากภาพที่ 5.16 จะเห็นไดวามนิ เทอม m3 และ m7 ใน อมิพลิแคนทเฉพาะ yz ถกู ใชจ ับกลมุ 2 ครง้ั
119 ภาพที่ 5.16 อิมพลแิ คนทเฉพาะท้ังหมดของฟงกชัน F ในภาพที่ 5.15 จากคําจาํ กัดความสําคัญที่ไดกลาวมาน้ี เราสามารถอธิบายขั้นตอนวิธีการลดรูปฟงกชนั ใหอยูรูปผลบวกของผลคูณและมจี าํ นวนสญั พจนนอ ยที่สุดโดยใชแผนภาพคารนอหไ ดดังน้ี 1) เขียนอมิ พลิแคนททัง้ หมดของฟง กชนั 2) หาอมิ พลแิ คนทเ ฉพาะทจ่ี าํ เปน ท้ังหมดจากอมิ พลแิ คนทเฉพาะที่ได 3) ถาอิมพลิแคนทเฉพาะท่ีจําเปนทั้งหมดครอบคลุมมินเทอมทั้งหมดของฟงกชัน การออรของอิมพลิแคนทเฉพาะท่ีจําเปนท้ังหมดจะเปนคําตอบท่ีตองการ แตถาอิมพลิแคนทเฉพาะที่จําเปนทั้งหมดไมครอบคลุมมินเทอมท้ังหมดของฟงกชัน ใหนําอิมพลิแคนทเฉพาะท่ีครอบคลุมมินเทอมท่ีไมถูกครอบคลุมดวยอิมพลิแคนทเฉพาะท่ีจําเปนไปรวมเปนคําตอบดวย เพ่ือใหผลบวกของผลคูณของเทอมท่ปี ระกอบไปดวยมนิ เทอมทง้ั หมดของฟง กชัน จากตวั อยางฟงกช ัน ������������(������������, ������������, ������������) = ∑ ������������ (2, 3, 5, 7) ในภาพที่ 5.15 เราจะเหน็ วาอิมพลิแคนทเฉพาะท่ีจําเปน ������������̅������������ และ ������������������������ ไดครอบคลุมจํานวนมินเทอมท้ังหมดของฟงกชัน F ดังแสดงในภาพท่ี5.17 เพราะฉะนั้นเราจงึ สรปุ ไดว า ������������(������������, ������������, ������������) = ∑ ������������ (2, 3, 5, 7) = ������������̅������������ + ������������������������ ภาพท่ี 5.17 การลดรปู ฟง กช นั ������������(������������, ������������, ������������) = ������������̅������������ + ������������������������ โดยใชแ ผนภาพคารน อห
120 5.2.4 แผนภาพคารนอหแบบ 4 ตัวแปร ภาพท่ี 5.18 แสดงแผนภาพคารนอหแบบ 4 ตัวแปรซ่ึงประกอบดวยมินเทอมท้ังหมด 16มินเทอม โดยในแตละชองสี่เหล่ียมของแผนภาพคารนอหใชระบุคาของมินเทอมของตัวแปรท้ัง 4ตัวแปร และใหสังเกตวาเมื่อมีการเปลี่ยนจากแถวหรือสดมภหนึ่งไปแถวหรือสดมภถัดไป จะมีการเปล่ียนคาฐานสองของตัวแปรแค 1 บิตเทาน้ัน เชน การเปลี่ยนคาของอินพุต wx จากแถวที่ 1 ไปถึงแถวท่ี 4 จะเปลีย่ นคาจาก 00 ไป 01 ไป 11 ไป 10 ตามลําดบั คาของมนิ เทอมในแตละชองนั้น ไดมาจากการรวมตัวเลขของแถวและสดมภเขาดวยกัน เชน ชองสี่เหล่ียมที่อยูแถวที่ 3 (wx = 11) และสดมภที่ 4 (yz = 10) เม่ือนําจํานวนฐานสองมารวมกันแลว เราจะไดจํานวนฐานสองคือ wxyz = 1110หรือ 1410 ในระบบจาํ นวนฐานสบิ จึงใชแ สดงคา มนิ เทอม m14 หรือ w�xyz น่นั เอง ภาพที่ 5.18 แผนภาพคารนอหแบบ 4 ตวั แปร การลดรูปโดยใชแผนภาพคารนอหแบบ 4 ตัวแปรก็ทําไดโดยใชขั้นตอนวิธเดียวกันกับการลดรูปโดยใชแผนภาพคารนอหแบบ 3 ตัวแปรโดยตองคํานึงวาแถวท่ี 1 และ 4 ของแผนภาพคารน อหน น้ั เปรียบเสมือนติดกนั และใชแสดงคา x̅ ในภาพท่ี 5.18 จงึ สามารถจบั กลุมกันได ดังนัน้ กฎการจบั กลมุ สําหรบั แผนภาพคารน อหแบบ 4 ตัวแปรสามารถสรุปไดดังนี้ • จบั กลุม 1 มนิ เทอมจะได 1 มนิ เทอมทม่ี ี 4 สัญพจน • จบั กลมุ 2 มีนเทอมจะลดรปู ไดเทอมผลคณู ที่มี 3 สัญพจน • จบั กลมุ 4 มินเทอมจะลดรูปไดเทอมผลคูณที่มี 2 สัญพจน • จับกลมุ 8 มินเทอมจะลดรปู ไดเทอมผลคณู ท่ีมี 1 สญั พจน • จบั กลมุ 16 มินเทอมจะลดรูปเหลอื ฟงกช ันท่มี ีคา เปน 1 เสมอ
Search
Read the Text Version
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287