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

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

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

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

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

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

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

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

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

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

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

راه اول:

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

• ${\displaystyle (p\to q)\equiv (\mathrm{\neg }p\vee q)}$
• ${\displaystyle (p\leftrightarrow q)\equiv (p\to q)\wedge (q\to p)\equiv (\mathrm{\neg }p\vee q)\wedge (\mathrm{\neg }q\vee p)}$

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

• ${\displaystyle \mathrm{\neg }(p\vee q)\equiv (\mathrm{\neg }p\wedge \mathrm{\neg }q)}$
• ${\displaystyle \mathrm{\neg }(p\wedge q)\equiv (\mathrm{\neg }p\vee \mathrm{\neg }q)}$
• ${\displaystyle \mathrm{\neg }(\mathrm{\neg }p)\equiv p}$

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

• ${\displaystyle p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)}$

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

${\displaystyle \Rightarrow (\mathrm{\neg }p\vee (r\wedge s))\wedge (\mathrm{\neg }(r\wedge s)\vee p)}$

${\displaystyle \Rightarrow (\mathrm{\neg }p\vee r)\wedge (\mathrm{\neg }p\vee s)\wedge (\mathrm{\neg }r\vee \mathrm{\neg }s\vee p)}$

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

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

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

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

${\displaystyle (\mathrm{\neg }p\vee \mathrm{\neg }q)}$

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

${\displaystyle (\mathrm{\neg }p\vee \mathrm{\neg }q)\wedge (p\vee q)}$

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

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