≡
فهرست:
۱.۰روند منطق نوین
۱.۱روند
۲.۱روند کارآمد
۳.۱تصمیم پذیری
آزبان و فرازبان
۱.آزبان صوری
۲.آمعرفی زبان صوری LC
۳.آزبان شاهد و زبان موضوع
۴.آمتغیرهای نحوی
۵.آصورت گزاره‌ای و فرمول
بتعبیر
۱.بخیلی کوتاه درباره نظریه‌های معنا
۲.بتعبیر زبان LC
۳.بمدل و فرمول
۴.بمجموعه فرمول و مدل آن
۵.بصورت توتولوژیک
۶.بصورت نامعتبر
۷.بصورت متناقض
۸.بصدق پذیری و سازگاری معنایی
۹.برابطه استلزام منطقی
۱.۹.برابطه هم‌ارزی منطقی
۱۰.بآزمون اعتبار یک استنتاج سمانتیکی
۱۱.بچند نتیجه
۱۲.بکارآمدی استنتاج سمانتیکی
جبنای دستگاه استنتاج طبیعی
۰.جمقدمه
۱.۰.جزندگی‌نامه کوتاه گرهارد گنتزن
۱.جاستنتاج
۲.جخاصیت این‌همانی
۳.جهم‌ارزی نحوی
۴.جقاعده جایگزینی نحوی
۵.جاثبات اعتبار استنتاج نحوی
۶.جناسازگاری نحوی
۷.جقضیه در دستگاه استنتاجی
۱.۷.جتعریف قضیه در دستگاه استنتاجی
۸.جقاعده برهان شرطی
۹.جمثال قضیه
دفرامنطق
۰.دمقدمه
۱.داستواری دستگاه CND
د.۱.۰طرح سردستی اثبات فرا-قضیه استواری
۲.دتمامیت دستگاه CND
۳.داستواری و تمامیت
د.۳.۱زندگی‌نامه مختصر لایبنیتس
۴.دصدق منطقی
۵.دسازگاری دستگاه:CND
۶.د(فرا)قضیه  ناتمامیت
۷.دتصمیم پذیری دستگاه CND
دستگاه صوری استنتاج - درآمدی به منطق درآمدی یه منطق

دستگاه صوری استنتاج

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

 درآمد به منطق

روند ۴. دستگاه صوری استنتاج

ج■ مقدمه

در قسمت قبل در مثال‌های ۱، ۲ و ۳ به ترتیب نشان دادیم:

مثال.۱- (p⊃q)⊩(~q⊃~p) یک استنتاج معتبر سمانتیکی است.

مثال.۲- p⊃(q⊃r), p⊃(q⊃r)⊩(p∨q)⊃r یک استنتاج سمانتیکی نامعتبر است.

مثال.۳- ((p•q)⊃r))⊩((p⊃r)∨(q⊃r)) یک استنتاج سمانتیکی معتبر است.

آن‌طور که دیدیم، روند اثبات در مثال‌های بالا بدین قرار بود که، نشان دهیم هر تعبیر که برای مقدمات مدل است برای نتیجه نیز مدل است و برای خلاف آن بدین قرار که، نشان دهیم دست‌کم یک تعبیر وجود دارد که برای مقدمات مدل است ولی برای نتیجه مدل نیست (مثال ۲). ازاین‌جهت، این‌گونه روند گسترش به نظریه مبتنی بر مدل [نیز معناشناختی مبتنی بر مدل] موسوم است که در آن واژه بنیاد بر تعبیر (مدل) است. در این قسمت بر آنیم تا برای مثال (~q⊃~p) را از (p⊃q) نه در یک روند تعبیری که در یک روند نحوی (لفظی) به دست آوریم نماییم (اشتقاق نحوی). این روند به نظریه برهان (برهان شناختی / نظریه مبتنی بر برهان / معناشناختی مبتنی بر نظریه برهان] موسوم است.

درواقع، این روند بر این فرض‌ بنیادی استوار است که مفهوم اصلی، ازاین‌جهت که چه معنایی به عبارت‌های زبان (در اینجا LC) نظیر شود، همانا به‌جای تعبیر، برهان خواهد بود. به‌عبارت‌دیگر، در این روند برهان صوری اعتبار بجای تعبیر خواهد نشست. بنابراین، در این قسمت آنچه از تعبیر، به شمول مقدار معنایی، مدل و جدول ارزش گفته موقتاً به کنار نهاده و آنچه خواهیم داشت زبان صوری و فرمول است و بس➥.

آنچه خواهد آمد هم‌اکنون در فصل ده کتاب، قسمت ۷، دستگاه استنتاجی، بر پایه زبان نمادین LC به‌تفصیل گسترانده شده. در ادامه، آنچه گسترانده شده را موجز و کمی متفاوت مرور می‌کنیم. این دستگاه، که به شمول مفاهیمی چون قواعد استنتاج، برهان صوری، افزونگی و کارآمدی است، را از این‌پس دستگاه CND [برای:Copi's Natural Deduction] خواهیم نامید.

برای یادآوری، در جدول ۱ در زیر نه قاعده استنتاج آمده است.

فرض کنید: f مجموعه فرمول‌های LC باشد. یک قاعده استنتاج نحوی [یا فقط قاعده استنتاج] در یک دستگاه نحوی، یک رابطه به صراحت تعریف‌شده بین فرمول‌ها (یعنی، f) و مجموعه‌های فرمول (یعنی، مجموعه توانی f) است، به قسمی که، بتوان تصمیم گرفت آیا هر فرمول در این رابطه با هر مجموعه فرمول دلخواه (یعنی، هر عضو دلخواه مجموعه توانی f) است یا نه؟ بنابراین هر قاعده استنتاج یک رابطه تصمیم پذیر است.

۹ قاعده استنتاج نحوی
~β, α ⊃ β
 —————R۲
~α		۲.α , α ⊃ β
———————R۱
β		۱.
(α∨β ) , ~α
———————R۴
β		۴.(α ⊃ β), (β ⊃ γ)
—————————R۳
α ⊃ γ		۳.
α ⊃ β
 ———————R۶
α ⊃ (α • β)		۶.(α ⊃ β)•(γ ⊃ λ), (α∨γ )
————————————R۵
β∨λ		۵.
α , β
————R۸
α • β		۸.α • β
————R۷
α		۷.
α
————R۹
α∨β		۹.

■ گرهارد گنتسن - Gerhard Gentzen

بر آن بودم تا فرمالیسمی بنا کنم هر چه بیشتر نزدیک به استدلال، آن‌گونه که هست. این بود که حساب استنتاج طبیعی به وجود آمد. __گرهارد گنتزن Gerhard Gentzen, "Investigations into Logical Deduction", American Philosophical Quarterly, Vol. 1, No. 4 (Oct., 1964), pp. 288-306

زندگی‌نامه

Gerhard Gentzen

گرهارد گنتسن (Gerhard Gentzen - ۱۹۴۵-۱۹۰۹) ریاضیدان و منطقی آلمانی در برگن (شهری واقع در جزیره روگن آلمان) پا به دنیا گشود. پدر وی که یک حقوق‌دان بود در جنگ جهانی اول کشته شد. وی در ۱۹۲۸ تحصیلات متوسطه را به پایان برد و از همان موقع توان استثنایی وی در ریاضیات آشکار گردید. تحصیل ریاضیات را از سال ۱۹۲۸ به ترتیب در دانشگاه‌های گریفزوالد(Greifswald) گوتینگن، برلین و مونیخ ادامه داد. سرانجام در ۱۹۳۳ از دانشگاه گوتینگن دکتری خود را دریافت کرد. پس از مدتی استراحت برای بازیابی سلامت به‌عنوان دستیار هیلبرت در دانشگاه کوتینگتن به کار ادامه داد. گنتزن به‌ویژه همکار اصلی هیلبرت در برنامه اصل موضوعی کردن ریاضیات بود. ازجمله کارهای وی معرفی دستگاه‌های استنتاج طبیعی (Natural deduction systems) و دستگاه حساب دنبالک‌ها (Sequent calculus systems) است.

گرهارد گنتسن(Gerhard Gentzen - ۱۹۴۵ - ۱۹۰۹

گنتزن در زمان جنگ دوم به‌عنوان مدرس در مؤسسه ریاضی دانشگاه آلمانی پراگ در چک مشغول کار شد ودر روزهای پایانی جنگ در اعتراض مردم پراگ به اشغال، همراه با سایر اعضای آلمانی دانشگاه دستگیر و ۴ روز بعد از دستگیری و آمدن روس‌ها به آنان تحویل شد. وی که سابقه حمایت از نازی‌ها را داشت تحت شرایط بدی در بازداشت روس‌ها باقی ماند و سه ماه بعد به علت سوءتغذیه درگذشت. — برگرفته از:

http://www-history.mcs.st-andrews.ac.uk/Biographies/Gentzen.html

دو مقاله از گنتسن:
پژوهش‌های استنتاج منطقی I؛
پژوهش‌های استنتاج منطقی II. ➥

ج■ مرور چند تعریف

■ استنتاج و برهان

Turnstile

گیریم S={α۱, α۲, . . ., αn} یک مجموعه فرمول‌ باشد. گوییم فرمول β در دستگاه CND از S دست آوردنی [همچنین:β نتیجه استنتاجی S، یا β نتیجه برهانی S، یا β نتیجه نحوی S] است و نوشته:

(آ'): S ⊢CNDβ

اگر و فقط اگر دنباله متناهی فرمول‌های:

(ب'): <β۱, β۲, . . ., βm>

وجود دارد، به قسمی که؛

۱- هر عضو این دنباله متعلق به S یا در رابطه با یکی از قواعد استنتاج و زیرمجموعه‌ای از عناصر قبلی‌ دنباله باشد؛
و بعلاوه
۲- βm همان β باشد.

می‌توان در S ⊢β به‌جای S اعضای آن را فهرست کرد و نوشت:

α۱, α۲, . . ., αn ⊢CNDβ

به (آ') در بالا یک استنتاج معتبر نحوی [یا فقط استنتاج] و به دنباله β۱, β۲, . . .,βm یک برهان در دستگاه CND گفته می‌شود. بعلاوه به مجموعه S مقدمان استنتاج می‌گویند.

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

وقتی نام دستگاه استنتاجی موردبحث از زمینه معلوم است (آ') را به‌صورت زیر می‌نویسند:

S ⊢ β

گرچه نماد '⊢' یک نماد فرازبانی (موسوم به Turnstile / گردان در) است ولی S⊢β طبق تعریف برابر با دنباله (ب') آنگونه که گفته شد است.

مراد از S, α ⊢β استنتاج S∪{α}⊢β است.

ج■ خاصیت این‌همانی: α⊢α یک استنتاج معتبر نحوی است.

اثبات:

در دنباله تک عنصری <α۱=α> آخرین عنصر، یعنی α، یک مقدمه α⊢α است. بنابراین طبق تعریف، دنباله <α> یک برهان α⊢α است. این خاصیت که نتیجه مستقیم تعریف برهان در دستگاه CND است را خاصیت این‌همانی می‌نامیم.

ج■ هم‌ارزی نحوی

صورت‌های گزاره‌ای αو β را هم‌ارزی نحوی گوییم اگر و فقط اگر α⊢β و β⊢α. در این صورت می‌نویسیم α⊢⊣β.

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

ج■ قاعده جایگزینی نحوی

اکنون قاعده جایگزینی نحوی را معرفی می‌کنیم؛ قاعده‌ای که طبق آن مجازیم از هر فرمول، فرمول حاصل از جایگزینی هر مؤلفه دلخواه آن را با هر عبارت به گونه نحوی هم‌ارز با آن مؤلفه، دست آوریم. [ب قاعده جایگزینی در کتاب مقایسه نمایید.] برای قاعده جایگزینی نحوی ۱۰ مورد کاربرد به‌عنوان هم‌ارزی‌های مقدماتی نحوی به شرح جدول زیر معرفی می‌کنیم.

هم‌ارزی‌های نحوی مقدماتی — کاربرد قاعده جایگزینی نحوی
(α∨β) ⊢⊣ (β∨α)

(α•β) ⊢⊣ (β • α)		۱۱.~(α•β) ⊢⊣ (~α∨~β)

~(α∨β) ⊢⊣ (~α • ~β)		۱۰.
[α•(β∨γ)] ⊢⊣ [(α•β)∨(α•γ)]

[α∨(β•γ)] ⊢⊣ [(α∨β)•(α∨γ)]		۱۳.[(α•β)•γ] ⊢⊣ [α•(β•γ)]

[(α∨β)∨γ] ⊢⊣ [α∨(β∨γ)] 		۱۲.
α ⊃ β ⊢⊣ ~β ⊃ ~α۱۵.α ⊢⊣ ~~α۱۴.
(α ≡ β ) ⊢⊣ [(α•β)∨(~α • ~β)]

(α ≡ β) ⊢⊣ [(α⊃β)∨(α⊃β)] 		۱۷.(α ⊃β) ⊢⊣ (~β ∨α)۱۶.
α ⊢⊣ (α∨α )

α ⊢⊣ (α • α)		۱۹.[(α • β)⊃ γ] ⊢⊣ [α ⊃ (β ⊃γ)]۱۸.
جدول ۲. ۱۰ مورد کاربرد قاعده جایگزینی

ج■ اثبات اعتبار یک استنتاج نحوی، به‌وسیله برهان است.

مثال: نشان می‌دهیم رابطه:

((p•q)⊃r)) ⊢CND ((p⊃r)∨(q⊃r))

یک استنتاج معتبر نحوی است.

مقدمه(p•q)⊃r۱.
۱ و هم‌ارزی ۱۶~(p•q)∨r۲.
۲ و هم‌ارزی ۱۰(~p∨~q)∨r۳.
۳ و هم‌ارزی ۱۳(~p∨r)∨(~q∨r)۴.
۴ و هم‌ارزی ۱۶(p⊃r)∨(q⊃r)۵.

ج■ ناسازگاری نحوی

گوییم دستگاه CND یک دستگاه صوری ناسازگار است اگر و فقط اگر در آن فرمول β وجود داشته باشد، به قسمی که β از {~β} دست آمدنی است، یعنی داشته‌ باشیم: {~β} ⊢β. در غیر این صورت CND را دستگاه صوری سازگار گوییم.

ج■ انفجار استنتاج

گیریم دستگاه CND ناسازگار؛ در این صورت فرمول β هست که از ~β دست آمدنی است. اما بنا بر R۹ و R۳ فرمول β∨x که در آن x فرمول دلخواه است نیز از ~β دست آمدنی است. اما از β∨x و ~β و قاعده R۴ می‌توان x را به دست آورد.

منطق فراسازگار - انفجار استنتاجی- درآمد به منطق

بنابراین، اگر دستگاه CND ناسازگار باشد آنگاه هر فرمولی دست آمدنی است. در سخن این مساله، یعنی اینکه از یک تناقض هر گزاره‌ای قابل به دست آوردن است به انفجار استنتاجی (یا اصل انفجار) موسوم است. آشکار است که چنین دستگاه استنتاجی در منطق کلاسیک (سه قانون اندیشه) دارای هیچ دیدگاه وجودی نیست و خانه از پای‌بست ویران است.

نشان دادن سازگاری دستگاه CND را در بند (د.) خواهیم دید.

ج■ منطق‌های پاراسازگار (فراسازگار)

جهان سازگار است یا سازگار نیست؟! حداقل گاهی و جایی ناسازگار می‌نماید. پرسشی که از ۱۹۷۰ توسط ریاضیدانان و فیلسوفان، نیوتون دا کاستا (Newton da Costa) گراهام پریست (Graham Priest)، به‌طور نظام‌مند و جدی پی گرفته شد و دست آوُرد آن منطق‌های موسوم به منطق‌های فراسازگار (Paraconsistent logics) بود. این منطق‌ها پذیرای ناسازگاری بگونه‌ ویژه‌ای هستند. در این منطق‌ها ناسازگاری اداره می‌شود. به عبارت دیگر، به شیوه خاص از میان ناسازگاری (یا از کنار آن / para ) گذر می‌شود.

در گونه‌ای دستگاه منطق فراسازگار موسوم به منطق گفتمانی تعبیر درستی/نادرستی به کجا یا چه هنگام بر می‌گردد. فرض کنید (آ) مدعی گزاره A~ و (ب) مدعی گزاره A~ است. در این حالت در تعبیری می‌توان گفت که A در جهان ممکن w۱ و A~ در جهان ممکن w۲ درست است. در این دستگاه آنچه در کل درست است حاصل تمام ادعاهایی است که در جهان‌های ممکن (ادعا کنندگان) ادعا شده است. بنابراین A و A~ هر دو در این تعبیر از دستگاه منطق گفتمان درست هستند. در این دستگاه اگر گزاره x در هیچ جهان ممکن درست نباشد آنگاه نادرست برآوُرد می‌گردد و چنین نیست که انفجار استنتاج روی دهد.

گونه دیگری دستگاه منطقی پاراسازگار  منطق ناافزونه‌ای نام دارد. در این دستگاه قاعده پیوست معتبر نیست و در واقع داریم:

{A , B} ⊭ A • B.

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

بیشتر را می‌توان در مدخل منطق‌های پاراسازگار در دانشنامه فلسفه استنفورد یافت. همچنین مقاله:

This paradoxical life.
When logic fails to make sense of a world noisy with inconsistency, paraconsistent logics hold out (im)possible solutions (2021).

  در نشریه Aeon خواندنی است.

ج■ قاعده برهان شرطی

قاعده برهان شرطی، به‌عنوان یک قاعده استنتاج، اجازه می‌دهد تا استنتاج با شمای ⊢α⊃β را از استنتاج معتبر نحوی با شمای α⊢β نتیجه گرفت. به عبارت دیگر:

α⊢β ⇒ ⊢α⊃β.

از اینجا به بعد از دستگاه CND به شمول قاعده برهان شرطی با CND+Cp یاد می‌کنیم.

ج■ قضیه در دستگاه استنتاجی:

به فرمول α در یک دستگاه استنتاجی یک قضیه گوییم (نیز α را در این دستگاه اثبات شدنی گوییم)، اگر α بدون هیچ مقدمه یا فرض در این دستگاه دست آوردنی باشد. به‌عبارت‌دیگر، اگر α در آن دستگاه استنتاجی نتیجه نحوی یک استنتاج با مجموعه مقدمات تهی باشد. قضیه بودن α را در دستگاه‌های استنتاجی به‌صورت {}⊢α نشان می‌دهند. همان‌طور که مشاهده می‌شود مقدمات این استنتاج یک مجموعه تهی است. ازآنجاکه یک و فقط یک مجموعه تهی وجود دارد، برای قضیه بودن فرمول α به نوشتن ⊢α بسنده می‌گردد. فرمول α را در یک دستگاه استنتاجی اثبات نشدنی گوییم) اگر α بدون هیچ مقدمه یا فرض در این دستگاه دست آمدنی نباشد.

ج■ مثال قضیه

۱- نشان می‌دهیم در دستگاه CND+Cp داریم ⊢α⊃α. به‌عبارت‌دیگر، α⊃α یک قضیه‌یِ CND+Cp است.

برهان:خاصیت این‌همانیα⊢α۱.
۱ و قاعده برهان شرطی α⊃α۲.

۲- نشان ‌دهید α⊃(β⊃α) در دستگاه CND+Cp قضیه است.

◄ توجه: