Important Announcement
PubHTML5 Scheduled Server Maintenance on (GMT) Sunday, June 26th, 2:00 am - 8:00 am.
PubHTML5 site will be inoperative during the times indicated!

Home Explore เอกสารประกอบการสอนวิชาดิจิทัลอิเล็กทรอนิกส์

เอกสารประกอบการสอนวิชาดิจิทัลอิเล็กทรอนิกส์

Published by Physics Bansomdej, 2018-06-21 00:32:39

Description: ใช้สำหรับการเรียนการสอนวิชาดิจิทัลอิเล็กทรอนิกส์
สาขาวิชาเทคโนโลยีคอมพิวเตอร์อิเล็กทรอนิกส์
คณะวิทยาศาสตร์และเทคโนโลยี
มหาวิทยาลัยราชภัฏบ้านสมเด็จเจ้าพระยา

Keywords: digital,electronics,design

Search

Read the Text Version

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 ตามสดมภไมไดเปล่ียนแบบการนับเลขฐานสองตามปกติแบบ00011011 แตเปนการเปล่ียนคาของตัวแปรแบบ 00011110 เพ่ือใหคาบิตของตัวแปร 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 เสมอ


Like this book? You can publish your book online for free in a few minutes!
Create your own flipbook