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

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

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

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

  • (DNF: Disjunctive Normal Form)صورت نرمال تركيب فصلي:
گزاره اي كه به فرم جمع حاصل ضرب ها نوشته شود را، فرم نرمال DNF گوييم. بعنوان مثال عبارت زير يك عبارت DNF مي باشد:
  • (CNF: Conjunctive Normal Form)صورت نرمال تركيب عطفي:
گزاره اي كه به فرم ضرب حاصل جمع ها نوشته شود را، فرم نرمال CNF گوييم. بعنوان مثال عبارت زير يك CNF مي باشد:
  • (PDNF: Principle DNF)صورت نرمال تركيب فصلي اساسی:
اگر گزاره اي به فرم جمع مينترم ها نوشته شود به آن PDNF گويند. بعنوان مثال عبارت زير به فرم جمع مينترم هاست.
  • (PCNF:Principle CNF)صورت نرمال ترکیب عطفی اساسی:
اگر گزاره اي به فرم ضرب ماكسترم ها نوشته شود به آن 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»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد.