กลับไปหน้าบทความ

อ่าน 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สำหรับสูตรในรูปแบบปกติของการเชื่อมโยง ปัญหาความถูกต้องสามารถแก้ไขได้ในเวลาพหุนาม และสำหรับสูตรในรูปแบบปกติของการแยก ปัญหาความสามารถในการทำให้เป็นจริงสามารถแก้ไขได้ในเวลาพหุนาม

ดูเพิ่มเติม

หมายเหตุ

  • แอปเพล็ต Java สำหรับแปลงสูตรตรรกะเป็นรูปแบบปกติของการปฏิเสธ (Negation Normal Form) พร้อมแสดงกฎที่ใช้
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Negation_normal_form&oldid=1337324522 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ รูปแบบปกติของการปฏิเสธ

ในตรรกศาสตร์ทางคณิตศาสตร์สูตรจะอยู่ในรูปแบบปกติของการปฏิเสธ ( NNF ) ก็ต่อเมื่อ ตัวดำเนิน การปฏิเสธ ( , ไม่ ) ใช้กับตัวแปรเท่านั้น และตัวดำเนินการบูลีน อื่นๆ ที่อนุญาต...

คำนิยาม

ต่อไปนี้เป็น ไวยากรณ์ที่ไม่ขึ้นกับบริบท สำหรับ NNF :

ตัวอย่างและตัวอย่างค้าน

สูตรต่อไปนี้ทั้งหมดอยู่ในรูปแบบปกติของการปฏิเสธ:

การแปลงเป็น NNF

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