نظریه اصل موضوعی منطق گزاره‌ای ۲

منطق و فرامنطق

درآمد به منطق


روند استواری، تمامیت و سازگاری دستگاه 𝓛

۱- سرآغاز

۵- نتیجه

۲- استواری نظریه 𝓛

۶- سازگاری نظریه 𝓛.

۳- (لم). پیش قضیه تمامیت

۷- تمرین *

۴- تمامیت نظریه 𝓛

■ سرآغاز

در قسمت پیشین↝ (قسمت یکم - معرفی 𝓛) دستگاه صوری 𝓛 را معرفی کردیم و چندین قضیه، از جمله قضیه استنتاج، را در آن ثابت کردیم. افزون بر این، با نحوه کار در تئوری 𝓛 آشنا شدیم.

در این یادداشت، یعنی قسمت دوم، به اثبات استواری، تمامیت(↝↝) و سازگاری(↝↝)  𝓛 می‌پردازیم.

منبع و مرجع اصلی ما در چهار قسمت «نظریه اصل موضوعی منطق گزاره‌ای» متن:

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 خواهیم داشت:

لم g.۱۱.۱ ( p'k ⇒ β) ⇒ ((¬p'k ⇒ β) ⇒ β)۱
۱، 'a و M.P(¬p'k ⇒ β) ⇒ β۲
۲، 'b و 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.۱۱.۱ داریم:

⊢ ¬β ⇒ (β ⇒ ς).

اصل  انفجار در منطق –Explosion principle in logic

بنابراین، اگر 𝓛 ناسازگار بود، یعنی اگر فرمولی مانند β و نقیض آن ¬β وجود داشت که هر دو قابل اثبات بودند، آنوقت با دو بار کارزدن M.P می‌رسیدیم به اینکه هر فرمول ς اثبات شدنی است.

(آنچه گفته شد در هر نظریه که قیاس استثنایی به عنوان یک قاعده استنتاج حاضر باشد و c.۱۱.۱ اثبات شدنی باشد، برقرار است.) (منطق‌های فراسازگار را ببینید.)

به نظریه‌ای که در آن همه فرمول‌ها قضیه نیستند مطلقاً سازگار↝ می‌گویند، و این تعریف حتی برای نظریه‌هایی که دارای نماد نقیض هم نیستند برقرار است.


■ تمرین *

(۱.۵۰) فرض کنید β یک صورت گزاره‌ای باشد که توتولوژی نیست. نیز فرض کنید 𝓛+ نظریه صوری به دست آمده از 𝓛 با اضافه کردن به عنوان اصول موضوع جدید همه فرمول‌های قابل دستیابی از β با جایگزین کردن صورت‌های گزاره‌ای دلخواه به جای حروف گزاره‌ای در β باشد، به صورتی که جایگزین همه موارد یک حرف گزاره‌‌‌ای شود. نشان دهید که 𝓛+ ناسازگار است.

• حل:

(ص.۴۲۱) تعبیری (گمارش مقادیر ارزش به حروف گزاره‌ای) از β را در نظر بگیرید که β تحت آن نادرست است. در این تعبیر هر جا یک حرف گزاره‌ای مقدار ارزش درست دارد آن را با p۱∨¬p۱ جایگزین کنید و هر جا یک حرف گزاره‌ای مقدار ارزش نادرست دارد  آن را با p۱∧¬p۱ جایگزین کنید. صورت گزاره‌ای حاصل را ς بنامید. بنابراین ς یک اصل موضوع 𝓛+ است و داریم:

⊢𝓛+ ς.

توجه کنید که ς تحت هر تعبیر نادرست است. پس ¬ς یک توتولوژی است. بنابراین:

⊢𝓛+ ¬ς.


◄ توجه: