Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۶:ترکیبیات:سوال ۲

منطق، بی‌ منطق

در منطق گزاره‌ای:

آ) فرض کنید S مجموعه‌ای از عبارات و A یک عبارت باشد که لزومن در S نیست. اگر داشته باشیم SA و S(¬A) آن‌گاه ثابت کنید به ازای هر عبارت دل‌خواه مانند B داریم SB.

ب) فرض کنید S مجموعه‌ای از عبارات و A یک عبارت باشد که لزومن در S نیست. اگر به ازای عبارتی مانند B داشته باشیم (S{(¬A)})B و (S{(¬A)})(¬B) آن‌گاه داریم SA.

ج) فرض کنید A,B دو عبارت دل‌خواه باشند. ثابت کنید: (((¬A)B)(((¬A)(¬B))A))

د) فرض کنید A یک عبارت دل‌خواه باشد. ثابت کنید: ((¬(¬A)))A)

پیوست‌های سوال:

  • اصول منطق گزاره‌ای، سه اصل زیر هستند:
  1. (A(BA))
  2. ((A(BC))((AB)(AC)))
  3. (((¬A)(¬B))(BA))
  • تنها قانون منطق گزاره‌ای این است که اگر A و (AB) قابل اثبات باشند، B نیز قابل اثبات است.
  • در کلاس گفته شد اگر S مجموعه‌ای از عبارات و A,B عباراتی دل‌خواه باشند که (S{A})B آن‌گاه S(AB). می‌توانید از این قضیه استفاده کنید.
  • در تمرین‌تان گفته شد به ازای هر دو عبارت A,B داریم ((¬A)(AB)). از این حکم نیز می‌توانید استفاده کنید.
  • در هر یک از قسمت‌های سوال، می‌توانید درستی قسمت‌های قبلی را فرض کنید؛ حتّی اگر اثبات نکرده باشید.

ابزار صفحه