نظریه اصل موضوعی منطق گزاره‌ای ۳
منطق و رایانش
درآمد به منطق
استقلال اصول موضوعه و منطق‌های چند ارزشی
۱- سرآغاز | ۴- منطق‌های چند ارزشی |
۲- استقلال بنداشت‌ها | ۵- منطق چند ارزشی ℳ |
۳- قضیه. طرح‌وارهای بنداشتی (A۱)-(A۳) نابسته هستند. | ۶- تمرین * |
■ سرآغاز
قسمت پیشین (قسمت دوم نظریه اصل موضوعی منطق گزاره‌ای↝) به اثبات استواری، تمامیت و سازگاری 𝓛 گذشت.
در این یادداشت، یعنی قسمت سوم از نظریه اصل موضوعی منطق گزاره‌ای، ابتدا به اثبات «استقلال بنداشت‌ها در نظریه 𝓛» می‌پردازیم. سپس با بهره‌گیری از راه کار به کار رفته در این اثبات‌ها به «منطق‌های چند ارزشی» می‌پردازیم.
منبع و مرجع اصلی ما در چهار قسمت «نظریه اصل موضوعی منطق گزاره‌ای» متن:
Mendelson, Elliott. Introduction to mathematical logic. 6th,ed, CRC Press, Taylor & Francis Group. 2015.
است.
■ [۵.۱] استقلال بنداشت‌ها
یک زیرمجموعه Y از بنداشت‌های یک نظریه را بنداشت‌های نابسته (بنداشت‌های مستقل) گوییم اگر برخی فرمول در Y را نتوان از قاعده استنتاج و بقیه بنداشت‌های (بنداشت‌هایی که در Y نیستند) آن نظریه استنتاج کرد.
■ [۱۷.۱.↧] قضیه. طرح‌وارهای بنداشتی (A۱)-(A۳) نابسته هستند.
• Mendelson, Elliott. Introduction to mathematical logic. 6th,ed, CRC Press, Taylor & Francis Group. 2015. pg. 36.
■ اثبات استقلال طرحواره بنداشت A۱ [α⇒(β⇒α)]
برای اثبات استقلال طرح بنداشتی A۱ ابتدا به دو جدول زیر توجه کنید:
| جدول ۲ | جدول ۱ | |||
| A=B | B | A | ¬A | A |
| ۰ | ۰ | ۰ | ۱ | ۰ |
| ۲ | ۰ | ۱ | ۱ | ۱ |
| ۰ | ۰ | ۲ | ۰ | ۲ |
| ۲ | ۱ | ۰ | ||
| ۲ | ۱ | ۱ | ||
| ۰ | ۱ | ۲ | ||
| ۲ | ۲ | ۰ | ||
| ۰ | ۲ | ۱ | ||
| ۰ | ۲ | ۲ | ||
این دو جدول برای هر گمارش مقادیر سمانتیکی از قرار ۰، ۱ و ۲ به حروف گزاره‌ای فرمولی مانند β، مقدار نظیر β را تعیین می‌کنند. اگر β همیشه مقدار ۰ را بگیرد، β را برگزیده / Select [صورت برگزیده] می‌نامیم.
به آسانی می‌توان دید که قیاس استثنایی برگزیدگی را نگه می‌دارد، یعنی اگر β و β⇒ς برگزیده باشند آنگاه ς هم برگزیده خواهد بود. همچنین می‌توان بررسی کرد و دید که همه موردهای طرح‌های بنداشتی A۲ و A۳ نیز برگزیده هستند.
از این رو، هر فرمولی که از A۲ و A۳ توسط قیاس استثنایی به دست آمده باشد برگزیده است. با این حال،
p۱ ⇒ (p۲ ⇒ p۱),
که موردی از A۱ است، برگزیده نیست. زیرا وقتی p۱ مقدار ۱ و p۲ مقدار ۲ بگیرد آنگاه فرمول بالا مقدار ۲ را خواهد گرفت. بنابراین، A۱ نابسته به A۲ و A۳ است.
■ اثبات استقلال طرح بنداشت A۲
برای اثبات استقلال طرح بنداشتی A۲ به دو جدول زیر توجه کنید:
| جدول ۲ | جدول ۱ | |||
| A=B | B | A | ¬A | A |
| ۰ | ۰ | ۰ | ۱ | ۰ |
| ۰ | ۰ | ۱ | ۰ | ۱ |
| ۰ | ۰ | ۲ | ۱ | ۲ |
| ۲ | ۱ | ۰ | ||
| ۲ | ۱ | ۱ | ||
| ۰ | ۱ | ۲ | ||
| ۱ | ۲ | ۰ | ||
| ۰ | ۲ | ۱ | ||
| ۰ | ۲ | ۲ | ||
به فرمولی که مطابق این جدول همیشه مقدار ۰ را بگیرد کولِگ / گروتسک / Grotesque [صورت کولِگ] می‌گوییم.
قیاس استثنایی کولگی را نگه می‌دارد، یعنی اگر β و β⇒ς کولگ باشند آنگاه ς هم کولگ خواهد بود. همچنین می‌توان بررسی کرد و دید که همه موردهای طرح‌های بنداشتی A۱ و A۳ نیز کولگ هستند. از این رو، هر فرمولی که از A۱ و A۳ توسط قیاس استثنایی به دست آمده باشد کولگ است. با این حال،
(p۱ ⇒ (p۲ ⇒ p۳)) ⇒ ((p۱ ⇒ p۲) ⇒ (p۱ ⇒ p۳)),
که موردی از A۲ است، کولگ نیست. زیرا وقتی p۱ مقدار ۰ و p۲ مقدار ۰ و p۳ مقدار ۱ بگیرند آنگاه فرمول بالا مقدار ۲ را خواهد گرفت. بنابراین، A۲ نابسته به A۱ و A۳ است.
■ اثبات استقلال طرح بنداشت A۳
اگر فرمول h(β) که با پاک کردن تمام نمادهای نقیض در β به دست می‌آید یک توتولوژی باشد، فرمول β را برتر / Super [صورت برتر] می‌نامیم. می‌توان دید که همه موردهای طرح‌های بنداشتی A۱ و A۲ دارای ویژگی برتری هستند. قیاس استثنایی ویژگی برتری را حفظ می‌کند. چرا که اگر:
h(β ⇒ ς) و h(β)
توتولوژی باشند آنگاه h(ς) نیز توتولوژی است. [توجه کنید که h(β⇒ς) همان h(β)⇒h(ς) است. از این و بنا بر بند ۸ نتیجه می‌شود که h(ς) توتولوژی است.] از این رو، هر فرمولی که از A۱ و A۲ توسط قیاس استثنایی به دست آمده باشد برتر است. با این حال،
h((¬p۱ ⇒ ¬p۱) ⇒ ((¬p۱ ⇒ p۱) ⇒ p۱))
که می‌شود:
(p۱ ⇒ p۱) ⇒ ((p۱ ⇒ p۱) ⇒ p۱)
یک توتولوژی نیست. بنابراین
(¬p۱ ⇒ ¬p۱) ⇒ ((¬p۱ ⇒ p۱) ⇒ p۱)
که موردی از A۳ است یک برتر نیست و نمی‌تواند از A۱ و A۲ با کارزدن قیاس استثنایی به دست آید.
■ منطق‌های چند ارزشی
تدبیری که در اثبات استقلال طرحواره‌های بنداشتی A۱ و A۲ استفاده شد، می‌تواند به مفهوم منطق‌های چند ارزشی تعمیم داده شود.
روند چنین تعمیم به قرار زیر است:
آ- عدد صحیح مثبت n را انتخاب کنید، اعداد ۰، ۱، …، n را مقدار سمانتیکی بنامید.
ب- عدد m را طوری انتخاب کنید که ۰≤m<n باشد.
ج- هر یک از اعداد ۰، ۱، …، m را یک مقدار گزیده (designated value) بنامید.
د- تعداد متناهی "جدول ارزش" را که نشان‌دهنده توابع با مجموعه‌های آغازی و انجامی مطابق،
{۰, ۱, …، n}k↜↦ {۰, ۱, …، n}
هستند، در نظر بگیرید.
ه- برای هر جدول ارزش، یک نماد به عنوان رابط نظیر به آن جدول معرفی کنید.
اکنون با استفاده از این رابط‌ها و حروف گزاره‌ای، می‌توانیم «صورت‌های گزاره‌ای» بسازیم. هر چنین صورت گزاره‌ای که دربردار j حرف متمایز باشد، یک «تابع ارزش»،
از {۰, ۱, …، n}k در {۰, ۱, …، n}
را تعیین می‌کند. به صورت‌های گزاره‌ای که تابع ارزش متناظر آن فقط به مقادیر گزیده برآورد می‌شود صورت استثنایی گفته می‌شود.
■ منطق چند ارزشی ℳ
اعداد m و n و جداول ارزش پایه‌ای یک منطق چند ارزشی ℳ (متناهی) را تعریف می‌کنند. اکنون می‌گوییم:
یک نظریه صوری شامل حروف گزاره‌ای و رابط‌های موجود در ℳ برای ℳ یک نظریه صوری سازوار (suitable) است اگر و فقط اگر قضایای نظریه با صورت‌های گزاره‌ای استثنایی در ℳ موافق (coincide) باشند.
آشکارا همه این انگاره‌ها را می‌توان به تعداد نامتناهی از مقادیر ارزش تعمیم داد. اگر n=۱ و m=۰ جداول ارزش آنهایی هستند که برای ¬ و ⇒ دیده‌ایم است، آنگاه منطق دو ارزشی نظیر همان چیزی است که تاکنون به آن پرداخته‌ایم. فرمول‌های استثنایی در این منطق، توتولوژی نامیده شده‌اند. همانطور که در بندهای ۸ و ۱۰ نشان داده شده است، دستگاه 𝓛 برای این منطق سازوار است.
سرانجام، همانطور که دیدیم نیز برای اثبات استقلال طرحواره‌های بنداشتی A۱↝ و A۲↝ از دو منطق متفاوت سه ارزشی استفاده شده است.
■ تمرین *
* ۵۱.۱ استقلال طرحواره A۳ را با ساختن جدول ارزش مناسب برای ⇒ و ¬ ثابت کنید.
حل.
(Deborah Moll) از دو مقدار ارزش استفاده کنید. جدول ارزش ⇒ را طبق معمول بگیرید و تعبیر ¬ را تابع ثابت F (نادرست) فرض کنید. در این صورت وقتی B دارای مقدار F است آنگاه:
(¬B ⇒ ¬A) ⇒((¬B ⇒ A) ⇒ B)
به مقدار F تعبیر خواهد شد.
* ۵۲.۱ نظریه بنداشتی P را در نظر بگیرید که در آن دقیقاً یک رابط دوتایی * وجود دارد. تنها قاعده استنتاج P قیاس استثنایی (یعنی ς از β و β*ς به دست می‌آید) است، و بنداشت‌ها همگی فرمول‌هایی از صورت β*β هستند. نشان دهید که P برای هیچ منطق چند ارزشی (متناهی) سازوار نیست.
حل.
قضایای P همان بنداشت‌ها هستند. فرض کنید که P برای برخی از منطق n-ارزشی سازوار است. پس، برای همه مقادیر k مقدار k*k یک مقدار از پیش معین خواهد بود. دنباله فرمول‌های
B۰ = A,
Bj+۱ = A * Bj.
را در نظر بگیرید. از آنجایی که nn تابع ارزش ممکن از یک متغیر وجود دارد، در بین
β۰, …, βn
باید دو فرمول مختلف βj و βk وجود داشته باشد که تابع ارزش یکسانی را تعریف می‌کنند. از این رو، βk*βj یک فرمول استثنایی خواهد بود که یک قضیه نیست.
* ۵۳.۱ نشان دهید برای هر منطق چند ارزشی (متناهی) M، یک نظریه بنداشتی سازوار برای M وجود دارد.
حل.
همه فرمول‌های استثنایی را به عنوان بنداشت و تابع اینهمانی را به عنوان تنها قاعده استنتاج در نظر بگیرید.
اطلاعات بیشتر در باره منطق‌های چند ارزشی را می‌توان در منابع زیر یافت:
۱- Rosser and Turquette (1952),
۲- Rescher (1969)
۳- Bolc and Borowik (1992),
۴- Malinowski (1993).
