เทคนิค SAR

จากวิกิพีเดีย สารานุกรมเสรี

เทคนิค SAR (Systematic Algebraic Reduction (SAR) Technique) คือ วิธีการในการลดรูปพีชคณิตแบบบูล (Boolean minimization) ที่มีความซับซ้อนยุ่งยากให้มีรูปแบบที่ง่ายขึ้น เพื่อช่วยในการลดความยุ่งยากของสมการลอจิก โดยทำสมการให้อยู่ในรูปของ Sum-of-product (SOP) แล้วนำกฎหรือทฤษฎีการลดรูปพีชคณิตมาใช้ในการลดรูปสมการ

ทฤษฎีในการลดรูปสมการ[แก้]

  • Adjacency theorem

คือ การรวมเทอมต่างๆ ในสมการให้เล็กลงหรือมีขนาดของเทอมน้อยลง ตัวอย่างเช่น

  • Idempotency theorem

คือ ทฤษฎีการรวมเทอมที่เหมือนกันให้เหลือเพียงเทอมเดียว ได้แก่

  • Consensus theorem

คือ ทฤษฎีการรวมเทอม โดยจะทำการเพิ่มตัวที่ขาดในแต่ละเทอมให้ครบก่อน แล้วจึงทำการลดรูปสมการ ตัวอย่างเช่น

การลดรูปสมการพีชคณิตด้วยเทคนิค SAR นั้นต้องทำสมการให้อยู่ในรูป SOP ก่อน แล้วจึงเปรียบเทียบเทอมทุกเทอม โดยใช้กฎทางตรรกศาสตร์ในการยุบเทอมให้มีขนาดลดลง

ขั้นตอนของลดรูปสมการ[แก้]

  1. ทำสมการให้อยู่ในรูป SOP
  2. เปรียบเทียบเทอมแรกกับทุกเทอมถัดไปจนถึงเทอมสุดท้าย (โดยเปรียบเทียบแบบนี้กับเทอมที่ 2, 3, ..., n-1)
  3. นำผลที่ได้จากการเปรียบเทียบมาเชื่อมด้วยเครื่องหมาย + (OR-gate)
SAR Technique1.jpg

นอกจากใช้เทคนิค SAR ในการลดรูปสมการแล้วยังสามารถใช้วิธีการอื่นๆ ได้อีก เช่น แผนผัง Karnaugh map และ Quine–McCluskey algorithm เป็นต้น

ดูเพิ่ม[แก้]