حساب گزاره‌ای

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

حساب گزاره‌ها یا حساب گزاره‌ای (Propositional calculus) سامانه‌ای است صوری (formal) که به نمایش مواد و اصول منطق گزاره‌ای می‌پردازد. گزاره‌ها و ترکیب آن با ادوات منطقی شکل می‌گیرد. گزاره‌های مورد توجه منطق گزاره‌ها فقط گزاره‌های خبری ست. در منطق کلاسیک یا منطق دو ارزشی، گزاره‌ها دارای ارزش درست یا غلط هستند.

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

تاریخچه[ویرایش]

با وجود اینکه منطق گزاره ای (یا معادلا "حساب گزاره ای ") توسط فلاسفه ماقبل مورد اشاره قرار گرفته بود توسط رواقیون به یک منطق سوری توسعه یافت و خریسپیوس آن را گسترش داد . این منطق متمرکز بر گزاره ها بود. این پیشرفت با منطق قیاسی سنتی که مبتنی بر روابط است متفاوت بود . با این وجود با گذر زمان منطق گزاره ای توسعه یافته توسط رواقیون دیگر مورد فهم نبود و در نتیجه این سیستم توسط پیتر آبلارد بازآفرینی شد.

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

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

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

اصطلاح شناسی[ویرایش]

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

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

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

زبان یک منطق گزاره ای تشکیل شده از موارد زیر است:

1- مجموعه ای از نماد های ابتدایی که با الفاظ مختلف از جمله فرمول های اتمی ،جا نگهدار ها، ورتنده های گزاره ای یا متغیر شناخته می شوند.

2- مجموعه ای از عملگر ها که با نام هایی مانند رابط‌های منطقی یا عملگر های منطقی شناخته می شوند.

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


ریاضی دانان گاهی اوقات میان ورتنده های گزاره ای ، متغیر های گزاره ای و طرحواره تمایز قایل می شوند . ورتنده های گزاره ای یک گزاره ی خاص را نمایش می دهند در حالی که متغیر های گزاره ای تمام مجموعه فرمول های اتمی را فرا می گیرند. رایج است که ورتنده های گزاره ای را با B, A و C و متغیر های گزاره ای را با Q , P و R نشان دهند. برای طرحواره هم معمولا از حروف الفبای یونانی \varphi \,\!, \psi, \chi استفاده می شود.

مفاهیم پایه[ویرایش]

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

1- زبان ، که در واقع مجموعه ی خاصی از نماد های ابتدایی و عملگر هاست .

2- مجموعه ی اصول یا فرمول های مشخص

3- مجموعه قواعد استنتاج

می توانیم هر گزاره داده شده را با یک حرف که آن را یک ثابت گزاره ای می نامیم نمایش دهیم که این کار متناظر با نمایش دادن اعداد با حروف الفبا در ریاضیات است برای مثال  a = 5. لازم است که تمام گزاره ها دقیقا یکی از دو ارزش ممکن یعنی صحیح یا غلط را داشته باشند . برای مثال  P را گزاره ای در نظر بگیرید که " بیرون باران می بارد " . این گزاره اگر باران ببارد صحیح و در غیر این صورت غلط خواهد بود .

با شروع از نقیض عملگر های درستی را تعریف می کنیم. برای نمایش نقیض P از \neg P استفاده می کنیم ، که می تواند تکذیب گزاره P تلقی شود. در مثال فوق \neg P بیان می کند که "الان بیرون باران نمی بارد". زمانی که P درست باشد، \neg P غلط است و زمانی که \neg P درست باشد،P غلط خواهد بود. \neg\neg P همواره همان مقدار درستی P را دارد.

ترکیب عطفی یک تابع درستی hاست که از دو گزاره ساده تر ، مثلا P و Q ، یک گزاره مرکب می سازد.ترکیب عطفی P و Q به صورت P \and Q نوشته می شود که نشان می دهد هر دو گزاره درست هستند . P \and Q را " P و Q " می خوانیم. برای هر دو گزاره ای چهار وضعیت ممکن از مقادیر درستی وجود دارد :

1- P درست و Q درست باشد

2- P درست و Q غلط باشد

3- P غلط و Q درست باشد

4- P غلط و Q غلط باشد

ترکیب عطفی P و Q در مورد یک درست و در سایر موارد غلط است. هنگامی که P گزاره ای باشد که "بیرون باران می بارد" و Q گزاره ای باشد که "یک جبهه ی هوای سرد در اطراف کانزاس است"، P \and Q تنها زمانی درست است که بیرون باران ببارد و یک جبهه ی هوای سرد در اطراف کانزاس باشد. اگر بیرون باران نبارد یا جبهه ی هوای سرد در کانزاس نباشد P \and Q غلط خواهد بود.

ترکیب فصلی از آن جهت که یک گزاره مرکب از دو گزاره ساده تر تولید می کند مشابه ترکیب عطفی است. ترکیب فصلی را به P \vee Q نمایش می دهیم که "P یا Q" خوانده می شود. این گزاره بیان می کند که یا P یا Q یا هردو درست هستند.بنابراین در مثال های بالا ترکیب فصلی P و Q در تمام موارد غیر از مورد چهارم درست است. طبق مثال قبلی ترکیب فصلی بیان می کند که یا باران می بارد یا یک جبهه هوای سرد بر فراز کانزاس است (توجه شود که ترکیب فصلی باید به نوعی استفاده از واژه "یا" را شبیه سازی کند اما بیشتر شبیه "یا عمومی" است،که برای نشان دادن صحیح بودن حداقل یکی از دو گزاره استفاده می شود.پس ترکیب فصلی با "یا انحصاری" در زبان انگلیسی که نشان دهنده درست بودن دقیقا یکی از دو گزاره است تفاوت دارد.به عبارت دیگر "یا انحصاری" زمانی که هر دو گزاره P و Q درست باشند غلط خواهد بود (مانند مورد اول). مثالی از یا انحصاری به شکل زیر خواهد بود : "شما می تواند پاستا یا سالاد بخورید، نه هر دو را". معمولا در گفتگو های عادی زبانی عبارت "ولی نه هر دو" حذف می شود اما به طور ضمنی مورد نظر است. در ریاضیات همیشه منظور از یا همان "یا عمومی است" ، در صورتی که "یا انحصاری مورد نظر باشد به طور صریح،احتمالا با استفاده از "xor" مشخص می شود.)

ترکیب شرطی نیز دو گزاره ساده تر را با هم ترکیب می کند و آن را با P \rightarrow Q نمایش می دهیم که خوانده می شود "اگر P آنگاه Q". گزاره سمت چپ "شرط مقدم" و گزاره سمت راست "شرط موخر" خوانده می شود (از آنجا که ترکیب فصلی و عطفی شرکت پذیر هستند چنین مشخصه ای برای آن ها تعریف نمی شود).

بسته بودن نسبت به عملیات[ویرایش]

منطق گزاره ای نسبت به عملگر های درستی نگهدار بسته است. یعنی برای هر گزاره \varphi \,\!, \neg \varphi \,\! هم یک گزاره است. برای مثال برای هر دو گزاره \varphi \,\! \psi \,\!, \varphi \and \psi \,\! هم یک گزاره است که به طور مشابه برای ترکیب فصلی، ترکیب شرطی و ترکیب دو شرطی هم برقرار است. این بیان می کند که از آنجا که P \and Q یک گزاره است می تواند با گزاره ای دیگر عطف شود. برای نمایش دادن این رابطه باید با استفاده از پرانتز ها مشخص کنیم که کدام گزاره ها با هم عطف می شوند. برای نمونه P \and Q \and R یک رابطه خوش ساخت نیست زیرا نمی دانیم که داریم P \and Q با R عطف می کنیم یا P با Q \and R. بنابراین یا باید بنویسیم (P \and Q) \and R تا اولی را نمایش دهیم با باید بنویسیسم P \and (Q \and R) تا نشان دهیم که شکل دوم مد نظر بوده است. با ارزیابی شرایط درستی در می یابیم که هر دو عبارت شرایز درستی یکسانی دارند و به طور جامع تر هر گزاره ای که با چینش دلخواهی از ترکیب ای عطفی ساخته شود، صرف نطر از جایگاه پرانتز ها مقادیر درستی ثابتی خواهد داشت.این به خاطر آن است که ترکیب عطفی خاصیت پخشی دارد اما این موضوع نباید باعث شود وجود پرانتز ها را بی دلیل بدانیم. به عنوان نمونه مقادیر درستی عبارت P \and (Q \vee R) با عبارت (P \and Q) \vee R یکسان نیست، بنابراین این ها عبارت های متفاوتی هستند که با توجه به قرارگیری پرانتز ها از هم متمایز می شوند. خواننده می تواند این موضوع را با استفاده از جدول درستی تحقیق کند.

نکته : برای هر تعداد دلخواه از ورتنده های گزاره ای می توانیم مجموعه متناهی از حالت های ممکن برای مقادیر درستی آن ها را ارائه دهیم. یک راه ساده برای تولید این لیست استفاده از جداول درستی است .برای هر مجموعه k تایی از ورتنده های گزاره ای از حروف P, Q, …, Z استفاده می کنیم. در زیر این لیست 2^k ردیف خالی می گذاریم. زیر P نیمه ی اول ردیف ها را با "درست" (T) و نیمه ی دوم را با "غلط" (F) پر می کنیم.زیر Q یک چهارم را با T، یک چهارم بعدی را با F، یک چهارم سوم را با T و در نهایت یک چهارم آخر را با F پر می کنیم. ستون بعدی برای هر یک هشتم ردیف ها ، ستون بعد تر برای هر یک شانزدهم و در نهایت ستون آخر برای هر ردیف بین مقادیر T و F نوسان می کند. این فرآیند یک لیست کامل از نگاشت های درستی ممکن برای گزاره های اولیه را ارائه می دهد.

استدلال[ویرایش]

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


\begin{array}{rl}
1. & P \rightarrow Q \\
2. & P \\
\hline
\therefore & Q
\end{array}

این مجموعه ای از سه گزاره است که گزاره سوم از دو گزاره قبلی نتیجه می شود. به دو گزاره اول "فرض" و به گزاره سوم "نتیجه" می گوییم . می گوییم گزاره دلخواه C از مجموعه گزاره های (P_1, ..., P_n) نتیجه می شود اگر زمانی که تمام گزاره های (P_1, ..., P_n) درست باشند C هم درست باشد. در استدالال بالا برای هر P و Q هنگامی که P \rightarrow Q و P درست باشند ، لزوما Q هم درست خواهد بود. توجه شود که زمانی که P درست باشد حالت های 3و4 از جدول درستی را نمی توانیم در نظر بگیریم . هنگامی که P \rightarrow Q درست باشد هم حالت دوم را نمی توانیم در نظر بگیریم پس تنها حالت 1 باقی می ماند که هم P و هم Q درست هستند. بنابراین Q بر اساس فرض ها نتیجه می شود.


\begin{array}{rl}
1. & \varphi \rightarrow \psi \\
2. & \varphi \\
\hline
\therefore & \psi
\end{array}

بقیه شکل های استدلال علی زغم سادگی لزوما مورد نیاز نیستند. در کنار مجموعه ی کاملی از اصول وضع مقدم برای اثبات تمام استدلال های دیگر در حساب گزاره ای کافی است. توجه شود که این وضع د

ویژگی برجسته استدلال در حساب گزاره ای آن است که می توان بر اساس استدلال های ثابت شده ،استدلال های درست جدید به دست آورد. در اولین مثال بالا، با دو فرض داده شده نمی توان در مورد درستی Q اظهار نظری کرد اما بعد از استدلال درستی Q نتیجه گیری می شود. بنابراین یک نظام قیاسی را به صورت مجموعه ی تمام گزاره هایی که می توانند از هم نتیجه گیری شوند تعریف می کنیم. برای نمونه بر پایه مجموعه گزاره های A = \{ P \or Q, \neg Q \and R, (P \or Q) \rightarrow R \} ، می توانیم سامانه قیاسی \Gamma را که جامع تمام گزاره های نتیجه شونده از A است تعریف کنیم. تصریح همواره مفروض است بنابراین P \or Q, \neg Q \and R, (P \or Q) \rightarrow R \in \Gamma . همچنین بر اساس عضو اول و آخر A و نیز وضع مقدم ، R نتیجه می شود پس R \in \Gamma. از آنجا که هنوز اصول به حد کافی غامض را معرفی نکرده ایم نمی توانیم نتیجه گیری دیگری داشته باشیم. بنابراین با وجود اینکه عمده سیستم های اسنتاجی مورد مطالعه در حساب گزاره ای قادر به نتیجه گیری (P \or Q) \leftrightarrow (\neg P \rightarrow Q) هستند، این سیستم ضعیف تر از آن است که بتواند چنین گزاره ای را ثابت کند.

توصیف کلی یک حساب گزاره ای[ویرایش]

یک حساب گزاره ای یک سیستم صوری \mathcal{L} = \mathcal{L} \left( \Alpha,\ \Omega,\ \Zeta,\ \Iota \right) است به طوریکه :

مجموعه ی "آلفا" \Alpha یک مجموعه ی متناهی از اعضا موسوم به "نماد های گزاره ای" یا "متغیر های گزاره ای" است. از نظر نحوی این ها ساده ترین عناصر سازنده زبان نحوی \mathcal{L} یا همان " فرمول های اتمی " هستند.در مثال های پیش رو اعضای \Alpha را عمدتا با حروف p, q, r و ... نشان می دهیم.

مجموعه ی "امگا" \Omega یک زیرمجموعه ی متناهی از اعضا موسوم به " عملگر ها یا رابط های منطقی است. مجموعه ی \Omega به شکل زیر به زیرمجموعه های مستقل افراز مجموعه می شود :

\Omega = \Omega_0 \cup \Omega_1 \cup \ldots \cup \Omega_j \cup \ldots \cup \Omega_m.

در این افراز، \Omega_j مجموعه ی عمگلر ها از Arity j است.

در حساب شناخته شده تر گزاره ای، \Omega را معمولا به شکل زیر افراز می کنیم :

\Omega_1 = \{ \lnot \},
\Omega_2 \subseteq \{ \land, \lor, \rightarrow, \leftrightarrow \}.

مرسوم است که مقادیر ثابت درستی را عملگر هایی از مرتبه صفر در نظر می گیریم، بنابراین :

\Omega_0 = \{ 0, 1 \}.\,\!

بعضی مولفان از نماد تیلدا(~)، به جای ¬ و بعضی دیگر از آمرسان (&) یا پیشوند K با جای ∧ استفاده می کنند. نماد گزاری برای مجموعه ی مقادیر منطقی حتی متنوع تر است، به گونه ای که نماد های {false, true}, {F, T}, or \{ \bot, \top \} در متون مختلف به جای {0, 1} استفاده می شوند.

مجموعه ی "زتا" \Zeta یک مجموعه ی متناهی از قواعد ترادیسی است که در کاربرد های منطقی اصطلاحا قوانین استنتاج خوانده می شوند.

مجموعه "یوتا" \Iota یک مجموعه ی متناهی از نقاط اولیه است که وقتی قرار است به طور منطقی مفهوم شوند اصل موضوعی خوانده می شوند.

زبان \mathcal{L}، که با مجموعه ی روابط خوش ساختش شناخته می شود، به طور استقرایی بر اساس قوانین زیر تعریف می شود:

1- بر اساس قانون 1، p یک رابطه است.

2- بر اساس قانون 2، \neg p یک رابطه است.

3- بر اساس قانون 1، q یک رابطه است.

4- بر اساس قانون 2، ( \neg p \lor q ) یک رابطه است.

مثال ۱. یک سیستم ساده اصل موضوعی[ویرایش]

فرض کنیم \mathcal{L}_1 = \mathcal{L}(\Alpha,\Omega,\Zeta,\Iota)، بطوری که \Alpha, \Omega, \Zeta, \Iota به صورت زیر تعریف شده اند:

  • مجموعه آلفا \Alpha، مجموعه ای متناهی از نمادها است که به اندازه کافی بزرگ هست تا نیازهای یک مبحث را تامین کند، برای مثال:
\Alpha = \{p, q, r, s, t, u \}.\,\!
  • از سه علامت ربط برای ترکیب های عطفی، فصلی و شرطی (\wedge, \lor, و \rightarrow)، یکی را می توان به عنوان عملگر اصلی انتخاب نموده و دو عملگر دیگر بر اساس آن عملگر و عملگر نقیض (\neg) تعریف خواهند شد.در واقع تمام عملگر های منطقی می توانند بر اساس یک عملگر کامل تعریف شوند. دوشرطی منطقی (\leftrightarrow) نیز می تواند بر اساس عطف و عملگر شرط منطقی تعریف شود، به این صورت که a \leftrightarrow b به صورت (a \to b) \land (b \to a) تعریف شود.
انتخاب نقیض و شرط منطقی به عنوان عملگر های اصلی یک حساب گزاره ای هم ارز است با این که مجموعه امگا \Omega = \Omega_1 \cup \Omega_2 را به این صورت داشته باشیم که:
\Omega_1 = \{ \lnot \},
\Omega_2 = \{ \rightarrow \}.
  • یکی از سیستم های اصل موضوعی، که توسط یان ووکاشویچ (به لهستانی: Jan Łukasiewicz) ارائه شده است، حسابی گزاره ای را به صورتی که در اینجا توضیح داده شده فرمولیزه می کند. اصول موضوعی، همگی حاصل جایگذاری متغیر ها در گزاره های زیر هستند.
  • (p \to (q \to p))
  • ((p \to (q \to r)) \to ((p \to q) \to (p \to r)))
  • ((\neg p \to \neg q) \to (q \to p))
  • قانون استنتاج، قیاس استثنایی است (یعنی، از p و (p \to q)، نتیجه می گیریم q). پس a \lor b به صورت \neg a \to b ، و a \land b به صورت \neg(a \to \neg b) تعریف می شود.

مثال ۲. دستگاه نتیجه گیری طبیعی[ویرایش]

فرض کنیم \mathcal{L}_2 = \mathcal{L}(\Alpha, \Omega, \Zeta, \Iota)، به طوری که \Alpha, \Omega, \Zeta, \Iota به صورت ذیل الذکر تعریف شده اند:

  • مجموعه آلفا \Alpha، مجموعه ای متناهی از نمادها است که برای تامین نیاز های یک مبحث معین به اندازه کافی بزرگ هست. برای مثال:
    \Alpha = \{p, q, r, s, t, u \}.\,\!
  • مجموعه امگا \Omega = \Omega_1 \cup \Omega_2 این گونه تقسیم بندی می شود:
    \Omega_1 = \{ \lnot \},
    \Omega_2 = \{ \land, \lor, \rightarrow, \leftrightarrow \}.

در این مثال از حساب گزاره ای، هدف این است که قوانین استنتاج، برگرفته از قوانین استنتاج دستگاه موسوم به دستگاه نتیجه گیری طبیعی باشند. دستگاهی که در اینجا ارائه می شود فاقد هرگونه نقطه ابتدایی است. یعنی در تفسیر این دستگاه از عملیات منطقی، قضایا را از مجموعه ای تهی به عنوان اصول موضوعی استنتاج می شوند.

  • مجموعه نقاط ابتدایی بحث خالی است. یعنی <math\Iota = \varnothing</math>.
  • مجموعه قوانین استنتاج، \Zeta، این گونه توصیف می شود:

دستگاه گزاره ای ما دارای ده قانون نتیجه گیری است. این قوانین به ما اجازه می دهند تا از مجموعه ای از فرمولها که به صورت پیش فرض درست تلقی شده اند، فرمولهای صحیح دیگری را نتیجه بگیریم. نه قانون اول صرفا بیان می کنند که چگونه می توان بعضی فرمولهای خوش ساخت را از برخی دیگر نتیجه گرفت. اما آخرین قانون از استدلالی مبتنی بر فرض استفاده می کند، به این معنا که در پیش فرض این قانون، موقتا فرض می کنیم که فرضیه ای اثبات نشده بخشی از فرمولهای استنتاج شده ما باشد، تا امکان نتیجه گرفتن یک فرمول خاص دیگر را بررسی نماییم. از آنجا که نه قانون اول این کار را نمی کنند، آنها را قوانین غیر فرض محور (به انگلیسی non-hypothetical) می خوانند و قانون دهم را قانون فرض محور (به انگلیسی hypothetical) نامیده اند.

در توصیف قوانین استنتاج، ممکن است برای سادگی در زبان فراتر از گزاره ها (به انگلیسی metalanguage: سیستمی برای گزاره هایی راجع به گزاره ها) از نماد جدید \vdash استفاده کنیم. این نماد، اختصاراً به معنی "نتیجه می دهد" می باشد و قالب استفاده از این نماد به صورت \Gamma \vdash \psi است، که در آن \Gamma مجموعه ای (نه لزوما ناتهی) از فرمولهاست که فرض (مقدم) نامیده می شوند، و \psi فرمولی است که نتیجه (یا مؤخر) نام دارد. قانون استنتاجی که \Gamma \vdash \psi بیان می کند، به این معنی است که اگر تمام گزاره های عضو \Gamma قضیه باشند (یا مقدار درستی آنها با اصول موضوعی یکسان باشد)، آنگاه \psi نیز یک قضیه خواهد بود. توجه نمایید که طبق تعریف عطف (به انگلیسی Conjunction introduction) خواهیم داشت که هرگاه \Gamma بیش از یک فرمول را شامل شود، می توان بی سادگی آن را به کمک عطف یا "و" منطقی آنها را به یک گزاره مرکب کاهش داد. پس به این ترتیب می توان \Gamma را به جای یک مجموعه به صورت یک گزاره معرفی نماییم. مطلب دیگر آن که هرگاه \Gamma تهی باشد ممکن است آن را برای راحتی ننویسیم.

تعریف نقیض
از (p \to q) و (p \to \neg q), نتیجه می گیریم \neg p.
یعنی, \{ (p \to q), (p \to \neg q) \} \vdash \neg p.
حذف نقیض
از \neg p, نتیجه می گیریم (p \to r).
یعنی, \{ \neg p \} \vdash (p \to r).
حذف دو منفی
از \neg \neg p, نتیجه می گیریم p.
یعنی, \neg \neg p \vdash p.
تعریف عطف
از p و q, نتیجه می گیریم (p \land q).
یعنی, \{ p, q \} \vdash (p \land q).
حذف عطف
از (p \land q), نتیجه می گیریم p.
از (p \land q), نتیجه می گیریم q.
یعنی, (p \land q) \vdash p و (p \land q) \vdash q.
تعریف فصل
از p, نتیجه می گیریم (p \lor q).
از q, نتیجه می گیریم (p \lor q).
یعنی, p \vdash (p \lor q) و q \vdash (p \lor q).
حذف فصل
از (p \lor q) و (p \to r) و (q \to r), نتیجه می گیریم r.
یعنی, \{p \lor q, p \to r, q \to r\} \vdash r.
تعریف دوشرطی
از (p \to q) و (q \to p), نتیجه می گیریم (p \leftrightarrow q).
یعنی, \{p \to q, q \to p\} \vdash (p \leftrightarrow q).
حذف دوشرطی
از (p \leftrightarrow q), نتیجه می گیریم (p \to q).
از (p \leftrightarrow q), نتیجه می گیریم (q \to p).
یعنی, (p \leftrightarrow q) \vdash (p \to q) و (p \leftrightarrow q) \vdash (q \to p).
وضع مقدم (conditional elimination) 
از p و (p \to q), نتیجه می گیریم q.
یعنی, \{ p, p \to q\} \vdash q.
اثبات شرطی (تعریف استنتاج) 
از [قبول کردن این که p دلیل بر درستی q باشد]، نتیجه می گیریم (p \to q).
یعنی, (p \vdash q) \vdash (p \to q).


شکل های پایه و مشتق استدلال[ویرایش]

Basic and Derived Argument Forms
نام نتیجه گیری توضیح
وضع مقدم ((p \to q) \land p) \vdash q اگر p آنگاه q؛ p؛ پس q
نفی تالی ((p \to q) \land \neg q) \vdash \neg p اگر p آنگاه q؛ not q؛ پس p نادرست است
قیاس فرضیه ای ((p \to q) \land (q \to r)) \vdash (p \to r) اگر p آنگاه q؛ اگر q آنگاه r؛ پس, اگر p آنگاه r
قیاس فصلی ((p \lor q) \land \neg p) \vdash q یا p درست است یا q، یا هردو؛ not p; پس، q
بحث سازنده (به انگلیسی Constructive Dilemma) ((p \to q) \land (r \to s) \land (p \lor r)) \vdash (q \lor s) اگر p آنگاه q؛ و اگر r آنگاه s؛ ولی p یا r؛ پس q یا s
بحث مخرب (به انگلیسی Destructive Dilemma) ((p \to q) \land (r \to s) \land(\neg q \lor \neg s)) \vdash (\neg p \lor \neg r) اگر p آنگاه q؛ و اگر r آنگاه s؛ ولی q نادرست باشد یا sنادرست باشد؛ پس p نادرست است یا r نادرست است
بحث دو طرفه ((p \to q) \land (r \to s) \land(p \lor \neg s)) \vdash (q \lor \neg r) اگر p آنگاه q؛ و اگر r آنگاه s؛ ولی p یا این که s نادرست باشد؛ پس q یا این که r نادرست است.
ساده سازی (p \land q) \vdash p p و q درست هستند؛ پس p درست است.
عطف منطقی p, q \vdash (p \land q) p و q جداگانه درست هستند؛ پس به صورت توام نیز درست هستند.
افزودن p \vdash (p \lor q) p صحیح است؛ پس فصل (p یا q) نیز صحیح است.
توزیع شرط بر عطف ((p \to q) \land (p \to r)) \vdash (p \to (q \land r)) If p then q; and if p then r; therefore if p is true then q and r are true
قوانین دمورگان (1) \neg (p \land q) \vdash (\neg p \lor \neg q) نقیض عبارت (p و q) هم ارز است با (p درست نباشد یا q درست نباشد)
قوانین دمورگان (2) \neg (p \lor q) \vdash (\neg p \land \neg q) نقیض عبارت (p یا q) هم ارز است با (pدرست نباشد و نیز q درست نباشد)
خاصیت جابجایی فصل (p \lor q) \vdash (q \lor p) (p یا q) هم ارز است با (q یا p)
خاصیت جابجایی عطف (p \land q) \vdash (q \land p) (p و q) هم ارز است با (q و p)
خاصیت جابجایی دوشرطی (p \leftrightarrow q) \vdash (q \leftrightarrow p) (p is equiv. to q) هم ارز است با (q is equiv. to p)
شرکت پذیری فصل (p \lor (q \lor r)) \vdash ((p \lor q) \lor r) p یا (q یا r) هم ارز است با (p یا q) یا r
شرکت پذیری عطف (p \land (q \land r)) \vdash ((p \land q) \land r) p و (q و r) هم ارز است با (p و q) و r
توزیع عطف بر فصل (p \land (q \lor r)) \vdash ((p \land q) \lor (p \land r)) p و (q یا r) هم ارز است با (p و q) یا (p و r)
توزیع فصل بر عطف (p \lor (q \land r)) \vdash ((p \lor q) \land (p \lor r)) p یا (q و r) هم ارز است با (p یا q) و (p یا r)
حذف دو منفی p \vdash \neg \neg p p هم ارز است با نادرستی نقیض p
عکس نقیض (p \to q) \vdash (\neg q \to \neg p) اگر p آنگاه q هم ارز است با اگر q نادرست باشد آنگاه p نادرست است.
قانون استنتاج (1) (p \to q) \vdash (\neg p \lor q) اگر p آنگاه q هم ارز است با این که p نادرست باشد یا q
هم ارزی (1) (p \leftrightarrow q) \vdash ((p \to q) \land (q \to p)) (p اگر و فقط اگر q) هم ارز است با (اگر p درست باشد آنگاه q درست است) و (اگر q درست باشد آنگاه p درست است)
هم ارزی (2) (p \leftrightarrow q) \vdash ((p \land q) \lor (\neg p \land \neg q)) (p اگر و فقط اگر q) هم ارز است با این که (p و q درست هستند) یا (p و q نادرست هستند)
هم ارزی (3) (p \leftrightarrow q) \vdash ((p \lor \neg q) \land (\neg p \lor q)) (p اگر و تنها اگر q) هم ارز است با، (p یا نقیض q درست است) و (نقیض p یا q درست است)
بیرون کشیدن (به انگلیسی Exportation) ((p \land q) \to r) \vdash (p \to (q \to r)) از (اگر p و q درست باشند آنگاه r درست است) می توانیم اثبات کنیم (اگر q درست باشد آنگاه r درست است, اگر p درست باشد)
وارد کردن (به انگلیسی Importation) (p \to (q \to r)) \vdash ((p \land q) \to r) اگر p آنگاه (اگر q پس r) هم ارز است با این که اگر p و q درست باشند آنگاه r درست است
راستگو (تاتولوژی یا همان‌گو) (1) p \vdash (p \lor p) این که p درست است هم ارز است با p است یا p درست است
راستگو (تاتولوژی یا همان‌گو) (2) p \vdash (p \land p) این که p درست است هم ارز است با p است و p درست است
اصل طرد ثالث \vdash (p \lor \neg p) p یا نقیض p صحیح است
قانون عدم تناقض \vdash \neg (p \land \neg p) این که (p و نقیض p) نادرست است، گزاره ای همواره درست است.

اثبات ها در حساب گزاره ای[ویرایش]

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

در ادامه، یک اثبات به صورت دنباله ای از خطوط شماره دار ارائه می شود که هر خط آن تنها یک رابطه را در بر دارد، و به همراه آن دلیل یا توجیه صحت این رابطه نیز آمده است. هر پیش فرض برای استدلال، یعنی چیزی که به عنوان فرض از قبل پذیرفته شده، در ابتدای دنباله فهرست شده و به عنوان یک "پیش فرض" در محل توجیه موردنظر علامت گذاری شده است. نتیجه، در سطر پایانی بیان شده است. یک اثبات هنگامی کامل است که هر سطر، پیرو خط های پیشین با به کار گیری درست قوانین استنتاج باشد. (به عنوان یک راهکار متفاوت از این دستگاه، می توان روش نمودار تحلیل (درخت درستی)، یا به انگلیسی proof-trees، را معرفی نمود)

مثالی از یک اثبات[ویرایش]

  • حکم این است که A \to A.
  • یک راه ممکن برای اثبات این موضوع، که علی رغم درستی تعداد مراحل آن بیش از حد نیاز است، در ادامه آمده است:
Example of a Proof
ردیف رابطه دلیل
1 A\,\! پیش فرض
2 A \lor A از (۱) بر اساس تعریف فصل
3 (A \lor A) \land A از (۱) و (۲) بر اساس تعریف عطف
4 A\,\! از (۳) بر اساس 'حذف فصل'
5 A \vdash A جمع بندی (۱) تا (۴)
6 \vdash A \to A از (۵) بر اساس اثبات شرطی

رابطه A \vdash A را به این صورت تفسیر کنید که "به فرض درستی A، نتیجه می گیریم A". همچنین، رابطه \vdash A \to A را بخوانید «بدون هیچ فرضی نتیجه گرفتن A، نشان می دهد A"، یا "این یک راستگو (تاتولوژی) است که A نتیجه می دهد A"، یا به عبارت دیگر "این همواره صحیح است که A نتیجه می دهد A".

صحت و کامل بودن قوانین[ویرایش]

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

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

تعریف می کنیم که یک نگاشت درستی مانند A \,، رابطه ای خوش ساخت (که قبل تر در همین متن تعریف شده است) را با قوانین زیر اقناع می کند:

  • A \, متغیر گزاره ای P \, را اقناع می کند اگر و فقط اگر A(P) = \text{true} \,
  • A \,، \neg \phi \, را اقناع می کند اگر و فقط اگر A \,، \phi \, را اقناع نکند
  • A \,، (\phi \land \psi) \, را اقناع می کند اگر و فقط اگر A \, هر دو متغیر \phi \, و \psi \, را اقناع کند
  • A \,، (\phi \lor \psi) \, را اقناع می کند اگر و فقط اگر A \, حداقل یکی از دو متغیر \phi \, یا \psi \, را اقناع نماید.
  • A \,، (\phi \to \psi) \, را اقناع می کند اگر و فقط اگر اینگونه نباشد که A \,، \phi \, را اقناع کند ولی \psi \, را اقناع نکند
  • A \,، (\phi \leftrightarrow \psi) \, را اقناع می کند اگر و فقط اگر A \, هر دو متغیر \phi \, و \psi \, را اقناع کند یا این که هیچ کدام را اقناع نکند.

با داشتن این تعاریف، اکنون می توانیم به طور قاعده مند تعریف نماییم، این که مجموعه ای چون S \, از روابط، دلیل بر رابطه \phi \, باشد به چه معناست. باز به طور شهودی این جمله هنگامی درست است که در تمام دنیاهایی که با توجه به درستی روابط S \, ممکن هستند، \phi \, نیز برقرار باشد. به عبارتی، در هر حالتی از امور که مجموعه روابط S \, در آن برقرار باشد، رابطه \phi \, نیز درست باشد. بر اساس این تعریف شهودی، به این تعریف قاعده مند خواهیم رسید: می گوییم مجموعه S \, از رابطه های خوش ساخت، به لحاظ معنایی دلیل بر رابطه خوش ساخت \phi \, است، هنگامی که هر نگاشت درستی که تمام رابطه های عضو S \, را اقناع می کند، \phi \, را نیز اقناع نماید.

در پایان، دلالت بر اساس قواعد ترکیب را این گونه تعریف می کنیم که S \, به لحاظ ترکیبی دلیل بر \phi \, است، هنگامی که بتوان \phi \, را بر اساس قوانین استنتاج (که قبل تر توضیح داده شد) در متناهی مرحله از روابط مجموعه S \, نتیجه گرفت. بنابراین می توانیم به طور دقیق صحت و کامل بودن را مطابق زیر تعریف نماییم:

صحت 
اگر مجموعه S \, از رابطه های خوش ساخت، بر اساس قواعد ترکیب، دلیل بر رابطه خوش ساخت \phi \, باشد، آنگاه S \, به لحاظ معنایی نیز دلیل بر \phi \, است
کامل بودن 
اگر مجموعه S \, از رابطه های خوش ساخت، به لحاظ معنایی دلیل بر رابطه خوش ساخت \phi \, باشد، آنگاه S \, بر اساس قواعد ترکیب نیز دلیل بر \phi \, است

برای مجموعه قوانین فوق، این دو شرط برقرار هستند.

پیوند به بیرون[ویرایش]

منابع[ویرایش]

  • Ebbinghaus, H. -D., Flum, J., and Thomas, W. Mathematical logic, Springer-Verlag New York Inc., ۱۹۸۴. ISBN 0-387-96170-4 *Russell, S., and Norvig, P. Artificial Intelligence, A Modern Approach, ۲nd edition, Pearson Education, Inc., ۲۰۰۳. ISBN 0-13-790395-2

جستارهای وابسته[ویرایش]