ผู้ใช้:ZeroMoke

จากวิกิพีเดีย สารานุกรมเสรี

ในพีชคณิตแบบบูล วิธีการของเพทริค (รวมถึงรู้จักกันในชื่อ วิธีขยายและจำกัดเขต) เป็นกลวิธีที่ใช้ในการกำหนดผลเฉลยในรูปผลบวกของผลคูณน้อยสุดทุกตัวจากแผนภูมิ 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

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

External links[แก้]