فهرست:

درخت معنایی و الگوریتم آن

مفاهیم بنیادین منطق

فصل ۱۰ قسمت ۱۴ درآمد به منطق (پیوست ۳)

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

درخت معنایی و الگوریتم آن

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

■ درخت معنایی

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

۱. ساختار درختی

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

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

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

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

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

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

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

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

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


۲. ساختن درخت معنا:

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

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

مثال ۱:

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

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) مدل نیست اگر و فقط اگر مدل (pq) باشد و مدل r نباشد (مدل ~r باشد.)

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

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

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

 (چرخه-۲)

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

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

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

 (چرخه-۳)

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

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

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

 (چرخه-۴)

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

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

۳. قواعد ساخت درخت معنا:

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

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

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

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

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

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

مثال ۲:

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

مثال ۵

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

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

۴. درخت معنا و توتولوژی:

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

مثال ۳:

با کارزدن درخت معنا، شکل ۶، نشان می‌دهیم عبارت:

(p⊃q)∨p 

یک مورد توتولوژی است.

شکل ۶
شکل ۶

مثال ۴:

با کارزدن درخت معنا، شکل ۷، نشان می‌دهیم عبارت:

(A⊃(B⊃C))⊃((A⊃B)⊃(A⊃C)) 

یک مورد توتولوژی است.

شکل ۷
شکل ۷ 

مثال ۵:

با کارزدن درخت معنا، شکل ۸، نشان می‌دهیم عبارت:

(A⊃(B⊃C))≡((A•B)⊃C)

 یک مورد توتولوژی است.

شکل ۷
شکل ۸ 

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

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

مثال ۶:

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

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

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

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

۶. استواری تکنیک درخت معنا:

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

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

 
درخت معنا جدول ارزش

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

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

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

 
جدول ارزش درخت معنا

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

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

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



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

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

http://umsu.de/logik/trees/   Tree Proof Generator.

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

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

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