نظریه اصل موضوعی منطق گزارهای ۲
منطق و فرامنطق
درآمد به منطق
استواری، تمامیت و سازگاری دستگاه 𝓛
۱- سرآغاز | ۵- نتیجه |
۲- استواری نظریه 𝓛 | ۶- سازگاری نظریه 𝓛. |
۳- (لم). پیش قضیه تمامیت | ۷- تمرین * |
۴- تمامیت نظریه 𝓛 |
■ سرآغاز
در قسمت پیشین↝ (قسمت یکم - معرفی 𝓛) دستگاه صوری 𝓛 را معرفی کردیم و چندین قضیه، از جمله قضیه استنتاج، را در آن ثابت کردیم. افزون بر این، با نحوه کار در تئوری 𝓛 آشنا شدیم.
در این یادداشت، یعنی قسمت دوم، به اثبات استواری، تمامیت(↝↝) و سازگاری(↝↝) 𝓛 می‌پردازیم.
منبع و مرجع اصلی ما در چهار قسمت «نظریه اصل موضوعی منطق گزارهای» متن:
Mendelson, Elliott. Introduction to mathematical logic. 6th, ed, CRC Press, Taylor & Francis Group. 2015.
است.
■ استواری نظریه 𝓛. هر قضیه در 𝓛 یک توتولوژی↝ است.
[لم.۱۲.۱] به آسانی می‌توان بوسیله جدول ارزش نشان داد همه بنداشت‌های در نظریه 𝓛 توتولوژی هستند. برای نمونه، جدول ارزش آمده در زیر نشان می‌دهد A1 یک صورت توتولوژیک است:
| α | β | β ⇒ α | A1: α ⇒ (β ⇒ α) |
| د | د | د | د |
| د | ن | د | د |
| ن | د | ن | د |
| ن | ن | د | د |
افزون بر این، می‌توان نشان داد↝ که اگر α و α⇒β توتولوژی باشند، β نیز توتولوژی خواهد بود. بنابراین، قیاس استثنایی توتولوژی‌ها را به توتولوژی‌های دیگر روانه می‌کند. از این رو، هر قضیه 𝓛 یک توتولوژی است.
■ پیش قضیه تمامیت
[لم.۱۳.۱] گیریم β یک فرمول باشد و p۱, p۲, ...,pk حروف گزارهای باشند که در β روی داده‌اند. برای تعبیر داده شده‌ای (یعنی، یک گمارش مقادیر ارزش به همه حروف گزارهای β) اگر در این گمارش مقدار ارزش pj درست باشد آنگاه p'j را pj گرفته؛ و اگر مقدار ارزش pj در این تعبیر نادرست باشد آنگاه p'j را ¬pj می‌گیریم. در این صورت داریم،
p'۱, p'۲, ...,p'k ⊢ β'■
** اثبات بعد از مثال **
مثال: فرض کنید β فرمول زیر باشد،
¬(¬p۲ ⇒ p۵).
جدول ارزش β به قرار زیر است:
| استنتاج به درست آمده از کارزدن لم ۱۳.۱ به فرمول ¬(¬p۲ ⇒ p۵) | ¬(¬p۲ ⇒ p۵) | p۵ | p۲ | |
| p۲, p۵ ⊢ ¬¬(¬p۲ ⇒ p۵) | ن | د | د | ۱ |
| ¬p۲, p۵ ⊢ ¬¬(¬p۲ ⇒ p۵) | ن | د | ن | ۲ |
| p۲, ¬p۵ ⊢ ¬¬(¬p۲ ⇒ p۵) | ن | ن | د | ۳ |
| ¬p۲, ¬p۵ ⊢ ¬(¬p۲ ⇒ p۵) | د | ن | ن | ۴ |
☚: از این پیش قضیه (۱۳.۱) برمی‌آید که برای هر تعبیر یک فرمول، یک استنتاج نظیر (رابطه استنتاجی نظیر) وجود دارد.
اثبات:
اثبات را با استقرا روی n (یعنی، تعداد رویداد ¬ و ⇒ در فرمول β) پیش می‌بریم. (فرض می‌کنیم β کوتاه شده برای رابط‌های ∧، ∨ و ≡ نوشته شده است.)
• گام نخست استقرا
اکر n = ۰ آنگاه β فقط شامل یک حرف گزارهای مانند p۱ است و در این حالت پیش قضیه به:
p۱ ⊢ p۱ و ¬p۱ ⊢ ¬p۱
کاهش می‌یابد.↝
• گام دوم: فرض استقرا پیش قضیه برای j<n برقرار است.
حالت ۱: β دارای شمای ¬ς است. در این صورت تعداد رویدادهای رابط‌های ¬ و ⇒ در ς کمتر از n است. در این حالت:
حالت فرعی 𝒶.۱:
فرض کنید ς در گمارش مقادیر ارزش به حروف گزارهای درست برآورده شده است. بنابراین، مقدار β نادرست خواهد بود. پس (طبق روند تعریف شده در صورت پیش قضیه)، ς' عبارت است از ς و β' عبارت است از ¬β. با کار زدن فرض استقرا به ς داریم،
p'۱, . . ., p'k ⊢ ς.
با استفاده از لم b.۱۱.۱ [¬¬β⇒β] و M.P داریم،
p'۱, . . ., p'k ⊢ ¬¬ς.
اما ¬¬ς همان β' است. بنابراین:
p'۱, . . ., p'k ⊢ β'.
حالت فرعی 𝒷.۱:
فرض کنید ς مقدار نادرست را در گمارش مقادیر ارزش بگیرد. بنابراین، β مقدار درست می‌گیرد. پس ς' عبارت خواهد شد از ¬ς و β' عبارت خواهد شد از β. از فرض استقرا داریم:
p'۱, . . ., p'k ⊢ ¬ς.
اما ¬ς همان β' است.
حالت ۲: β به شمای ς ⇒ δ است. در این صورت تعداد رویدادهای رابط‌های ¬ و ⇒ در ς و δ کمتر از n است. در این حالت:
حالت فرعی 𝒶.۲:
فرض کنید ς مقدار نادرست برآورد شده است. پس، β مقدار درست را می‌گیرد. بنابراین، ς' عبارت است از ¬ς و β' عبارت است از β است. بنابراین،
p'۱, . . ., p'k ⊢ ¬ς.
با استفاده از c.۱۱.۱ [¬β⇒(β⇒ς)]،
p'۱, . . ., p'k ⊢ ς ⇒ δ.
اما ς ⇒ δ همان β' است.
حالت فرعی 𝒷.۲:
δ مقدار درست می‌گیرد. پس، β هم مقدار درست را خواهد گرفت. بنابراین، δ' همان δ است و β' نیز β است. از اینجا داریم:
p'۱, . . ., p'k ⊢ δ.
اکنون از M.P و A1 خواهیم داشت:
p'۱, . . ., p'k ⊢ ς ⇒ δ.
اما ς ⇒ δ همان β' است.
حالت فرعی 𝒸.۲:
ς مقدار درست می‌گیرد و δ مقدار نادرست می‌گیرد. پس، β مقدار نادرست را خواهد گرفت. بنابراین، ς' همان ς است و δ' نیز ¬δ و β' نیز ¬β است. از اینجا داریم:
p'۱, . . ., p'k ⊢ ς
و
p'۱, . . ., p'k ⊢ ¬δ.
اکنون از f.۱۱.۱ [β⇒(¬ς⇒¬(β⇒ς))] و M.P خواهیم داشت:
p'۱, . . ., p'k ⊢ ¬(ς ⇒ δ).
اما ¬(ς ⇒ δ) همان β' است.
■ تمامیت نظریه 𝓛: اگر فرمولی در 𝓛 توتولوژی↝ باشد، آنگاه آن فرمول یک قضیه 𝓛 است.
[۱۴.۱] اثبات: ( 1935, Kalmár_35)☚↧
• Mendelson, Elliott. Introduction to mathematical logic. 6th,ed, CRC Press, Taylor & Francis Group. 2015.
•
• Kalmár, L. (1935) Über die Axiomatisierbarkeit des Aussagenkalküls. Acta Sci. Math., 7, 222–243.
فرض کنیذ β یک توتولوژی و p۱, p۲, ...,pk حروف گزارهای آن باشند. بنا بر لم ۱۳.۱ برای هر تعبیری (هر گمارش مقادیر ارزش به همه حروف گزارهای β) داریم:
p'۱, p'۲, ...,p'k ⊢ β.
[از آنجاکه β یک توتولوژی است و مقدار ارزش آن برای هر تعبیر درست است، β' همان β است.]
بنابراین:
روند A:
وقتی در تعبیری مقدار گمارده به p'k درست باشد داریم:
a. p'۱, p'۲, ..., p'k-۱, p'k ⊢ β.
و وقتی در تعبیری مقدار گمارده به p'k نادرست باشد داریم:
b.p'۱, p'۲, ..., p'k-۱, ¬p'k ⊢ β.
از کارزدن قضیه استنتاج به ترتیب به ۱ و ۲ در بالا می‌نویسیم:
a'.p'۱, p'۲, ..., p'k-۱ ⊢ p'k ⇒ β,
b'.p'۱, p'۲, ..., p'k-۱ ⊢ ¬ p'k ⇒ β.
اکنون از لم g.۱۱.۱ و M.P خواهیم داشت:
بنابراین، می‌توان نوشت:
b.p'۱, p'۲, ..., p'k-۱ ⊢ β.
اکنون به همان شیوه روند A می‌گوییم می‌توان p'k-۱ را درست یا نادرست برگزید و با استفاده از قضیه استنتاج و M.P می‌توانیم همانگونه که p'k را حذف کردیم p'k-۱ را نیز حذف کنیم و داشته باشیم:
p'۱, p'۲, ..., p'k-۲ ⊢ β.
بنابراین و در کل، با k بار اجرای روند A می‌رسیم به:
⊢ β.
و در اینجا اثبات قضیه تمامیت به پایان می‌رسد.■
■ نتیجه
[۱۵.۱] گیریم ς یک عبارت باشد که شامل نمادهای ¬، ⇒، ∨، ∧ و ⇔ است به گونه‌ای که (ς) کوتاه شده فرمول β در 𝓛 باشد. در این صورت، ς یک توتولوژی است اگر و تنها اگر β یک قضیه 𝓛 باشد.
در تعریف‌های ↜(D۱)–(D۳)، فرمول‌های اختصاری جایگزین فرمول‌هایی می‌شوند که هم‌ارز منطقی هستند. از این رو، بنا بر قضیه تمامیت β و ς هم‌ارز منطقی هستند، و ς یک توتولوژی است اگر و تنها اگر β یک توتولوژی باشد. نتیجه اکنون نتیجه مورد نظر از قضیه‌های ۱۲.۱ و ۱۴.۱ به دست می‌آید.
■ سازگاری نظریه 𝓛.
[۱۶.۱] دستگاه 𝓛 سازگار↝ است، یعنی فرمول β وجود ندارد به قسمی که β و ¬β هر دو قضیه‌های 𝓛 باشند.
اثبات:
از قضیه ۱۲.۱ (استواری) داریم هر قضیه 𝓛 یک توتولوژی است. نقیض توتولوژی نمی‌تواند توتولوژی باشد و بنابراین غیرممکن است که β و ¬β هر دو قضیه‌های 𝓛 باشند.
توجه کنید که 𝓛 در صورتی سازگار است که تنها و فقط تنها اگر همه فرمول‌های آن قضیه نباشند. در واقع، اگر 𝓛 سازگار باشد، فرمولی‌هایی وجود دارند که قضیه نیستند (به عنوان مثال، نقیض قضیه‌ها).
از دیگر سوی، از c.۱۱.۱ داریم:
⊢ ¬β ⇒ (β ⇒ ς).
بنابراین، اگر 𝓛 ناسازگار بود، یعنی اگر فرمولی مانند β و نقیض آن ¬β وجود داشت که هر دو قابل اثبات بودند، آنوقت با دو بار کارزدن M.P می‌رسیدیم به اینکه هر فرمول ς اثبات شدنی است.
(آنچه گفته شد در هر نظریه که قیاس استثنایی به عنوان یک قاعده استنتاج حاضر باشد و c.۱۱.۱ اثبات شدنی باشد، برقرار است.) (منطق‌های فراسازگار را ببینید.)
به نظریه‌ای که در آن همه فرمول‌ها قضیه نیستند مطلقاً سازگار↝ می‌گویند، و این تعریف حتی برای نظریه‌هایی که دارای نماد نقیض هم نیستند برقرار است.
■ تمرین *
(۱.۵۰) فرض کنید β یک صورت گزارهای باشد که توتولوژی نیست. نیز فرض کنید 𝓛+ نظریه صوری به دست آمده از 𝓛 با اضافه کردن به عنوان اصول موضوع جدید همه فرمول‌های قابل دستیابی از β با جایگزین کردن صورت‌های گزارهای دلخواه به جای حروف گزارهای در β باشد، به صورتی که جایگزین همه موارد یک حرف گزارهای شود. نشان دهید که 𝓛+ ناسازگار است.
• حل:
(ص.۴۲۱) تعبیری (گمارش مقادیر ارزش به حروف گزارهای) از β را در نظر بگیرید که β تحت آن نادرست است. در این تعبیر هر جا یک حرف گزارهای مقدار ارزش درست دارد آن را با p۱∨¬p۱ جایگزین کنید و هر جا یک حرف گزارهای مقدار ارزش نادرست دارد آن را با p۱∧¬p۱ جایگزین کنید. صورت گزارهای حاصل را ς بنامید. بنابراین ς یک اصل موضوع 𝓛+ است و داریم:
⊢𝓛+ ς.
توجه کنید که ς تحت هر تعبیر نادرست است. پس ¬ς یک توتولوژی است. بنابراین:
⊢𝓛+ ¬ς.
