Introduction to Logic

توجه:

روش درخت ارزش در منطق گزارها؛ روش‌های استنتاج؛  درآمد به منطق آخرین ویرایش: ۱۳۹۶/۱۲/۰۱ 

 درخت ارزش

سرآغاز:

توجه: در تمام این قسمت مراد از استدلال همانا استدلال تابع-ارزش، یعنی استدلالی با عبارت‌های گزاره‌ای همگی تابع-ارزش، است.

درخت

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

روشی که برای اعتبارسنجی استدلال در اینجا خواهد آمد و به درخت ارزش موسوم است کاستی گفته‌شده در بالا را ندارد و از جمله کارآمدترین در این زمینه است. بنابراین مراد از درخت ارزش یک روند کارساز، آن‌گونه که خواهیم دید، برای آزمون اعتبار استدلال است. درواقع، این روند (درخت ارزش) فصل مشترک جدول-ارزش و آنچه برهان صوری اعتبار نامیده شد است. بن‌مایه روش درخت ارزش آنچه در (ب).۹. ۱.۰ زیر عنوان "لم درخت" آمد و در ادامه آن را مرور خواهیم کرد است.

۱. نمودار (ساختار) درختی

در فصل دوم  کتاب با  ماتریس  و کاربرد آن در حل مسائل فکری آشنا شدیم. ماتریس گونه‌ای ساختار  نموداری است که ازجمله در آن روابط بین فقرات اطلاعات آشکاری می‌یابد. جدول ارزش که به‌کرات از آن‌ها در فصل ۹ و ۱۰ کتاب سود جستیم مورد دیگری از کاربرد ماتریس بود. ساختار نموداری دیگری نیز به نام درخت هست که بسیار در منطق و دانش کامپیوتر به کار می‌رود. در ادامه نگاهی ابتدایی به درخت و واژگان آن خواهیم داشت تا آنچه اینجا نیاز داریم فراهم  شود.

Leveled tree
نمای شماتیک درخت
درخت

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

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

مسیر: یک مسیر در یک درخت یک دنباله شمارا است که عنصر اول آن ریشه درخت و هر عنصر به‌جز عنصر آخر دنباله (اگر وجود دارد) مادر عنصر بعدی دنباله باشد. بنابراین یک پیوند خود یک مسیر است.

شاخه: یک شاخه در یک درخت یک مسیر است که عنصر آخر آن (در صورت محدود بودن مسیر) یک گره‌ انتهایی(برگ) باشد.

گره ساده گره‌ای است که دقیقاً یک فرزند داشته باشد. برای مثال، گره ۱۲ در درخت بالا یک گره ساده است. در این درخت فقط همین گره یک گره ساده است.

گره انشعاب گره‌ای است که بیش از یک فرزند داشته باشد. برای مثال، گره ۹ و ۳ و مانند آن‌ها در درخت بالا یک گره انشعاب هستند.

 درخت دودویی درختی است که در آن هر مادر حداکثر دو فرزند می‌تواند داشته باشد.


۲.  ساختن درخت ارزش:

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

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

مثال ۱:

می‌خواهیم اعتبار صورت استدلال زیر را بسنجیم:

 p q
r ~q
∴ (p q)r

گام اول: ایجاد ریشه درخت

در سیاهه بالا (یعنی، صورت استدلال داده‌شده)، بجای نتیجه نقیض آن را قرار می‌دهیم تا مجموعه زیر را داشته باشیم:

(۱) : Root= { p q, r ~q, ~((p q)r)}

گره‌ ریشه را ایجاد و محتوای آن را مجموعه Root قرار می‌دهیم.

 

اگر نشان دهیم: محتوای ریشه، یعنی مقدمات صورت استدلال داده شد و نقیض نتیجه آن، دارای مدل نیست آنگاه:  صورت داده‌شده معتبر است؛

 

وگرنه  صورت استدلال داده‌شده نامعتبر است.

به عبارت دیگر: اگر نشان داد مقدمات یک صورت استدلال و نقیض نتیجه آن منطقاً سازگار است آنگاه این صورت استدلال نامعتبر است؛ وگرنه معتبر است.
روش درخت-ارزش بیان جمله قبل همچون یک روند کارساز است.

 گام دوم: تکرار چرخه‌های کاهش برای گسترش درخت

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

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

تکرار این چرخه‌ها را مادام که یکی از شرایط زیر برقرار نیست ادامه می‌دهیم: 

 

آ- درخت بسته شده، یعنی گسترش بیشتر آن مستلزم تناقض است. در این حالت استدلال داده‌شده معتبر است.

ب- درخت باز است ولی هیچ شاخه آن قابل تحلیل (کاهش) بیشتر نیست. در این حالت استدلال داده‌شده نامعتبر است.

اینک اولین چرخه:

 (چرخه-۱)

تحلیل

یک تعبیر برای نقیض نتیجه، یعنی؛

(I)-   ~((p q)r)  

مدل است اگر و فقط اگر برای

(II)-   (p q)r  

مدل نباشد، (ب).۱.۳.

اما: یک تعبیر برای (II) مدل نیست که اگر و فقط اگر مدل (p q) باشد و مدل r نباشد (مدل ~r باشد.)

آنچه تاکنون انجام شد را تحلیل فرمول‌~((p q)r)  نامیده و آن را به شیوه زیر، شکل ۱، نمودار می‌کنیم:

شکل ۱
شکل ۱.  
چرخه یکمِ ساختن درخت ارزش صورت استدلال داده‌شده:
 تحلیل فرمول  ~((p q)r)
نشانه تیک، ، در نمودار نشان می‌دهد که عبارت تیک خورده هم‌اکنون تحلیل‌شده است.
این درخت دارای سه گره است که محتوی ریشه آن مقدمات و نقیض نتیجه صورت استدلال داده‌شده است.

ازآنجاکه در درخت شکل ۱ هنوز فرمول‌های تیک نخورده (تحلیل نشده) مثل r ~q وجود دارد و درخت بسته نیست نیاز به چرخه دیگر برای تحلیل آن است. پس:

 (چرخه-۲)

در چرخه ۲ می‌گوییم یک تعبیر برای r ~q (مقدمه دوم) مدل است اگر و فقط اگر برای r یا  ~qمدل باشد. این تحلیل را با نمایش انشعاب (∨برای)  آن‌گونه که در نمودار (شکل ۲) آمده نمودار می‌کنیم.

شکل ۲
شکل ۲.
   چرخه دوم ساختن درخت ارزش استدلال: تحلیل r ~q، مقدمه دوم. 
نشانه ×، در نمودار نشان می‌دهد در روند ساختن درخت این شاخه بسته و گسترش آن پایان‌یافته، زیرا ادامه آن مستلزم تناقض است (تعبیری به‌طور هم‌زمان مدل r و ~r است.)

ازآنجاکه در درخت شکل ۲ هنوز فرمول‌های تیک نخورده (تحلیل نشده) مثل p q و نیز شاخه باز وجود دارد نیاز به چرخه دیگر برای تحلیل آن است. پس:

 (چرخه-۳)

در چرخه  ۳ می‌گوییم یک تعبیر برای p q (مقدمه سوم) مدل است اگر و فقط اگر برای ~p یا  qمدل باشد (p⊃qهم‌ارز منطقی~p∨q). این تحلیل را با نمایش انشعاب (⊃برای)  آن‌گونه که در نمودار (شکل ۳) آمده نمودار می‌کنیم.

شکل ۳
شکل ۳.
   چرخه سوم  ساختن درخت ارزش استدلال: تحلیل p ⊃q، مقدمه یکم. 
نشانه ×، در نمودار نشان می‌دهد در روند ساختن درخت این شاخه بسته شده و گسترش آن پایان‌یافته، زیرا مستلزم تناقض است (تعبیری به‌طور هم‌زمان مدل q و ~q است.)

ازآنجاکه در درخت شکل ۳ هنوز فرمول‌های تیک نخورده (تحلیل نشده) مثل p q وجود دارد  نیاز به چرخه دیگر برای تحلیل آن است. پس:

 (چرخه-۴)

در چرخه  ۴ می‌گوییم یک تعبیر برای فرمول‌ p q، که در روند ساختن درخت ارزش پدید آمده، مدل است اگر و فقط اگر برای p یا  qمدل باشد. این تحلیل را با نمایش انشعاب (∨برای)، مانند چرخه ۲، آن‌گونه که در نمودار (شکل ۴) آمده در انتهای تنها مسیر باز نمودار می‌کنیم.

شکل ۴
شکل ۴.
   چرخه چهارم  ساختن درخت ارزش استدلال: تحلیل p ⊃q، پدید آمده در روند ساخت.
نشانه ×، در نمودار نشان می‌دهد تمام برگ‌های درخت بسته‌شده‌اند(مسیر منهی به آن‌ها بسته است. بعلاوه، فرمول قابل‌تحلیل دیگری که هنوز تحلیل نشده باشد در درخت وجود ندارد. بنابراین، همه تعبیر‌ها برای مجموعه فرمول ('۱) منجر به تناقض می‌شود. و ازاینجا، می‌گوییم این مجموعه فرمول‌ مدل ندارد. بنابراین، بنا بر آنچه در بالا، زیر عنوان بن‌مایه روش درخت ارزش  گفته شد، صورت استدلال داده‌شده معتبر است.

۳.  قواعد ساخت درخت ارزش:

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

قاعده نفی دوگانه
قاعده نفی دوگانه
قاعده فصل
قاعده فصل
قاعده فصل
قاعده شرطی
قاعده عطف
قاعده عطف
قاعده نفی فصل
قاعده نفی فصل
قاعده  نفی شرطی
قاعده نفی شرطی
قاعده نفی عطف
قاعده نفی عطف
قاعده دو شرطی
قاعده دو شرطی
قاعده نفی دو شرطی
قاعده نفی دو شرطی
جدول ۱.
قواعد ساخت درخت ارزش

شاخه، درخت بسته و باز:

در یک درخت ارزش شاخه‌ای که شامل یک فرمول‌ و نقیض آن است را شاخه بسته می‌نامیم. شاخه‌ای که بسته نباشد را شاخه باز می‌گوییم. درختی که همه شاخه‌های آن بسته باشند را درخت بسته می‌نامیم. درختی که بعضی شاخه‌های آن باز باشند را درخت باز می‌نامیم.

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

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

مثال ۲:

در این مثال اعتبار استدلال زیر را خواهیم سنجید:

مثال ۵

در زیر (شکل ۵) درخت آن را می‌بینیم که به‌موجب آن استدلال معتبر است.

شکل ۵
شکل ۵.  
در این درخت ارزش گرچه مقدمه دوم تحلیل نشده باقی‌مانده ولی درخت بسته شده و بنابراین استدلال داده‌شده معتبر است. این درخت ارزش یک درخت ارزش کامل و بسته است.

۴.  درخت ارزش و توتولوژی:

گیریم α فرمول‌؛ اگر بتوان نشان داد  مدل ندارد (صدق‌پذیر نیست) آنگاه α توتولوژی است(نتیجه ۱).

مثال ۳:

با کارزدن درخت ارزش، شکل ۶، نشان می‌دهیم (pq)p یک صورت توپولوژیک است.

شکل ۶
شکل ۶.  
این درخت ارزش نشان می‌دهد (pq)p یک صورت توپولوژیک است.

مثال ۴:

با کارزدن درخت ارزش، شکل ۷، نشان می‌دهیم (A⊃(B⊃C))⊃((A⊃B)⊃(A⊃C)) یک مورد توتولوژی است.

شکل ۷
شکل ۷.  
این درخت ارزش نشان می‌دهد گزاره مرکب (A⊃(B⊃C))⊃((A⊃B)⊃(A⊃C)) یک مورد توتولوژی است.

مثال ۵:

شکل ۷
شکل ۸.  
این درخت ارزش نشان می‌دهد گزاره مرکب (A⊃(B⊃C))≡((A•B)⊃C) یک مورد توتولوژی است.

۵.  ترتیب تحلیل فرمول‌ها در درخت ارزش:

در ادامه (استواری و تمامیت در درخت ارزش) خواهیم دید ترتیب تحلیل فرمول‌ها در درخت ارزش گرچه می‌تواند به درخت‌های ارزش متفاوت منجر شود ولی در نتیجه پایانی، یعنی معتبر بودن یا نامعتبر بودن استدلال، بی‌تأثیر است. در مثال زیر این نکته نشان داده‌شده.

مثال ۶:

در این مثال با دو گسترش متفاوت درخت ارزش، به قسمی که ترتیب تحلیل فرمول‌ها در آن‌ها متفاوت است، نشان می‌دهیم صورت استدلال زیر معتبر است:

شکل ۸
شکل ۹.  
دو درخت ارزش به دو ترتیب متفاوت در تحلیل فرمول‌ها نشان می‌دهند صورت استدلال داده‌شده معتبر است.

به‌عنوان یک راهکار در گسترش درخت ارزش می‌توان ترتیب زیر را مدنظر داشت:

 

  • قواعد نفی (نقیض) را بکار زد.
  • قواعدی که منجر به گسترش خطی (غیر انشعابی) درخت می‌شوند را بکار زد.

 

۶.  استواری تکنیک درخت ارزش:

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

اکنون می‌توان نوشت:

 
درخت ارزشجدول ارزش

متقن بودن روش درخت ارزش را نیز می‌توان با عبارت‌ زیر بیان کرد:

 

۷.  تمامیت تکنیک درخت ارزش:

تمامیت روش درخت ارزش وارون استواری درخت ارزش است. این خاصیت را که اینجا اثبات آن را فرو می‌گذاریم به‌قرار زیر می‌نویسیم:

 
جدول ارزشدرخت ارزش

تمامیت روش درخت ارزش را نیز می‌توان با عبارت زیر بیان کرد:

 

۹.  تصمیم پذیری:

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



آ.  معرفی وبگاه برای حساب درخت ارزش:

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

http://umsu.de/logik/trees/

ب.  معرفی برخی کتاب:

دو کتاب زیر رهیافت درخت را بکار برده‌اند.
Logic with Trees:
An Introduction to Symbolic Logic

در فصل ۴ این کتاب اثبات استواری و تمامیت تکنیک درخت ارزش را می‌توان یافت.
Formal Logic: Its Scope and Limits
چاپ سوم این کتاب(۱۹۶۷) به شرح زیر به فارسی ترجمه و نشر گردیده. ویرایش جدید، متن اصلی، این کتاب(۲۰۰۶) دارای دو تکمیلی افزوده است.
قلمرو و مرزهای منطق صوری/ /  تالیف ریچارد جفری ؛ ؛ ترجمه پرویز پیر تهران: : علمی و فرهنگی، ، ‭۱۳۶۶‬.





nextprev