หน่วย 2 พืชคณิตบูลีน

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

พชี คณติ บูลลนี (Boolean Algebra) • เครอ่ื งคอมพวิ เตอร ประกอบดว ยวงจรไฟฟา ทาํ งานเปนจงั หวะ และประสานงานกนั เปนระบบ วงจรไฟฟา เหลา นป้ี ระกอบดว ยชน้ิ สวนพน้ื ฐานซ่งึ รับขอมลู และสงขอมูลออกโดยที่ขอมูล เหลา นีแ้ ทนดวย 2 สถานะ คอื ปด หรอื เปด • การออกแบบวงจรท้ังหลายไดอาศัยหลกั การทางตรรกะ ซึง่ ถอื เปนพน้ื ฐานของพชี คณติ บูลลนี โดยการแทนการทาํ งานของวงจรดว ยฟงกช นั บูลลนี ฟง กช ันดงั กลา วสามารถเขยี นในรปู นพิ จน ที่ประกอบดวยตวั แปร แบบ 2 สถานะ และตวั ดําเนนิ การบลู ลนี และกรรมวิธีในการ ลดรูปนพิ จนบลู ลีน ซงึ่ จะสงผลใหว งจรทอี่ อกแบบมีความซบั ซอนนอยและทาํ งานอยา งมี ประสทิ ธภิ าพ ฟงกช นั บลู ลนี • พีชคณิตบลู ลนี ประกอบดว ยการดาํ เนนิ การ และกฏซึ่งกระทํากับคาหรอื ชุดของคา • คาแตล ะคา นน้ั กําหนดไดเ ปน 2 ลกั ษณะ เขียนแทนดว ยสญั ลกั ษณ 0 (คา เทจ็ - false) และ 1 (คา จริง - true) • การดาํ เนนิ การท่ใี ชก นั ทวั่ ไปมีอยู 3 การดาํ เนินการคือ (1) complementation (2) การบวกบลู ลนี (3) การคูณบลู ลนี 1. การดาํ เนนิ การ complementation (-) และกาํ หนดให 0= 1 1= 0 2. การดาํ เนินการบวกบลู ลนี หรือ OR แทนดวยสญั ลกั ษณ + และกําหนดให 1+1 = 1 1 +0 = 1 0+1 = 1 0+0 = 0 3. การดาํ เนินการคณู บลู ลีน หรือ AND แสดงดวยสัญลักษณ . 1.1 = 1

1.0 = 0 0.1 = 0 0.0 = 0 โดยปกติ เราสามารถละสัญลักษณ . ได • ในนิพจนบลู ลนี ซ่ึงมีตัวดาํ เนินการบูลลนี ปนกัน ถาไมม ีเครอ่ื งหมายวงเล็บกําหนดให กระทําการใดกอน ใหด ําเนนิ การเรียงตามลาํ ดบั คือ ทํา complement กอนจากนน้ั ทํา AND ทายทีส่ ุดจงึ ทํา OR • ตัวอยา งท่ี 1 หาคา 1.0 + (0 + 1) 1. 0 + (0 + 1) = 0 + 1 =0+0 =0 • ตวั ดาํ เนินการบูลลีน complement AND และ OR มคี วามหมายตรงกบั ตัวดาํ เนินการตรรกะ ~ ^ และ v ตามลําดับ • ในทางตรรกะนัน้ 0 หมายถงึ คา เท็จ และ 1 หมายถงึ คาจริง ดังนั้นพีชคณติ บลู ลีน และ ตรรกศาสตรจ ึงมคี วามสัมพันธกนั อยางใกลชดิ ตัวแปรบลู ลนี • ตวั แปรบูลลีน หมายถึงตัวแปรซงึ่ อาจมคี า 0 หรอื 1 เทานัน้ • ถากาํ หนดให B = {0,1} และ x1, x2, … xn เปนตวั แปรบูลลีนแลว ฟง กช ันบลู ลีนลําดับท่ี n หมายถงึ ฟง กช นั จากเซต Bn (เซต Bn คือ {(x1,x2,…,xn) | xi ∈ B, 1 ≤ i ≤ n}) ไปสเู ซต B เรามักอธบิ ายฟงกช นั บูลลนี ดวยตารางแสดงความสมั พนั ธข อง x1,x2,…,xnกับคา ของฟง กช ัน ตารางที่ 1 แสดงฟง กช นั บลู ลนี F(x,y) สําหรบั ตวั ดาํ เนนิ การ AND xy F(x,y) 00 0 01 0 10 0 11 1 2

• สามารถเขยี นฟงกช ันบลู ลนี ดวยนิพจนบูลลีน ซึง่ ประกอบดวยคาคงทบี่ ูลลีน ตวั แปรบลู ลนี และตวั ดําเนนิ การบลู ลีน • นิพจนบ ูลลนี ท่ีใชไ ด (valid) มดี งั นี้ 1. คาคงท่ี 0 และ 1 เปนนิพจนบ ูลลนี 2. ตัวแปร เปน นพิ จนบ ูลลนี 3. ถา E1 และ E2 เปนนพิ จนบลู ลนี แลว E1, E1.E2, E1 + E2, ( E1 ), (E1 . E2) และ (E1+E2) จะเปน นิพจนบ ลู ลีน • คา ของนิพจนบ ูลลนี หรอื ฟงกช ันบูลลีน คาํ นวณไดโ ดยการแทนคา ตวั แปรดวย 0 หรอื 1 แลว คํานวณตามกฏการดาํ เนินการ ตวั อยางท่ี 2 หาคาของฟงกช นั บลู ลนี F(x,y,z) = x + yz x y zx yz F(x,y,z) 0001 0 1 1 0011 0 1 1 0101 0 0 0 0111 1 0 1 1000 0 1010 0 1100 0 1110 1 • ฟงกช ันบลู ลีนลําดับที่ 2 เปน ฟงกช ันจากตวั แปรสองตัว ซงึ่ ผสมกนั ไดทั้งหมด 4 แบบนัน้ คา ของฟงกช ันจึงมีไดทง้ั หมด 24 หรอื 16 แบบ ตารางท่ี 3 แสดงคาทีเ่ ปนไปไดทั้งหมดของฟงกชนั บูลลีนลําดบั ท่ี 2 X y F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 000000000011111111 010000111100001111 100011001100110011 110101010101010101 3

ตัวอยา งท่ี 3 หาจาํ นวนฟงกช นั บลู ลนี ของฟง กชนั บูลลนี ลาํ ดับท่ี n ฟง กช ันบลู ลีนลําดบั ท่ี n มตี ัวแปรทั้งหมด n ตวั แตล ะตวั เปน ได 2 สถานะ ฉะนน้ั มวี ธิ ีผสมตวั แปรไดทงั้ หมด 2n วิธี ซงึ่ คือจาํ นวนคาของฟงกช นั แตละคาเปนได 2 สถานะ ดงั นั้นจาํ นวนฟง กช นั ทงั้ หมดจงึ มคี า 2(2n) • จากตัวอยา งท่ี 3 ใหส ังเกตวา จํานวนฟง กชนั ท่ีเปนไปไดส ําหรบั n ตัวแปรมขี นาดเพ่ิมเรว็ มาก เม่ือ n มีคามากขึ้น ดังนัน้ การใชฟ งกชนั บลู ลนี ควบคมุ หรอื แสดงการทํางานจึงทาํ ไดม ากมาย • ในการแสดงฟง กชนั บูลลนี ดว ยนพิ จน เราตองการแสดงนพิ จนท ี่มีรูปแบบงายทส่ี ดุ คือ จํานวน ตวั แปรนอยทส่ี ดุ และเกย่ี วของกบั ตวั ดาํ เนนิ การนอ ยทส่ี ดุ ในรปู แบบท่ซี บั ซอนนอยท่สี ุด การ ลดรูปนิพจนมเี อกลกั ษณ ซงึ่ สามารถชว ยลดรูปไดดังแสดงในตารางที่ 4 • ในการพิสูจนเ อกลักษณ เราสามารถใชวิธสี รางตาราง โดยกาํ หนดคา 0 และ 1 ใหกบั ตวั แปร แตละตวั และพิจารณาทกุ คาที่เปน ไปไดข องชดุ ตัวแปร (ทกุ combination) ตารางที่ 4 เอกลักษณบ ูลลนี x=x เอกลักษณ x+x = x x+y = y+x x .x = x x .y = y.x x+0 = x x + ( y + z ) = ( x + y) + z x .1 = x x . ( y + z ) = ( x . y) . z x+1 = 1 x + yz = ( x + y)( x + z ) x .0 = 0 x ( y + z ) = xy + xz xy = x + y x+y = x.y 4

ตัวอยางท่ี 4 ใหพสิ จู นเ อกลกั ษณ x + yz = (x + y)(x + z) xyz yz x + y x + z x + yz (x+ y)(x+ z) 000 0 000 0 001 0 010 0 010 0 011 1 100 0 100 0 101 0 110 0 111 1 111 1 111 1 111 1 111 1 111 1 สดมภสดุ ทา ยทั้งสองของตารางมีคาตรงกัน ดังน้นั เอกลกั ษณ x + yz = (x + y)(x + z)จึงเปนจรงิ ตวั อยา งที่ 5 ใชเอกลักษณใ นการพิสูจนว า p(p + r) = p p(p + r) = (p + 0)(p + r) Q x + 0 = x =p+0⋅r Q x + yz = (x + y)(x + z) =p+r⋅0 Q xy = yx =p+0 Qx⋅0=0 =p Qx+0=x Duality จากตารางท่ี 4 ใหสงั เกตวา เราจดั เอกลักษณเปน ชดุ ๆละ 2 เอกลกั ษณ เอกลักษณแ ตล ะชุดนั้นมี ลกั ษณะเปน คกู ัน (duality) คู (dual) ของนพิ จนบลู ลนี ใดคํานวณไดโดยการเปลยี่ นตัวดําเนนิ การ AND เปน OR และ เปล่ียนตวั ดาํ เนนิ การ OR เปน AND และเปล่ียนคาคงท่ี 0 เปน 1 และเปลี่ยนคาคงที่ 1 เปน 0 ตัวอยางท่ี 6 หาคขู องนพิ จน x(y + 0) และ x . 1 + (y + z) คขู อง x(y + 0) คือ x + (y . 1) 5

คขู อง x . 1 + ( y + z) คือ (x + 0) . (y . z) หลกั ของลกั ษณะคู (duality principle) กลาววา เอกลักษณใดเปนจริงแลว คขู องเอกลกั ษณนน้ั จะเปน จรงิ ดว ย หลกั การนท้ี ําใหเรา สามารถหาเอกลักษณใ หมๆไดอยางงา ยดายในเชงิ ฟง กชนั บลู ลนี ตัวอยา งที่ 7 หาเอกลักษณซ งึ่ เปนคขู องเอกลักษณ x(x + y) = x คูข องนิพจน x(x + y) คือ x + (xy) คขู อง x คือ x ดังนน้ั คเู อกลกั ษณข องx(x + y) = x คือ เอกลักษณ x + xy = x การแทนฟง กช นั บูลลีน ในหวั ขอนเ้ี ราจะศกึ ษาปญ หา 2 ปญหา o ปญหาแรกคอื ถา ทราบคาของฟงกช ันบลู ลนี แลว จะหานพิ จนบ ูลลนี ที่แทนฟง กช ันนีไ้ ด อยา งไร o ฟง กช ันบลู ลนี ใด ๆ สามารถแสดงดวยผลบวกของผลคณู บูล ลนี ของตวั แปร และสว น เติมเตม็ (complement) ของตวั แปร o ผลสรุปคอื เราสามารถแทนฟง กช ันบลู ลีนใดๆโดยการใชตวั ดําเนนิ การเพียง 3 แบบคอื . + และ - o ปญ หาทีส่ องคือสามารถแทนฟง กชนั บลู ลนี ใดๆ โดยใชต วั ดาํ เนินการนอ ยกวานีไ้ ดห รอื ไม o แทนฟง กชนั บลู ลีนโดยใชตวั ดาํ เนนิ การเดยี วได ตวั อยา งที่ 8 หานพิ จนซ่ึงแทนฟง กชัน F(x,y,z) และ G(x,y,z) ในตารางตอไปนี้ x y z F(x,y,z) G(x,y,z) 000 0 0 001 0 0 010 0 1 011 0 0 100 0 0 101 1 0 110 0 1 111 0 0 6

สาํ หรบั F นพิ จนท ีแ่ ทน F จะตองมีคา 1 เมอื่ x = z = 1 และ y = 0 และมคี า 0 ใน กรณีทีเ่ หลือ นิพจนด งั กลา วคอื ผลคณู บลู ลนี ของ x, y และ z ซง่ึ x y z จะมคี า 1 เฉพาะเมือ่ x = y = z = 1 น่นั คอื x = z = 1 และ y = 0 สาํ หรับ G นิพจนท่ีแทน G จะตอ งมีคา 1 เม่ือ x = z = 0 และ y = 1 หรอื เมือ่ x = y =1 และ z = 0 สามารถแทนคาํ อธบิ ายดงั กลา วดว ยผลบวกบลู ลนี ของผลคณู บูลลีน 2 พจน ผลคณู แตล ะพจนคือ แตละกรณี สวนผลบวกแสดงถงึ การรวมกรณีทัง้ สอง ซ่ึงในขณะใดขณะหน่งึ เกดิ ขน้ึ ไดเพยี งกรณี เดยี ว ผลคณู x y z มคี า 1 เฉพาะเม่ือ x = z = 0 และ y = 1 และ ผลคณู x y z มคี า 1 เฉพาะเมือ่ x = y = 1 และ z = 0 ดงั นัน้ เราสามารถแทน G ดว ย x y z + x y z ซ่ึงหมายความ วา G มีคา 1 เฉพาะเม่อื x = z = 0 และ y = 1 หรอื เฉพาะเมอื่ x = y = 1 และ z = 0 • ตัวอยา งขางตน นาํ ไปสูวิธกี ารสรางนิพจนท จ่ี ะแทนฟง กช นั โดยการพิจารณาคาของตวั แปรท่ี จะทําใหฟ ง กช นั ท่คี า 1 ถา x เปน ตวั แปรบูลลนี แลว เราเรียก x และ x วา เปน literal ของ x เมอื่ พิจารณาตวั แปร n ตัว ผลคณู ของ literal ของตวั แปรทั้ง n ตัวน้ี เรยี กวา พจนส ั้น (minterm) • พจนส ้ันใดๆจะมีคา 1 เฉพาะเมอื่ literral ทกุ ตัวของพจนสัน้ น้ันมคี า 1 เทา นั้น หรอื กลา วได วาเฉพาะเมื่อชดุ ตวั แปรในพจนสนั้ นั้นมีคา ท่เี หมาะสมเทา นนั้ ถา x1, x2, …, xn เปน ตัวแปรทพี่ จิ ารณา พจนสัน้ จะอยูในรปู y1 y2 … yn โดยท่ี yi เปน literal และมรี ูปแบบ xi หรอื xi คาของ y1 y2 … yn มีคา 1 กต็ อ เมอื่ yi = 1 สาํ หรับ i = 1, 2, …, n ถา yi มีรูปแบบ xi กรณนี ้กี ็คอื เม่ือ xi = 1 ถา yi มรี ูปแบบ xi กรณนี ้ีก็คือเม่อื xi = 0 ตวั อยา งที่ 9 หาพจนสัน้ ซ่ึงมีคา 1 เฉพาะเมือ่ x1 = x3 = 0 และ x2 = x4 = x5 =1 พจนสนั้ ดังกลา วคือ x1 x2 x3 x4 x5 ซึง่ มคี า 1 เฉพาะเม่อื x1= x2= x3= x4 = 1 หรือเฉพาะเมอ่ื x1 = x3 = 0 และ x2 = x4 = x5 = 1 • เม่ือนําพจนสนั้ ซงึ่ ไมเ หมือนกันมาบวกกนั เราจะไดน พิ จนบ ูลลนี ซ่ึงจะมคี า 1 เฉพาะเมอื่ พจน สัน้ 1 พจนใ นติพจนบ ูลลนี นน้ั มคี า 1 และพจนส้นั อนื่ ๆมคี า 0 น้นั คือ นพิ จนบ ูลลีนจะมีคา 1 เฉพาะเมอื่ ผสมคา ตวั แปรท่ีเหมาะสมเทาน้ัน แตละการผสมคาตวั แปรทเ่ี หมาะสมคือหนงึ่ พจนสั้น 7

การกระจายผลบวกของผลคณู (sum-of-products expansion หรอื การหา disjunctive normal form) เปน การแทนฟงกช นั บลู ลนี โดยหานพิ จนบลู ลนี ซงึ่ อยใู นรปู ผลบวกของพจนสั้น ซ่งึ แตละ พจนส น้ั แทนแตล ะกรณผี สมคา ตวั แปรทที่ ําใหฟง กชันมคี า 1 ตัวอยา งท่ี 10 หาผลบวกของผลคูณของฟงกช นั F(x,y,z) = xy + z เราแทน F(x,y,z) ดวยตาราง xyz xy z xy + z 000 0 1 1 0 001 0 0 1 0 010 0 1 1 0 011 0 0 1 1 100 0 1 101 0 0 110 1 1 111 1 0 พิจารณาสดมภสดุ ทา ย กรณที ี่ xy + z มีคา 1 จะได F(x,y,z) = x y z + x y z + x y z + x y z + x y z • ณ จดุ น้เี ราพอจะบอกไดวา เราสามารถแทนฟง กชนั บลู ลนี ใดๆไดด วย ผลบวกของผลคูณซ่ึงใช ตวั ดําเนินการเพยี ง 3 แบบคือ . + และ - เราเรียกเซต {. , + , - } วา มีคุณสมบตั สิ มบรู ณแบบ การทาํ งาน (functionally complete) • ปญหาท่ีนา คดิ คอื มีเซตสมบูรณแ บบการทาํ งานขนาดเลก็ กวานี้หรือไม คาํ ตอบก็คือมีไดถ า เรา สามารถแทนตวั ดําเนนิ การใดตวั ดําเนนิ การหนง่ึ ในเซตขางตนดว ยตวั ดําเนินการทเี่ หลือได จาก ตารางท่ี 4 ในหัวขอท่ผี า นมา เราทราบวา x+y = x y ดงั นั้น x + y = x y (Q P =P) หรอื x + y= x y (Q P = P) 8

นนั่ คือเราสามารถแทนการ + ดว ย ⋅ และ - หรือเซต { ⋅, - } มคี ุณสมบัตสิ มบรู ณแบบ การทํางาน ในทํานองเดยี วกนั เราสามารถพสิ ูจนไดว า xy = x + y ดังนัน้ { + , - } จงึ มคี ุณสมบัตสิ มบูรณแบบการทํางานเชน กัน • ปญหาทีน่ าคิดตอ ไปคือ มเี ซตสมบูรณแบบการทาํ งานท่ีมขี นาดเล็กกวาน้หี รอื ไม (คอื มตี วั ดาํ เนนการเพียงตัวเดยี ว) ตัวดําเนินการดังกลาวคือ NAND (NAND กค็ ือ NOT AND หรือ x NAND Y = x ⋅ y)หรือ | ซึ่งกาํ หนดการทํางานคอื 0 | 0 = 1, 0 | 1 = 1, 1 | 0 = 1 และ 1 | 1 = 0 • การแสดงวา { | } จงึ มคี ณุ สมบตั เิ ดยี วกนั น้ี ใหผเู รยี นลองพสิ ูจนเ อกลกั ษณตอ ไปนี้ x = x⏐x xy = (x ⏐ y) ⏐(x ⏐ y) • ตัวดําเนินการทนี่ า สนใจอีกตวั หนง่ึ คอื NOR(NOR ก็คอื NOT OR หรือ x NOR y = x + y) หรอื ↓ ซง่ึ กาํ หนดการทํางานคอื 0 ↓ 0 = 1, 0 ↓ 1 = 0,1 ↓ 0 = 0, และ 1 ↓ 1 = 0 • เซต { ↓ } มคี ณุ สมบตั สิ มบูรณแ บบการทํางานเชนกนั ประตตู รรกะ อปุ กรณค อมพวิ เตอรน ั้นทีสว นประกอบมากมาย แตละสว นประกอบดว ยวงจรอกี เปน จาํ นวนมาก วงจรแตละวงจรไดถกู ออกแบบใหทํางานโดยมีทางสาํ หรบั รับสญั ญาณเขา และ ทางสาํ หรบั สงสญั ญาณออกไปสูวงจรอืน่ เราสามารถแทนสญั ญาณเขาและออกดว ยคา จากเซต { 0, 1} ดงั น้นั เราจึงสามารถแทนหนา ที่ของวงจรไดด ว ยฟงกช นั บูลลีน โดยการแทนสัญญาณเขา ดว ยตัวแปรของฟง กชัน และสญั ญาณออกดว ยคา ของฟง กช ัน วงจรประกอบดว ยสวนยอยคือ ประตูตรรกะ ( logic gate ) หรือเรียกสั้น ๆวา ประตู ( gate ) แตล ะประตูก็คือตวั ดาํ เนินการ บลู ลีนนนั่ เอง ในหัวขอ นเ้ี ราจะศึกษาวงจรซึ่งมีคา สญั ญาณออกขนึ้ อยกู บั สญั ญาณเขาเทา นั้น วงจร ประเภทน้ีคา สญั ญาณออกจะไมข ึ้นอยกู บั สถานะเดิมของวงจร น่นั คอื ไมม ีความจําสําหรบั สถานะ เดิมวงจรประเภทนีม้ ีชื่อเรียกวา วงจรคอมบเิ นชนั นอล (combinational circuit) เนอ่ื งจากเซต { +, *, - } มีคุณสมบัตสิ มบรุ ณแ บบการทาํ งาน เราจงึ สามารถสรา งวงจร คอมบเิ นชันนอล ดว ยประตู 3 แบบ ตามแบบตวั ดําเนนิ การในเซตดงั กลา ว ประตแู บบแรกชอ่ื วา ตัวกลับคา (inverter) ซึ่งรบั สญั ญาณเขา 1 สญั ญาณ และใหสญั ญาณออก 1 สญั ญาณ ซ่ึงมีคา ตรง ขา มกับสญั ญาณเขา ตัวกลบั คานี้ก็คอื ตวั ดาํ เนนิ การ complement ประตแู บบทส่ี องช่อื วา ประตู 9

AND (AND gate) และแบบท่ีสามช่ือวาประตู OR (OR gate) ประตูท้ังสองแบบน้ีรับสญั ญาณเขา ต้งั แต 2 สญั ญาณขน้ึ ไป และใหส ัญญาณออก 1 สัญญาณ ซง่ึ มคี าเปนผลคูณ บูลลนี และผลบวกบลู ลนี ของสัญญาณเขาทง้ั หมดตามลําดบั รปู ท่ี 8.1 แสดงสัญลกั ษณแ ทนประตู ท้ัง 3 แบบ ลกู ศรทศิ ทางเขาไปยังประตแู สดงสญั ญาณเขา และลกู ศรทศิ ทางออกจากประตแู สดง สญั ญาณออก เมอ่ื เขา ใจสญั ลกั ษณด แี ลวเราสามารถละทิศทางดงั กลา วได ในวงจรคอมบิเนชันนอล สัญญาณเขาหนง่ึ สญั ญาณ อาจจะใชร ว มกันโดยประตูหลาย ประตูได ในทางกลบั กันสญั ญาณออกหนง่ึ สัญญาณ กอ็ าจแยกไปเขา ประตูหลายประตูไดรูป แสดงวงจรคอมบิเนชนั นอล สําหรับฟง กชนั บลู ลีน xy + xy ซึ่งเขียนไดเ ปนสองแบบจะเลอื กใช แบบใดกไ็ ดเพอื่ ใหเ กดิ ความชัดเจนทสี่ ดุ (แตถา วเิ คราะหในแงระดบั สัญญาณทางไฟฟาอาจตา งกนั บาง) รูปที่ .2 วงจร x y + x y ซ่ึงเขยี นได 2 แบบ 10

ตวั อยางที่ 11 วาดรปู วงจรซงึ่ คาํ นวณฟง กช ัน ก. (x + y )x ข. x (y + z) ค. (x + y + z) ( x y z) รปู ที่ 3 วงจรแทนฟง กช ันในตัวอยางที่ 11 11

ตวั อยา งท่ี 12 คณะกรมการพจิ ารณาขอ เสนอชดุ หนึง่ มี 3 คน ในการพจิ ารณาขอเสนอหน่ึงๆ ถา กรรมการอยา งนอยสองคนเห็นดว ยกบั ขอ เสนอ มตทิ ปี่ ระชุมจึงจะผา นขอ เสนอนน้ั ใหออกแบบ วงจรเพือ่ แสดงมติของทีป่ ระชมุ เราสามารถแทนการเหน็ ดว ย ดวยคา 1 และการไมเ ห็นดว ย ดว ยคา 0 กําหนดให ความเหน็ ของกรรมการทง้ั สามคือ ตวั แปร x, y และ x ตามลาํ ดบั ดงั นั้นวงจรทต่ี องการจะให สัญญาณออกเปน คา 1 เมือ่ อยา งนอยตวั แปรสองตัวมคี า เปน 1 เมื่ออยางนอ ยตวั แปรสองตัวมคี า เปน 1 ฟง กช นั บูลลีนสําหรับการทาํ งานนมี้ ีคา xy + xz + yz รูปที่ 8.4 แสดงวงจรดงั กลาว รปู ที่ 4 วงจรเสยี งสวนใหญ ตวั อยางท่ี 13 ในการควบคุมการเปดและปด ไฟบนั ไดดวงหนง่ึ เราใชสวติ ชสองสวติ ชเ มือ่ ไฟดบั อยู การสบั สวติ ชใ ดสวติ ชห น่ึง จะมีผลใหไฟสวา ง และเมอ่ื ไฟสวา งอยูกบั การสบั สวิตชใดสวติ ช หนงึ่ จะมีผลใหไฟดับ ใหอ อกแบบวงจรควบคุมการทาํ งานของดวงไฟในลักษณน้ี เราสามารถแทนการทาํ งานของสวิตชทั้งสองดวยตัวแปร x และ y ถาตัวแปรเหลา นี้มคี า 0 ใหห มายความวาปด สวติ ช (ตอ งการใหไ ฟดบั ) และถามคี า 1 ใหห มายความวา เปดสวติ ช (ตองการใหไฟสวาง) สาํ หรบั วงจรท่ตี อ งการนน้ั จะใหส ัญญาณ 0 เพื่อดับไฟ และสัญญาณ 1 เพอื่ เปดไฟ พิจารณาแทนการทํางานของวงจรนด้ี ว ยฟง กช ันบูลลนี F(x,y) เม่ือเรมิ่ ตน ใหส วิตชท ้งั สอง อยูในสถานะปดสวติ ชและไฟดบั ดังนน้ั F(1,1) = 1 จากสถานะนถี้ า เปลยี่ นสถานะของสวิตชใด สวิตชห น่งึ เปน เปด สวติ ช ไฟกจ็ ะสวาง ดังนนั้ F(0,1) = F(1,0) = 0 จากสถานะทงั้ สองนถ้ี า เปลีย่ นสถานะของสวิตชท่ีปดเปน สถานะสวิตชเปด ไฟก็จะดบั อกี ครง้ั หนึง่ ดงั นนั้ F(0,0) = 1 การทํางานนีอ้ ธิบายไดด ว ยตาราง x y F(x,y) 001 011 101 111 12

จากตารางเราไดว า F(x,y) = x y + x y รปู ท่ี 5 วงจรสองสวติ ชควบคมุ การเปด-ปดไฟ ADDER ในระบบคอมพิวเตอรทว่ั ไปจะแทนเลขจาํ นวนเต็มดว ยเลขฐานสอง ดังน้ันวงจรบวก เลขฐานสองจงึ มใี ชในหนว ยประมวลผล ลองพจิ ารณาการบวกเลขฐานสองตอ ไปนี้ 1011+ 0010 1101 เม่ือพิจารณาการบวกแตล ะตาํ แหนง จะพบวาเปน การนําเลข 3 บติ มาบวกกนั คอื ตวั ต้ัง ตัว บวกและตวั ทดจากตําแหนงทางขวา ผลลัพธจะไดเ ปน 2 บิตคือ ผลบวกและตวั ทดไปยังตําแหนง ทางซายวงจรทท่ี าํ การบวก 3 บิตน้ีชอ่ื วา ตัวบวกเต็ม (full adder) การบวกตวั ต้งั และตัวบวก (ตวั ละ 1 บิต) แลวไดผลลัพธ 2 บิต คอื ผลบวก และตวั ทด ถา ให x เปน บิตตวั ตง้ั y เปน บติ ตวั บวก s เปนบิตผลบวก และ c เปนบติ ตัวทด เราจะได ตารางความสมั พันธของขอ มลู เขา และออกจากวงจรดังน้ี xysc 0000 0110 1010 1101 ฟงกชันบลู ลีนท่ีไดจากตารางนีค้ อื s = x y + x y = (x + y)(xy) (ลองพสิ ูจน !) 13

c = xy ดังน้ันวงจรตวั บวกครึง่ จงึ มีรปู แบบ สาํ หรบั วงจรตวั บวกเตม็ กาํ หนดให x เปน บิตตัวต้งั y เปน บิตตวั บวก ci เปน บิตตวั ทด เขา s เปน บติ ผลบวก และ ci+1 เปนตัวทดออก เราสามารถเขยี นตารางแสดความสมั พนั ธข อง ขอ มูลเขาและออกของวงจรดงั น้ี x y ci s ci+1 00000 00110 01010 01101 10010 10101 11001 11111 ฟง กชนั บลู ลีนท่ไี ดจากตารางคือ s = x y ci + x y ci + x y ci + x y ci ci+1 = x y ci + x y ci + x y ci + x y ci จากฟง กชนั บลู ลนี ขา งตน เราสามารถเขยี นรปู วงจรได ในท่ีนี้ขอพจิ ารณาการสรางตัวบวก เตม็ จากตวั บวกคร่งึ ถา เราใชต ัวบวกครง่ึ เพ่ือบวก 3 บติ เราจะไดโ ครงสรางวงจรงา ยๆ คอื 14

ขา งตนจะเห็นวา มตี วั ทดออกเปน 2 บิต ถา พิจารณาใหด ีจะพบวา คาตวั ทดทงั้ 2 บิตนตี้ อ งอยใู นรปู 01 หรอื 00 เทานน้ั เพราะการบวกบิต 3 บิตเขาดว ยกนั จะมีตัวทดไดอ ยา งมากทส่ี ุดเพยี ง 1 ตัว ทด ( กรณีบวกบิต 3 บิตแลวไดผลลพั ธม ากท่ีสดุ คอื 1 + 1 + 1 = 11 ) ดังนนั้ วงจรที่ ใชไ ดคือ ผูอา นสามารถตรวจความถกู ตอ งของวงจรขา งตน โดยการเขียนฟงกชนั บูลลนี แลวพยายามลดรปู หรือเปรยี บเทียบกับฟง กชนั บลู ลีนทไ่ี ดจากตาราง การลดรูปวงจรตรรกะ ประสิทธิภาพของวงจรคอมมิเนชันนอล ข้ึนอยกู ับจาํ นวนประตูตรรกะและการจดั รปู วงจร วงจรที่มจี าํ นวนประตูนอยจะใชพ ลังงานนอ ย และมกั จะใชเ น้อื ทน่ี อ ยตามไปดว ยวงจรทป่ี ระตู ตรรกะตอเรยี งกนั เปนสายจะทาํ งานชา กวาวงจรที่ตอประตตู รรกะเรียงกนั เปนสายสันกวา ในหวั ขอ นี้เราจะศกึ ษาวธิ ีลดรปู นิพจนบ ูลลนี ใหมรี ปู แบบงายท่ีสดุ เพอื่ ทจี่ ะใชสรา งวงจรตรรกะทม่ี ี ประสทิ ธภิ าพ ในการหาฟงกช ันบลู ลีนนัน้ เราสามารถเริ่มไดจ ากตารางความสัมพนั ธของสญั ญาณเขา และสัญญาณออก ตารางนแี้ สดงคา สัญญาณออกสําหรบั แตล ะคาประสมกันของสัญญาณเขา (combination ของสัญญาณเขา วงจรทไ่ี ดจ ึงเรยี กวา combinational circuit) ตารางดงั กลา วมชี ื่อ เรียกวา ตารางจรงิ เท็จ (truth table) จากตารางจริงเทจ็ เราสามารถเขยี นนิพจนผ ลบวกของผลคูณ แทนฟงกชันบลู ลนี ได นพิ จนด ังกลา วมักจะยังไมอ ยใู นรปู แบบท่ีงา ยทส่ี ดุ เชน ถา นพิ จน ประกอบดว ยพจนผ ลคูณสองพจน ซงึ่ มีตัวแปรเดยี วกันทกี่ ลับคา กนั เราสามารถละตัวแปรนน้ั ได ลองพิจารณานพิ จน x y z + x y z เราสามารถลดรูปไดคือ x y z + x y z = xz( y + y ) = xz ⋅ 1 = xz 15

ดงั นั้นการสรา งวงจรสาํ หรบั ฟง กชนั x y z + x y z จงึ ทาํ ไดส องแบบ ดงั รูปท่ี 6 รูปที่ 6 วงจรแสดงแบบซงึ่ ทาํ งานไดผ ลเหมอื นกนั จากตวั อยา งขางตนจะเห็นวา เราสามารถรวมพจนบางพจนในนพิ จนผลบวกของผลคูณได วธิ กี ารพื้นฐานท่ีนยิ มใชท วั่ ไปในการลดรูปนพิ จน คือการใชผ งั คารน อฟ (Karnaugh map) ซ่ึง เหมาะสําหรับลดรูปผลบวกของผลคณู ทเ่ี กีย่ วของกบั ตวั แปรนอยกวา หรือเทา กับ 6 ตวั ขอเริม่ พจิ ารณาฟง กชันบลู ลีนแบบ 2 ตัวแปรกอนคอื x และ y สําหรบั ฟงกชันแบบนี้จะ มพี จนส้นั (minterm - ผลคูณของ literal ของทุกตวั แปร) ทัง้ หมด 4 แบบ คือ x y, x y, x y และ x y ผงั คารน อฟ ประกอบดว ยชองสี่เหลีย่ มจัตุรสั โดยที่แตล ะชองแทนหน่ึงพจนส ้นั ในกรณีนผ้ี ังคารน อฟมี 4 ชอ ง การจัดชอ งนน้ั ตอ งจดั ชอ งใหช อ งสองชองทีต่ ิดกนั ใดๆ แทนพจน สนั้ ที่มี literal ของตวั แปรเดยี วกัน แตม ีคาตรงกันขามเพยี งหนึง่ ตวั เชน ชองซึ่งแทน x y ตองติด กับชอง x y และ x y รปู ที่ 7 แสดงผังคารนอฟสําหรับฟงกชนั บลู ลีน 2 ตัวแปร รูปท่ี 7 ผงั คารนอฟส ําหรับฟง กชันสองตวั แปร 16

ในรูปท่ี 7 แตล ะชอ งในผังมพี จนส้นั กาํ กบั อยู ในทางปฏบิ ตั ิเราสามารถละพจนสัน้ ทกี่ าํ กบั นไี้ ด ในการแทนฟงกช นั บูลลีนดว ยผังคารน อฟ ใหพ จิ ารณานพิ จนผลบวกของพจนส ้นั เมอื่ มพี จน สน้ั ใดในฟง กช ัน กใ็ หเ ขียน “ 1 “ ลงในชองซง่ึ แทนพจนสัน้ นั้น ตัวอยางท่ี 15 ใหเขยี นผังคารนอฟ แทนผลบวกของพจนสั้นตอไปนี้ ซ่งึ แทนฟงกช นั แบบ 2 ตวั แปร : xy + x y, x y + x y และ x y + x y + x y จากวธิ ีท่อี ธบิ ายขางตนเราไดผ ังคารนอฟท ้ังสามตามลําดบั คอื ในการรวมพจนส ้นั ทอี่ ยูใ นผังคารน อฟ ใหพจิ ารณชอ งทมี่ ี “ 1 “ และอยูตดิ กนั 2 ชอง ชอ งทงั้ สองน้คี อื พจนส้ัน 2 พจน ซง่ึ มี literal ของตัวแปรเดยี วกันทีม่ คี า ตรงขา มกันหนึง่ ตวั ( x กับ x หรอื y กับ y ) เราเขียนกรอบลอ มรอบชอ งท้งั สองน้เี ปน ชองเดยี ว และแทนชอ งใหม นีด้ วยผลคูณบลู ลีนของพจนส น้ั ของชว งเดมิ ทงั้ สอง ซ่งึ ตัด literal ท่มี คี า ตรงขา มกันทิง้ ไป เชน ถา ชอ ง x y และชอ ง x y มคี า เปน “ 1 “ เราสามารถรวมชอ งท้งั สองเปนชอ งเดยี วแลว เขยี วแทนดว ย y ( เหตผุ ลกค็ อื x y + x y = (x + x) y = y) การรวมชอ งน้ี จํานวนชองที่รวมตองมคี าเปน เลข 2 ยกกําลัง คอื 20, 21, 22, …ในกรณี รวมสองชอ งก็คือ 21 ดังนน้ั การรวมชองจาํ นวนมากถดั ขึ้นไปคือ รวม 22 หรอื 4 ชอ งเปนชอ ง เดยี ว คาท่แี ทนชองใหมน ค้ี อื “ 1 “ ( นํา x y, x y, x y และ x y มาคูณกนั โดยตัด literal ของตัว แปรเดียวกนั ทม่ี ีคาตรงขา มกนั ท้ิง) ดังนั้นการลดรปู โดยใชผังคารน อฟ ถาตองการผลลพั ธท่ีซับซอนนอ ยทส่ี ุด กต็ องรวมชอง ท่อี ยตู ดิ กนั ใหม ากทส่ี ุดเทา ทจี่ ะมากได ใหไ ดจํานวนชอ งใหมนอยทีส่ ุด ผลลพั ธก ็คือ ผลบวกของ นพิ จนซ่งึ แทนแตล ะชองใหม ตวั อยา งที่ 16 ลดรปู ฟงกช ันบูลลีนซง่ึ แทนโดยผังคารนอฟในตวั อยางท่ี 815 กรณที ี่ 1 ผลลัพธค อื x y + x y = y 17

กรณที ่ี 2 เน่ืองจากชอ งทีเ่ ปน “1“ ทัง้ สองไมไดอยตู ดิ กนั จึงรวมชอ งไมไ ด ผลลัพธย งั คงเดิม กรณีท่ี3 ผลลพั ธค ือ (x y + x y) + ( x y + x y) = x + y ผงั คารนอฟสาํ หรบั ฟงกช นั บลู ลีนสามตัวแปร ผงั คารนอฟสาํ หรับฟงกชันบลู ลีนสามตัวแปร ประกอบดวั ยชอ งสี่เหลย่ี มจตั รุ สั 8 ชอง โดยทีแ่ ตล ะชอ งแทนพจนส้ันขนาดตวั แปร (มไี ดท ้งั หมด 23 = 8 แบบ) การแสดงผังคารน อฟ แบบสามตวั แปรนิยมแสดงตามรปู ท่ี 8(a) ความจรงิ แลว การแสดงผังคารน อฟต องใหช อ งซ่ึงมี literal ของตัวแปรเดยี วกนั แตม ีคาตรงขามกนั หน่งึ ตวั แปรอยตู ดิ กัน ดังนน้ั ชอ ง x y z ตองติดกบั ชอ ง x y z ตองติดกับชอ ง x y z จากรปู ที่ 8(a) เราสามารถมว นผงั ใหข อบซายยอนมาตดิ ขอบ ขวาได กลายเปนรปู ท่ี 8(b) ซง่ึ เปน ผงั คารนอฟทถ่ี ูกตอ ง อยา งไรกต็ ามการแสดงผังคารนอฟต าม รปู ท่ี 8(a) เปน แบบท่ใี ชก นั ทวั่ ไป รูปท่ี 8 ผงั คารนอฟส ําหรับฟง กชนั สามตวั แปร ในการลดรปู นพิ จน จะตองรวมชอ งทม่ี คี า “1” และอยตู ดิ กันเปนผืนขนาด 2 ชอ ง 4 ชอง หรอื 8 ชอ ง เพ่อื กําจดั ตวั แปร 1 ตวั 2 ตวั หรือ 3 ตวั ตามลาํ ดับ ตัวแปรที่กาํ จัดกค็ อื ตวั แปรใน พจนส้นั ซึ่งมคี าตรงขา มกนั ในผนื ทพ่ี ิจารณา ผลของผนื รวมจะมคี า เทา กับผลคูณของตวั แปรที่ 18

เหลือ ซง่ึ มคี าตรงขา มกันในผนื ที่พจิ ารณา ผลของผืนรวมจะมีคา เทา กบั ผลคณู ของตัวแปรทเี่ หลือ รูปท่ี 9(a) และ 9(b) แสดงผนื รวมขนาด 2 ชอง รปู ที่ 9(c)และ 9(d) แสดงผนื รวมขนาด 4 ชอ ง และรูปที่ 9 (e) แสดงผืนรวมขนาด 8 ชอ ง รปู ที่ 9 ตวั อยา งการลดรปู ในผังคารน อฟข นาดสามตวั แปร การลดรูปคือ การหาผืนรวมจํานวนนอ ยผนื ที่สุด โดยทแ่ี ตละผนื มีขนาดใหญท ส่ี ุด ตวั อยา งท่ี 17 ใชผังคารน อฟในการลดรปู ผลบวกของผลคูณสําหรบั ฟง กช นั สามตวั แปร ตามขอ a-d ในรปู ที่ 8 19

สาํ หรบั กรณีส่ตี วั แปร ผงั คารน อฟม ักแสดงดวยผนื สีเ่ หลย่ี มจัตุรัสขนาด 4×4 ชองโดยท่ี แตล ะชองแทนหนึง่ พจนส นั้ ดงั รปู ท่ี 10 รูปที 10 ผังคารน อฟสาํ หรับฟงกชันสต่ี ัวแปร ความจรงิ แลวชอ งหน่งึ ชอ งในผลคารน อฟจ ะตอ งอยูตดิ กบั ชองที่มคี าตัวแปรตางกนั หน่งึ ตวั ในกรณฟี ง กชนั ส่ตี วั แปร ชอ งหน่ึงชองตองอยูตดิ กับชอ งอน่ื ๆ อีกส่ชี อง ดังนน้ั ผังคารนอฟท ่ี ถกู ตองในรปู ท่ี 8.10 ตองมว นขอบซายมาชดิ ขอบขวา แลวมว นขอบบนมาชดิ ขอบลา ง รปู ที่ไดจ ะ เปน เหมอื นโดนทั ซ่งึ ตามภาษาคณิตศาสตร เรียกวา ทอรัส (torus) อยา งไรกต็ ามเมอ่ื แสดงในสอง มิตเิ รามักจะแทนเปนสเ่ี หลีย่ มจตุรสั ขนาด 4×4 การลดรปู นพิ จนกท็ าํ ไดท ํานองเดียวกบั กรณฟี งกชันสามตัวแปร คอื รวมชองทม่ี คี า “1” และอยตู ดิ ัน เปน ผนื ขนาด 2 ชอง, 4 ชอง, 8 ชอง หรอื 16 ชอ ง เพอ่ื กาํ จัดตวั แปร 1 ตัว, 2 ตวั , 3 ตัว หรอื 4 ตวั ตามลําดบั จุดมุง หมายก็คอื ตองการจาํ นวนผนื นอ ยทสี่ ดุ โดยทแ่ี ตล ะผนื มขี นาด ใหญที่สดุ รูปที่ 11 แสดงตวั อยางการรวมชองดงั กลา ว 20

รูปท่ี 11 ตวั อยา งการลดรูปในผงั คารน อฟข นาดส่ตี วั แปร ตวั อยา งท่ี 18 ใชผังคารนอฟในการลดรปู ผลบวกของผลคูณสําหรบั ฟง กชนั สต่ี ัวแปร 21