fbpx
วิกิพีเดีย

วิธีการของเพทริค

ในพีชคณิตแบบบูล วิธีการของเพทริค (รวมถึงรู้จักกันในชื่อ วิธีขยายและจำกัดเขต) เป็นกลวิธีที่ใช้ในการกำหนดผลเฉลยในรูปผลบวกของผลคูณน้อยสุดทุกตัวจากแผนภูมิ implicant ปฐมภูมิ (prime implicant chart) วิธีการของเพทริคนั้นน่าเบื่อหน่ายเป็นอย่างมากเมื่อใช้กับแผนภูมิขนาดใหญ่ แต่ดำเนินการได้ง่ายดายบนเครื่องคอมพิวเตอร์

  1. ลดขนาดแผนภูมิ implicant ปฐมภูมิลงโดยกำจัดแถวและหลักที่เกี่ยวข้องกับ implicant ปฐมภูมิที่จำเป็นออก
  2. ตั้งชื่อแถวของแผนภูมิ implicant ปฐมภูมิที่ถูกลดออกว่า , , , ตามลำดับ
  3. สร้างฟังก์ชันตรรกะ ซึ่งเป็นจริงเมื่อทุกแถวที่มี minterm ครอบคลุมอยู่ P ดังกล่าวประกอบไปด้วยผลคูณของผลบวก โดยแต่ละพจน์ของผลบวกอยู่ในรูปของ โดย แต่ละตัวแสดงถึงแถวที่ครอบคลุมหลัก
  4. ทำการลด ลงให้เหลือเพียงผลบวกของผลคูณอย่างต่ำ โดยกระจายการคูณ แล้วใช้กฎการลดรูป
  5. แต่ละพจน์ของผลลัพธ์เป็นตัวแทนของคำตอบ ซึ่งก็คือ เป็นเซตของแถวที่ครอบคลุมทุก minterm ในตาราง ในการกำหนดผลเฉลยน้อยสุด ขั้นตอนแรกคือ ให้หาพจน์เหล่านั้น ซึ่งเก็บค่าจำนวนน้อยสุดของ implicant ปฐมภูมิไว้
  6. ขั้นถัดไป นับจำนวนสัญพจน์ที่ของ implicant ปฐมภูมิที่มีในพจน์ที่ได้จากขั้นตอนที่ห้า แล้วหาจำนวนของสัญพจน์ทั้งหมด
  7. เลือกพจน์ที่เกิดจากประกอบกันของสัญพจน์ ที่มีจำนวนสัญพจน์น้อยสุด แล้วเขียนผลรวมของ implicant ปฐมภูมิที่สอดคล้อง


ตัวอย่างวิธีการของเพทริค (คัดลอกจาก http://www.mrc.uidaho.edu/mrc/people/jff/349/lect.10)

เราต้องการลดรูปฟังก์ชันถัดไป:

ยกตัวอย่างแผนภูมิ implicant ปฐมภูมิจาก prime implicant chart ดังนี้:

  | 0 1 2 5 6 7 ---------------|------------ K (0,1) a'b' | X X L (0,2) a'c' | X X M (1,5) b'c | X X N (2,6) bc' | X X P (5,7) ac | X X Q (6,7) ab | X X 

อ้างจากตัว X ในตารางข้างบน เราสามารถสร้างผลคูณของผลบวกของทุกแถว โดยการบวกแต่ละแถวเข้าด้วยกัน และคูณแต่ละหลักเข้าด้วยกัน ได้ผลลัพธ์ออกมาดังนี้:

 (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) 

ใช้กฎการกระจายเพื่อเปลี่ยนนิพจน์ให้อยู่ในรูปของผลบวกของผลคูณ แล้วใช้กฎการสมมูลเพื่อลดรูนิพจน์สุดท้าย เช่น X + XY = X และ XX = X และ X + X = X

 = (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) = (K+LM)(N+LQ)(P+MQ) = (KN+KLQ+LMN+LMQ)(P+MQ) = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ 

จากนั้นใช้กฎการสมมูลอีกครั้งเพื่อลดรูปสมการขึ้นอีก: X + XY = X

 = KNP + KLPQ + LMNP + LMQ + KMNQ 

เลือกผลคูณที่มีจำนวนพจน์น้อยสุด โดยในตัวอย่าง มีผลคูณสองตัวที่มีเพียงสามพจน์

 KNP LMQ 

เลือกพจน์ที่มีจำนวนสัญพจน์น้อยสุด โดยในตัวอย่าง ผลคูณทั้งสองสามารถกระจายออกเป็น 6 สัญพจน์

KNP กระจายออกเป็น a'b'+ bc'+ ac LMQ กระจายออกเป็น a'c'+ b'c + ab 

เพราะฉะนั้นจึงสามารถนำพจน์ไหนไปใช้ก็ได้ โดยทั่วไปแล้ว การนำวิธีการของเพทริคไปใช้จะเสียเวลามากเมื่อกระทำกับแผนภูมิขนาดใหญ่ แต่สามารถนำไปดำเนินการได้ง่ายดายบนเครื่องคอมพิวเตอร์

แหล่งข้อมูลอื่น

  • http://www.simpogical.com/download แบบฝึกหัดเกี่ยวกับควิน-แมคคลัสกี้และวิธีการของเพทริค (pdf) 2011-08-28 ที่ เวย์แบ็กแมชชีน (ภาษาอังกฤษ)
  • http://webdocs.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld098.htm วิธีการของเพทริค (สไลด์) (ภาษาอังกฤษ)

การของเพทร, ในพ, ชคณ, ตแบบบ, รวมถ, งร, กก, นในช, ขยายและจำก, ดเขต, เป, นกลว, ใช, ในการกำหนดผลเฉลยในร, ปผลบวกของผลค, ณน, อยส, ดท, กต, วจากแผนภ, implicant, ปฐมภ, prime, implicant, chart, นน, าเบ, อหน, ายเป, นอย, างมากเม, อใช, บแผนภ, ขนาดใหญ, แต, ดำเน, นการได, าย. inphichkhnitaebbbul withikarkhxngephthrikh rwmthungruckkninchux withikhyayaelacakdekht epnklwithithiichinkarkahndphlechlyinrupphlbwkkhxngphlkhunnxysudthuktwcakaephnphumi implicant pthmphumi prime implicant chart withikarkhxngephthrikhnnnaebuxhnayepnxyangmakemuxichkbaephnphumikhnadihy aetdaeninkaridngaydaybnekhruxngkhxmphiwetxr ldkhnadaephnphumi implicant pthmphumilngodykacdaethwaelahlkthiekiywkhxngkb implicant pthmphumithicaepnxxk tngchuxaethwkhxngaephnphumi implicant pthmphumithithukldxxkwa P 1 displaystyle P 1 P 2 displaystyle P 2 P 3 displaystyle P 3 P 4 displaystyle P 4 tamladb srangfngkchntrrka P displaystyle P sungepncringemuxthukaethwthimi minterm khrxbkhlumxyu P dngklawprakxbipdwyphlkhunkhxngphlbwk odyaetlaphcnkhxngphlbwkxyuinrupkhxng P i 0 P i 1 displaystyle P i0 P i1 displaystyle cdots P i N displaystyle P iN ody P i j displaystyle P ij aetlatwaesdngthungaethwthikhrxbkhlumhlk i displaystyle i thakarld P displaystyle P lngihehluxephiyngphlbwkkhxngphlkhunxyangta odykracaykarkhun aelwichkdkarldrup X X Y X displaystyle X XY X aetlaphcnkhxngphllphthepntwaethnkhxngkhatxb sungkkhux epnestkhxngaethwthikhrxbkhlumthuk minterm intarang inkarkahndphlechlynxysud khntxnaerkkhux ihhaphcnehlann sungekbkhacanwnnxysudkhxng implicant pthmphumiiw khnthdip nbcanwnsyphcnthikhxng implicant pthmphumithimiinphcnthiidcakkhntxnthiha aelwhacanwnkhxngsyphcnthnghmd eluxkphcnthiekidcakprakxbknkhxngsyphcn thimicanwnsyphcnnxysud aelwekhiynphlrwmkhxng implicant pthmphumithisxdkhlxngtwxyangwithikarkhxngephthrikh khdlxkcak http www mrc uidaho edu mrc people jff 349 lect 10 eratxngkarldrupfngkchnthdip f A B C m 0 1 2 5 6 7 displaystyle f A B C sum m 0 1 2 5 6 7 yktwxyangaephnphumi implicant pthmphumicak prime implicant chart dngni 0 1 2 5 6 7 K 0 1 a b X X L 0 2 a c X X M 1 5 b c X X N 2 6 bc X X P 5 7 ac X X Q 6 7 ab X X xangcaktw X intarangkhangbn erasamarthsrangphlkhunkhxngphlbwkkhxngthukaethw odykarbwkaetlaaethwekhadwykn aelakhunaetlahlkekhadwykn idphllphthxxkmadngni K L K M L N M P N Q P Q ichkdkarkracayephuxepliynniphcnihxyuinrupkhxngphlbwkkhxngphlkhun aelwichkdkarsmmulephuxldruniphcnsudthay echn X XY X aela XX X aela X X X K L K M L N M P N Q P Q K LM N LQ P MQ KN KLQ LMN LMQ P MQ KNP KLPQ LMNP LMPQ KMNQ KLMQ LMNQ LMQ caknnichkdkarsmmulxikkhrngephuxldrupsmkarkhunxik X XY X KNP KLPQ LMNP LMQ KMNQ eluxkphlkhunthimicanwnphcnnxysud odyintwxyang miphlkhunsxngtwthimiephiyngsamphcn KNP LMQ eluxkphcnthimicanwnsyphcnnxysud odyintwxyang phlkhunthngsxngsamarthkracayxxkepn 6 syphcn KNP kracayxxkepn a b bc ac LMQ kracayxxkepn a c b c ab ephraachanncungsamarthnaphcnihnipichkid odythwipaelw karnawithikarkhxngephthrikhipichcaesiyewlamakemuxkrathakbaephnphumikhnadihy aetsamarthnaipdaeninkaridngaydaybnekhruxngkhxmphiwetxraehlngkhxmulxun aekikhhttp www simpogical com download aebbfukhdekiywkbkhwin aemkhkhlskiaelawithikarkhxngephthrikh pdf Archived 2011 08 28 thi ewyaebkaemchchin phasaxngkvs http webdocs cs ualberta ca amaral courses 329 webslides Topic5 QuineMcCluskey sld098 htm withikarkhxngephthrikh sild phasaxngkvs ekhathungcak https th wikipedia org w index php title withikarkhxngephthrikh amp oldid 9665807, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม