ขั้นตอนวิธีของควิน-แม็กคลัสกีย์

ขั้นตอนวิธีของควิน-แม็กคลัสกีย์  เป็นหนึ่งในขั้นตอนวิธีที่ใช้สำหรับการลดรูปนิพจน์ตรรกศาสตร์ให้อยู่ในรูปอย่างง่ายที่มีประสิทธิภาพสูง พัฒนาโดย ดับเบิลยู.วี. ควิน (W.V.Quine) และเอ็ดเวิด เจ. แมกคลัสกีย์ (Edward J. McCluskey)
ขั้นตอนวิธีของควิน-แม็กคลัสกีย์เป็นขั้นตอนวิธีที่ช่วยในการลดรูปนิพจน์ตรรกะได้เมื่อข้อมูลขาเข้าที่มีปริมาณตัวแปรจำนวนมาก แต่ในการทำงานยังมีข้อจำกัดในเรื่องของเวลาอยู่ จึงควรดูขนาดของข้อมูลขาเข้า ว่ามีขนาดเท่าไหร่ และสมควรที่จะใช้วิธีการนี้หรือไม่ หากไม่สมควรควรจะเลือกใช้วิธีการอื่นที่สามารถลดนิพจน์ตรรกะได้ เช่น วิธีการเอกเพรซโซ่ ซึ่งเป็นวิธีการที่จะใช้ผ่านโปรแกรม
วิธีการทำงาน.
วิธีการนี้มีขั้นตอนการทำงานเหมือนกับการทำแผนผังคาร์โนห์ (Karnaugh map หรือ K-map) แต่มีความยืดหยุ่นมากกว่า ในด้านการนำไปประยุกต์เพื่อสร้างโปรแกรมคอมพิวเตอร์อย่างมีประสิทธิภาพ และด้านการใช้งานกับนิพจน์ตรรกศาสตร์ที่มีตัวแปรเป็นจำนวนมาก 
ขั้นตอนการทำงาน แบ่งออกเป็นสองขั้นตอน ดังนี้:
 ตัวอย่างรหัสเทียมสำหรับการทำงานของขั้นตอนวิธีควิน-แมกคลัสกีย์
รหัสเทียม.
ตัวอย่างรหัสเทียม.
Function QM1 (levels) returns primes
put { } (empty set) into primes
for each level level do
 irredundant level (remove duplicates from level)
 put { } (empty set) into nonprimes
 for every term term in level from 1 to the size of level –1 do
 for every term compterm in level from term + 1 to the size of level do
 put –1 into differentLiteral as a flag
 for every literal literal from 1 to NUMINPUTS do
 if literal literal of term ? literal literal of compterm then
 if differentLiteral = –1 then
 (there was no previous difference)
 put literal into differentLiteral
 else (there was a previous difference)
 put –1 into differentLiteral as a flag
 break (get out of this comparison loop)
 end if
 end if
 end for of literal
 if differentLiteral ? –1 then (there was exactly one difference)
 add term to nonprimes
 add compterm to nonprimes
 add term with 2 in literal differentLiteral to level level + 1
 end for of compterm
 end for of term
 if the size of nonprimes > 0 then
 add all terms not in nonprimes to primes
 else
 break (get out of loop for levels)
 end if
end for of level
return primes
 ถึงแม้วิธีการนี้จะได้ผลดีกว่ากว่าแผนผังคาร์โนห์เมื่อใช้ลดนิพจน์ตรรกศาสตร์ที่มีตัวแปรมากกว่าสี่ตัวก็ตาม แต่เวลาที่ใช้ในการทำงานจะเพิ่มมากขึ้นอย่างรวดเร็วตามจำนวนของตัวแปร (เพิ่มขึ้นในอัตราส่วนแบบฟังก์ชันเลขชี้กำลัง) โดยสามารถแสดงในรูปแบบของฟังก์ชันขอบเขตสูงสุดของตัวแปร <math>n</math> ตัว ได้เป็น <math>\frac{3^{n}}{n}</math> ซึ่งหากนิพจน์ตรรกศาสตร์มีจำนวนตัวแปรเท่ากับ 32 ตัว หรือ <math>n=32</math> อาจจะมีเทอมที่ไม่สามารถจับคู่ได้มากกว่า <math>6.5\times1015</math> เทอม ดังนั้นหากต้องการลดนิพจน์ตรรกศาสตร์ที่มีจำนวนตัวแปรมากๆ ควรใช้วิธีการอื่นแทน เช่น การใช้โปรแกรมเอสเปรสโซ่ เป็นต้น
 ขั้นตอนวิธีนี้ เป็นขั้นตอนวิธีปัญหา เอ็นพี-แบบยาก เพราะมีอัตราการทำงานเติบโตในรูปของฟังก์ชันเอกซ์โพเน็นเชียล
ตัวอย่างขั้นตอนการทำงาน.
ลดรูปนิพจน์ตรรกศาสตร์ต่อไปนี้:
 <math>f (A,B,C,D) =\sum m (4,5,6,8,9,10,13) + d (0,7,15) \,</math>
 เนื่องจากนิพจน์ตรรกศาสตร์ดังกล่าว มีตัวแปรจำนวน 4 ตัว ได้แก่ A, B, C และ D ดังนั้นจึงสามารถสร้างตารางค่าความจริงได้ทั้งหมด 16 กรณี ดังนี้
รวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอม.
ในการรวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอมนั้น จะพิจารณาจากเทอมที่มีค่าของ A,B,C และ D ต่างกันเพียง 1 บิต ตัวอย่างเช่น 0000 กับ 0100 (ต่างกันที่บิตที่สอง) หรือ 0000 กับ 1000 (ต่างกันที่บิตที่หนึ่ง) เป็นต้น ดังนั้นเพื่อให้ง่ายต่อการพิจารณา จะทำการแบ่งกลุ่มที่มีค่าของ A,B,C และ D ต่างกันเพียง 1 บิตโดยแบ่งตามจำนวนของเลข 1 ในค่า A,B,C และ D ดังนี้
จากตารางด้านบน จะเห็นว่าเราสามารถแบ่งกลุ่มที่มีค่าของ A,B,C,D ต่างกันเพียง 1 บิทได้เป็น 5 กลุ่ม ดังนั้นในการรวมเทอมที่มีรูปแบบคล้ายกัน เราจะพิจารณาแต่ละกลุ่มเทียบกันโดยใช้วิธีการเขียนตาราง ดังนี้
จากตารางด้านบน แสดงให้เห็นว่าพจน์ที่ไม่สามารถยุบรวมได้อีก มีทั้งหมด 7 พจน์ ได้แก่ 0-00, -000, 100-, 10-0, 1-01, 01-- และ -1-1
สร้างตารางเพื่อหานิพจน์ตรรกศาสตร์ในรูปอย่างง่าย.
การสร้างตาราง.
การสร้างตารางในเบื้องต้น มีขั้นตอนดังนี้
การหารูปอย่างง่ายของนิพจน์ตรรกศาสตร์.
หลังจากสร้างตารางเสร็จเรียบร้อยแล้ว หลักการในการหารูปอย่างง่ายของนิพจน์ตรรกศาสตร์ คือการเลือกแถวให้น้อยที่สุด โดยเลือกให้ครอบคลุมทุกคอลัมน์
ดังนั้น นิพจน์ตรรกศาสตร์ในรูปอย่างง่าย คือ :<math> f_{A,B,C,D} = AB'D' + AC'D + A'B </math>