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

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

$A\land B$

$A\!$

$(A\land B)\lor C$

$(A\land \neg B\land \neg C)\lor (\neg D\land E\land F)$

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

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

$A\lor (B\land (C\lor D))$ — an OR is nested within an AND

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

$(X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})$

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

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

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

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

۱: فرم نرمال فصلی اصلی PDNF

۲: فرم نرمال عطفی اصلی PCNF

۱:فرمی که فقط از فصل عباراتی تشکیل شده که فقط شامل عطف(and) هستند

(p&q)|(~p&q)

۲:فرمی که فقط از عطف عباراتی تشکیل شده که فقط شامل قصل(or) هستند

(p|q)&(~p|q)

در بعضی از سوالات از ما انتظار می‌رود که بتوانیم یک عبارت شرطی را برحسب PDNF یا PCNF بنویسیم که چندین راه برای این کار وجود دارد ولی اسان‌ترین راه کشیدن جدول به طریق زیر است:

برای نوشتن عبارات شرطی به صورت فرم‌های نرمال اصلی ابتدا باید نوع فرم را مشخص کنیم

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

فرم نرمال عطفی اصلی PCNF

حال فرض کنید قصد نوشتن فرم نرمال فصلی اصلی (PDNF) را داریم در مرحله بعد تمام متغیرهای موجود را در جدولی وارد کرده و تمام حالات true و false بین ان‌ها را می‌نویسیم.

مثلاً اگر دو متغیر pو q داشته باشیم ((تعداد متغیرها)^۲)حالت true و false بین ان‌ها بوجود می‌آید.

حال درستی و نادرستی عبارت شرطی را بر اساس حالات مختلف pو q تعیین می‌کنیم. در این مرحله فقط خانه‌هایی از جدول برای ما اهمیت دارد که مقدار عبارت شرطی برای آن‌ها true است. به ستون اول و دوم که حاوی p و q هستند دقت می‌کنیم.

به ازای هر ردیف ترکیبی عطفی طبق دستور زیر می‌سازیم:

به ازای عبارت true خودشان

به ازای مقادیر false نقیض ان‌ها را قرار می‌دهیم.

حال ترکیب فصلی از این عبارات می‌سازیم.

دقت کنید که برای نوشتن PCNF تمام حالات بالا عکس می‌شود. برای درک بیشتر به تصاویر زیر دقت کنید

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

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

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

منابع

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

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

• 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