فرم نرمال

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 27 مرداد 1400
دسته‌بندی: منطق گزاره
امتیاز:
بازدید: 27 مرتبه

یک فرمول ممکن است به یکی از سه صورت زیر باشد:

  • Toutology یک گزاره همیشه درست است.
  • Contradictian یک گزاره همیشه نادرست است.
  • Satisfiable حداقل به‌ازای یکی از ترکیبات، ارزش ممکنه برای متغیرهای دارای ارزش T است.

وضعیت هر فرمولی را می‌توان با تشکیل جدول ارزش آن مشخص کرد، حال روش‌های دیگری به نام تقلیل به‌صورت نرمال ارائه می‌دهیم.

روشDNF

DNF=Disjunctive  Normal  Form

از این به بعد به‌جای ترکیب فصلی  یا Disjunctive از کلمه sum یا حاصل جمع استفاده می‌کنیم.

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

p~ppq

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

p~pF

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

p~pT

رویه به‌دست آوردنDNF

  1. لفظ‌های پیوند دهنده   ,    ,  ¯  ,    ,   را با فرمول‌های هم‌ارز جایگزین می‌کنیم که فقط در آن ~,, ظاهر شوند.
  2. در صورتی‌که بخشی از فرمول به‌صورت نفی ظاهر شده باشد با استفاده از قوانین دمورگان سعی می‌کنیم نفی فقط در متغیرها ظاهر شود.
  3. اگر بخشی از فرمول به‌صورت حاصل‌ضرب مجموع‌ها بیان شده باشد با استفاده از قانون توزیع‌پذیری آن را به‌صورت مجموع حاصل‌ضرب تبدیل می‌کنیم.

دریافت مثال

مینترمminterm

دو متغیر گزاره‌ای p و q را در نظر بگیرید، با این دو متغیر 22=4 ترکیب عطفی متمایز می‌توان نوشت که عبارتند از:

pqp~q~pq~p~q

هر ترکیب عطفی دیگری که بتوان به‌وسیله p و q یا ~p و ~qنوشت، قطعا با یکی از ترکیبات فوق هم‌ارز خواهد بود.

فرم نرمال - پیمان گردلو 

ترکیب عطفی متغیرهای دل‌خواه (گزاره‌نما) که در آن هر متغیر تنها یک‌بار یا به‌صورت اصلی یا به‌صورت نفی ظاهر شده باشد را minterm نامیده می‌شود و آن را با m نمایش می‌دهیم.

خواص mintermها به‌صورت زیر است:

  •  mintermهای متمایز، هم‌ارز نیستند.
  • هر minterm تنها به‌ازای یکی از ترکیبات ارزش ممکنه برای متغیرها دارای ارزش T می‌باشد، این امر در جدول بالا نشان داده شده است.
  • اگر n متغیر وجود داشته باشد، آن‌گاه 2n تا minterm وجود دارد.  

تعریفPDNF

PDNF=PrincipalDisjuctiveNormalform

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

با استفاده از جدول ارزش و mintermهایی که دارای ارزش T هستند، می‌توان PDNF فرمولی را به‌دست آورد.

نکته

در یک فرمول Toutology همه ترکیبات عطفی ممکنه برای متغیرها در PDNF آن فرمول ظاهر خواهند شد، بدون در نظر گرفتن ترتیب قرار گرفتن mintermها در PDNF یک فرمول PDNF هر فرمولی منحصربه‌فرد است.      

رویه به‌دست آوردنPDNF

  1. DNF فرمول را به‌دست می‌آوریم.
  2. جملات حاصلضرب همیشه نادرست را حذف می‌کنیم.
  3. با به‌کار گرفتن متغیرهای مفقود، mintermها را به‌دست می‌آوریم.p~pT
  4. mintermهای مشابه را حذف می‌کنیم.     

تذکر

اگر PDNF فرمول A در دست باشد، PDNF فرمول ~Aمجموع mintermهایی است که در PDNF فرمول A ظاهر نشده است.     

دریافت مثال

روشCNF

CNF=Conjunctive  Normal  Form

از این به بعد به‌جای ترکیب عطفی  یا Conjunctive از کلمه product یا حاصل ضرب استفاده می‌کنیم.

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

pq~p~q

رویه به‌دست آوردنCNF

  1. لفظ‌های پیوند دهنده   ,    ,  ¯  ,    ,   را با فرمول‌های هم‌ارز جایگزین می‌کنیم که فقط در آن ~,, ظاهر شوند.
  2. در صورتی‌که بخشی از فرمول به‌صورت نفی ظاهر شده باشد با استفاده از قوانین دمورگان سعی می‌کنیم نفی فقط در متغیرها ظاهر شود.
  3. اگر بخشی از فرمول به‌صورت مجموع حاصل‌ضرب‌ها بیان شده باشد با استفاده از قانون توزیع‌پذیری آن را به‌صورت حاصل‌ضرب مجموع تبدیل می‌کنیم.

دریافت مثال

ماکسترمMaxterm

دو متغیر گزاره‌ای p و q را در نظر بگیرید، با این دو متغیر 22=4 ترکیب فصلی متمایز می‌توان نوشت که عبارتند از:

pqp~q~pq~p~q

هر ترکیب فصلی دیگری که بتوان به‌وسیله p و q یا ~p و ~qنوشت، قطعا با یکی از ترکیبات فوق هم‌ارز خواهد بود.

ترکیب فصلی متغیرهای دل‌خواه (گزاره‌نما) که در آن هر متغیر تنها یک‌بار یا به‌صورت اصلی یا به‌صورت نفی ظاهر شده باشد را Maxterm نامیده می‌شود و آن را با M نمایش می‌دهیم.

فرم نرمال - پیمان گردلو

خواص Maxtermها به‌صورت زیر است:

  •  Maxtermهای متمایز، هم‌ارز نیستند.
  • هر Maxterm تنها به‌ازای یکی از ترکیبات ارزش ممکنه برای متغیرها دارای ارزش F می‌باشد، این امر در جدول بالا نشان داده شده است.
  • اگر n متغیر وجود داشته باشد، آن‌گاه 2n تا Maxterm وجود دارد.  

تعریفPCNF

PCNF=PrincipalConjunctiveNcrmalForm

هم‌ارز یک فرمول را که به‌صورت حاصل‌ضرب Maxtermها بیان شده باشد PCNF آن فرمول گویند.

با استفاده از جدول ارزش و Maxtermهایی که دارای ارزش F هستند، می‌توان PCNF فرمولی را به‌دست آورد.

تذکر

اگر PCNF فرمول A در دست باشد، PCNF فرمول ~Aحاصل‌ضرب Maxtermهایی است که در PCNF فرمول A ظاهر نشده است.    

تمرین

PCNF فرمول ~pqرا به‌دست ‌آورید:

~pq~pq~qqp~p~pq~p~qqpq~ppq~pq~p~q


همان‌طور که مشاهده می‌شود ماکسترمم p~q وجود ندارد اما اگر فرمول را نقیض کنیم Maxterm ساخته می‌شود:

~~pqp~q

رویه به‌دست آوردنPCNF

  1. CNF فرمول را به‌دست می‌آوریم.
  2. جملات مجموع همیشه درست را حذف می‌کنیم.
  3. با به‌کار گرفتن متغیرهای مفقود، Maxtermها را به‌دست می‌آوریم.p~pF
  4. Maxtermهای مشابه را حذف می‌کنیم.   

دریافت مثال

تذکر

با استفاده از هم‌ارزی A~~A و به‌کار گرفتن قوانین دمورگان می‌توان از PDNF یا PCNF فرمول ~A، PDNF یا PCNF فرمول A را به‌دست آورد.  

تمرین

فرض کنید PCNF فرمول ~S به‌صورت زیر تعریف شده باشد:

~S:pq~R~p~QR~p~q~R

از هم‌ارزی S~~S استفاده کنید و PDNF فرمول S را به‌دست آورید. 

S~~S:~pq~R~p~qR~p~q~R~pq~R~~p~qR~~p~q~R~p~qRpq~RpqR

نکته

در صورتی‌که برای متغیرها، Maxtermها، mintermها ترتیب خاصی قائل شویم و می‌توانیم PDNF و PCNF فرمولی را به‌طور منحصربه‌فرد نشان داد.   

از آنجایی که غالبا برای نمایش متغیرها ازحروف بزرگ انگلیسی استفاده می‌کنیم بنابراین آنها را می‌توان به ترتیب حروف الفبا مرتب نمود.

حال اگر هر یک از این حروف دارای اندیس هم باشند، می‌توان آنها را به صورت زیر مرتب کرد.

A  ,  B  ,    ,  Z  ,  A1  ,  B1  ,  Z1  ,  A2  ,    ,  Z2  ,  .

به‌عنوان نمونه Q3  ,   T2  ,  S1R3QP1 به‌ترتیب زیر مرتب می‌گردند:

Q,P1  ,S1  ,T2  ,Q3  ,R3

تذکر

1- فرض کنیم n متغیر دل‌خواه به‌طور مرتب چیده شده باشند، 2n تا minterm مربوط به این n متغیر را می‌توان به‌صورت زیر نشان داد:  

m2n1   ,    ,  m1  ,  m0

در صورتی‌که اندیس‌ها را به معادل باینری آنها تبدیل کرده و در صورت نیاز تعدادی صفر به‌سمت چپ آنها اضافه کنیم به‌طوری‌که تعداد بیت‌ها با تعداد متغیرها یکسان شوند، می‌توان mintermها را به‌صورت زیر به‌دست آورد. 

اگر در موضع iام از سمت چپ 1 وجود داشته باشد در ترکیب عطفی، نفی متغیر ظاهر می‌شود. 

اگر در موضع iام از سمت چپ 0 وجود داشته باشد در ترکیب عطفی خود متغیر ظاهر می‌شود.

به‌عنوان نمونه فرض کنید P و Q و R سه متغیر باشند که به‌همین ترتیب چیده شده‌اند، برای نمایش mintermها به‌صورت زیر عمل می‌کنیم:  

فرم نرمال - پیمان گردلو

در صورتی‌که mintermها را فقط با اندیس آنها و ترکیب فصلی (مجموع) را با نشان دهیم، می‌توان مجموع حاصل‌ضرب‌های متناظر را با mk  ,  mj  ,  mi به‌صورت i,j,k نشان داد.  

تذکر

2- فرض کنیم n متغیر دل‌خواه به‌طور مرتب چیده شده باشند، 2n تا Maxterm مربوط به این n متغیر را می‌توان به‌صورت زیر نشان داد:   

M2n1  ,..  ,  M1  ,  M0

در صورتی‌که اندیس‌ها را به معادل باینری آنها تبدیل کرده و در صورت نیاز تعدادی صفر به‌سمت چپ آنها اضافه کنیم به‌طوری‌که تعداد بیت‌ها با تعداد متغیرها یکسان شوند، می‌توان Maxtermها را به‌صورت زیر به‌دست آورد. 

اگر در موضع iام از سمت چپ 1 وجود داشته باشد، در ترکیب فصلی نفی متغیر ظاهر می‌شود.

اگر در موضع iام از سمت چپ 0 وجود داشته باشد، در ترکیب فصلی خود متغیر ظاهرمی‌شود.

به‌عنوان نمونه فرض کنید P و Q و R سه متغیر باشند که به‌همین ترتیب چیده شده‌اند، برای نمایش Maxtermها به‌صورت زیر عمل می‌کنیم:  

فرم نرمال - پیمان گردلو

در صورتی‌که Maxtermها را فقط با اندیس آنها و ترکیب عطفی (حاصل‌ضرب) را با نشان دهیم، می‌توان حاصل‌ضرب‌ مجموع‌های متناظر را با Mk  ,Mj  ,Mi به‌صورت i,j,k نشان داد.  

دریافت مثال

مثال‌ها و جواب‌ها

فرم نرمال

1,300تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید