รูปแบบปกติที่ไม่ต่อเนื่องคืออะไร (dnf) - คำจำกัดความจาก techopedia

คำจำกัดความ - Disjunctive Normal Form (DNF) หมายถึงอะไร

Disjunctive normal form (DNF) คือการทำให้เป็นมาตรฐานของสูตรเชิงตรรกะในคณิตศาสตร์บูลีน กล่าวอีกนัยหนึ่งสูตรตรรกะว่ากันว่าอยู่ในรูปแบบปกติแยกถ้ามันเป็นความแตกแยกของสันธานกับทุกตัวแปรและการปฏิเสธของมันจะมีอยู่ครั้งเดียวในแต่ละร่วมกัน แบบฟอร์มทั้งหมดที่แยกจากกันนั้นไม่ซ้ำกันเนื่องจากรูปแบบปกติทั้งหมดที่แยกออกสำหรับข้อเสนอเดียวกันนั้นเทียบเท่ากัน

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

Techopedia อธิบาย Disjunctive Normal Form (DNF)

สูตรเชิงตรรกะอยู่ในรูปแบบปกติที่ไม่ต่อเนื่องกันหากว่ามีการสลับกันของหนึ่งหรือมากกว่าหนึ่งตัวของหนึ่งหรือมากกว่าหนึ่งตัวอักษร สูตรถูกพิจารณาว่าอยู่ในรูปแบบปกติที่ไม่ต่อเนื่องเต็มรูปแบบหากตัวแปรทั้งหมดที่เกี่ยวข้องถูกแสดงเพียงครั้งเดียวในทุกประโยค คล้ายกับรูปแบบปกติซึ่งเชื่อมโยงกันตัวดำเนินการเชิงประพจน์ในรูปแบบปกติที่แยกออกจะเหมือนกัน: AND, OR และ NOT

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