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

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

$A\land B$$A\land B$

$A\!$$A\!$

$(A\land B)\lor C$$(A\land B)\lor C$

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

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

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

$A\lor (B\land (C\lor D))$$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})$$(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

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

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

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

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

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

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

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

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

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

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

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

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

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

مثلا اگر دو متغير pو q داشته باشيم ((تعداد متغير ها)^2)حالت 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