บทที่ 5 พีชคณิตบลูลีน

บทที่ 5 พชี คณติ บูลนี ในวงจรคอมพิวเตอร์น้นั สถานภาพของวงจรจะเป็ นไดเ้ พียงสองสถานะคือ เปิ ด(on) หรือปิ ด(off) เท่าน้นั ซ่ึงจากพ้ืนฐานแนวคิดน้ี ไดม้ ีผูค้ ิดคน้ เซตของกฎเฉพาะท่ีเกิดข้ึนจากการดาเนินการ2 ชนิด เราเรียกกฎเฉพาะน้ีวา่ พีชคณิตบูลีน(Boolean algebra) และไดม้ ีการพฒั นาแนวคิดน้ีต่อมาเพอ่ื ใชใ้ นการออกแบบวงจรสวติ ซ์อิเลก็ ทรอนิกส์ทางคอมพวิ เตอร์5.1 การดาเนินการทวภิ าค การดาเนินการบนเซตใด ๆ ท่ีจะเรียกได้ว่าเป็ นการดาเนินการทวิภาค เป็ นดงั บทนิยามต่อไปน้ีบทนิยาม 5.1 การดาเนินการทวภิ าค(binary operation)  บนเซต A คือกฎเกณฑ์ที่กาหนด ใหค้ ูอ่ นั ดบั ใน A  A กระทากนั แลว้ ไดส้ มาชิกตวั หน่ึงบน A นนั่ คือ ถา้ a , b , c  A และ  เป็ นการดาเนินการทวิภาค บน A แลว้ เราจะเขียน a  b แทน a ดาเนินการ  กบั b และถา้ a  b  c แลว้ จะไดว้ า่ c จะเป็ นสมาชิก เพยี งตวั เดียวใน A ซ่ึงเป็นผลจากการดาเนินการ  บน a กบั b จากบทนิยาม 5.1 จะไดว้ า่ ถา้ ทุก a , b  A แลว้ a  b  A นนั่ คือการดาเนินการทวภิ าคจะมีคุณสมบตั ิปิ ด และการดาเนินการ  ของ a กบั b จะมีเพียงหน่ึงผลลพั ธ์เทา่ น้นัตัวอย่าง 5.1 ให้ A  { 0 , 2 , 4 , 6 , 8 } และให้  เป็นการดาเนินบน A โดย a  b  เลขในหลกั หน่วยของ a  b ซ่ึงสร้างตารางไดด้ งั น้ี 0 2 4 6 8 002468 224680 446802 668024 880246

174 คณิตศาสตร์สาหรับคอมพวิ เตอร์ จะไดว้ า่  เป็นการดาเนินการทวภิ าคบน A เนื่องจากสาหรับทุก a , b  A ถา้ a  b  c จะไดว้ า่ c  A และมี c เพียงตวั เดียวท่ีสอดคลอ้ งกบั a  bตวั อย่าง 5.2 ให้ A  I และกาหนดให้  เป็นการดาเนินการที่กาหนดให้ a  b  a  b พิจารณา a  b  a  bเม่ือ a , b  I จะไดว้ า่ a  b  Iและจะไดว้ า่ a  b จะใหผ้ ลลพั ธ์ที่เป็นจานวนเตม็ เพยี ง 1 ค่าเท่าน้นั ดงั น้นั จะไดว้ า่  เป็นการดาเนินการทวภิ าคบน Iตวั อย่าง 5.3 กาหนดให้ S  { 1 , 0 , 1 } และกาหนดใหก้ ารดาเนินการ  และ  ดงั น้ี 1)  1 0 1 1 2 1 0 1 0 1 0 2 10 12)  1 0 1 1 1 0 1 0 00 0 1 1 0 1จะไดว้ า่  ไมใ่ ช่การดาเนินการทวภิ าคบน S เน่ืองจาก 1) (1)  (1)  2 โดยท่ี 2  S และ 11  2 โดยที่ a  S

บทท่ี 5 พีชคณิตบูลีน 1752)  เป็นการดาเนินการทวภิ าคบน S เนื่องจากทุก a , b  S แลว้ a  b  S และ a  b ใหผ้ ลลพั ธ์เพียงหน่ึงผลลพั ธ์บทนิยาม 5.2 ถา้ S เป็ นเซตที่ไม่ใช่เซตวา่ ง และ  เป็ นการดาเนินการทวิภาคบน S แลว้ เซต S กบั การดาเนินการ  จะเป็ นระบบคณิตศาสตร์ระบบหน่ึง เขียนแทนดว้ ย สัญลกั ษณ์ (S ,  )บทนิยาม 5.3 (S ,  ) จะมีสมบตั ิสลบั ที่(commutative property) กต็ ่อเม่ือ a  b  b  a ทุกค่าของ a , b  Sบทนิยาม 5.4 (S ,  ) จะมีสมบตั ิการเปลี่ยนหมู(่ associative property) กต็ ่อเม่ือ (a  b)  c  a  ( b  c ) ทุก a , b , c  Sบทนิยาม 5.5 (S ,  ) จะเป็นก่ึงกรุป (semigroup) กต็ ่อเมื่อ  เป็นการดาเนินการทวภิ าคที่มี สมบตั ิการเปลี่ยนหมูบ่ น Sตวั อย่าง 5.4 ให้ S  { 1 , 0 , 1 } และนิยามการดาเนินการ  ดงั ตาราง  1 0 1 1 1 0 1 0 00 0 1 1 0 1 จงพจิ ารณาวา่ ( S ,  ) มีสมบตั ิการสลบั ท่ี , การเปลี่ยนหมู่ หรือไม่วธิ ีทา จากตารางจะไดว้ า่  เป็นการดาเนินการทวิภาคบน S พจิ ารณา (1)  1  1  1  (1) (1)  0  0  0  (1) 01  0  1 0 ดงั น้นั ( S ,  ) มีสมบตั ิการสลบั ที่

176 คณิตศาสตร์สาหรับคอมพวิ เตอร์พิจารณา ( (1)  1)  0  (1)  0  0 (1)  ( 1  0 )  (1)  0  0 1 หรือ ( (1)  1)  (1)  (1)  (1)  1 (1)  ( 1  (1) )  (1)  (1) จะไดว้ า่ ( S ,  ) มีสมบตั ิการเปล่ียนหมู่ดงั น้นั ( S ,  ) มีสมบตั ิการสลบั ที่ และมีสมบตั ิการเปลี่ยนหมู่ตวั อย่าง 5.5 ให้ A  { a , b , c } และกาหนดนิยามของการดาเนินการทวภิ าค  และ บน A ดงั น้ี a b c 2)  a b c 1) aabc aabc bbca bcab ccab cbca จงพิจารณาวา่ (A , ) , (A , ) มีสมบตั ิการสลบั ที่ สมบตั ิการเปลี่ยนหมู่หรือไม่ และระบบคณิตศาสตร์ใดเป็ นก่ึงกรุ ปวธิ ีทา 1) พจิ ารณาระบบ A กบั การดาเนินการ  พิจารณา a  b  b ba  b และ b  c  a cb  a ac  c ca  c ดงั น้นั (A , ) มีสมบตั ิการสลบั ที่ พิจารณา ( a  b )  c  b  c  a a(bc)  aa  a (ba)c  bc  a b(ac)  bc  a ดงั น้นั (A , ) มีสมบตั ิการเปล่ียนหมู่ (A , ) จึงเป็นก่ึงกรุป

บทท่ี 5 พชี คณิตบูลีน 1772) พจิ ารณาระบบ A กบั การดาเนินการ  พิจารณา a  b  b ba  c ดงั น้นั (A , ) ไม่มีสมบตั ิการสลบั ท่ี พจิ ารณา ( a  b )  c  b  c  b a(bc)  ab  b (ca)b  bb  a c(ab)  cb  c  (A , ) ไม่มีสมบตั ิการเปลี่ยนหมู่ ดงั น้นั (A , ) ไมเ่ ป็นก่ึงกรุป5.2 กรุปและอาบเี ลยี นกรุป ระบบคณิตศาสตร์ระบบหน่ึง จะเป็นกรุปหรืออาบีเลียนกรุปไดด้ งั บทนิยามต่อไปน้ีบทนิยาม 5.6 ( G ,  ) จะเป็นกรุป(group) เม่ือระบบ G และการดาเนินการทวภิ าค  บน G มีสมบตั ิครบ 4 ขอ้ ดงั น้ี 1. มีสมบตั ิปิ ด นน่ั คือ สาหรับทุก a , b  G แลว้ a  b  G 2. มีสมบตั ิการเปลี่ยนหมู่ นนั่ คือ สาหรับทุก a , b , c  G แลว้ (ab)c  a(bc) 3. มีเอกลกั ษณ์(identity) ของระบบ (G , ) นนั่ คือ จะมีสมาชิก e หน่ึงตวั ใน G ที่ a  e  e  a  a ทุก a  G เรียก e วา่ เอกลกั ษณ์ของระบบ (G , ) 4. สมบตั ิการมีตวั ผกผนั (inverse) ของสมาชิกทุกตวั ใน G นนั่ คือ ทุก a  G จะมี a G ที่ทาให้ a  a  e  a a เรียก a วา่ ตวั ผกผนั ของ a

178 คณิตศาสตร์สาหรับคอมพวิ เตอร์ตวั อย่าง 5.6 จงพิจารณาระบบจานวนเตม็ กบั การคูณวา่ เป็นระบบคณิตศาสตร์ท่ีเป็ นกรุปหรือไม่วธิ ีทา พิจารณาจานวนเตม็ กบั การคูณ เน่ืองจากถา้ a , b  I แลว้ a  b  I และ a  b ได้ผลลพั ธ์เพียงจานวนเดียวดงั น้นั การคูณเป็นการดาเนินการทวภิ าคบน Iพิจารณาสมบตั ิ 4 ขอ้ ต่อไปน้ี1. สมบตั ิปิ ด(I , ) มีสมบตั ิปิ ด เพราะ  เป็นการดาเนินการทวภิ าคบน I2. สมบตั ิการเปล่ียนหมู่ทุก a , b , c  I จะไดว้ า่a  ( b  c )  ( a  b )  c เช่น3  ( (2)  (1) )  3  2  6( 3  (2) )  (1)  (6)  (1)  63. สมบตั ิการมีเอกลกั ษณ์ในเซตของจานวนเตม็ กบั การคูณมี 1 เป็นเอกลกั ษณ์ของการคูณเน่ืองจากทุก a  I จะไดว้ า่ a  1  a  1  aนนั่ คือ (I , ) มีเอกลกั ษณ์คือ 14. สมบตั ิการมีตวั ผกผนั ทุกสมาชิกใน Iในเซตของจานวนเตม็ กบั การคูณน้นั สาหรับ a  Iถา้ กาหนดใหต้ วั ผกผนั ของ a แทนดว้ ย a จะไดว้ า่ a  1 a 1เพราะ a  a  1 ซ่ึงเป็นเอกลกั ษณ์ของการคูณใน Iแต่เนื่องจาก 1 บางจานวนไมใ่ ช่จานวนเต็ม เช่นaถา้ a  2 แลว้ 1  I 2จะไดว้ า่ ตวั ผกผนั ของ 2 ไมใ่ ช่จานวนเตม็นน่ั คือ (I , ) ไม่มีสมบตั ิการมีตวั ผกผนัดงั น้นั (I , ) ไมใ่ ช่กรุป

บทท่ี 5 พชี คณิตบูลีน 179ตัวอย่าง 5.7 กาหนด (A , ) ดงั ตาราง a b c d aabc d bbcd a ccda b ddab cจงหาวา่ 1) (A , ) มีเอกลกั ษณ์ของระบบหรือไม่วธิ ีทา 2) หาตวั ผกผนั ของสมาชิกทุกตวั ใน A 1) เอกลกั ษณ์ของระบบ (A , ) คือ a เนื่องจาก aa  a 2) ba  b  ab ca  c  a c da  d  a d พิจารณาการมีตวั ผกผนั ของสมาชิกทุกตวั ใน A ตวั ผกผนั ของ a คือ a เนื่องจาก a  a  a ตวั ผกผนั ของ b คือ d เน่ืองจาก b  d  a ตวั ผกผนั ของ c คือ c เน่ืองจาก c  c  a ตวั ผกผนั ของ d คือ b เน่ืองจาก d  b  a ดงั น้นั สมาชิกทุกตวั ใน A มีตวั ผกผนับทนิยาม 5.7 กาหนดให้ (G , ) เป็ นกรุป ถา้ สมาชิก a และ b ใดๆ ใน G กบั การ ดาเนินการ  มีสมบตั ิการสลบั ท่ี นนั่ คือ ab  ba แลว้ จะเรียก (G , ) วา่ เป็ นอาบีเลียนกรุป(abelian group)

180 คณิตศาสตร์สาหรับคอมพวิ เตอร์ พิจารณา (G , ) โดยท่ี  เป็ นการดาเนินการทวิภาคบน G และพิจารณาสมบตั ิ5 ขอ้ ต่อไปน้ี 1. สมบตั ิปิ ด 2. สมบตั ิการเปล่ียนหมู่ 3. สมบตั ิการเอกลกั ษณ์ของ (G , ) 4. สมบตั ิการมีตวั ผกผนั ของทุกสมาชิกใน G 5. สมบตั ิการสลบั ที่ ถา้ (G ,  ) มีสมบตั ิขอ้ 1 และ 2 เราเรียกไดว้ า่ (G ,  ) เป็นก่ึงกรุป ถา้ (G , ) มีสมบตั ิขอ้ 1 , 2 , 3 และ 4 เราเรียกไดว้ า่ (G ,  ) เป็นกรุป ถา้ (G ,  ) มีสมบตั ิท้งั 5 ขอ้ ขา้ งตน้ แลว้ (G ,  ) เป็นอาบีเลียนกรุปตวั อย่าง 5.8 กาหนด (A , ) ดงั น้ี 0 2 4 6 8 002468 224680 446802 668024 880246 จงพิจารณาวา่ (A , ) เป็นอาบีเลียนกรุปหรือไม่วธิ ีทา 1. (A , ) มีสมบตั ิปิ ด (พจิ ารณาจากตาราง) 2. (A , ) มีสมบตั ิการเปล่ียนหมู่ เพราะจากตารางเราไดว้ า่ สาหรับทุก a , b , c  A แลว้ (a  b)  c  a  (b  c) เช่น (2  4)  8  6  8  4 2  (4  8)  2  2  4

บทท่ี 5 พชี คณิตบูลีน 1813. (A , ) มีเอกลกั ษณ์ คือ 0 เนื่องจาก 00  0 20  2  02 40  4  04 60  6  06 80  8  084. สมาชิกทุกตวั ใน A มีตวั ผกผนั ตวั ผกผนั ของ 0 คือ 0 ตวั ผกผนั ของ 2 คือ 8 ตวั ผกผนั ของ 4 คือ 6 ตวั ผกผนั ของ 6 คือ 4 ตวั ผกผนั ของ 8 คือ 25. (A , ) มีสมบตั ิการสลบั ท่ี เพราะจากตารางเราไดว้ า่ สาหรับทุก a , b  A แลว้ a  b  b  a เช่น 26  8  62ดงั น้นั (A , ) เป็นอาบีเลียนกรุปบทนิยาม 5.8 กาหนดให้ (G , ) และ ( G  , ) เป็นกรุป จะเรียกไดว้ า่ (G , ) สมสณั ฐาน(isomorphism) กบั ( G  , ) กต็ อ่ เม่ือ 1. มีฟังกช์ นั f ซ่ึงเป็นฟังกช์ นั 1-1 จาก G ไปทว่ั ถึง G  2. f(x  y)  f(x)  f(y) ทุก x , y  G เราเรียก f วา่ เป็นสมสณั ฐานจาก G ไปทวั่ ถึง G  เขียนแทนดว้ ย G  G 

182 คณิตศาสตร์สาหรับคอมพวิ เตอร์ตัวอย่าง 5.9 กาหนดให้ G  { 1 , 1 } กบั การดาเนินการคูณบน G และ S  { a , b }กบั การดาเนินการ  ดงั ตาราง 1 1 a b1 1 1 aab1 1 1 bba และกาหนดให้ f เป็นฟังกช์ นั จาก G ไป S โดยกาหนดให้ f(1)  a f(1)  b จงพจิ ารณาวา่ f เป็นสมสัณฐานจาก G ไปบน S หรือไม่วธิ ีทา พิจารณา (G , ) จะไดว้ า่ (G , ) เป็นกรุ๊ป ที่มี (1) เป็นเอกลกั ษณ์ของระบบ และมี (1) เป็นตวั ผกผนั ของ 1 มี 1 เป็นตวั ผกผนั ของ (1) พจิ ารณา (S , ) จะไดว้ า่ (S , ) เป็นกรุปที่มี a เป็นเอกลกั ษณ์ของระบบ มี a เป็นตวั ผกผนั ของ a มี b เป็นตวั ผกผนั ของ b พิจารณา f : G  S จะไดว้ า่ f เป็นฟังกช์ นั 1-1 จาก G ไปทวั่ ถึง S พจิ ารณา f(x  y) และ f(x)  f(y) จากตารางx y x  y f(x  y) f(x) f(y) f(x)  f(y)11 1 a aa a1 1 1 b a b b1 1 1 b b a b1 1 1 a bb aจะไดว้ า่ ทุก x , y  G f (x  y)  f(x)  f(y)ดงั น้นั f เป็นสมสัณฐานจาก G ไปทวั่ ถึง S

บทที่ 5 พีชคณิตบูลีน 1835.3 พชี คณติ บูลนี ในหวั ขอ้ น้ีจะกล่าวถึงพีชคณิตบูลีนซ่ึงเป็ นระบบคณิตศาสตร์กบั ดาเนินการทวิภาคสองอยา่ งซ่ึงมีสมบตั ิเฉพาะดงั บทนิยามต่อไปน้ีบทนิยาม 5.9 พชี คณิตบูลีน คือระบบคณิตศาสตร์ซ่ึงประกอบดว้ ยเซต S ซ่ึงไมใ่ ช่เซตวา่ งและการ ดาเนินการทวภิ าคสองอยา่ งคือ  และ  ซ่ึงมีสมบตั ิตอ่ ไปน้ี 1. มีสมบตั ิการเปล่ียนหมูใ่ นเซต S สาหรับการดาเนินการ  และ  2. มีสมบตั ิการสลบั ท่ีสาหรับการดาเนินการ  และ  3. มีสมบตั ิการแจกแจง(distributive property) ของ  บน  และของ  บน  นน่ั คือทุก a , b , c  S a(bc)  (ab)(ac) a (bc)  (ab)(ac) 4. มีเอกลกั ษณ์ e สาหรับการดาเนินการ  และมีเอกลกั ษณ์ i สาหรับการดาเนินการ  โดยที่ e  i และ e , i  S นน่ั คือ ทุก a  S แลว้ a  e  a  e  a และ ai  a  ia 5. ทุก a  S จะมี a S ที่ทาให้ a  a  i  a  a และ a  a  e  a a เรียก a วา่ ตวั ผกผนั ของ a เราเรียกระบบคณิตศาสตร์ (S , , ) ท่ีมีสมบตั ิท้งั 5 ขอ้ น้ีวา่ เป็นพชี คณิตบูลีนตัวอย่าง 5.10 ให้ A  { 1 , 0 } และนิยามการดาเนินการ  และ  บนเซต A ดงั น้ี 0 1 0 1 001 00 0 111 10 1จงพิจารณาวา่ (A ,  , ) เป็นพีชคณิตบูลีนหรือไม่

184 คณิตศาสตร์สาหรับคอมพวิ เตอร์วธิ ีทา (A , ) มีสมบตั ิปิ ดใน A และ (A , ) มีสมบตั ิปิ ดใน A ดงั น้นั  ,  เป็นการดาเนินการทวภิ าคบน A 1. 0  ( 1  0 )  0  1  1 (0  1)  0  1  0  1 และ 0  ( 0  1 )  0  0  0 (0  0)  1  0  1  1 ดงั น้นั (A ,  , ) มีสมบตั ิการเปล่ียนหมู่ 2. มีสมบตั ิการสลบั ที่ของการดาเนินการ  และ  เช่น 0  1  1  1  0 01 0  10 ดงั น้นั (A ,  , ) มีสมบตั ิการสลบั ที่ 3. 1  ( 0  1 )  1  0  1 (1  0)  (1  1)  1  1  1 นน่ั คือ (A ,  , ) มีสมบตั ิการแจกแจง  บน  1  (0  1)  1  1  1 (1  0)  (1  1)  0  1  1 นนั่ คือ (A ,  , ) มีสมบตั ิการแจกแจง  บน  4. ในเซต A มี 0 เป็นเอกลกั ษณ์ของการดาเนินการ  และมี 1 เป็นเอกลกั ษณ์ของการดาเนินการ  5. ทุก a  A จะมีตวั ผกผนั a A ซ่ึงทาให้ a  a  1 และ a  a  0 ดงั น้ี ตวั ผกผนั ของ 0 คือ 1 เพราะ 01  1 01  0 ตวั ผกผนั ของ 1 คือ 0 เพราะ 10  1 10  0 ดงั น้นั จะไดว้ า่ (A ,  , ) เป็นพีชคณิตบูลีน

บทท่ี 5 พชี คณิตบูลีน 185ตัวอย่าง 5.11 ให้ B  { T , F } และนิยามการดาเนินการ 2 อยา่ ง คือ  และ  ดงั ตาราง T F T F TTF TTT FFF FTF จงพจิ ารณาวา่ (B ,  ,  ) เป็นพชี คณิตบูลีนหรือไม่วธิ ีทา1. (B ,  ,  ) มีสมบตั ิการเปล่ียนหมูใ่ น B สาหรับการดาเนินการท้งั 2 อยา่ ง2. T  F  F  F  T TF  T  FT ดงั น้นั (B ,  ,  ) มีสมบตั ิการสลบั ท่ีของการดาเนินการท้งั  และ 3. T  ( F  T )  T  T  T (T F)  (T T)  F  T  T และ T  ( T  F )  T  F  T (T T)  (T F)  T  T  T ดงั น้นั (B ,  ,  ) มีสมบตั ิการแจกแจง  บน  และการแจกแจง  บน 4. มีเอกลกั ษณ์ของการดาเนินการ  คือ T และมีเอกลกั ษณ์ของการดาเนินการ  คือ F5. ทุก a  B จะมี a B ซ่ึงa  a Fa  a  T ดงั น้นั เพราะตวั ผกผนั ของ T คือ F FTF TF  T เพราะตวั ผกผนั ของ F คือ T FFT FT Tดงั น้นั (B ,  ,  ) เป็นพีชคณิตบูลีน

186 คณิตศาสตร์สาหรับคอมพวิ เตอร์ทฤษฎบี ทสาคัญทเี่ ก่ียวกบั พชี คณติ บูลนีทฤษฎบี ท 5.1 ถา้ (A ,  ,  ) เป็นพชี คณิตบูลีนแลว้ ทุก a  S จะไดว้ า่ 1. a  a  a 2. a  a  aพสิ ูจน์ ให้ (A ,  ,  ) เป็นพชี คณิตบูลีนท่ีมี e เป็นเอกลกั ษณ์ของการดาเนินการ มี i เป็นเอกลกั ษณ์ของการดาเนินการ  และทุก a ใดๆที่ a  A จะมีตวั ผกผนั a A1. a  a  e บทนิยาม 5.9 ขอ้ 4 a  ( a  a ) บทนิยาม 5.9 ขอ้ 5 ( a  a )  ( a  a ) บทนิยาม 5.9 ขอ้ 3 (a  a)  i บทนิยาม 5.9 ขอ้ 5 aa บทนิยาม 5.9 ขอ้ 4นนั่ คือ ถา้ (A ,  ,  ) เป็นพีชคณิตบูลีนแลว้ a  a  a2. a  a  e บทนิยาม 5.9 ขอ้ 4 a  ( a  a ) บทนิยาม 5.9 ขอ้ 5 ( a  a )  ( a  a ) บทนิยาม 5.9 ขอ้ 3 (a  a)  e บทนิยาม 5.9 ขอ้ 5 aa บทนิยาม 5.9 ขอ้ 4นนั่ คือ ถา้ (A ,  ,  ) เป็นพีชคณิตบูลีนแลว้ a  a  aทฤษฎบี ท 5.2 ถา้ (A ,  ,  ) เป็นพีชคณิตบูลีนแลว้ ทุก a  A จะไดว้ า่ 1) a  i  i 2) a  e  e

บทท่ี 5 พีชคณิตบูลีน 187พสิ ูจน์ a  ( a  a ) บทนิยาม 5.9 ขอ้ 51. a  i  ( a  a )  a บทนิยาม 5.9 ขอ้ 1 a  a ทฤษฎีบท 5.1  i บทนิยาม 5.9 ขอ้ 5 แลว้ a  i  i  a  ( a  a) บทนิยาม 5.9 ขอ้ 5  ( a  a )  a บทนิยาม 5.9 ขอ้ 1 นน่ั คือ ทุก a  A a  a ทฤษฎีบท 5.12. a  e  e บทนิยาม 5.9 ขอ้ 5   ทฤษฎบี ท 5.3 ถา้ (A ,  ,  ) เป็นพีชคณิตบูลีนแลว้ ทุก a , b  A จะไดว้ า่ 1. a  ( a  b )  a 2. a  ( a  b )  aพสิ ูจน์1. a  (a  b)  ( a  e )  ( a  b ) บทนิยาม 5.9 ขอ้ 4  a  (e  b) บทนิยาม 5.9 ขอ้ 3  ae ทฤษฎีบท 5.2 a บทนิยาม 5.9 ขอ้ 4 นนั่ คือ ทุก a , b  A โดยท่ี (A ,  ,  ) เป็นพชี คณิตบูลีนแลว้ a  (a  b)  a2. ขอ้ 2 ใหพ้ สิ ูจนเ์ ป็นแบบฝึกหดัทฤษฎบี ท 5.4 ถา้ (A ,  ,  ) เป็นพีชคณิตบูลีน และสาหรับ a , b  A แลว้ 1. (a  b )  a  b 2. (a  b )  a  b

188 คณิตศาสตร์สาหรับคอมพวิ เตอร์พสิ ูจน์ กาหนดให้ (A ,  ,  ) เป็นพีชคณิตบูลีน และ a , b  A จะพิสูจน์วา่1. (a  b )  a  bดงั น้นั ตอ้ งแสดงใหเ้ ห็นวา่(a  b)  (a  b)  eและ (a  b )  (a  b)  i(a  b)  (a  b)  (a  b)  (a  b) การสลบั ที่  ((a  b)  a )  ((a  b)  b ) การแจกแจง  (( b  a)  a )  ((a  b)  b ) การสลบั ท่ี  ( b  (a  a ) )  (a  ( b  b ) ) การเปล่ียนหมู่  (b  e )  (a  e) บทนิยาม 5.9 ขอ้ 5  ee ทฤษฎีบท 5.2 e ทฤษฎีบท 5.1 (a  b)  (a b)  ((a  b )  a)  ((a  b )  b) การแจกแจง  (( b  a )  a)  ((a  b )  b) การสลบั ที่  ( b  (a  a) )  (a  ( b  b) ) การเปลี่ยนหมู่  (b  i)  (a  i) บทนิยาม 5.9 ขอ้ 5  i  i ทฤษฎีบท 5.2  ดงั น้นั จะไดว้ า่ (a  b ) i ทฤษฎีบท 5.1การพิสูจน์ ขอ้ 2 ใหท้ าแบบฝึกหดั  a  b

บทที่ 5 พีชคณิตบูลีน 1895.4 การประยุกต์พชี คณติ บูลนี เราประยกุ ตใ์ ชพ้ ชี คณิตบูลีนกบั วงจรสวติ ซ์ไฟฟ้า ซ่ึงจะมีสถานการณ์ในทางานเพียง 2 แบบคือ สวติ ซ์ปิ ดและสวติ ซ์เปิ ด ดงั รูปท่ี 5.1 และ 5.2 AB รูปที่ 5.1 แสดงสถานการณ์ทางานของสวติ ซ์เปิ ด AB รูปที่ 5.2 แสดงสถานะการทางานของสวติ ซ์ปิ ด จากรูปที่ 5.1 ถา้ สวติ ซ์เปิ ดวงจรจะไมเ่ ช่ือมต่อกนั ดงั น้นั จะไม่มีกระแสไฟฟ้าไหลผา่ นวงจร จากรูปท่ี 5.2 ถา้ สวติ ซ์ปิ ดวงจรเกิดการเช่ือมต่อจึงเกิดการไหลของกระแสไฟฟ้าในวงจร ถ้ากาหนดให้ P คือสวิตซ์ไฟฟ้า และแทนสถานะการทางานของสวิตซ์คือให้ 0 แทนสวติ ซ์เปิ ด 1 แทนสวติ ซ์ปิ ด และสร้างตารางแสดงสถานะของ P และ P ไดด้ งั ตาราง 5.1 P P 10 01 ตาราง 5.1 แสดงสถานะการทางานของสวติ ซ์ P และ P การตอ่ วงจรไฟฟ้าน้นั เรามีวธิ ีการตอ่ ได้ 2 แบบ ไดแ้ ก่การต่อวงจรแบบอนุกรม และการต่อวงจรแบบขนาน ซ่ึงจะมีลกั ษณะการต่อวงจร ดงั น้ี

190 คณิตศาสตร์สาหรับคอมพวิ เตอร์ 1. การตอ่ วงจรอนุกรม ถา้ เรามีสวิตซ์ 2 ตวั คือ สวิตซ์ P และ สวติ ซ์ Q การต่อสวติ ซ์ P และ Q โดยการต่อวงจรแบบอนุกรมจะมีลกั ษณะดงั รูปท่ี 5.3AP QBรูปท่ี 5.3 แสดงการต่อสวติ ซ์ P และ Q แบบวงจรอนุกรม สวิตซ์ P และสวิตซ์ Q ที่ต่อแบบอนุกรมน้นั สถานะการทางานของ สวิตซ์ท้งั 2 เป็ นได้4 แบบ ไดแ้ ก่ แบบที่ 1 สวติ ซ์ P เปิ ด และสวติ ซ์ Q เปิ ด ซ่ึงแสดงไดด้ งั รูปที่ 5.4 แบบท่ี 2 สวติ ซ์ P ปิ ด และสวติ ซ์ Q เปิ ด ซ่ึงแสดงไดด้ งั รูปท่ี 5.5 แบบที่ 3 สวติ ซ์ P เปิ ด และสวติ ซ์ Q ปิ ด ซ่ึงแสดงไดด้ งั รูปที่ 5.6 แบบที่ 4 สวติ ซ์ P ปิ ด และสวติ ซ์ Q ปิ ด ซ่ึงแสดงไดด้ งั รูปที่ 5.7AP Q B รูปที่ 5.4AP Q B รูปท่ี 5.5AP Q B รูปท่ี 5.6AP Q B รูปที่ 5.7 สถานะของการทางานของสวิตซ์ P และ Q ซ่ึงต่อวงจรแบบอนุกรมดังรูปขา้ งต้นกระแสไฟฟ้าจะไหลในวงจรน้ีเม่ือสวิตซ์ปิ ด ถา้ วงจรมีสวิตซ์ 2 ตวั กระแสไฟฟ้าจะไหลจากจุดA ไปหาจุด B ไดเ้ ม่ือท้งั สวติ ซ์ P และ สวติ ซ์ Q อยใู่ นสถานะปิ ดท้งั คู่ แต่ถา้ ในวงจรมีสวิตซ์ตวั ใดตวั หน่ึงหรือท้งั สองตวั เปิ ดอยู่ กระแสไฟฟ้าจะไม่สามารถไหลผา่ นจุด A ไปจุด B ได้ ถา้ เราแทนสวติ ซ์ปิ ดหรือวงจรปิ ด แลว้ ทาใหเ้ กิดกระแสไฟฟ้าไหลผา่ นไดด้ ว้ ย 1 และใช้0 แทนสถานะของสวิตซ์เปิ ดหรือวงจรเปิ ดไม่มีกระแสไฟฟ้าไหลในวงจร เราสามารถแสดงสถานะของการทางานของสวติ ซ์ P และ Q และวงจรอนุกรมไดด้ งั ตาราง 5.2

บทที่ 5 พีชคณิตบูลีน 191 PQ วงจรอนุกรม P , Q 00 0 01 0 10 0 11 1 ตาราง 5.2 แสดงสถานะของสวติ ซ์ P , Q และวงจรอนุกรม2. การต่อวงจรขนานสวติ ซ์ P และ สวติ ซ์ Q ที่ต่อวงจรโดยใชว้ งจรแบบขนาน จะมีลกั ษณะการต่อดงั รูปที่ 5.8 P AB Q รูปที่ 5.8 แสดงการต่อวงจรแบบขนานสถานะการทางานของสวติ ซ์ P และ Q ก็จะเป็นได้ 4 แบบไดแ้ ก่แบบท่ี 1 สวติ ซ์ P เปิ ด และสวติ ซ์ Q เปิ ด ซ่ึงแสดงไดด้ งั รูปที่ 5.9แบบที่ 2 สวติ ซ์ P เปิ ด แตส่ วิตซ์ Q ปิ ด ซ่ึงแสดงไดด้ งั รูปท่ี 5.10แบบที่ 3 สวติ ซ์ P ปิ ด แต่สวติ ซ์ Q เปิ ด ซ่ึงแสดงไดด้ งั รูปที่ 5.11แบบท่ี 4 สวติ ซ์ P ปิ ด และสวติ ซ์ Q ปิ ด ซ่ึงแสดงไดด้ งั รูปที่ 5.12 PA B รูปที่ 5.9 Q

192 คณิตศาสตร์สาหรับคอมพวิ เตอร์ P B รูปท่ี 5.10 B รูปท่ี 5.11A B รูปท่ี 5.12 Q PA Q PA Q พิจารณารูปที่ 5.9 วงจรขนานท่ีสวติ ซ์ P และ Q เปิ ดท้งั คู่ กระแสไฟฟ้าไม่สามารถไหลผา่ น จากจุด A ไป B ได้ รูปที่ 5.10 วงจรขนานที่สวิตซ์ P เปิ ด Q ปิ ด แมว้ า่ กระแสไฟฟ้าจะไม่สามารถไหลผา่ นสวติ ซ์ P ที่เปิ ดได้ แต่กระแสไฟฟ้าสามารถไหลจากจุด A ไปยงั จุด B โดยผา่ นสวติ ซ์ Q ท่ีปิ ดอยไู่ ด้ รูปท่ี 5.11 ก็จะเป็ นในทานองเดียวกนั กบั รูปท่ี 5.10 คือ กระแสไฟฟ้าสามารถไหลผ่านจากจุด A ไปยงั จุด B โดยผา่ นสวติ ซ์ตวั ท่ีปิ ดคือ สวติ ซ์ P รูปที่ 5.12 สวิตซ์ P และ Q ปิ ดท้งั คู่ ดงั น้นั กระแสไฟฟ้าสามารถไหล จากจุด Aผา่ นสวติ ซ์ท้งั คูม่ ายงั จุด B ได้ ถา้ ให้ 1 แทนสวติ ซ์ปิ ดหรือวงจรปิ ดท่ีกระแสไฟฟ้าไหลผา่ นวงจรได้ และ 0 แทนสวติ ซ์เปิ ดหรือวงจรเปิ ดที่กระแสไฟฟ้าไม่สามรถไหลผ่านวงจรได้ เราสามารถสร้างตารางแสดงสถานะการทางานของสวติ ซ์ P และ Q และวงจรขนานไดด้ งั ตาราง 5.3

บทท่ี 5 พชี คณิตบูลีน 193 PQ วงจรขนาน P Q 00 0 01 1 10 1 11 1ตาราง 5.3 แสดงสถานะของสวติ ซ์ P , Q และวงจรขนาน PQ ถา้ เปรียบเทียบการต่อสวติ ซ์วงจรไฟฟ้าวงจรอนุกรมและวงจรขนานกบั การใชต้ วั เช่ือม “และ”และตวั เช่ือม “หรือ” ของประพจน์ 2 ประพจน์ โดยใหค้ ่าความจริง T เท่ากบั 1 และค่าความจริง F เทา่ กบั 0 ดงั น้ี สวติ ซ์วงจรไฟฟ้า ประพจน์และตวั เชื่อมทางตรรกศาสตร์1. สถานะของสวติ ซ์ ค่าความจริงของประพจน์ P P P P 10 TF 01 FT2. วงจรอนุกรม ประพจน์กบั ตวั เชื่อม “  ” P Q วงจร P Q PQ TTT 11 1 TFF 10 0 FTF 01 0 FFF 00 0

194 คณิตศาสตร์สาหรับคอมพวิ เตอร์3. วงจรขนาน ประพจนก์ บั ตวั เช่ือม “  ” P Q วงจร P Q PQ TTT 11 1 TFT 10 1 FTT 01 1 FFF 00 0 จากการเปรียบเทียบขา้ งตน้ จะเห็นวา่ การต่อวงจรสวิตซ์ไฟฟ้าแบบอนุกรมสมมูลกบั การเชื่อมประพจน์โดยใชต้ วั เชื่อม “  ” และการต่อวงจรสวติ ซ์ไฟฟ้าแบบขนานสมมูลกบั การเช่ือมประพจน์โดยใชต้ วั เชื่อม “  ” เราจึงสามารถแทนท่ีวงจรอนุกรมดว้ ยประพจน์กบั ตวั เชื่อม “  ” และแทนที่วงจรขนานดว้ ยประพจนก์ บั ตวั เชื่อม “  ” โดยใชก้ ฎการแทนที่ท่ีไดเ้ รียนมาแลว้ ในบทที่ 3ถา้ กาหนดให้ A  { 0 , 1 } และนิยามการดาเนินการ  และ  ดงั น้ี0 1 0 1001 000111 101 จะไดว้ า่ (A ,  , ) เป็นพชี คณิตบูลีน(แสดงแลว้ ในตวั อยา่ ง 5.10) และถา้ เปรียบเทียบการต่อสวติ ซ์ P และ สวติ ซ์ Q แบบวงจรขนานโดยการแทนท่ีสวติ ซ์วงจรแบบขนานดว้ ยประพจน์กบัตวั เช่ือม “  ” กบั การดาเนินการ  บน A ดงั น้ีสวติ ซ์และการตอ่ วงจรขนาน A กบั การดาเนินการ  P Q PQ 11  1 111 10  1 101 01  1 011 00  0 000

บทท่ี 5 พีชคณิตบูลีน 195 เปรียบเทียบการต่อสวิตซ์ P และ Q แบบวงจรอนุกรมโดยการแทนที่ดว้ ยประพจน์และตวั เชื่อม “  ” กบั การดาเนินการ  บน A ดงั น้ีสวติ ซ์และการต่อวงจรอนุกรม A กบั การดาเนินการ  P Q PQ 11  1 111 10  0 100 01  0 010 00  0 000 จะเห็นไดว้ า่ สถานะของสวติ ซ์ในการตอ่ วงจรแบบขนานและอนุกรมสัมพนั ธ์กบั A และการดาเนินการ  และ  ซ่ึงเป็ นพีชคณิตบูลีน เราจึงถือว่าสวิตซ์และการต่อวงจรแบบขนานและแบบอนุกรมสมสัณฐานกบั (A ,  , ) ทาใหส้ วติ ซ์และการต่อวงจรแบบขนานและอนุกรมเป็ นพชี คณิตบูลีนดว้ ย ดงั น้นั ทฤษฎีบทและสมบตั ิตา่ งๆ ท่ีเป็นจริงสาหรับพีชคณิตบูลีนก็เป็ นจริงสาหรับสวติ ซ์และการต่อวงจรแบบขนานและแบบอนุกรมดว้ ยเช่นกนั ซ่ึงจะแสดงใหเ้ ห็นบางประการดงั น้ีพชี คณิตบูลีน สวติ ซ์และการต่อวงจร1. a  b  b  a 1. a  b (สลบั ที่การบวก) b a2. a b  b a 2. b b a (สลบั ท่ีการคูณ) a3. a (bc)  (a b)c 3. a a (เปล่ียนหมู่การบวก) b b  c c

196 คณิตศาสตร์สาหรับคอมพวิ เตอร์พชี คณิตบูลีน สวติ ซ์และการตอ่ วงจร4. a (bc)  (a b) c 4. b ca b c (เปล่ียนหมู่การคูณ) a 5. b ab a ac5. a ( b  c )  a b  a c ( การแจกแจง ) c6. a  (bc)  (a  b)(a  c) 6. a aa (การแจกแจง) bc  bc7. a  0  a 7. (เอกลกั ษณ์การบวก) a a 08. a . 1  a 8. a1  a (เอกลกั ษณ์การคูณ)9. a  a  1 9. a (ตวั ผกผนั ) 110. a . a  1 a ( ตวั ผกผนั ) 10. a a  0

บทที่ 5 พชี คณิตบูลีน 197 เราสามารถใชพ้ ีชคณิตบูลีนชนิดสองค่าคือ { 0 , 1 } กบั การดาเนินการบวกและคูณแทนวงจรสวติ ซ์แบบขนานและแบบอนุกรม ซ่ึงทาใหเ้ ราสามารถเปล่ียนวงจรไฟฟ้าท่ีมีความซบั ซอ้ นใหอ้ ยใู่ นรูปที่ง่ายข้ึนตวั อย่าง 5.12 จงใชพ้ ีชคณิตบูลีนชนิดสองค่าคือ { 0 , 1 } กบั การดาเนินการบวกและคูณเพื่อแสดงวา่ ab  ba 1) a  (b c)  (a  b)(a  c) 2)วธิ ีทา 1) a b ab ba 1111 1000 0100 0000ดงั น้นั ab  ba2)a b c bc a  bc a  b a  c (a  b)(a  c)1111 1 1 1 11100 1 1 1 11010 1 1 1 11000 1 1 1 10111 1 1 1 10100 0 1 0 00010 0 0 1 0 00000 0 0 0ดงั น้นั a  (bc)  (a  b)(a  c)

198 คณิตศาสตร์สาหรับคอมพวิ เตอร์ตวั อย่าง 5.13 จงแสดงความสมมูลของวงจรสวติ ซ์ไฟฟ้ากบั พีชคณิตบูลีนต่อไปน้ี 1) a  1  1 2) a  (a  b)  a  bวธิ ีทา1) a  1  1 a 1 12) a  (a  b)  a  b  a a b a bตวั อย่าง 5.14 จงทาวงจรตอ่ ไปน้ีใหง้ ่ายข้ึน a abวธิ ีทา เปล่ียนวงจรใหเ้ ป็นพีชคณิตบูลีนจะได้ a  (ab)เนื่องจาก a  (ab)  a.1  a.b  a (1  b)  a (1 ) aดงั น้นั จะไดว้ งจรท่ีง่ายข้ึนคือ a

บทที่ 5 พีชคณิตบูลีน 199ตัวอย่าง 5.15 จงพจิ ารณาวงจรต่อไปน้ีใหง้ ่ายข้ึน c c ab a b c a bวธิ ีทา เปล่ียนวงจรใหเ้ ป็นพชี คณิตบูลีนจะได้ abc  abc  abcเน่ืองจาก abc  abc  abc  c(ab  ab  ab)  c(a(b  b)  ab)  c(a(1)  ab)  c (a  ab)  c[ (a  a) (a  b) ]  c (1) (a  b)  c(a  b)จะไดว้ งจรท่ีง่ายข้ึนคือ a c bบทสรุป พชี คณิตบูลีนมีประโยชน์มากในการประยุกตใ์ ชก้ บั วงจรสวติ ซ์ไฟฟ้าซ่ึงมีสถานการณ์ทางานเพียงสองสถานะคือสวติ ซ์ปิ ดหรือสวติ ซ์เปิ ด การต่อสวติ ซ์วงจรแบบขนานและแบบอนุกรมที่ซบั ซอ้ นการพจิ ารณาสถานการณ์ทางานของวงจรทาไดย้ งุ่ ยาก แต่ถา้ ใชพ้ ีชคณิตบูลีนชนิดสองค่าแทนท่ีวงจรที่ซับซ้อนแลว้ ใช้ทฤษฎีบทหรือสมบตั ิต่างๆของพีชคณิตบูลีนเขา้ มาช่วยจะทาให้การพิจารณาวงจรที่ซบั ซอ้ นใหเ้ ป็นไปไดง้ ่ายข้ึน

200 คณิตศาสตร์สาหรับคอมพวิ เตอร์ แบบฝึ กหดั บทที่ 51. จงพิจารณาวา่ การดาเนินการในขอ้ ใดต่อไปน้ีเป็ นการดาเนินการทวภิ าค 1) ให้ A  { 0 , 1 , 2 } และนิยามการดาเนินการ  บน A ดงั น้ี a  b  เศษจากการหาร (a  b) ดว้ ย 3 0 1 2 0012 1120 2201 2) ให้ B  { 0 , 1 } และนิยามการดาเนินการ  บน B ดงั น้ี 0 1 000 101 3) ให้ C  { 0 , 1 } และนิยามการดาเนินการ O บน B ดงั น้ี O0 1 001 1122. กาหนดให้ S  { a , b } และนิยาม  ดงั น้ี 1) a b aaa baa

บทที่ 5 พีชคณิตบูลีน 201 2) a b aaa bba 3) a b aaa bbb (S ,  ) ในขอ้ ใดเป็ นกรุป3. จงพจิ ารณาวา่ ขอ้ ใดตอ่ ไปน้ีเป็นไดเ้ พยี งการดาเนินการทวภิ าค ก่ึงกรุป กรุป หรือเป็น อาบีเลียนกรุป 1) (I , ) 2) (I , ) 3) (S , O) เม่ือ S  { 0 , 1 } และนิยามการดาเนินการ  ดงั น้ี 4) (A , ) เมื่อ A  { 0 , 2 , 4 , 6 , 8 } และนิยามการดาเนินการ  ดงั น้ี 0 2 4 6 8 000000 204826 408642 602568 806284

202 คณิตศาสตร์สาหรับคอมพวิ เตอร์5) (A , ) เมื่อ A  { 1 , 1 2 } และนิยามการดาเนินการ  ดงั น้ี 0 1 2 0012 1120 22014. กาหนดให้ A  { a , b } ดงั น้นั เซตกาลงั ของ A หรือ P(A)  { {a} , {b} , {a , b} ,  } ถ้ากาหนดการดาเนินการ 2 อย่าง คือ  และ  จงแสดงใหเ้ ห็นวา่ (P(A) ,  ,  ) เป็นพีชคณิตบูลีน5. ให้ (A ,  ,  ) เป็นพชี คณิตบูลีนแลว้ จงพสิ ูจน์วา่ ทุก a , b , c  A จะไดว้ า่ a  (a  b ) a6. ให้ (A ,  ,  ) เป็นพชี คณิตบูลีนแลว้ จงพสิ ูจน์วา่(a  b)  a  b7. จงใชพ้ ีชคณิตบูลีนชนิด 2 คา่ แสดงวา่ ทฤษฎีต่อไปน้ีเป็ นจริง 1) a (b c)  (a b) c 2) a  (b  c)  (a  b)  c 3) a b  a b  a 4) a b  ab  ( a  b) (a  b)8. จงแทนความสมมูลของพีชคณิตบูลีนต่อไปน้ีดว้ ยการต่อวงจรสวติ ซ์ไฟฟ้า 1) a . 0  0 2) a  a  a 3) a . a  a 4) a ( a  b )  a 5) a  ab  a

บทท่ี 5 พีชคณิตบูลีน 2039. จงเขียนวงจรสวติ ซ์ไฟฟ้าต่อไปน้ีในรูปพชี คณิตบูลีน1) a b a a2) a a b c c b bc3) a a b b b abc c10. จงแทนพชี คณิตบูลีนต่อไปน้ีโดยวงจรสวติ ซ์ไฟฟ้า 1) ab  (b  c)a  a(b  c) 2) ab ( c  a)  [ (ab  c) a  b] 3) a  b  [ c(a  b)a  ( ab  ca ) ]