วิธีการของเพทริค
ในพีชคณิตแบบบูล วิธีการของเพทริค (รวมถึงรู้จักกันในชื่อ วิธีขยายและจำกัดเขต) เป็นกลวิธีที่ใช้ในการกำหนดผลเฉลยในรูปผลบวกของผลคูณน้อยสุดทุกตัวจากแผนภูมิ implicant ปฐมภูมิ (prime implicant chart) วิธีการของเพทริคนั้นน่าเบื่อหน่ายเป็นอย่างมากเมื่อใช้กับแผนภูมิขนาดใหญ่ แต่ดำเนินการได้ง่ายดายบนเครื่องคอมพิวเตอร์
- ลดขนาดแผนภูมิ implicant ปฐมภูมิลงโดยกำจัดแถวและหลักที่เกี่ยวข้องกับ implicant ปฐมภูมิที่จำเป็นออก
- ตั้งชื่อแถวของแผนภูมิ implicant ปฐมภูมิที่ถูกลดออกว่า , , , ตามลำดับ
- สร้างฟังก์ชันตรรกะ ซึ่งเป็นจริงเมื่อทุกแถวที่มี minterm ครอบคลุมอยู่ P ดังกล่าวประกอบไปด้วยผลคูณของผลบวก โดยแต่ละพจน์ของผลบวกอยู่ในรูปของ โดย แต่ละตัวแสดงถึงแถวที่ครอบคลุมหลัก
- ทำการลด ลงให้เหลือเพียงผลบวกของผลคูณอย่างต่ำ โดยกระจายการคูณ แล้วใช้กฎการลดรูป
- แต่ละพจน์ของผลลัพธ์เป็นตัวแทนของคำตอบ ซึ่งก็คือ เป็นเซตของแถวที่ครอบคลุมทุก minterm ในตาราง ในการกำหนดผลเฉลยน้อยสุด ขั้นตอนแรกคือ ให้หาพจน์เหล่านั้น ซึ่งเก็บค่าจำนวนน้อยสุดของ implicant ปฐมภูมิไว้
- ขั้นถัดไป นับจำนวนสัญพจน์ที่ของ implicant ปฐมภูมิที่มีในพจน์ที่ได้จากขั้นตอนที่ห้า แล้วหาจำนวนของสัญพจน์ทั้งหมด
- เลือกพจน์ที่เกิดจากประกอบกันของสัญพจน์ ที่มีจำนวนสัญพจน์น้อยสุด แล้วเขียนผลรวมของ implicant ปฐมภูมิที่สอดคล้อง
ตัวอย่างวิธีการของเพทริค (คัดลอกจาก http://www.mrc.uidaho.edu/mrc/people/jff/349/lect.10 เก็บถาวร 2017-04-12 ที่ เวย์แบ็กแมชชีน)
เราต้องการลดรูปฟังก์ชันถัดไป:
ยกตัวอย่างแผนภูมิ 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
เพราะฉะนั้นจึงสามารถนำพจน์ไหนไปใช้ก็ได้ โดยทั่วไปแล้ว การนำวิธีการของเพทริคไปใช้จะเสียเวลามากเมื่อกระทำกับแผนภูมิขนาดใหญ่ แต่สามารถนำไปดำเนินการได้ง่ายดายบนเครื่องคอมพิวเตอร์