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

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

1. ลดขนาดแผนภูมิ implicant ปฐมภูมิลงโดยกำจัดแถวและหลักที่เกี่ยวข้องกับ implicant ปฐมภูมิที่จำเป็นออก
2. ตั้งชื่อแถวของแผนภูมิ implicant ปฐมภูมิที่ถูกลดออกว่า $P_1$, $P_2$, $P_3$, $P_4$ ตามลำดับ
3. สร้างฟังก์ชันตรรกะ $P$ ซึ่งเป็นจริงเมื่อทุกแถวที่มี minterm ครอบคลุมอยู่ P ดังกล่าวประกอบไปด้วยผลคูณของผลบวก โดยแต่ละพจน์ของผลบวกอยู่ในรูปของ $(P_{i0}+P_{i1}+$$\cdots$$+P_{iN})$ โดย $P_{ij}$ แต่ละตัวแสดงถึงแถวที่ครอบคลุมหลัก $i$
4. ทำการลด $P$ ลงให้เหลือเพียงผลบวกของผลคูณอย่างต่ำ โดยกระจายการคูณ แล้วใช้กฎการลดรูป $X+XY=X$
5. แต่ละพจน์ของผลลัพธ์เป็นตัวแทนของคำตอบ ซึ่งก็คือ เป็นเซตของแถวที่ครอบคลุมทุก minterm ในตาราง ในการกำหนดผลเฉลยน้อยสุด ขั้นตอนแรกคือ ให้หาพจน์เหล่านั้น ซึ่งเก็บค่าจำนวนน้อยสุดของ implicant ปฐมภูมิไว้
6. ขั้นถัดไป นับจำนวนสัญพจน์ที่ของ implicant ปฐมภูมิที่มีในพจน์ที่ได้จากขั้นตอนที่ห้า แล้วหาจำนวนของสัญพจน์ทั้งหมด
7. เลือกพจน์ที่เกิดจากประกอบกันของสัญพจน์ ที่มีจำนวนสัญพจน์น้อยสุด แล้วเขียนผลรวมของ implicant ปฐมภูมิที่สอดคล้อง

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

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

$f(A,B,C)=\sum m(0,1,2,5,6,7)$

ยกตัวอย่างแผนภูมิ 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) แม่แบบ:Webarchive (ภาษาอังกฤษ)
• http://webdocs.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld098.htm วิธีการของเพทริค (สไลด์) (ภาษาอังกฤษ)