درخت صدق (معنا) و الگوریتم آن

■ درخت صدق

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

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

۲. ساختن درخت صدق:

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

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

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

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

قاعده نفی دوگانه [پیوست ۱]	قاعده فصل [گسست ۲]	قاعده شرطی [گسست ۱]
قاعده عطف [پیوست ۴]	قاعده نفی فصل [پیوست ۳]	قاعده نفی شرطی [پیوست ۲]
قاعده نفی عطف [گسست ۵]	قاعده دو شرطی [گسست ۴]	قاعده نفی دو شرطی [گسست ۳]
جدول ۱. قواعد ساخت درخت صدق (معنا)

مثال ۱:

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

(P_۱): p ⊃ q

(P_۲): r ∨ ~q

∴ (p ∨ q) ⊃ r

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

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

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

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

 

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

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

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

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

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

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

یا

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

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

 (چرخه-۱)

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

I: ~((p ∨q)⊃r)

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

شمای (I) همان شمای ریشه‌یِ قاعده نفی شرطی است. بنابراین، قاعده نفی شرطی را به (I) بکار می‌زنیم.

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

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

 (چرخه-۲)

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

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

 (چرخه-۳)

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

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

 (چرخه-۴)

در چرخه ۴ صورت 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.