صورت بهنجار فصلی

در منطق بولی، یک صورت بهنجار فصلی (به انگلیسی: disjunctive normal form) یا فرم نرمال فصلی (اختصاری دی‌اِن‌اف) یک استاندارد (یا بهنجارشده) از یک فرمول منطقی است که یک صورت بهنجار متعارف است. از سوی دیگر به صورت اَند و اُر‌هایی است که ان را به عنوان مجموع حاصل‌ضرب (به انگلیسی: sum of products) می‌شناسید. همچنین یک صورت بهنجار برای اثبات خودکار قضایا مفید است. یک فرمول منطقی در فرم دی‌اِن‌اف در نظر گرفته شده است اگر و تنها اگر به صورت یک فصل یاچند اتصال از یک یا چند عملگر باشد. اگر هر یک از متغیرهای دی‌اِن‌اف دقیقاً یک بار در هر عبارت باشند، فرمول دی‌اِن‌اف به‌طور کامل درصورت بهنجار فصلی است. مانند صورت بهنجار سی‌اِن‌اف، تنها عملگرهای گزاره‌ای در نات، اَند، اُر، دی‌اِن‌اف هستند. عملگر نات تنها می‌تواند به عنوان بخشی از عملگر استفاده شود به این معنی که فقط می‌تواند قبل از یک متغیر گزاره‌ای بیاید. برای مثال همه فرمول‌های زیر به شکل دی‌اِن‌اف است:

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

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

• $\neg (A\lor B)$ — نات بیرونی‌ترین عملگر است
• $A\lor (B\land (C\lor D))$ — درون اَند قرار گرفته است
• $\neg (A\land B)\lor C$ از آنجایی که یک اَند در یک نات قرار دارد

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

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

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

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

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

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

۱: صورت بهنجار فصلی اصلی پی‌دی‌اِن‌اف

۲: صورت بهنجار عطفی اصلی پی‌سی‌اِن‌اف

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

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

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

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

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

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

صورت بهنجار فصلی اصلی پی‌دی‌ان‌اف

صورت بهنجار عطفی اصلی پی‌سی‌اِن‌اف

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

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

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

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

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

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

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

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

صورت بهنجار فصلی اصلی

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

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

منابع

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

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

• 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