فرم نرمال اشتراکی - ویکی‌پدیا، دانشنامهٔ آزاد

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

• (DNF: Disjunctive Normal Form) صورت نرمال ترکیب فصلی:

گزاره‌ای که به فرم جمع حاصل ضرب‌ها نوشته شود را، فرم نرمال DNF گوییم. به عنوان مثال عبارت زیر یک عبارت DNF می‌باشد:

${\displaystyle (p\land r)\lor (\neg q\land t)}$

• (CNF: Conjunctive Normal Form) صورت نرمال ترکیب عطفی:

گزاره‌ای که به فرم ضرب حاصل جمع‌ها نوشته شود را، فرم نرمال CNF گوییم. به عنوان مثال عبارت زیر یک CNF می‌باشد:

${\displaystyle (p\lor q)\land (\neg q\lor \neg t)}$

• (PDNF: Principle DNF) صورت نرمال ترکیب فصلی اساسی:

اگر گزاره‌ای به فرم جمع مینترم‌ها نوشته شود به آن PDNF گویند. به عنوان مثال عبارت زیر به فرم جمع مینترم هاست.

${\displaystyle F(x_{1},x_{2},x_{3})=m_{0}+m_{5}+m_{7}}$

• (PCNF:Principle CNF) صورت نرمال ترکیب عطفی اساسی:

اگر گزاره‌ای به فرم ضرب ماکسترم‌ها نوشته شود به آن PCNF گویند. به عنوان مثال عبارت زیر به فرم PCNF می‌باشند:

${\displaystyle F(x_{1},x_{2},x_{3})=M_{1}\times M_{2}\times M_{3}\times M_{4}\times M_{7}}$

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

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

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

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

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

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

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

• ${\displaystyle \neg A\wedge (B\vee C)}$
• ${\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E)}$
• ${\displaystyle A\lor B}$
• ${\displaystyle A\wedge B}$

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

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

• ${\displaystyle \neg (B\vee C)}$
• ${\displaystyle (A\wedge B)\vee C}$
• ${\displaystyle A\wedge (B\vee (D\wedge E)).}$

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

• ${\displaystyle \neg B\wedge \neg C}$
• ${\displaystyle (A\vee C)\wedge (B\vee C)}$
• ${\displaystyle A\wedge (B\vee D)\wedge (B\vee E).}$

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

راه اول:

گام اول: جایگزین کردن علامت‌های (${\displaystyle \to }$) , (${\displaystyle \leftrightarrow }$)به صورت زیر:

• ${\displaystyle (p\to q)\equiv (\neg p\lor q)}$
• ${\displaystyle (p\leftrightarrow q)\equiv (p\to q)\land (q\to p)\equiv (\neg p\lor q)\land (\neg q\lor p)}$

گام دوم: استفاده از قانون دمورگان (برای انتقال نقیض(${\displaystyle \neg }$) به داخل پرانتزها)

• ${\displaystyle \neg (p\lor q)\equiv (\neg p\land \neg q)}$
• ${\displaystyle \neg (p\land q)\equiv (\neg p\lor \neg q)}$
• ${\displaystyle \neg (\neg p)\equiv p}$

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

• ${\displaystyle p\lor (q\land r)\equiv (p\lor q)\land (p\lor r)}$

به مثال توجه کنید:CNF عبارت روبه رو را به دست می‌آوریم. ${\displaystyle p\leftrightarrow (r\land s)}$

${\displaystyle \Rightarrow (\neg p\lor (r\land s))\land (\neg (r\land s)\lor p)}$

${\displaystyle \Rightarrow (\neg p\lor r)\land (\neg p\lor s)\land (\neg r\lor \neg s\lor p)}$

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

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

به مثال روبه رو توجه کنید.${\displaystyle A=p\oplus q}$

• ابتدا یک جدول درستی برای عبارت A تشکیل می‌دهیم. این جدول اگر n متغیر گزاره‌ای در عبارت A داشته باشیم ${\displaystyle 2^{n}}$ سطر دارد.

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

${\displaystyle (\neg p\lor \neg q)}$ و ${\displaystyle (p\lor q)}$

• در نهایت بین جمله‌ها ${\displaystyle \land }$ قرار می‌دهیم.

${\displaystyle (\neg p\lor \neg q)\land (p\lor q)}$

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

• برای اثبات یک هم‌ارزی استفاده از این روش آسان‌تر است. (برای نشان دادن ${\displaystyle A\equiv B}$) باید هر دورا به فرم نرمال تبدیل کرده وهم ارزی فرم‌های نرمال را بررسی نمود.
• اثبات قضایا دربارهٔ همه گزاره‌ها
• ممکن است برای ساده کردن مناسب باشد. به‌طور مثال اگر یک عبارت داشته باشیم که شامل ${\displaystyle (p\lor \neg p\lor ...)}$ باشد می‌دانیم که این جمله True است.
• می‌توانیم در مدارها از این فرم استفاده کنیم چون باعث می‌شود هر عبارت بولی را تنها با دو گیت پیاده‌سازی کرد.

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

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

این یک مقالهٔ خرد ریاضیات است. می‌توانید با گسترش آن به ویکی‌پدیا کمک کنید.

این یک مقالهٔ خرد هوش مصنوعی است. می‌توانید با گسترش آن به ویکی‌پدیا کمک کنید.