Introduction to Logic

توجه:

صورت، معنی و فرامنطق؛ تعبیر  آخرین ویرایش: ۱۳۹۵/۰۷/۰۱ 

تعبیر

 (ب). تعبیر

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

 (ب).۱. خیلی کوتاه درباره نظریه‌های معنا:

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

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

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

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

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

-مدخل "نظریه‌های معنا" در دانشنامه فلسفی استنفورد: 
   http://plato.stanford.edu/entries/meaning.
-مدخل "سمانتیک" در دانشنامه ویکی‌پدیا: 
   https://en.wikipedia.org/wiki/Semantics.
Paul Horwich, "Meaning", December 1998, Oxford University Press.
  در Google Book

 

تعبیرِ زبان LC

 (ب).۲. تعبیرِ زبان 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. برای مثال، تعبیر I۱ در بالا برای فرمول (pq)p مدل است. حال‌آنکه تعبیر I۲ در بالا برای همین فرمول مدل نیست.

 (ب).۱.۳.  نتیجه:

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

 

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

 (ب).۴.  مجموعه فرمول و مدل آن:

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

(ب).۱.۴ مدل مجموعه فرمول تهی 

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

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

 (ب).۵.  صورت توتولوژیک:

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

 

صورت نامعتبر

(ب).۶.  صورت نامعتبر:

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

 

(ب).۷.  صورت متناقض:

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

 

(ب).۸.  صدق پذیری و سازگاری معنایی:

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

 

(ب).۹.  رابطه استلزام منطقی:

گیریم β فرمول و 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 تهی باشد، معمولاً به‌جای  β فقط می‌نویسند β :('آ). اگر رابطه ('آ) برقرار باشد آنگاه β توتولوژی خواد بود، زیرا با توجه به (ب).۱.۴ و تعریف استلزام منطقی، تعبیری نیست که مدل β نباشد.

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

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

 

(ب).۹. ۰ تعریف:

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

 

(ب).۹. ۱.۰ لم درخت:

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

φα   φ,

اثبات:

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

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

(ب).۹. ۱ رابطه هم‌ارزی منطقی:

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

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

مثال ۱: نشان دهید:    (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=، درست(q)j=] هم‌ارزی مادی است. اما همین فرمول برای تعبیر  i [درست(q)i=، درست(q)i=] هم‌ارزی مادی نیست.

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

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

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

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

(ب).۱۲  کارآمدی استنتاج سمانتیکی: 

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

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

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

 

nextnext

© 1987 - 2017 KHcc Sc.