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

آخرین ویرایش: 08 اسفند 1402
دسته‌بندی: منطق گزاره
امتیاز:
نظر کاربران: برای نظر دادن اولین باش!

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

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

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

تمرین

فرمولی هم‌ارز برای p∧q⇄r∨r⇄p بنویسید که گزاره دوشرطی نداشته باشد.

p∧q→r∧r→q∨r→p∧p→r

فرمولی معادل برای p∧q⇄r بنویسید به‌طوری‌که گزاره‌های شرطی و دوشرطی را نداشته باشد.

p∧q⇄r⇔p∧q→r∧r→q⇔p∧~q∨r∧~r∨q


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

p∧q⇔~~p∨~qp∨q⇔~~p∧~q


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

نکته

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

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

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

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

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

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

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

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

نکته

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

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

p∨¯q⇔q∨¯p

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

p∨¯q∨¯r⇔p∨¯q∨¯r

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

p∧q∨¯r⇔p∧q∨¯p∧r

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

p∨¯q⇔p∧~q∨~p∧q

p∨¯q⇔~p⇄Q

 تعریفNOR↓   ,    NAND↑

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

p↑q⇔~p∧qp↓q⇔~p∨q

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

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

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

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

p↑p⇔~p∧p⇔~p∨~p⇔~p

p↑q↑p↑q⇔~p↑q∧p↑q⇔~p↑q⇔p∧q

p↑p↑q↑q⇔~p↑~q⇔~~p∧~q⇔p∨q

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

p↓p⇔~p∨p⇔~p∧~p⇔~p

p↓q↓p↓q⇔~p↓q∨p↓q⇔~p↓q⇔~~p∨q⇔p∨q

p↓p↓q↓q⇔~p∨p↓~q∨q⇔~p↓~q⇔~~p∨~q=p∧q

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

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

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

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

نکته

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

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

p↑q⇔q↑pp↓q⇔q↓p

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

p↑q↑r⇔p↑~q∧r⇔~p∧~q∧r⇔~p∨q∧rp↑q↑r⇔p∧q∨~r

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