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

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

 ข้อจำกัด 
 ถึงแม้วิธีการนี้จะได้ผลดีกว่ากว่าแผนผังคาร์โนห์เมื่อใช้ลดนิพจน์ตรรกศาสตร์ที่มีตัวแปรมากกว่าสี่ตัวก็ตาม แต่เวลาที่ใช้ในการทำงานจะเพิ่มมากขึ้นอย่างรวดเร็วตามจำนวนของตัวแปร (เพิ่มขึ้นในอัตราส่วนแบบฟังก์ชันเลขชี้กำลัง) โดยสามารถแสดงในรูปแบบของฟังก์ชันขอบเขตสูงสุดของตัวแปร  ตัว ได้เป็น  ซึ่งหากนิพจน์ตรรกศาสตร์มีจำนวนตัวแปรเท่ากับ 32 ตัว หรือ  อาจจะมีเทอมที่ไม่สามารถจับคู่ได้มากกว่า  เทอม ดังนั้นหากต้องการลดนิพจน์ตรรกศาสตร์ที่มีจำนวนตัวแปรมากๆ ควรใช้วิธีการอื่นแทน เช่น การใช้โปรแกรมเอสเปรสโซ่ เป็นต้น
 ขั้นตอนวิธีนี้ เป็นขั้นตอนวิธีปัญหา เอ็นพี-แบบยาก เพราะมีอัตราการทำงานเติบโตในรูปของฟังก์ชันเอกซ์โพเน็นเชียล

 ปัญหาที่เกี่ยวข้อง 
 วิธีการของแพททริก

 ตัวอย่างขั้นตอนการทำงาน 
ลดรูปนิพจน์ตรรกศาสตร์ต่อไปนี้:

 รวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอม 
 เนื่องจากนิพจน์ตรรกศาสตร์ดังกล่าว มีตัวแปรจำนวน 4 ตัว ได้แก่ A, B, C และ D ดังนั้นจึงสามารถสร้างตารางค่าความจริงได้ทั้งหมด 16 กรณี ดังนี้
  A  B  C  D   fm0  0  0  0  0   xm1  0  0  0  1   0m2  0  0  1  0   0m3  0  0  1  1   0m4  0  1  0  0  1m5  0  1  0  1  1m6  0  1  1  0  1m7  0  1  1  1  xm8  1  0  0  0  1m9  1  0  0  1  1m10  1  0  1  0  1m11  1  0  1  1   0m12  1  1  0  0   0m13  1  1  0  1  1m14  1  1  1  0   0m15  1  1  1  1  x 

ในการรวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอมนั้น จะพิจารณาจากเทอมที่มีค่าของ A,B,C และ D ต่างกันเพียง 1 บิต ตัวอย่างเช่น 0000 กับ 0100 (ต่างกันที่บิตที่สอง) หรือ 0000 กับ 1000 (ต่างกันที่บิตที่หนึ่ง) เป็นต้น ดังนั้นเพื่อให้ง่ายต่อการพิจารณา จะทำการแบ่งกลุ่มที่มีค่าของ A,B,C และ D ต่างกันเพียง 1 บิตโดยแบ่งตามจำนวนของเลข 1 ในค่า A,B,C และ D ดังนี้
 จำนวนเลข 1 ใน A,B,C,D  m  ค่าของ A,B,C,D 0 m0  0000 1 m4  0100 m8  1000 2 m5  0101 m6  0110 m9  1001 m10  1010 3 m7  0111 m13  1101 4 m15  1111

จากตารางด้านบน จะเห็นว่าเราสามารถแบ่งกลุ่มที่มีค่าของ A,B,C,D ต่างกันเพียง 1 บิทได้เป็น 5 กลุ่ม ดังนั้นในการรวมเทอมที่มีรูปแบบคล้ายกัน เราจะพิจารณาแต่ละกลุ่มเทียบกันโดยใช้วิธีการเขียนตาราง ดังนี้
 เขียนค่าของ ABCD ที่ต้องการพิจารณาลงในคอลัมน์เริ่มต้นของตาราง (คอลัมน์ที่ 1)
 เปรียบเทียบค่า ABCD ที่ต่างกันเพียง 1 บิต (ค่าของกลุ่มติดกันที่แบ่งไว้ข้างต้น) เพื่อยุบรวมเป็นตัวเดียว โดยแทนตัวที่ต่างกันด้วย "-" และแทนตัวที่เหมือนกันด้วยตัวเลขนั้นๆ เขียนผลลัพธ์ลงในคอลัมน์ถัดไป (คอลัมน์ที่ 2) ตัวอย่างเช่น เปรียบเทียบ 0000 กับ 0100 แล้วรวมเป็น 0-00, เปรียบเทียบ 0000 กับ 1000 แล้วรวมเป็น -000 เป็นต้น
 เมื่อยุบรวมพจน์เรียบร้อยแล้ว ให้ทำการเขียนเครื่องหมายถูก "/" หากยุบไม่ได้ก็ใส่เครื่องหมายดอกจัน "*" ไว้ด้านหลังพจน์ที่ถูกยุบรวมแล้ว
 ทำการเปรียบเทียบค่า ABCD ไปเรื่อยๆ เพื่อยุบรวมพจน์จนกระทั่งไม่สามารถยุบรวมได้อีก

 คอลัมน์ที่ 1  คอลัมน์ที่ 2  คอลัมน์ที่ 3 0000 / 0-00 * 01-- * - -000 *   0100 /  -1-1 * 1000 /  010- /   -  01-0 /   0101 / 100- *   0110 / 10-0 *   1001 /    1010 /  01-1 /   -  -101 /   0111 /  011- /   1101 / 1-01 *   -    1111 /  -111 /    11-1 /  

จากตารางด้านบน แสดงให้เห็นว่าพจน์ที่ไม่สามารถยุบรวมได้อีก มีทั้งหมด 7 พจน์ ได้แก่ 0-00, -000, 100-, 10-0, 1-01, 01-- และ -1-1

 สร้างตารางเพื่อหานิพจน์ตรรกศาสตร์ในรูปอย่างง่าย 
 การสร้างตาราง 
การสร้างตารางในเบื้องต้น มีขั้นตอนดังนี้
 สำหรับแต่ละแถว คือ พจน์ที่ไม่สามารถยุบรวมได้อีก ที่ได้หามาแล้วในขั้นตอนที่ 1
 สำหรับแต่ละคอลัมน์ คือ พจน์ที่มีค่าฟังก์ชันเป็น 1
 ทำเครื่องหมายกากบาท "X" ในตารางตามช่องที่มีตัวเลขในแถวและคอลัมน์เหมือนกัน

+ ขั้นตอนที่ 1  4  5  6  8  9  10  130,4 (0-00) X        0,8 (-000)    X     8,9 (100-)    X  X    8,10 (10-0)    X   X   9,13 (1-01)     X   X 4,5,6,7 (01--) X  X  X      5,7,13,15 (-1-1)  X      X

 การหารูปอย่างง่ายของนิพจน์ตรรกศาสตร์ 
หลังจากสร้างตารางเสร็จเรียบร้อยแล้ว หลักการในการหารูปอย่างง่ายของนิพจน์ตรรกศาสตร์ คือการเลือกแถวให้น้อยที่สุด โดยเลือกให้ครอบคลุมทุกคอลัมน์
 ในการเลือกแถวเบื้องต้นนั้น จะทำการตรวจสอบคอลัมน์ที่มีเครื่องหมาย "X" เพียงแถวเดียว แล้วทำการเลือกแถวนั้นๆ เนื่องจากเป็นแถวที่จำเป็นต้องเลือก หากไม่เลือกจะทำให้ไม่ครอบคลุมครบทุกคอลัมน์
 ทำเครื่องหมายทั้งในแนวแถวและคอลัมน์ที่เลือก
+ ขั้นตอนที่ 2  4 56 8 910 13 0,4 (0-00) X     0,8 (-000)   X   8,9 (100-)   X X          9,13 (1-01)    X X         5,7,13,15 (-1-1)  X   X

 จากนั้นให้ทำเครื่องหมายให้กับ "X" ที่อยู่ในคอลัมน์เดียวกันทั้งหมด เพื่อแสดงว่าคอลัมน์นั้นๆ ได้ถูกครอบคลุมโดยแถวที่เลือกไปแล้ว
+ ขั้นตอนที่ 3 4568 910 13 0,4 (0-00)X   0,8 (-000)X   8,9 (100-)X X          9,13 (1-01) X X         5,7,13,15 (-1-1)X  X

 เลือกแถวที่ครอบคลุม "X" ในคอลัมน์ที่เหลืออยู่ แล้วทำเครื่องหมายสำหรับแถวนั้น (หากมีหลายแถวจะต้องเลือกแถวที่ครอบคลุมคอลัมน์ได้มากที่สุด)
 ผลที่ได้จะมีจำนวนแถวที่เลือกน้อยที่สุด และครอบคลุมส่วนที่เหลือทั้งหมดได้
+ ขั้นตอนที่ 4 456891013 0,4 (0-00)X 0,8 (-000)X 8,9 (100-)XX                    5,7,13,15 (-1-1)XX

ดังนั้น นิพจน์ตรรกศาสตร์ในรูปอย่างง่าย คือ :

 ดูเพิ่ม 
 นิพจน์ (คณิตศาสตร์)
 ตรรกศาสตร์
 แผนผังคาร์โนห์
 พีชคณิตแบบบูล
 POS และ SOP
 วงจรเชิงผสม
 ตารางค่าความจริง

 อ้างอิง 

 85-89.http://www.freebookzone.com/fetch.php?bkcls=hw_logic&bkidx=7 Contemporary Logic Design

 เชื่อมต่อภายนอก 
 การลดทอนฟังก์ชัน
 การลดรูปสมการบูลลีน
 Quine-McCluskey Algorithm 
 Minimization
 ตัวอย่างขั้นตอนวิธีของควินและแมกคลัสกีย์ 
 รหัสเทียมของขั้นตอนวิธีควินและแมกคลัสกีย์ 
 เกี่ยวกับควิน-แม็กคลัสกีย์
 โปรแกรมลดรูปแบบควิน-แม็กคลัสกีย์แบบออนไลน์ 
 ตัวอย่างโปรแกรมภาษาซี
 ตัวอย่างโปรแกรมออนไลน์ 

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:พีชคณิตแบบบูล