فرم نرمال اشتراکی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

هر تابع منطقی را می‌توان به فرم‌های مختلفی بیان نمود. برای آنکه بتوان دو تابع منطقی را با هم مقایسه نمود از فرم‌های نرمال استفاه می‌کنیم. انواع فرم‌های نرم عبارتند از:[۱]

  • (DNF: Disjunctive Normal Form)صورت نرمال ترکیب فصلی:
گزاره‌ای که به فرم جمع حاصل ضرب‌ها نوشته شود را، فرم نرمال DNF گوییم. بعنوان مثال عبارت زیر یک عبارت DNF می‌باشد:
  • (CNF: Conjunctive Normal Form)صورت نرمال ترکیب عطفی:
گزاره‌ای که به فرم ضرب حاصل جمع‌ها نوشته شود را، فرم نرمال CNF گوییم. بعنوان مثال عبارت زیر یک CNF می‌باشد:
  • (PDNF: Principle DNF)صورت نرمال ترکیب فصلی اساسی:
اگر گزاره‌ای به فرم جمع مینترم‌ها نوشته شود به آن PDNF گویند. بعنوان مثال عبارت زیر به فرم جمع مینترم هاست.
اگر گزاره‌ای به فرم ضرب ماکسترم‌ها نوشته شود به آن PCNF گویند. به عنوان مثال عبارت زیر به فرم PCNF می‌باشند:

اکنون هدف، بررسی فرم نرمال عطفی (CNF) است.

تعریف[ویرایش]

فرم نرمال عطفی (به انگلیسی: Conjunctive normal form) یا سی ان اف در منطق بولین به ترکیبی از جملات (در منطق) گویند به طوری که جمله تشکیل شده از تفکیک یا فصل منطقی لیترال‌ها باشد. (لیترال:یک متغیر بولی یا مکمل آن می‌باشد) از سوی دیگر می‌توان گفت به صورت and و orهایی است که به شکل an AND of ORs ترکیب شد اند.

  • به بیان دیگر: در منطق بولی، یک فرم نرمال عطفی CNF یک استاندارد (یا نرمال شده) از یک فرمول منطقی است که یک جداکننده عبارات فصلی است.
  • به بیان دیگر:فرمولی که هم ارز بایک فرمول دیگر باشد واز عطف تعدادی جمله تشکیل شده است که هر جمله شامل حاصل جمع‌های اولیه (فصل تعدادی متغیر و نقیض آنها) می‌باشد.

تنها عملگرهای گزاره‌ای در این فرم or, and و not هستند. عملگر not تنها می‌تواند به عنوان بخشی از لیترال استفاده شود. به این معنی که فقط می‌تواند قبل از یک متغیر گزاره‌ای بیاید.

مثال‌ها[ویرایش]

همه فرمول‌های زیر در فرم CNF هستند:

در ضمن دو فرمول آخر در فرم DNF هم هستند.

فرمول‌های زیر در فرم CNF نیستند:

هر فرمولی می‌تواندهم ارز با یک فرمول دیگر در فرم CNF باشد. به طور مثال برای سه مثال بالا، به ترتیب سه فرمول زیر در فرم CNF، هم ارز با آنها وجودد دارد:

تبدیل به CNF[ویرایش]

راه اول:

گام اول: جایگزین کردن علامت‌های () , ()به صورت زیر:

گام دوم: استفاده از قانون دمورگان (برای انتقال نقیض() به داخل پرانتزها)

گام سوم :استفاده از قانون توزیع پذیری (پخش کردن or روی andها):

به مثال توجه کنید:CNF عبارت روبه رو را به دست می‌آوریم.

راه دوم[ویرایش]

استفاده از جدول درستی:(که البته راه طولانی تری است)

به مثال روبه رو توجه کنید.

  • ابتدا یک جدول درستی برای عبارت A تشکیل می‌دهیم. این جدول اگر n متغیر گزاره‌ای در عبارت A داشته باشیم سطر دارد.
A Q P
F T T
T F T
T T F
F F F
  • سپس باید سطرهایی از ستون A که F هستند راپیداکرد. در این مثال سطر اول و چهارم F هستند. سپس برای این دو سطر (برای هر سطر به طور جداگانه) پرانتزی می‌سازیم که شامل متغیرهای گزاره‌ای است. به گونه‌ای که اگر در آن سطر متغیر F بود خودمتغیر و اگر T بود نقیض آن را قرار می‌دهیم. به شکل زیر:

و

  • درنهایت بین جمله‌ها قرار می‌دهیم.

کاربردها[ویرایش]

  • برای اثبات یک هم‌ارزی استفاده از این روش آسان تر است. (برای نشان دادن ) باید هر دورا به فرم نرمال تبدیل کرده وهم ارزی فرم‌های نرمال را بررسی نمود.
  • اثبات قضایا دربارهٔ همه گزاره‌ها
  • ممکن است برای ساده کردن مناسب باشد. به طور مثال اگر یک عبارت داشته باشیم که شامل باشد می‌دانیم که این جمله True است.
  • می‌توانیم در مدارها از این فرم استفاده کنیم چون باعث می‌شود هر عبارت بولی را تنها با دو گیت پیاده‌سازی کرد.

منابع[ویرایش]

  1. مینایی، بهروز، و دیگران. ساختمان‌های گسسته. تهران:مدرسان شریف،1393.

مشارکت‌کنندگان ویکی‌پدیا. «Conjunctive normal form». در دانشنامهٔ ویکی‌پدیای انگلیسی .