DNF
বিয়োজক প্রামাণ্য রূপ
Disjunctive Normal Form — OR of ANDs। `(a ∧ ¬b) ∨ (¬a ∧ c)`। Truth table-এর সত্য row-গুলো থেকে সরাসরি পাওয়া যায়।
also: disjunctive normal form, sum of products, SOP
DNF = term-দের OR, যেখানে প্রতিটা term literal-দের AND।
(p ∧ ¬q ∧ r) ∨ (¬p ∧ q) ∨ (q ∧ ¬r)Truth table থেকে বানানো সহজ: যেসব row-তে ফল T, প্রতিটার
জন্য একটা term — literal সরাসরি (variable T হলে x, F হলে ¬x)।
প্রতিটা এমন term-কে বলে [[minterm]]।
Hardware ডিজাইনে একই রূপকে বলা হয় SOP (sum of products), আর সেটাই [[karnaugh-map]] minimization-এর লক্ষ্য।
SOP নাকি POS? 1-row কম হলে SOP ছোট; 0-row কম হলে POS ছোট।
সবসময় দুইটাই বের করে ছোটটা নিন — পার্থক্য নাটকীয় হতে পারে।
DNF-এ satisfiability যাচাই করা সহজ (একটা term সত্য করা গেলেই হলো), কিন্তু CNF-এ কঠিন। উল্টোদিকে tautology যাচাই CNF-এ সহজ, DNF-এ কঠিন। এই অসাম্যটা complexity theory-র একটা সুন্দর উদাহরণ।