فهرست:

صورت، معنی و فرا-منطق: (گزاره‌ها)

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

 درآمد به منطق

یافتنِ آغاز بسیار دشوار است. یا بهتر است بگوییم: سخت است از ابتدا آغاز کردن. نکوشید بیشتر به عقب برگردید.
 __ TL. Wingensrein, On Certainty, 471

روند .۳ صورت، معنی و فرا-منطق: (گزاره‌ها)

۱- خیلی کوتاه درباره نظریه‌های معنا

۹- صدق پذیری و سازگاری معنایی

۲- تعبیرِ زبان LC

۱۰- رابطه استلزام منطقی

۳- فرمول و مدل آن

۱۱- لم درخت

۴- مجموعه فرمول و مدل آن

۱۲- رابطه هم‌ارزی منطقی

۵- مدل مجموعه فرمول تهی

۱۳- آزمون اعتبار یک استنتاج سمانتیکی، به‌وسیله مدل است.

۶- صورت توتولوژیک

۱۴- چند نتیجه

۷- صورت نامعتبر

۱۵- صورت و معنی در منطق قدیم (ارسطویی)

۸- صورت متناقض

۱۶- کارآمدی استنتاج سمانتیکی

■ خیلی کوتاه درباره نظریه‌های معنا

در فصل‌های ۱، ۲ و ۳ کتاب‌درآمد به منطق به‌ تفصیل به زبان طبیعی پرداخته شده است و در همان ابتدا در ۱.۲ گفته شد جملات متفاوت می‌توانند محتوای گزاره یکسانی باشند. نیز گفته شد که هر گزاره خود مدعی برقراری موردی به‌طور واقع است یا مدعی برقراری موردی به‌طور واقع نیست. بنابراین هر گزاره‌ درست (راست /true) یا نادرست (دروغ /false) است. در منطق کلاسیک به مجموعه دو عضوی {درست، نادرست} — {True, False}، {راست، دروغ}، {صادق، کاذب} یا مانند آن‌ها — مجموعه مقادیر ارزش (یا مقادیر معنایی) دوتایی و به هر عضو آن‌، یک مقدار معنایی / مقدار سمانتیکی (Semantic value) می‌گویند. در فصل ۴، تعریف چیست و کاربرد آن، نیز معنای عبارت‌های عام به‌تفصیل شرح داده شد.

برای مثال، جمله‌های "برف سفید است." و "Snow is white." را در نظر بگیرید. در این دو جمله "برف" و "Snow" هر دو به‌ طور متعارف، هم در فارسی و هم انگلیسی، بخار متراکمی هستند که به‌ شکل بلورهای یخ از ابر می‌ریزند. و همین‌طور "سفید است" ("white")، به‌طور متعارف به نگاره سفیدی [Whiteness] یا به‌عبارت‌دیگر، به تابع گزاره‌ای:

سفید_است(شیء)

یا

 White(x)

ارجاع دارد، به قسمی ‌که برای هر شیء = برف [یا x = Snow] داریم:

سفید_است(برف) = درست [یا، White(Snow) = True].

و البته چنین است که سفید_است(شیء) و White(x) دو تابع مساوی هستند.

 نظریه‌های معنا را می‌توان به دو رده به‌قرار: ۱- نظریه‌های سمانتیکی (Semantic theories)، ۲- نظریه‌های بنیادی معنا تقسیم کرد.

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

1- Speaks, Jeff, "Theories of Meaning", The Stanford Encyclopedia of Philosophy (Spring 2021 Edition), Edward N. Zalta (ed.), URL = https://plato.stanford.edu/archives/spr2021/entries/meaning/.

■ تعبیرِ زبان LC:

در فصل ۹ کتاب‌درآمد به منطق و در قسمت‌های ۲ (نمادگذاری ترکیب عطفی، نقیض و ترکیب فصلی) و ۳ (گزاره‌ شرطی) با بهره جستن از زبان طبیعی، یعنی آنچه عمدتاً در فصل‌های ۱ تا ۴ کتاب‌درآمد به منطق آمده است، مجموعه دو عضوی {درست، نادرست} همچون مجموعه مقادیر ارزش [همچنین: مقادیر معنایی یا مقادیر سمانتیکی] تعریف و تثبیت گردید. سپس کوشش شد تا صورت‌های گزاره‌ای برحسب این مقادیر تعبیر گردند.

مراد از تعبیر در زبان صوری LC یک روند کارآمد است تا بتوان با آن فرمول‌های‌ LC را به مقادیر معنایی برآوُرد. در این روند ابتدا به متغیرهای گزاره‌ای مقادیر سمانتیکی گمارده، سپس طبق قواعد معینِ تثبیت‌شده و برحسب مقادیر معنایی گمارده به متغیر‌های گزاره‌ای، مقدار معنایی فرمول‌ها برآورد گردید. تعریف ساختار جداول ارزش رابط‌ها که در کتاب‌درآمد به منطق آمده است، همان قواعد معین تثبیت ‌شده هستند.

برای مثال اگر متغیرهای گزاره‌ای LC فقط q، p و r باشند آنگاه:

تعبیر I۱ می‌تواند گمارش: درست←p، نادرست←q و درست←r؛
تعبیر I۲ می‌تواند گمارش: نادرست←p، درست←q و نادرست←r باشد.

در تعبیر I۱ مقدار معنایی صورت گزاره‌ای  (pq)⊃p بنا به تابع تعبیر (جدول ارزش) «درست» برآورد می‌گردد. این برآورد را این‌گونه:

درست((pq)p)I۱

نشان می‌دهند. و به همین ترتیب نیز می‌نویسند:

. نادرست((pq)⊃p)I۲

ازآنجاکه در هر تعبیر، کارکرد واژگان '≡' ,'~' ,'⊃' ,' '•,'∨' تعریف و تثبیت‌شده است، به آن‌ها رابط‌های منطقی [همچنین ثابت‌های منطقی، رابط جمله گانی  و واژگان منطقی ] در LC گفته می‌شود. و ازآنجاکه در هر تعبیر، به متغیرهای گزاره‌ای مقادیر سمانتیکی گمارده می‌شود، به آن‌ها واژگان نامنطقی  در LC می‌گویند.

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

■ فرمول و مدل آن:

گیریم j یک تعبیر و α فرمول باشد. گوییم j برای α مدل است (یا α در j مدل است) اگر و فقط اگر  درست=(α)j. برای مثال، تعبیر I۱ در بالا برای فرمول (pq)p مدل است. حال‌آنکه تعبیر I۲ در بالا برای همین فرمول مدل نیست.

• نتیجه:

گیریم j یک تعبیر و α فرمول باشد. j برای α مدل است اگر و فقط اگر j برای مدل نباشد.

■ مجموعه فرمول و مدل آن:

گیریم j یک تعبیر و S مجموعه فرمول:

{α۱, α۲, . . ., αn}

باشد. گوییم j برای S مدل است اگر و فقط اگر برای:

α۱α۲ . . .αn

مدل باشد. به‌عبارت‌دیگر، j به‌طور هم‌‌زمان مدل فرمول‌های α۱, α۲, . . ., αn باشد. به‌ بیان دیگر، اگر و فقط اگر تعبیری نباشد که برای فرمولی در S مدل نباشد.

■ مدل مجموعه فرمول تهی

اگرمجموعه S تهی و j یک تعبیر دلخواه باشد آنگاه فرمولی در S نیست که j برای آن مدل نباشد (چون در S فرمولی وجود ندارد که برای آن مدل نباشد (درستی تهی را ببینید.) بنابراین، هر تعبیری برای مجموعه فرمول S (وقتی S تهی است) مدل است.

 ■ صورت توتولوژیک:

یک فرمول را توتولوژی (یا صورت توتولوژیک) گوییم اگر و فقط اگر هر تعبیر آن، مدل آن نیز باشد. صورت توتولوژیک را، صورت معتبر (یا فقط معتبر) نیز می‌نامند.

■ صورت نامعتبر:

یک فرمول را نامعتبر (یا صورت نامعتبر) گوییم اگر و فقط اگر توتولوژی نباشد.

■ صورت متناقض:

یک فرمول را تناقض (یا صورت متناقض) گوییم اگر و فقط اگر مدل نداشته باشد.

■ صدق پذیری و سازگاری معنایی:

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

■ رابطه استلزام منطقی:

گیریم β فرمول و S={α۱, α۲, . . ., αn} که در آن n عدد طبیعی دلخواه است، یک مجموعه‌ فرمول باشد. گوییم بین S و β رابطه استلزام منطقی برقرار است اگر و فقط اگر هر مدل S مدل β نیز باشد - به‌عبارت‌دیگر، چنین نیست که تعبیر j باشد به قسمی که،

درست(α۱α۲ . . .αn)j= و نارست(β)j=.

رابطه استلزام منطقی را با نماد نمایش داده و وقتی رابطه استلزام منطقی بین S و β برقرار باشد می‌نوسیم:

(آ):S β

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

S β اگر و فقط اگر چنین نباشد که تعبیر j باشد به قسمی که:

درست(α۱α۲ . . .αn)j= و  نارست(β)j=.

اگر Sβ، آنگاه نیز گفته می‌شود، S منطقاً مستلزم β است و نیز، β نتیجه منطقی S است.

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

(ب): α۱, α۲, . . ., αn β

 به (ب) در بالا وقتی برقرار است یک  استنتاج معتبر سمانتیکی یا استنتاج سمانتیکی نیز گفته می‌شود.

اگر S تهی باشد، معمولاً به‌جای β فقط می‌نویسند:

β :('آ).

اگر رابطه ('آ) برقرار باشد آنگاه β توتولوژی خواد بود، زیرا با توجه به (ب).۱.۴ و تعریف استلزام منطقی، تعبیری نیست که مدل β نباشد.

پس می‌توان نوشت:

β توتولوژی است اگر و فقط اگر  β.

تعریف:

گیریم S مجموعه فرمول؛ بنابر تعریف می‌نویسیم S اگر و فقط اگر S مدل نداشته باشد.

■ لم درخت:

گیریم α فرمول و S مجموعه فرمول، آنگاه داریم:

S α S,

اثبات:

اگر S α  آنگاه تعبیری نیست که مدل S باشد و مدل αنباشد. بنابراین تعبیری نیست که مدل S باشد و در عین حال مدل هم باشد. پس بنا به (ب).۹. ۰ داریم: S, .

اگرS, ~α  آنگاه، بنابر (ب).۹. ۰، تعبیری نیست که مدل S و  باشد. اما، بنابر (ب).۱.۳. هر تعبیر که مدل S باشد مدل نخواهد بود. باشد. پس بنابر (ب).۹. ۰ داریم: S, .

■ رابطه هم‌ارزی منطقی:

گوییم فرمول‌های αو β هم‌ارز منطقی هستند اگر و فقط اگر هر مدل α مدل β نیز باشد. در این صورت می‌نویسیم:

α هم‌ارز منطقی β.

(به‌آسانی می‌توان نشان داد هم‌ارز منطقی یک رابطه هم‌ارزی است.)

■ آزمون اعتبار یک استنتاج سمانتیکی، به‌وسیله مدل است.

مثال ۱: نشان دهید: (p⊃q) (~q⊃~p)

جدول ارزش زیر نشان می‌دهد هر تعبیر که برای p⊃q مدل است برای ~q⊃~p نیز مدل است. بنابراین ~q⊃~p نتیجه منطقی ~q⊃~p است. به‌عبارت‌دیگر:

(p⊃q) (~q⊃~p)

یک استلزام منطقی معتبر است.

جدول ارزش
جدول ارزش (p⊃q) ⊩(~q⊃~p)

مثال ۲: نشان دهید: p⊃(q⊃r), q⊃(p⊃r) (p∨q)⊃r یک استنتاج سمانتیکی معتبر نیست.

جدول ارزش زیر نشان می‌دهد: حداقل یک تعبیر (I4 یا  I6) برای مقدمات مدل است ولی برای نتیجه مدل نیست

جدول ارزش
همه تعبیرهای ممکن (جدول ارزش) برای آزمون استنتاج معنایی:
{p⊃(q⊃r), p⊃(q⊃r)}(p∨q)⊃r

مثال ۳: نشان ‌دهید  I: ((p•q)⊃r)) ((p⊃r)∨(q⊃r)) یک استلزام منطقی است.

۱- فرض خلاف: I یک استلزام منطقی نیست. به عبارت دیگر، تعبیر j یافت می‌شود، به قسمی که؛

j مدل (p⊃r)∨(q⊃r) نباشد و درعین‌حال مدل (p•q)⊃r) باشد.

۲- اگر j مدل (p⊃r)∨(q⊃r) نباشد، آنگاه j نه مدل (p⊃r) و نه مدل (q⊃r) خواهد بود.

۳- اگر j مدل p⊃r نباشد آنگاه j مدل p است ولی مدل r نیست.

۴- گر j مدل q⊃r نباشد آنگاه j مدل q است ولی مدل r نیست.

۵- از۱، ۳ و ۴ داریم j مدل r و نیز مدل (p•q) است.

۶- از ۵ داریم j مدل (p•q)⊃r) است، که خلاف فرض است.

نیز می‌توان نشان داد هر مدل (p⊃r)∨(q⊃r) مدل (p•q)⊃r) نیز هست. بنابراین می‌توان نوشت:

((p•q)⊃r)) هم‌ارز منطقی ((p⊃r)∨(q⊃r)).

■ چند نتیجه:

۱- α توتولوژی است اگر و فقط اگر یک تناقض باشد.

۲- اگر α توتولوژی باشد آنگاه صدق پذیر است، ولی عکس آن می‌تواند درست نباشد (برای مثال، فرمول p صدق پذیر است اما توتولوژی نیست.)

۳- α نامعتبر است اگر و فقط اگر حداقل تحت یک تعبیر نادرست باشد.

۴- اگر α تناقض باشد آنگاه نامعتبر است، ولی عکس آن می‌تواند درست نباشد(برای مثال، p⊃~p نامعتبر اما صدق پذیر است.)

۵- رابطه (ب) برقرار است اگر و فقط اگر (α۱ α۲ . . . αn )⊃β توتولوژی باشد. ازاین‌جهت در منطق گزاره‌ای به رابطه استلزام منطقی رابطه استلزام توتولوژیک نیز گفته می‌شود.

۶- فرض کنید αβ فرمول باشد. اگر این فرمول در (برای) تعبیری مدل باشد، فرمول αβ در این تعبیر هم‌ارزی مادی است. برای مثال  p~qp~q در تعبیر j [نادرست(q)j=، درست(p)j=] هم‌ارزی مادی است. اما همین فرمول برای تعبیر i [درست(q)i=، درست(p)i=] هم‌ارزی مادی نیست.

۷- فرض کنید αβ فرمول، گوییم این فرمول یک هم‌ارزی منطقی است اگر و فقط اگر در هر تعبیر مدل باشد، به‌عبارت‌دیگر توتولوژی باشد. <<مناسب است قسمت‌های ۸ و ۹ فصل ۱۰ کتاب‌درآمد به منطق مرور شود. >>

سلسله‌مراتب فرمول
شکل ۲. بعضی نامعتبرها صدق پذیرند.

۸- α β اگر و فقط اگر αβ. گیریم αβ پس αβ توتولوژی است. ازاینجا، تعبیری نیست که مدل α باشد و مدل β نباشد. بنابراین داریم  αβ αβ و وارون آن نیز. به همین ترتیب می‌توان نوشت:

α, γ β اگر و فقط اگر α⊃(γβ).

بند د: استدلال، گزاره‌های شرطی و توتولوژی را ببینید.

■ صورت و معنی در منطق قدیم (ارسطویی)

در نزد ارسطو و منطق (قدیم) صورت/Form و صوری/Formal متفاوت از صورت، صوری و معنی در منطق جدید است. در منطق ارسطویی هیچ تفکیک روشنی بین صورت و معنا وجود ندارد. نزد ارسطو صورت و صوری واژه‌ای متافیزیکی و نه منطقی و بحث آن نیز در مبحث متافیزیک (ماده و صورت) است.

Ainsworth, Thomas, "Form vs. Matter", The Stanford Encyclopedia of Philosophy (Summer 2020 Edition), Edward N. Zalta (ed.), URL = https://plato.stanford.edu/archives/sum2020/entries/form-matter/.

معنا یا سمانتیک در منطق ارسطو به محتوای واقعی یا موضوع استدلال اشاره دارد. این شامل مفاهیم، ایده‌ها و گزاره‌هایی است که در مورد آنها استدلال می شود. ارسطو بر این باور است که آنچه می‌توانیم «صحت متافیزیکی» بنامیم، شکل علمی دقیق‌تری از بیان منطقی ایجاد می‌کند. او دیدگاهی همه جانبه و از جمله متافیزیکی به منطق دارد و در عین حال معتقد است که این «صحت متافیزیکی» (Metaphysical correctness) به گزاره های درست منجر می شود.

Louis F. Groarke. Internet encyclopedia of internet. URL = https://iep.utm.edu/aristotle-logic#H3"

■ کارآمدی استنتاج سمانتیکی: 

روند تعبیر در منطق گزاره‌ها یک روند کارآمد است. به این معنی که روش جدول ارزش، روندی را در اختیار می‌گذارد که به‌وسیله اجرای آن، ماشین می‌تواند درباره اعتبار یک استنتاج سمانتیکی دلخواه تصمیم‌گیری و پاسخ آری یا نه را در زمان محدود ارائه کند. اما این روند گرچه کارآمد است (در زمان محدود به پایان می‌رسد) ولی کارآمدی آن کارآمدی چندجمله‌ای نیست یعنی، میانگین نسبت رشد زمان مصرفی توسط اجرای ماشینی این روند نسبت به رشد تعداد ورودی‌ها (متغیرهای گزاره‌ای متمایز در استنتاج معنایی) نمایی و نه چندجمله‌ای [فصل.۹، قسمت.۷ کتاب‌درآمد به منطق (رشد جدول ارزش) را ببینید.] توضیح بیشتر این است که، نسبت رشد تعداد ورودی‌ها به زمان مصرفی برای یک الگوریتم، درجه پیچیدگی زمانی نامیده می‌شود. الگوریتم‌های با درجه پیچیدگی-زمانی بالاتر از چندجمله‌ای در عمل (اجرای ماشینی) مفید نیستند. زیرا مسائل واقعی که با این الگوریتم‌ها و توسط سریع‌ترین ماشین‌ها چه در حال و چه آینده اجرا شوند برای به پایان رسیدن (ارائه جواب) به‌طور میانگین به زمانی گرچه محدود ولی بیش از طاقت بشری - گیریم که ماشین بتواند نامحدود کار کند - نیاز خواهند داشت. ازاین‌جهت، در دانش کامپیوتر، اغلب اوقات، مراد از یک الگوریتم کارساز، یک روند کارآمد است که درجه پیچیدگی آن حداکثر چندجمله‌ای باشد.

در نمودار زیر - شکل ۳ - چند پیچیدگی‌-زمانی الگوریتم‌ها نشان داده‌شده و مثل این را می‌توان برای مقدار حافظه مصرفی نیز در نظر گرفت و از پیچیدگی فضایی صحبت کرد.

Algorithms complexity
شکل ۳. مقایسه رشد (پیچیدگی) نمایی و رشد چندجمله‌ای

توجه: