فرم نرمال فصلی

در منطق بولی، یک فرم نرمال فصلی DNF یک استاندارد (یا نرمال شده) از یک فرمول منطقی است که یک جداکننده عبارات عطفی است. از سوی دیگر به صورت and وor‌هایی است که ان را به عنوان Sum of product می‌شناسید. همچنین یک فرم نرمال برای اثبات خودکار قضایا مفید است. یک فرمول منطقی درفرم DNF در نظر گرفته شده است اگر و تنها اگر به صورت یک فصل یاچند اتصال از یک یا چند عملگر باشد. اگر هر یک از متغیرهای dnf دقیقا یک بار در هر عبارت باشند، فرمول DNF به طور کامل درفرم نرمال فصلی است. مانند فرم نرمال CNF، تنها عملگرهای گزاره‌ای در not , and , or , DNF هستند. عملگر not تنها می‌تواندبه عنوان بخشی از عملگر استفاده شود به این معنی که فقط می‌تواند قبل از یک متغیر گزاره‌ای بیاید. برای مثال همه فرمول‌های زیر در فرم dnf است:

$A \and B$

$A\!$

$(A \and B) \or C$

$(A \and \neg B \and \neg C) \or (\neg D \and E \and F)$

بنابراین فرمول‌های زیر در فرم dnf نیستند

$\neg(A \or B)$ — NOT is the outermost operator

$A \or (B \and (C \or D))$ — an OR is nested within an AND

تبدیل یک فرمول به DNF شامل استفاده از معادله‌های منطقی مانند حذف دو منفی، قوانین دمورگان و قانون توزیع است. تمام فرمول‌های منطقی را می‌توان به شکل نرمال فصلی تبدیل کرد. با این حال در برخی موارد تبدیل به dnf می‌تواند به انفجار نمایی از فرمول منجر شود. به عنوان مثال فرمول منطقی زیر ۲ به توان n جمله دارد

$(X_1 \or Y_1) \and (X_2 \or Y_2) \and \dots \and (X_n \or Y_n)$

هرتابع بولی خاص را می‌توان بایک وتنها یک فرمال نرمال کامل فصلی، یکی از دوشکل متعارف، نشان داد. در زیر یک گرامر از فرم نرمال dnf وجود دارد

1. disjunct → conjunct
2. disjunct → disjunct ∨ conjunct
3. conjunct → literal
4. conjunct → (conjunct ∧ literal)
5. literal → variable
6. literal → ¬variable

که در ان یک متغیر هر متغیری می‌تواند باشد

جستارهای وابسته

• تابع بولی
• نقشه کارنو
• حساب گزاره‌ای
• الگوریتم کوین-مک‌کلاسکی
• جدول ارزش

منابع

• ویکی‌پدیای انگلیسی

پیوندهای بیرونی

• Disjunctive normal form", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 ٫ (Hazewinkel, Michiel, ed. (2001)
• Java applet for converting boolean logic expressions to CNF and DNF, showing the laws used