یافتنِ آغاز بسیار دشوار است. یا بهتر است بگوییم: سخت است از ابتدا آغاز کردن.
نکوشید بیشتر به عقب برگردید. __ 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)، ۲- نظریه‌های بنیادی معنا تقسیم کرد.
نظریه‌های سمانتیکی کوشش دارد تا به عبارات زبان، به‌طور سازگار، مقدار سمانتیکی نظیر کند. نظریه‌های بنیادی معنا کوشش دارد توضیح دهد چه روندی موجب شده تا عبارات زبان (طبیعی) دارای آن مقادیر سمانتیکی باشند. توضیح بیشتر را می‌توان در فصل ۳ (زبان و کارکردهای آن)، فصل ۴(تعریف)
کتاب‌درآمد به منطق و نیز
اینجا↱
دید.
مراد از تعبیر در
زبان صوری LC یک روند
کارآمد است تا بتوان با آن فرمول‌هایLC را به مقادیر معنایی برآوُرد. در این روند ابتدا به متغیرهای گزاره‌ای مقادیر سمانتیکی گمارده، سپس طبق قواعد معینِ تثبیت‌شده و برحسب مقادیر معنایی گمارده به متغیرهای گزاره‌ای، مقدار معنایی
فرمول‌ها برآورد گردید. تعریف ساختار جداول ارزش رابط‌ها که در
کتاب‌درآمد به منطق
آمده است، همان قواعد معین تثبیت شده هستند.
برای مثال اگر متغیرهای گزاره‌ای LC فقط q، p و r باشند آنگاه:
تعبیر I۱ می‌تواند گمارش: درست←p، نادرست←q و درست←r؛ تعبیر I۲ می‌تواند گمارش: نادرست←p، درست←q
و نادرست←r باشد.
در تعبیر I۱ مقدار معنایی صورت گزاره‌ای (p∨q)⊃p بنا به تابع تعبیر (جدول ارزش) «درست» برآورد می‌گردد. این برآورد را این‌گونه:
درست → ((p∨q)⊃p)I۱
نشان می‌دهند. و به همین ترتیب نیز می‌نویسند:
. نادرست → ((p∨q)⊃p)I۲
ازآنجاکه در هر تعبیر، کارکرد واژگان '≡' ,'~' ,'⊃' ,' '•,'∨' تعریف و تثبیت‌شده است، به آنها رابط‌های منطقی [همچنین ثابت‌های منطقی، رابط جمله گانی و واژگان منطقی ] در LC گفته می‌شود. و ازآنجاکه در هر تعبیر، به متغیرهای گزاره‌ای مقادیر سمانتیکی گمارده می‌شود، به آنها واژگان نامنطقی در LC می‌گویند.
گیریم j یک تعبیر و α فرمول باشد. گوییم j برای αمدل است
(یا α
در j مدل است) اگر و فقط اگر درست=(α)j. برای مثال، تعبیر I۱ در بالا برای فرمول (p∨q)⊃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, ~α⊩.
■ رابطه هم‌ارزی منطقی:
گوییم فرمول‌های αو βهم‌ارز منطقی هستند اگر و فقط اگر هر مدل α مدل β نیز باشد. در این صورت می‌نویسیم:
■ آزمون اعتبار یک استنتاج سمانتیکی، به‌وسیله مدل است.
مثال ۱: نشان دهید: (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•~q≡p∨~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"
■ کارآمدی استنتاج سمانتیکی:
روندتعبیر در منطق گزاره‌ها یک روند کارآمد است. به این معنی که روش جدول ارزش، روندی را در اختیار می‌گذارد که به‌وسیله اجرای آن، ماشین می‌تواند درباره اعتبار یک استنتاج سمانتیکی دلخواه تصمیم‌گیری و پاسخ آری یا نه را در زمان محدود ارائه کند. اما این روند گرچه کارآمد است (در زمان محدود به پایان می‌رسد) ولی کارآمدی آن کارآمدی چندجمله‌ای نیست— یعنی، میانگین نسبت رشد زمان مصرفی توسط اجرای ماشینی این روند نسبت به رشد تعداد ورودی‌ها (متغیرهای گزاره‌ای متمایز در استنتاج معنایی) نمایی و نه چندجمله‌ای [فصل.۹، قسمت.۷
کتاب‌درآمد به منطق (رشد جدول ارزش) را ببینید.] توضیح بیشتر
این است که، نسبت رشد تعداد ورودی‌ها به زمان مصرفی برای یک الگوریتم، درجه پیچیدگی زمانی
نامیده می‌شود. الگوریتم‌های با درجه پیچیدگی-زمانی بالاتر از چندجمله‌ای در عمل (اجرای ماشینی) مفید نیستند. زیرا مسائل واقعی که با این الگوریتم‌ها و توسط سریع‌ترین ماشین‌ها چه در حال و چه آینده اجرا شوند برای به پایان رسیدن (ارائه جواب) به‌طور میانگین به زمانی گرچه محدود ولی بیش از طاقت بشری - گیریم که ماشین بتواند نامحدود کار کند - نیاز خواهند داشت. ازاین‌جهت، در دانش کامپیوتر، اغلب اوقات، مراد از یکالگوریتم کارساز، یک روند کارآمد است که درجه پیچیدگی آن حداکثر چندجمله‌ای باشد.
در نمودار زیر - شکل ۳ - چند پیچیدگی-زمانی الگوریتم‌ها نشان داده‌شده و مثل این را می‌توان برای مقدار حافظه مصرفی نیز در نظر گرفت و از پیچیدگی فضایی صحبت کرد.
شکل ۳. مقایسه رشد (پیچیدگی) نمایی و رشد چندجمله‌ای
.۳ صورت، معنی و فرا-منطق: (گزاره‌ها)
((p⊃r)∨(q⊃r))
