رابطه‌ های منطقی کامل

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

مجموعه رابطه‌های منطقی کامل NOR   ,    NAND  ,   OR را بررسی می‌کنیم.

در این بخش نشان خواهیم داد که این‌طور نیست که تمام رابطه‌هایی که تاکنون تعریف کرده‌ایم تا این اندازه مورد نیاز باشند.

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

تمرین

فرمولی هم‌ارز برای pqrrp بنویسید که گزاره دوشرطی نداشته باشد.

pqrrqrppr

فرمولی معادل برای pqr بنویسید به‌طوری‌که گزاره‌های شرطی و دوشرطی را نداشته باشد.

pqrpqrrqp~qr~rq


توجه کنید که از قوانین دمورگان داریم:

pq~~p~qpq~~p~q


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

نکته

شگردی مشابه برای حذف رابط‌های فصلی وجود دارد.

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

مفهوم این نکته این است که مجموعه رابط‌های ,~ و ,~ تابعی کامل هستند.  

می‌توان نشان داد که مجموعه‌های ,,,,~ تابعی کامل نیستند.

از پنج رابطه ,,~,, لااقل دو مجموعه ,~ و ,~ رابطه تابعی کامل است. 

تعریفORانحصاری  

فرض کنید p و q دو فرمول دل‌خواه باشند، فرمول p¯q که در آن رابط ¯ یای انحصاری (OR انحصاری) خوانده می‌شود، درست است هرگاه p یا q درست باشند نه هر دوی آن.

رابطه‌های منطقی کامل - پیمان گردلو  

نکته

با استفاده از این تعریف هم‌ارزی‌های زیر به‌دست می‌آیند:

خاصیت متقارن:

p¯qq¯p

خاصیت شرکت‌پذیری:

p¯q¯rp¯q¯r

خاصیت توزیع‌پذیری:

pq¯rpq¯pr

خاصیت‌های دیگر:

p¯qp~q~pqp¯q~pQ

 تعریفNOR   ,    NAND

رابط NOR   ,    NAND برحسب رابط‌های ~,, تعریف می‌شوند.

pq~pqpq~pq

بنابراین اگر در فرمولی رابط‌های  یا به کار رفته باشد، می‌توان فرمولی به‌دست آورد که فقط شامل رابط‌های ~,, باشد.

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

نشان می‌دهیم که هر یک از نمادهای  یا  تابعی کامل هستند.

برای این کار کافی است نشان دهیم که مجموعه رابط‌های ,~ و ,~ بر حسب به‌تنهایی قابل نمایش هستند:

pp~pp~p~p~ppqpq~pqpq~pqpqppqq~p~q~~p~qpq

به‌کمک هم‌ارزی‌های زیر، رابط‌های ~,, بر حسب به‌تنهایی قابل نمایش هستند:

pp~pp~p~p~ppqpq~pqpq~pq~~pqpqppqq~pp~qq~p~q~~p~q=pq

تک عمل‌گرهای NAND یا NOR تابعی کامل‌اند، ما هر یک از مجموعه‌های , را یک مجموعه مینیمال گوییم یا یک مجموعه تابعی کامل مینیمال گوییم.

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

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

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

نکته

بعضی خواص اساسی رابط‌های NAND و NOR را برمی‌شماریم: 

1- رابط‌های   و  دارای خاصیت‌ جابه‌جایی است:   

pqqppqqp

2- رابط‌های   و  دارای خاصیت شرکت‌پذیری نیست:

pqrp~qr~p~qr~pqrpqrpq~r

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