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 unit 1 กฎของพีชคณิตบูลีนและทฤษฎีของดีมอร์แกน

unit 1 กฎของพีชคณิตบูลีนและทฤษฎีของดีมอร์แกน

Published by ประภาส พุ่มพวง, 2020-08-27 01:10:41

Description: unit 1 กฎของพีชคณิตบูลีนและทฤษฎีของดีมอร์แกน

Search

Read the Text Version

กฎของพีชคณิตบลู ีนและทฤษฎีของดีมอรแ์ กน

กฎของพีชคณิตบลู ีนและทฤษฎีของดีมอรแ์ กน ผคู้ ดิ คน้ พชี คณติ บูลนี คอื นกั คณติ ศาสตร์ชาวองั กฤษช่อื จอร์จ บลู (George Boole) ปี พ.ศ. 2390 ใชส้ าหรบั วเิ คราะหว์ งจรลอจกิ พชี คณิตบูลนี มกี ฎและขอ้ บงั คบั ต่าง ๆ เพ่อื นามาใชใ้ นการหาค่าผลลพั ธ์ของสมการ บูลนี (Boolean Expression) ลอจกิ ฟังก์ชนั (Logic Function) หรอื สมการลอจกิ การลดรูป สมการลอจกิ เพอ่ื นาไปสรา้ งวงจรลอจกิ และสามารถพสิ จู น์ความถกู ตอ้ งดว้ ยตารางความจรงิ ได้ ������ҧ อา่ นว่า นอตเอ หรอื เอบาร์

นิยามศพั ทท์ ่ีเก่ียวข้องกบั พีชคณิตบลู ีน 1. ตวั คงท่ี (Constant) ในพชี คณติ บลู นี คอื ตวั คงทป่ี ระกอบดว้ ยตวั เลข “0” และ “1” 2. ตวั แปร (Variable) คอื ตวั องั ษรหรอื สญั ลกั ษณ์ทใ่ี ชแ้ ทนหรอื กาหนดคา่ คงท่ี โดยอาจอย่ใู นรปู เชน่ A, B, C, X, Y และ Z หรอื อยใู่ นรปู คอมพลเี มนต์ (Complement) เชน่ ������ҧ ���ത��� ������ҧ 3. ตวั กระทา (Operator) มอี ยู่ 3 ตวั ไดแ้ ก่ (1) ตวั กระทาแอนด์ (AND) ใชส้ ญั ลกั ษณ์ (∙ ) อา่ นว่า แอนด์ เชน่ 0 · 0 = 0 , 1· 1 = 1 เป็นตน้ (2) ตวั กระทาออร์ (RO) ใชส้ ญั ลกั ษณ์ (+) อ่านวา่ ออร์ เชน่ 0 + 0 =0 , 1+1 = 1 (3) ตวั กระทานอต (NOT) ใชส้ ญั ลกั ษณ์ ( ഥ ) อ่านวา่ บาร์ เชน่ Aഥ 4. เทอม (Term) หมายถงึ การนาตวั แปรมากระทากนั มี 2 แบบ คอื 1) ตวั แปรมนิ เทอม(Min term) เชน่ ABഥC เป็นตน้ 2) ตวั แปรแมก็ ซเ์ ทอม (Max Term) เชน่ Xഥ + Y + Zത

5. ฟังกช์ นั (Function) อาจเรยี กวา่ ลอจกิ ฟังกช์ นั (Logic Function) เชน่ Y = ABഥ + ABC + AഥBCതD 6. นิพจน์ทางลอจกิ (Expression๗ คอื สมการลอจกิ ทม่ี กี ารนาเทอมของตวั แปรมากระทากนั ได้แก่ 1) สมการผลบวกของผลคณู (มนิ เทอม) เชน่ ���������ത��� + ���������ത��������� + ������������������������ 2) สมการผลคณู ของผลบวก (แมก็ ซเ์ ทอม) เชน่ (������ҧ + ������ + ������)(������ + ������ + ������ҧ) 7. คอมพลเี มนต์ฟังกช์ นั (Complement Function) หมายถงึ การนาตวั กระทานอตมากระทาทงั้ ฟังกช์ นั ทาใหฟ้ ังกช์ นั เดมิ ถูกกลบั เป็นตรงกนั ขา้ ม เชน่ ������������ + ������ คอื ������������ + ������ 8. ดอู ลั ลติ ้ฟี ังกช์ นั (Duality Function) หมายถงึ การเปลย่ี นตวั กระทาของฟังกช์ นั เดมิ จากแอนดเ์ ป็น ออร์ หรอื จากออรเ์ ป็นแอนด์ เชน่ ������ҧ ∙ ������ + ������ คอื ������ҧ + ������ ∙ ������ ตารางความจรงิ (Truth Table) เป็นตารางทแ่ี สดงระดบั ลอจกิ เอาต์พตุ

กฎข้อบงั คบั ของพีชคณิตบลู ีน กลุ่มท่ี 1 กฎของนอต กลมุ่ ท่ี 3 กฎของออร์ 1. 0ത = 1 10. A + 0 = A 2. 1ത = 0 11. A + 1 = 1 3. A = 0 ; (Aഥ = 1) 12. A +A = A 4. A = 1 ; (Aഥ = 0) 13. A + ������ҧ =1 5. Aന = A กลุ่มท่ี 4 กฎของการสลบั ท่ี (Commutative Law) กลุ่มท่ี 2 กฎของแอนด์ 14. A + B = B + A 6. A·0 = 0 15. A·B = B·A 7. A·1 = A กลมุ่ ท่ี 5 กฎของการจดั หมู่ (Associative Law) 8. A·A = A 16. A+ (B+C) = (A+B)+C = A+B+C 9. A·Aഥ = 0 17.A(BC) = (AB)C = ABC

กลมุ่ ท่ี 6 กฎของการกระจาย (Distributive Law) 18. A(B+C) = (AB)+(AC) 19. A+(BC)=(A+B)(A+C) กลุ่มท่ี 7 กฎของการซ้าซอ้ น(Redundance Law) 20. A + AB = A 21. A+AഥB = A+B 22. Aഥ+AB = Aഥ + B 23. A·(A+B) = A

ทฤษฎีของดีมอรแ์ กน (Demorgan’s Theorems) ดมี อรแ์ กนเป็นนกั คณติ ศาสตรท์ เ่ี สนอทฤษฎที ม่ี คี วามสาคญั ต่อพชี คณติ บลู นี เพอ่ื ใชใ้ นการลดรปู ของ สมการลอจกิ ไดด้ งั น่ี 1. AB = Aഥ + Bഥ 2. A + B = Aഥ ∙ Bഥ

ตวั อยา่ งท่ี 1.1 พิสจู น์ 1. ������������ = ���ഥ��� + ���ഥ��� (หน้า 7) A B ���ഥ��� ���ഥ��� ���ഥ��� + ���ഥ��� ������������ 001111 011011 100111 110000

ตวั อยา่ งท่ี 1.1 พิสจู น์ 2. ������ + ������ = ���ഥ��� ∙ ���ഥ��� A B ���ഥ��� ���ഥ��� ������ + ������ ���ഥ��� ∙ ���ഥ��� 001111 011000 100100 110000

ตวั อย่างท่ี 1.2 การประยกุ ตท์ ฤษฎีของดีมอรแ์ กนกบั สมการ ������������������ และ ������ + ������ + ������ ABC = Aഥ + Bഥ + Cത 1. AB = Aഥ + Bഥ A + B + C = Aഥ ∙ Bഥ ∙ Cത 2. A + B = Aഥ ∙ Bഥ

ตวั อยา่ งที่ 1.3 การประยกุ ตท์ ฤษฎีของดีมอรแ์ กนกบั สมการ (������ + ������ + ������)������ กาหนดให้ A+B+C = X และ D=Y ดงั นนั้ 1. AB = Aഥ + Bഥ 2. A + B = Aഥ ∙ Bഥ XY = ഥX + Yഥ A + B + C D = A + B + C + Dഥ ใชท้ ฤษฎดี มี อรแ์ กนกบั เทอม A + B + C + Dഥ A + B + C + Dഥ = AഥBഥCത + Dഥ

ตวั อย่างท่ี 1.4 1. AB = Aഥ + Bഥ 2. A + B = Aഥ ∙ Bഥ

การประยกุ ตใ์ ช้กฎของพีชคณิตบลู ีนและทฤษฎีของดีมอรแ์ กน ลดรปู สมการลอจิก ตวั อยา่ งท่ี 1.5 จงลดรปู สมการ BCത(Cത + CതA) + (Aഥ + Cത)(AഥB + AഥC) = ������������ҧ������ҧ 1 + ������ + ������ҧ������ҧ������ + ������ҧ������ҧ������ + ������ҧ������������ҧ + ������ҧ������������ҧ 9. A·������ҧ=0 8. A·A=A = ������������ҧ + ������ҧ������ + ������ҧ������ + ������ҧ������������ҧ = ������������ҧ + ������ҧ������ + ������ҧ������(1 + ������ҧ) 11. A+1=1 = ������������ҧ + ������ҧ������ + ������ҧ������

11. A+1=1 21. A+������ҧ������=A+B 13. A+������ҧ = 1 ดึงตวั รว่ ม 11. A+1=1

AB = Aഥ + Bഥ 21. A+������ҧ������=A+B 1+���ത��� + ������������������ҧ + ������ҧ 1 13. A+������ҧ = 1 1+���ത��� + ������ҧ ������������ + 1 1+���ത��� + ������ҧ 11. A+1= 1 1+���ത���������ҧ 13. A+������ҧ = 1 AB = Aഥ + Bഥ 1 11. A+1 = 1

แบบฝึ กหดั 1. จงหาคา่ Υ จากสมการ Υ = Α + ������ҧ + B (1) 2. จงหาคา่ Υ จากสมการ Υ = Α ( B +C ) ������ҧ + D ( D ) 3. จงพิสจู นว์ า่ ( Α + B ) ⋅ ( Α + ���ത��� ) = Α (A) 4. จงพิสจู นว์ ่าสมการ (������ + ������) = ΑΒ+( ΑΒ+ ������������ ) (������ + ������)

ตวั แปรแบบมินเทอมและแมก็ ซเ์ ทอม 1) ตวั แปรมนิ เทอม (Minterm) ผลรวมของผลคณู 2) ตวั แปรแมก็ ซเ์ ทอม(Maxterm) ผลคณู ของผลบวก 2 ตัวแปร ตัวแปร มนิ เทอม สัญลักษณ์ แมก็ ซเ์ ทอม สัญลักษณ์ เลขฐานสิบ AB 00 AഥBഥ มนิ เทอม แมก็ ซเ์ ทอม 0 01 AഥB 1 10 ABഥ m0 A+B M0 2 11 AB 3 m1 A + Bഥ M1 m2 Aഥ + B M2 m3 Aഥ + Bഥ M3

3 ตวั แปร

4 ตวั แปร หน้า 12

รปู แบบของสมการลอจิก 1) สมการลอจกิ แบบผลบวกของผลคณู (หน้า 13) ������ ������, ������, ������ = ������������ + ������ҧ������������ + ������ҧ������������ҧ เขยี นวงจรลอจกิ ไดด้ งั น้ี

รปู แบบของสมการลอจิก 1) สมการลอจกิ แบบผลบวกของผลคณู (หน้า 13) ������ ������, ������, ������ = ������������ + ������ҧ������������ + ������ҧ������������ҧ เขยี นวงจรลอจกิ ไดด้ งั น้ี

ตวั อยา่ งท่ี 1.10 จงเปลย่ี นสมการลอจกิ ตอ่ ไปน้ใี หอ้ ยใู่ นรปู แบบของสมการผลบวกของผลคณู 1. AB+B(CD+EF) = AB+B(CD+EF) = AB+BCD+BEF วาดวงจรลอจกิ 2. (A+B)(B+C+D)=AB+AC+AD+BB+BC+BD วาดวงจรลอจกิ 3. (A + B) + C = (A + B)Cത = ACത + BCത วาดวงจรลอจกิ

วาดวงจรลอจกิ 1. AB+B(CD+EF) 2. (A+B)(B+C+D) 3. (A + B) + C

เฉลย 2. (A+B)(B+C+D) 1. AB+B(CD+EF) 3. (A + B) + C

รปู แบบมาตรฐานของสมการผลบวกของผลคณู (Canonical Sum of Product From) ตวั อย่างท่ี 1.11 ������ ������, ������ = σ ������(0,1,2,3) (หน้าท่ี 14) ������ ������, ������ = ������ҧ���ത��� + ������ҧ������ + ���������ത��� + ������������ เลขฐานสบิ ตวั แปร มนิ เทอม สัญลักษณ์ AB มนิ เทอม ตวั อยา่ งท่ี 1.12 ������ ������, ������, ������ = σ ������ 0,2,4,6 0 00 AഥBഥ ตวั อยา่ งท่ี 1.13 ������ ������, ������, ������, ������ = σ ������(0,2,4,6) 1 01 AഥB m0 2 10 ABഥ m1 3 11 AB m2 m3

ตวั อย่างท่ี 1.12 ������ ������, ������, ������ = σ ������ 0,2,4,6

ตวั อยา่ งท่ี 1.13 ������ ������, ������, ������, ������ = σ ������(0,2,4,6)

การเปล่ียนสมการลอจิกให้อย่ใู นรปู แบบมาตรฐานสมการผลบวกของผลคณู ****เทอมไหนไมม่ ตี วั แปรใดใหค้ ณู ดว้ ยผลบวกของตวั แปรกบั คอมพลเี มนต์**** ตวั อยา่ งท่ี 1.14 จงเปลย่ี น ���������ത��� + ������������������ + ���������������������ഥ��� ใหอ้ ยใู่ นรปู แบบมาตรฐานของสมการแบบผลบวกของผลคณู เทอม ������ҧ������ = ������ҧ������(������ + ������ҧ) = ������ҧ������������ + ������ҧ������������ҧ = (������ҧ������������ + ������ҧ������������ҧ)(������ + ���ഥ���) = ������ҧ������������������ + ������ҧ���������������ഥ��� + ������ҧ������������ҧ������ + ������ҧ������������ҧ���ഥ��� เทอม ������ҧ���ത���C = ������ҧ���ത��������� ������ + ���ഥ��� = ������ҧ���ത��������������� + ������ҧ���ത������������ഥ��� ตอบ เพราะฉะนนั้ = ������ҧ������������������ + ������ҧ���������������ഥ��� + ������ҧ������������ҧ������ + ������ҧ������������ҧ���ഥ��� + ������ҧ���ത��������������� + ������ҧ���ത������������ഥ���

สมการลอจิกแบบผลคณู ของผลบวก สมการ (������ + ���ത���)(������ + ������ + ������ҧ)(������ҧ + ���ത��� + ���ഥ���) (หน้า 16)

สมการลอจิกแบบผลคณู ของผลบวก สมการ (������ + ���ത���)(������ + ������ + ������ҧ)(������ҧ + ���ത��� + ���ഥ���) (หน้า 16)

รปู แบบมาตรฐานของสมการผลคณู ของผลบวก (Canonical Product of Sum From) ตวั อย่างท่ี 1.15 ������ ������, ������ = ς ������(0,1,2,3) (หน้า 16) = (������ + ������)(������ҧ + ������)(������ + ���ത���)(������ҧ + ���ത���) ตวั อย่างท่ี 1.16 ������ ������, ������, ������ = ς ������(0,2,4,6) เลขฐานสบิ ตวั แปร แมก็ ซเ์ ทอม สัญลักษณ์ AB แมก็ ซเ์ ทอม 00 ตวั อย่างท่ี 1.17 ������ ������, ������, ������, ������ = ς ������(0,2,4,6) 0 01 A+B M0 1 10 A + Bഥ M1 2 11 Aഥ + B M2 3 Aഥ + Bഥ M3

ตวั อย่างท่ี 1.16 ������ ������, ������, ������ = ς ������(0,2,4,6)

ตวั อยา่ งท่ี 1.17 ������ ������, ������, ������, ������ = ς ������(0,2,4,6)

การเปล่ียนสมการลอจิกให้อย่ใู นรปู แบบมาตรฐานสมการผลคณู ของผลบวก ขนั้ ท่ี 1 นาเทอมผลบวกทต่ี วั แปรขาดหายไปบวกกบั ผลคณู ของตวั แปรและคอมพลเี มนต์ของ ตวั แปรทข่ี าดหายไป ขนั้ ท่ี 2 ใชข้ อ้ บงั คบั กลมุ่ ท่ี 6 กฎการกระจาย (Distributive Law) ขอ้ 19. A+BC = (A+B)(A+C) ขนั้ ท่ี 3 ทาซ้าขนั้ ตอน 1 และ 2 จนกระทงั่ เทอมของผลบวกประกอบดว้ ยทกุ ตวั แปรทกุ เทอม

ตวั อย่างท่ี 1.18 จงเปลย่ี นสมการลอจกิ (������ + ���ത���)(������ + ������ + ������ҧ)(������ҧ + ���ത��� + ���ഥ���) ใหอ้ ย่ใู นรปู แบบมาตรฐานของ สมการแบบผลคณู ของผลบวก (หน้า 18) เทอมแรก ������ + ���ത��� ขาดตวั แปร C และ D A+BC = (A+B)(A+C) = ������ + ���ത��� + ������������ҧ = (������ + ���ത��� + ������)(������ + ���ത��� + ������ҧ) = ������ + ���ത��� + ������ + ���������ഥ��� = (������ + ���ത��� + ������ + ������)(������ + ���ത��� + ������ + ���ഥ���) = ������ + ���ത��� + ������ҧ + ���������ഥ��� = (������ + ���ത��� + ������ҧ + ������)(������ + ���ത��� + ������ҧ + ���ഥ���) เทอมสอง ������ + ������ + ������ҧ ขาดตวั แปร D = ������ + ������ + ������ҧ + ���������ഥ��� = (������ + ������ + ������ҧ + ������)(������ + ������ + ������ҧ + ���ഥ���) เทอมสาม ������ҧ + ���ത��� + ���ഥ��� ขาดตวั แปร C = ������ҧ + ���ത��� + ���ഥ��� + ������������ҧ = (������ҧ + ���ത��� + ������ + ���ഥ���)(������ҧ + ���ത��� + ������ҧ + ���ഥ���) เพราะฉะนนั้ (������ + ���ത��� + ������ + ������)(������ + ���ത��� + ������ + ���ഥ���) ������ + ���ത��� + ������ҧ + ������ ������ + ���ത��� + ������ҧ + ���ഥ��� ������ + ������ + ������ҧ + ������ (������ + ������ + ������ҧ + ���ഥ���) (������ҧ + ���ത��� + ������ + ���ഥ���)(������ҧ + ���ത��� + ������ҧ + ���ഥ���)

การสร้างตารางความจริงจากสมการลอจิกรปู แบบมาตรฐาน 1) การสรา้ งตารางความจรงิ จากสมการรปู แบบผลบวกของผลคณู (หน้า 18) ตวั อย่างท่ี 1.19 จงสรา้ งตารางความจรงิ จากสมการผลบวกของผลคณู ������ҧ���ത���������ҧ + ������ҧ������������ + ���������ത���������ҧ + ���������ത��������� เทอมทเ่ี ป็น 1 คอื ������ҧ���ത���������ҧ = 000 , ������ҧ������������ = 011, ���������ത���������ҧ = 100, ���������ത��������� = 101 เขยี นเป็นตารางไดด้ งั น้ี อินพุต เอาตพ์ ุต AB C Y 00 0 1 00 1 0 01 0 0 01 1 1 10 0 1 10 1 1 11 0 0 11 1 0

การสรา้ งตารางความจริงจากสมการลอจิกรปู แบบมาตรฐาน 1) การสรา้ งตารางความจรงิ จากสมการรปู แบบผลบวกของผลคณู (หน้า 18) ตวั อยา่ งท่ี 1.19 จงสรา้ งตารางความจรงิ จากสมการผลบวกของผลคณู ������ҧ���ത���������ҧ + ������ҧ������������ + ���������ത���������ҧ + ���������ത��������� เทอมทเ่ี ป็น 1 คอื ������ҧ���ത���������ҧ = 000 , ������ҧ������������ = 011, ���������ത���������ҧ = 100, ���������ത��������� = 101 เขยี นเป็นตารางไดด้ งั น้ี อนิ พุต เอาตพ์ ุต AB C Y

การเปลี่ยนสมการรปู แบบผลคณู ของผลบวกเป็นตารางความจริง ตวั อยา่ งท่ี 1.20 จงสรา้ งตารางความจรงิ ของสมการแบบผลคณู ของผลบวก (หน้า 20) (������ + ������ + ������ҧ)(������ + ���ത��� + ������)(������ҧ + ���ത��� + ������)(������ҧ + ���ത��� + ������ҧ) เทอมทม่ี คี ่าเป็น 0 ������ + ������ + ������ҧ = 001 , ������ + ���ത��� + ������ = 010, ������ҧ + ���ത��� + ������ = 110, ������ҧ + ���ത��� + ������ҧ = 111 อินพุต เอาตพ์ ุต AB C Y 00 0 1 00 1 0 01 0 0 01 1 1 10 0 1 10 1 1 11 0 0 11 1 0

การเขียนสมการลอจิกแบบมาตรฐานจากตารางความจริง ตวั อยา่ งที่ 1.21 จงเขียนรูปแบบสมการผลบวกของผลคณู และสมการผลคณู ของผลบวกของตาราง (หนา้ 20) อนิ พุต เอาตพ์ ุต AB C Y คา่ ของเทอมอินพตุ มินเทอม 0 00 0 1 ������ ������, ������, ������ = σ ������(1,2,6,7) 1 ������ = ������ҧ���ത��������� + ������ҧ������������ҧ + ������������������ҧ + ������������������ 00 1 0 0 01 0 0 คา่ ของเทอมอินพตุ แม็กเทอม 1 01 1 1 ������ ������, ������, ������ = ς ������(0,3,4,5) 10 0 ������)(������ҧ + ������ + ������ҧ) ������ = (������ + ������ + ������)(������ + ���ത��� + ������ҧ)(������ҧ + ������ + 10 1 11 0 11 1

ความสมั พนั ธร์ ะหวา่ งวงจรลอจิกกบั สมการลอจิก 1) การเขยี นวงจรลอจกิ จากสมการลอจกิ ตวั อยา่ งท่ี 1.22 การเขยี นวงจรลอจกิ เกตจากสมการแบบผลบวกของผลคณู ������ = ������������ + ������������ ������ (หน้า 22) วาดวงจร

ตวั อย่างท่ี 1.23 การเขยี นวงจรลอจกิ เกตจากสมการแบบผลบวกของผลคณู ������ = ������ + ������ + ������ ( ���������ത��� + ������������ )

การเขียนสมการลอจิกจากวงจรลอจิก ตวั อย่างท่ี 1.24 การเขยี นสมการลอจกิ จากวงจรลอจกิ (หน้า 23) วงจรลอจกิ

ตวั อย่างท่ี 1.25 การเขยี นสมการลอจกิ จากวงจรลอจกิ วงจรลอจกิ

แบบฝึ กหดั หน้า 25-26 ข้อ 5 ข้อ 6 ขอ้ 7 ข้อ 8 ขอ้ 9 ขอ้ 10

แบบฝึ กหดั หน้า 25-26 ขอ้ 5 (ข) ข้อ 6 (ข) ข้อ 7 (ข) ขอ้ 8 (ง) ข้อ 9 (ข) ขอ้ 10 (ค)