ย่อ Boolean Expression ให้สั้นที่สุดด้วย Boolean Expression Simplifier และ Quine–McCluskey

ใครที่เคยเจอ boolean expression ที่พันกันยาวเป็นหางว่าว ไม่ว่าจะเป็น if-condition ในโค้ดที่ต่อกันสามบรรทัด หรือ combinational logic ในวงจร digital ที่ไล่ไม่ทัน คงรู้ดีว่าการย่อมันด้วยมือนั้นเสี่ยงมาก พลาดแค่ตัวเดียว ความหมายของ logic ทั้งฟังก์ชันก็เปลี่ยนไปจากหน้าตาเดิมโดยสิ้นเชิง Boolean Expression Simplifier คือทางออกของปัญหานี้ เป็นเครื่องมือออนไลน์ที่ย่อ expression ให้อยู่ในรูป minimal sum-of-products อย่างถูกต้องแม่นยำภายในไม่กี่วินาที

เบื้องหลังเครื่องมือคือ Quine–McCluskey algorithm ซึ่งเป็นวิธีย่อ boolean expression แบบเป็นระบบ ให้ผลลัพธ์ minimal ที่การันตีได้ ผสานกับการใช้ De Morgan's laws และ boolean identities ตัวหลักๆ ทำให้ expression อย่าง A·B + A·B' + A'·C ถูกย่อเหลือแค่ A + C ได้ทันที แถมยังมี truth table viewer ให้คุณตรวจสอบด้วยตาตัวเองว่าผลลัพธ์ใหม่มี logic เท่าเดิมทุกกรณี ทั้งหมดทำงาน client-side 100% ฟรี ไม่ต้องสมัครสมาชิก

ในบทความนี้เราจะไล่ตั้งแต่เหตุผลที่ควรใช้เครื่องมือ ฟีเจอร์ครบๆ วิธีใช้งานทีละขั้น ไปจนถึงเจาะลึกทฤษฎีเบื้องหลัง ทั้ง sum-of-products, minterms, prime implicants และ De Morgan's laws พร้อม use case จริงทั้งในโลกของวงจร digital การเขียนโค้ด และงาน FPGA เพื่อให้คุณหยิบเครื่องมือนี้ไปใช้ได้อย่างมั่นใจตั้งแต่ครั้งแรกที่ลอง

ทำไมต้องใช้ Boolean Expression Simplifier?

• แม่นยำกว่าการย่อด้วยมือ — Quine–McCluskey เป็น algorithm แบบ deterministic ที่ค้นหาผลลัพธ์ minimal อย่างเป็นระบบ ไม่ใช่การเดาว่า "น่าจะย่อได้อีก" แล้วค้างคาใจไว้ ทำซ้ำกี่ครั้งก็ได้คำตอบเดิมเสมอ
• ลดจำนวน logic gate ในวงจรได้จริง — expression ที่สั้นลงแปลว่าจำนวน gate น้อยลง วงจรเล็กลง กินพลังงานน้อยลง และ propagation delay ต่ำลง ซึ่งสำคัญมากในงาน hardware จริง
• โค้ดอ่านง่ายขึ้นอย่างเห็นได้ชัด — if-condition ที่ยาวจนต้อง scroll กลับมาอ่านซ้ำ เมื่อย่อเหลือบรรทัดเดียว จะลด cognitive load ให้ทั้งตัวคุณเองและคนที่มาอ่านโค้ดถัดไป
• ตรวจสอบความถูกต้องได้ทันที — truth table viewer แสดง output ของ expression เดิมกับตัวที่ย่อแล้วเทียบกันทุกแถว คุณยืนยันด้วยตัวเองได้ว่า logic ไม่เปลี่ยน
• เป็นตัวช่วยเรียนรู้ชั้นดี — นักศึกษาที่ฝึกย่อด้วย Karnaugh map เอง เอาคำตอบมาเทียบกับเครื่องมือ แล้วเข้าใจ identities อย่าง A·B + A·B' = A ได้เร็วขึ้น เพราะเห็นตัวอย่างจริงที่ไล่เหตุผลได้
• ฟรีและเป็นส่วนตัว 100% — ทุกอย่างประมวลผลใน browser ของคุณล้วนๆ ไม่มีการส่ง expression ออกไปไหน ไม่ต้อง install ไม่ต้องสมัครสมาชิก

ฟีเจอร์เด่น

จุดที่ทำให้ใช้สะดวกเป็นพิเศษคือ:

• การรองรับ input สองรูปแบบทำให้ทั้งคนที่ถนัดเขียนแบบคำ (อ่านง่าย คล้ายภาษา SQL) และคนที่ถนัด algebraic notation ใช้งานได้ลื่นไหลเหมือนกัน โดยไม่ต้องแปลงรูปก่อน
• ข้อจำกัด 6 variables ฟังดูน้อย แต่ครอบคลุมงานจริงส่วนใหญ่ เพราะ expression ที่ตัวแปรเกินกว่านี้มักควรแยกเป็น sub-expression ย่อยๆ อยู่ดี (ดูวิธีจัดการใน Best Practices)
• มี XOR / NAND / NOR ให้พิมพ์ตรงๆ ซึ่งมีประโยชน์มากกับวงจรที่สร้างจาก NAND gate ล้วน อย่างที่พบบ่อยในงาน hardware จริง ไม่ต้องไปเขียนย้อนเป็น (A AND B)' เอง

วิธีใช้งาน

1. เปิดหน้า Boolean Expression Simplifier ใน browser ได้เลย ไม่ต้องติดตั้งอะไรเลย
2. พิมพ์ boolean expression ลงในช่อง input เลือกได้ว่าจะเป็นแบบคำ เช่น A AND (B OR C) หรือแบบ algebraic เช่น A·B + A·B' + A'·C
3. กดปุ่ม simplify แล้วรอแป๊บเดียว
4. อ่านผลลัพธ์ minimal SOP ที่ได้ แล้วเปิด truth table viewer ดูว่า output ก่อน–หลังการย่อตรงกันครบทุกแถว
5. กดปุ่ม copy แล้วเอา expression ที่สะอาดแล้วไปวางในโค้ด ในวงจร หรือในเอกสารของคุณได้เลย

เข้าใจการย่อ Boolean Expression

ถ้าอยากใช้เครื่องมือนี้แบบมั่นใจ ไม่ใช่แค่เชื่อเครื่องมือเฉยๆ มาทำความเข้าใจกันว่าเบื้องหลังมีอะไรเกิดขึ้นบ้าง

Sum-of-products คืออะไร

sum-of-products (SOP) คือรูปแบบมาตรฐานของ boolean expression ที่เขียนเป็นการ OR กันของ product terms (แต่ละ term เป็นการ AND ของตัวแปร) เช่น A·B + A'·C คือ OR ของสอง product terms ถ้า product term มีตัวแปรครบทุกตัว ทั้งแบบตรงและแบบ complement เราเรียกมันว่า minterm และชุดของ minterms ทั้งหมดที่ให้ผลลัพธ์เป็น 1 จะนิยามฟังก์ชันนั้นได้เพียงแบบเดียว (เรียกว่า canonical form)

การย่อ SOP คือการหาชุด product terms ที่สั้นที่สุด ซึ่งยังครอบคลุม minterms เดิมได้ครบทุกตัว เท่ากับเขียนฟังก์ชันเดิมใหม่ด้วยตัวอักษรน้อยที่สุดเท่าที่เป็นไปได้

Quine–McCluskey ทำงานยังไง

algorithm นี้แบ่งเป็น 4 ขั้นตอนใหญ่ๆ:

1. หา minterms — แปลง expression เป็น truth table แล้วเก็บรายการแถวที่ output เป็น 1
2. จับคู่รวม term — จัดกลุ่ม minterms ตามจำนวน bit 1 ของแต่ละตัว แล้วจับคู่ minterms ที่ต่างกันเพียง 1 bit เมื่อรวมกัน ตัวแปรที่ต่างกันจะหลุดออกจาก term กลายเป็น don't care (นิยมเขียนด้วย -) เช่น 011 (A'·B·C) กับ 111 (A·B·C) รวมกันได้ -11 ซึ่งก็คือ term B·C
3. หา prime implicants — ทำการจับคู่ซ้ำๆ ไปเรื่อยๆ จนรวมต่อไม่ได้อีก product terms ที่เหลืออยู่คือ prime implicants คือ terms ที่ "ใหญ่ที่สุด" เท่าที่จะเป็นไปได้
4. เลือก minimal cover — สร้างตาราง prime implicant chart เพื่อดูว่าแต่ละ minterm ถูกคลุมโดย terms ตัวไหนบ้าง แล้วเลือกชุด terms ที่น้อยที่สุดที่ยังคลุม minterms ครบทุกตัว (term ที่เป็นทางเลือกเดียวของ minterm ใดๆ เรียกว่า essential prime implicant ต้องเลือกเสมอ)

จุดเด่นของวิธีนี้คือเป็น tabular method ที่ deterministic ทั้งกระบวนการ ทำกี่รอบก็ได้ผลเดิม และรับประกันว่าผลลัพธ์ที่คืนมาคือ minimal จริงๆ ไม่ใช่แค่ "สั้นพอใช้"

เทียบกับ Karnaugh map

Karnaugh map (K-map) คือเครื่องมือย่อ expression แบบกราฟิกที่เรียนกันในวิชา digital logic ใช้วิธีวาดตาราง 2 มิติแล้วลากกลุ่มเลข 1 ให้เป็นสี่เหลี่ยมใหญ่ที่สุด ซึ่งเจ๋งมากเมื่อมีตัวแปร 3–4 ตัว แต่พอเกิน 4–5 ตัวขึ้นไป ตารางจะโตแบบก้าวคูณ (6 variables = 64 ช่อง) จนมองเครียง grouping ไม่ออกด้วยตา

Quine–McCluskey ทำงานตรรกะเดียวกันแต่เป็นแบบตารางล้วน จึงเป็น alternative ที่ scale กว่า — ที่ 6 variables ยังทำงานได้สบายๆ และเพราะเป็น algorithm ที่ชัดเจนเป็นขั้นเป็นตอน จึง implement เป็นซอฟต์แวร์อัตโนมัติได้ง่าย ซึ่งก็คือเหตุผลที่เครื่องมือนี้เลือกใช้มัน

Identities และ De Morgan's laws ที่ต้องรู้

ระหว่างที่ algorithm ทำงาน มันกำลังใช้ boolean identities พื้นฐานเหล่านี้อยู่ตลอดเวลา:

• De Morgan's laws — (A·B)' = A' + B' และ (A + B)' = A'·B' กฎคู่นี้คือหัวใจของการแปลงไปมาระหว่าง AND/OR กับ NOT
• A·B + A·B' = A — สอง terms ที่ต่างกันแค่ตัวแปรเดียว (ตัวตรงกับตัว complement) รวมกันแล้วตัวแปรนั้นหายไป นี่คือหัวใจของการจับคู่รวม term ใน Quine–McCluskey
• A + A'·B = A + B — term ที่ถูกคูณด้วย complement ของ term อื่น สามารถตัดตัวคู่นั้นทิ้งได้
• A + A·B = A (absorption) — term ที่ถูก term อื่นกลืนหายไปทั้งหมด

ยกตัวอย่างจริง: A·B + A·B' + A'·C — สอง term แรกรวมกันด้วยกฎ A·B + A·B' = A ได้เป็น A + A'·C แล้วใช้กฎ A + A'·B = A + B ก็เหลือเพียง A + C ซึ่งก็คือผลลัพธ์ที่เครื่องมือคืนกลับมาให้คุณ

use case จริง

ออกแบบวงจร digital ลดจำนวน logic gate

สมมติว่าจาก requirement ของวงจร คุณเขียน expression ออกมาได้เป็น (A AND B) OR (A AND NOT B) OR (NOT A AND C) ถ้าสร้างตรงๆ ตามนี้ต้องใช้ AND gate 3 ตัว NOT 2 ตัว และ OR 1 ตัว ลองยัดเข้าเครื่องมือ จะได้คำตอบว่าทั้งก้อนย่อเหลือ A + C — เหลือแค่ OR gate ตัวเดียว วงจรเล็กลง ถูกลง กินไฟน้อยลง และเร็วขึ้น โดย logic เหมือนเดิมทุกกรณี แถม truth table viewer ยังเป็นหลักฐานยืนยันได้ว่า output ตรงกันครบทุกแถว

สำหรับงานออกแบบวงจร การได้ expression ที่ minimal ไม่ใช่แค่เรื่องความสวยงาม แต่แปลเป็นจำนวน transistor พลังงานที่ใช้ และเวลาที่สัญญาณใช้ propagate ผ่านวงจรได้โดยตรง

ล้าง if-condition ในโค้ดที่ซับซ้อน

เจอโค้ดแบบนี้บ่อยมากเวลา maintain โปรเจกเก่า:

if (isAdmin || (!isAdmin && hasPermission)) {
  openDashboard();
}

ในเชิง boolean นี่คือ A + A'·C ซึ่งย่อได้เป็น A + C ตามกฎที่เพิ่งดูไป ดังนั้นเขียนใหม่ได้เป็น:

if (isAdmin || hasPermission) {
  openDashboard();
}

หรือแบบคลาสสิกกว่านั้น:

// ก่อน: A ถูกเช็คไปมาโดยไม่มีผลกับผลลัพธ์
if ((isActive && hasItems) || (!isActive && hasItems)) {
  showCheckout();
}

// หลัง: A·B + A'·B = B
if (hasItems) {
  showCheckout();
}

วิธีใช้กับโค้ดจริงคือ map แต่ละ condition เป็น variable A, B, C พิมพ์ลงเครื่องมือ ย่อเสร็จค่อยแทนชื่อจริงกลับเข้าไป ข้อควรระวังมีอยู่อย่างเดียว: ถ้าใน condition มี function call ที่มี side effect การย่ออาจเปลี่ยนจำนวนครั้งที่มันถูกเรียก (รายละเอียดอยู่ใน Best Practices)

นักศึกษา digital logic เช็คการบ้าน

การบ้านวิชา digital logic มักให้ย่อ expression ด้วย Karnaugh map แล้วเขียนคำตอบเป็น minimal SOP วิธีใช้เครื่องมือนี้ให้เป็นตัวช่วยเรียนคือ ย่อมาเองก่อน แล้วเอาคำตอบไปเทียบกับ Quine–McCluskey ถ้าตรงกันก็สบายใจส่งได้เลย ถ้าไม่ตรง truth table viewer จะบอกว่าเพี้ยนตรง input ชุดไหน แล้วค่อยกลับไปดู grouping ใน K-map ของตัวเองว่าพลาดกลุ่มไหน นี่ได้ผลกว่าการแค่ดูเฉลย เพราะได้เห็นทั้งคำตอบและเหตุผล

ส่วนโจทย์จากหนังสือเรียนก็พิมพ์ตรงๆ ได้เลย เช่น F = A·B + A·B' + A'·C ใส่แบบ algebraic ได้ทันที หรือจะพิมพ์แบบคำอย่าง A AND B OR A AND NOT B... ก็ได้เหมือนกัน แล้วแต่ถนัด

FPGA prototyping ด้วย Verilog และ VHDL

ตอน prototype วงจรบน FPGA ทุก expression ที่เขียนจะถูก synthesis ลงเป็น LUT และ gates จริงบน chip expression ที่ย่อแล้วจึงแปลว่าใช้ resource น้อยลงและ timing ปิดง่ายขึ้น:

// ก่อน
assign y = (a & b) | (a & ~b) | (~a & c);

// ย่อด้วยเครื่องมือแล้วเหลือแค่ a | c
assign y = a | c;

ฝั่ง VHDL ก็เช่นเดียวกัน ทั้งหมดที่ต้องเขียนคือ y <= a or c; นอกจากจะประหยัด LUT แล้ว code ที่สั้นยังหมายความว่าคนที่มาอ่าน waveform และ testbench ของคุณภายหลังเข้าใจ behavior ของวงจรได้เร็วกว่ามาก

Best Practices

• ทำ mapping ตัวแปรไว้ก่อนเสมอ — ถ้า map จาก condition ในโค้ดมาเป็น A, B, C ให้จดไว้ชัดๆ ว่า A = user.isActive เป็นต้น กันพลาดตอนแทนชื่อกลับเข้าโค้ดจริง
• เช็ค truth table ทุกครั้งก่อนใช้ผลจริง — minimal ที่ถูกต้องต้องให้ output ตรงกับ expression เดิมครบทุกแถว กวาดตาดูแถวที่ output เป็น 1 เป็นพิเศษ เพราะเป็นจุดที่ term หลุดบ่อยที่สุด
• เกิน 6 variables ให้แยกย่อเป็นส่วน — ถ้า expression ใหญ่เกิน แตกเป็น sub-expression ย่อทีละชิ้นแล้วค่อยประกอบกลับ จะอ่านง่ายและ trace ปัญหาได้กว่ายัดทั้งก้อนเข้าไป
• เก็บ expression เดิมไว้ใน comment — วาง expression ก่อนย่อไว้ข้างโค้ดใหม่ เพื่อให้คนอ่านในอนาคต (รวมถึงตัวคุณเอง) trace ที่มาของ logic ได้โดยไม่ต้องเดา
• ระวัง side effect ใน condition ของโค้ดจริง — บาง identity ทำให้ term ที่มี function call หายไปทั้งอัน เช่น A && f() || !A ย่อได้เป็น true เลย แต่การเรียก f() ก็หายไปด้วย ถ้า call นั้นมี side effect ที่ตั้งใจไว้ พฤติกรรมโปรแกรมจะเปลี่ยนโดยที่ logic ยัง "ถูก" อยู่เหมือนเดิม
• ใช้คู่กับ truth table generator — สร้าง truth table จาก expression เดิมแยกไว้ต่างหาก แล้วเทียบกับตารางของผลที่ย่อแล้ว เป็นวิธี double-check ที่เห็นผลเร็วที่สุด

เริ่มย่อ expression แรกของคุณเลยตอนนี้

logic ที่สะอาดคุ้มค่ากว่าที่คิด — วงจรที่เล็กลง โค้ดที่อ่านปุ๊บเข้าใจปั๊บ และ bug ที่ไม่มีที่ซ่อน ทั้งหมดนี้เริ่มได้ในไม่กี่วินาทีจากตอนนี้ เปิด Boolean Expression Simplifier วาง expression ที่ยาวที่สุดที่คุณเจอวันนี้ลงไป แล้วดูมันหดเหลือบรรทัดเดียวต่อหน้าคุณ ไม่ต้องสมัครสมาชิก ไม่ต้องติดตั้งอะไร แค่พิมพ์ กด simplify แล้ว copy ไปใช้

เครื่องมือที่เกี่ยวข้อง:

• Truth Table Generator — สร้าง truth table จาก boolean expression เพื่อเทียบ output ก่อน–หลังการย่อให้เห็นกับตา
• Bitwise Calculator — คำนวณ AND, OR, XOR และ shift ระดับ bit ของตัวเลขจริง เหมาะกับงาน bitmask และ bit manipulation
• ASCII Binary Converter — แปลงข้อความ ASCII เป็น binary และย้อนกลับ สำหรับงาน encoding และ debug ข้อมูลระดับ byte

ขอให้สนุกกับการย่อ logic!