อ่าน 3 นาที
รูปแบบปกติของการปฏิเสธ
ในตรรกศาสตร์ทางคณิตศาสตร์สูตรจะอยู่ในรูปแบบปกติของการปฏิเสธ ( NNF ) ก็ต่อเมื่อ ตัวดำเนิน การปฏิเสธ ( , ไม่ ) ใช้กับตัวแปรเท่านั้น และตัวดำเนินการบูลีน อื่นๆ ที่อนุญาต...
รูปแบบปกติของการปฏิเสธ
ในตรรกศาสตร์ทางคณิตศาสตร์สูตรจะอยู่ในรูปแบบปกติของการปฏิเสธ ( NNF ) ก็ต่อเมื่อ ตัวดำเนิน การปฏิเสธ ( , ไม่ ) ใช้กับตัวแปรเท่านั้น และตัวดำเนินการบูลีน อื่นๆ ที่อนุญาต มีเพียงการเชื่อม ( , และ ) และการแยก ( , หรือ ) เท่านั้น
รูปแบบปกติของการปฏิเสธไม่ใช่รูปแบบมาตรฐานตัวอย่างเช่นและนั้นเทียบเท่ากัน และ และ ต่างก็อยู่ในรูปแบบปกติของการปฏิเสธ
คำนิยาม
ต่อไปนี้เป็นไวยากรณ์ที่ไม่ขึ้นกับบริบทสำหรับNNF :
เอ็นเอ็นเอฟ อย่างแท้จริง ( NNF NNF ) ( NNF NNF ) อย่างแท้จริง ตัวแปร ตัวแปร
โดยที่Variableคือตัวแปรใดๆ ก็ได้
ตัวอย่างและตัวอย่างค้าน
∨ / \ ∧ D / \ ∧ ¬ / \ | เอ ∨ ซี / \ ¬ C | บี
สูตรต่อไปนี้ทั้งหมดอยู่ในรูปแบบปกติของการปฏิเสธ:
ตัวอย่างแรกอยู่ในรูปประโยคปกติแบบเชื่อมโยง (conjunctive normal form ) ตัวอย่างสองตัวอย่างถัดมาอยู่ในทั้งรูปประโยคปกติแบบเชื่อมโยงและแบบแยก (disjunctive normal form)แต่ตัวอย่างสุดท้ายไม่อยู่ในรูปประโยคปกติแบบใดเลย
สูตรต่อไปนี้ไม่ได้อยู่ในรูปแบบปกติของการปฏิเสธ:
อย่างไรก็ตาม สูตรเหล่านี้เทียบเท่ากับสูตรต่อไปนี้ในรูปแบบปกติของการปฏิเสธ:
การแปลงเป็น NNF
ในตรรกศาสตร์คลาสสิกและตรรกศาสตร์โมดอล จำนวนมาก ทุกสูตรสามารถนำมาอยู่ในรูปแบบนี้ได้โดยการแทนที่การบ่งชี้ ( ) และความเท่าเทียมกัน ( ) ด้วยคำจำกัดความของพวกมัน โดยใช้กฎของเดอ มอร์แกน เพื่อผลักดันการปฏิเสธเข้าไปด้านใน และกำจัดการปฏิเสธซ้ำซ้อน กระบวนการนี้สามารถแสดงได้โดยใช้ กฎการเขียนใหม่ดังต่อไปนี้: [ 1 ]
การแปลงสูตรให้อยู่ในรูปแบบปกติแบบปฏิเสธจะทำให้ขนาดของสูตรเพิ่มขึ้นได้เพียงเชิงเส้นเท่านั้น กล่าวคือ จำนวนการปรากฏของสูตรอะตอมิกยังคงเท่าเดิม จำนวนการปรากฏทั้งหมดของและยังคงไม่เปลี่ยนแปลง และจำนวนการปรากฏของในรูปแบบปกติจะถูกจำกัดด้วยความยาวของสูตรเดิม
สูตรในรูปแบบปกติของการปฏิเสธ (negation normal form) สามารถแปลงให้อยู่ในรูปแบบปกติของการเชื่อมโยง (conjunctive normal form)หรือรูปแบบปกติของการแยก (disjunctive normal form) ที่แข็งแกร่งกว่าได้ โดยการใช้คุณสมบัติการกระจาย (distributivity ) การใช้คุณสมบัติการกระจายซ้ำๆ อาจทำให้ขนาดของสูตรเพิ่มขึ้นแบบทวีคูณ ในตรรกศาสตร์เชิงประพจน์ แบบคลาสสิก การแปลงเป็นรูปแบบปกติของการปฏิเสธไม่มีผลกระทบต่อคุณสมบัติการคำนวณ: ปัญหาความสามารถในการทำให้เป็นจริง (satisfiability problem)ยังคงเป็นNP-completeและปัญหาความถูกต้อง (validity problem) ยังคงเป็นco-NP-completeสำหรับสูตรในรูปแบบปกติของการเชื่อมโยง ปัญหาความถูกต้องสามารถแก้ไขได้ในเวลาพหุนาม และสำหรับสูตรในรูปแบบปกติของการแยก ปัญหาความสามารถในการทำให้เป็นจริงสามารถแก้ไขได้ในเวลาพหุนาม
ดูเพิ่มเติม
หมายเหตุ
- ↑โรบินสันและโวรอนคอฟ 2544 , หน้า 1. 204.
ลิงก์ภายนอก
- แอปเพล็ต Java สำหรับแปลงสูตรตรรกะเป็นรูปแบบปกติของการปฏิเสธ (Negation Normal Form) พร้อมแสดงกฎที่ใช้
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ รูปแบบปกติของการปฏิเสธ
ในตรรกศาสตร์ทางคณิตศาสตร์สูตรจะอยู่ในรูปแบบปกติของการปฏิเสธ ( NNF ) ก็ต่อเมื่อ ตัวดำเนิน การปฏิเสธ ( , ไม่ ) ใช้กับตัวแปรเท่านั้น และตัวดำเนินการบูลีน อื่นๆ ที่อนุญาต...
คำนิยาม
ต่อไปนี้เป็น ไวยากรณ์ที่ไม่ขึ้นกับบริบท สำหรับ NNF :
ตัวอย่างและตัวอย่างค้าน
สูตรต่อไปนี้ทั้งหมดอยู่ในรูปแบบปกติของการปฏิเสธ:
การแปลงเป็น NNF
ใน ตรรกศาสตร์คลาสสิก และ ตรรกศาสตร์โมดอล จำนวนมาก ทุกสูตรสามารถนำมาอยู่ในรูปแบบนี้ได้โดยการแทนที่ การบ่งชี้ ( ) และ ความเท่าเทียมกัน ( ) ด้วยคำจำกัดความของพวกมัน โดยใช้ กฎของเดอ มอร์แกน เพื่อผลักดันการปฏิเสธเข้าไปด้านใน และกำจัดการปฏิเสธซ้ำซ้อน...