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

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

تاریخچه

با وجود اینکه منطق گزاره‌ای (یا معادلا "حساب گزاره‌ای ") توسط فلاسفه ماقبل مورد اشاره قرار گرفته بود توسط رواقیون به یک منطق سوری توسعه یافت و خریسپیوس آن را گسترش داد. این منطق متمرکز بر گزاره‌ها بود. این پیشرفت با منطق قیاسی سنتی که مبتنی بر روابط است متفاوت بود. با این وجود با گذر زمان منطق گزاره‌ای توسعه یافته توسط رواقیون دیگر مورد فهم نبود و در نتیجه این سیستم توسط پیتر آبلارد بازآفرینی شد.
منطق گزاره‌ای در نهایت توسط منطق نمادین اصلاح شد .گوتفرید لایبنیتس به خاطر کارهایش در حساب دیفرانسیل و انتگرال استدلالی به عنوان بنیان‌گذار منطق نمادین شناخته می‌شود. با وجود این که آثار او اولین در نوع خود به حساب می‌آمد اما برای جامعهٔ علمی ناشناخته بود. در نتیجه بسیاری از پیشرفت‌های حاصله به لایبنیتس به‌طور کاملاً مستقل از او توسط منطق گرایانی مانند جرج بول و آگوستوس دمورگان دوباره به دست آمد.
درست همان گونه که منطق گزاره‌ای به نوعی یک پیشرفت در مقایسه با سیستم قدیمی تر منطق قیاسی است، منطق محمولاتی ابداع شده توسط گوتلاب فرگ هم پیشرفتی در مقایسه با منطق گزاره‌ای به حساب می‌آید. منطق محمولاتی به عنوان " تلفیقی از ویژگی‌های شاخص منطق قیاسی و منطق گزاره‌ای " توصیف شده‌است، در نتیجه آغازگر دورانی تازه در تاریخ منطق است. با این وجود پیشرفت‌های جدید در منطق گزاره‌ای بعد از فرگ هم انجام گرفته‌است از جمله کسر طبیعی، درخت‌های درستی و جدول ارزش. کسر طبیعی توسط گرهارد گنتزن و جان لوکاسویچ ابداع شده‌است اما در مورد منشأ اختراع جدول درستی بحث و اختلاف نظر وجود دارد.
ایده‌های پشت جدول ارزش در نوشته‌های هر دو فرگ و برتراند راسل یافت شده‌اند با این حال ساختار جدولی (یعنی قرار دادن مقادیر درستی در جدول‌ها) عمدتاً به لودویگ ویتگنشتاین، امیل لئون پست یا هر دو نسبت داده می‌شود (مستقل از یکدیگر). جدا از فرگ و راسل دیگرانی که به داشتن نظریاتی ماقبل جدول‌های درستی شناخته می‌شوند عبارتند از فیلو، بول، چارلز سندرز پرس و ارنست شرودر. همچنین علاوه بر پست و ویتگنشتاین ساختار جدولی را منتسب به افرادی چون لوکاسویچ، شرودر، آلفرد نورث وایت‌هد ،ویلیام استنلی جوونز، جان ون و کلارنس اروینگ لوویس می‌دانند. در نهایت بعضی چون جان شاشکی این‌گونه نتیجه‌گیری می‌کنند که «بدیهی است که هرکسی می‌تواند مخترع جدول ارزش شناخته شود».

اصطلاح‌شناسی

به‌طور کلی، یک حساب سیستم صوری است که از مجموعه‌ای از عبارات نحوی، یک زیرمجموعهٔ مشخص از این عبارات (اصول) به علاوهٔ مجموعه‌ای از قواعد صوری تشکیل شده که یک رابطهٔ زوج مرتبی خاص را، به قصد آن که به عنوان یک هم نهشتی منطقی دریافت شود، روی فضای عبارات تعریف می‌کند.
هنگامی که قرار است سیستم صوری قرار است یک نظام منطقی باشد عبارات باید به صورت احکام برداشت شوند، قواعد شناخته شده به عنوان قوانین استنتاج معمولاً درستی نگهدار هستند. در این ساختار قوانین (که ممکن است شامل اصول شوند) می‌توانند برای به دست آوردن (استنتاج) فرمول‌هایی که بیانگر احکام درست هستند از فرمول‌های داده شده بر اساس احکام درست مورد استفاده قرار گیرند.
مجموعه اصول ممکن است تهی، یک مجموعه متناهی ناتهی، یک مجموعهٔ شمارای نامتناهی یا طرحواره‌ای از اصول باشد. صرف و نحو صوری به‌طور بازگشتی عبارات و فرمول‌های خوش فرم زبان را توصیف می‌کند. به علاوه ممکن است یک معناشناسی داده شود که درستی و ارزشگذاری را تعیین کند (همان تفسیرها).
زبان یک منطق گزاره‌ای تشکیل شده از موارد زیر است:
۱- مجموعه‌ای از نمادهای ابتدایی که با الفاظ مختلف از جمله فرمول‌های اتمی، جا نگهدارها، ورتنده‌های گزاره‌ای یا متغیر شناخته می‌شوند.
۲- مجموعه‌ای از عملگرها که با نام‌هایی مانند رابط‌های منطقی یا عملگرهای منطقی شناخته می‌شوند.
یک فرمول خوش ساخت می‌تواند یک فرمول اتمی یا هر فرمول دیگری که می‌تواند بر اساس فرمول‌های اتمی و با استفاده از عملگرها در حوزهٔ قوانین نحوی ساخته شود باشد.
ریاضی دانان گاهی اوقات میان ورتنده‌های گزاره‌ای، متغیرهای گزاره‌ای و طرح‌واره تمایز قایل می‌شوند. ورتنده‌های گزاره‌ای یک گزارهٔ خاص را نمایش می‌دهند در حالی که متغیرهای گزاره‌ای تمام مجموعه فرمول‌های اتمی را فرا می‌گیرند. رایج است که ورتنده‌های گزاره‌ای را با ,  و  و متغیرهای گزاره‌ای را با  ,  و   نشان دهند. برای طرح‌واره هم معمولاً از حروف الفبای یونانی  , ,  استفاده می‌شود.

مفاهیم پایه

شرح ذیل حدود یک حساب گزاره‌ای استاندارد را مشخص می‌کند. فرموله سازی‌های بسیاری وجود دارند که همه تقریباً در اصل یکسانند اما دارای تفاوت‌هایی در جزییات زیر هستند:
۱- زبان، که در واقع مجموعهٔ خاصی از نمادهای ابتدایی و عملگر هاست.
۲- مجموعهٔ اصول یا فرمول‌های مشخص
۳- مجموعه قواعد استنتاج
می‌توانیم هر گزاره داده شده را با یک حرف که آن را یک ثابت گزاره‌ای می‌نامیم نمایش دهیم که این کار متناظر با نمایش دادن اعداد با حروف الفبا در ریاضیات است برای مثال . لازم است که تمام گزاره‌ها دقیقاً یکی از دو ارزش ممکن یعنی صحیح یا غلط را داشته باشند. برای مثال  را گزاره‌ای در نظر بگیرید که " بیرون باران می‌بارد ". این گزاره اگر باران ببارد صحیح و در غیر این صورت غلط خواهد بود.
با شروع از نقیض عملگرهای درستی را تعریف می‌کنیم. برای نمایش نقیض   از  استفاده می‌کنیم، که می‌تواند تکذیب گزاره  تلقی شود. در مثال فوق  بیان می‌کند که «الان بیرون باران نمی‌بارد». زمانی که  درست باشد،  غلط است و زمانی که  درست باشد، غلط خواهد بود.   همواره همان مقدار درستی  را دارد.
ترکیب عطفی یک تابع درستی hاست که از دو گزاره ساده‌تر، مثلاً  و  ، یک گزاره مرکب می‌سازد. ترکیب عطفی  و  به صورت  نوشته می‌شود که نشان می‌دهد هر دو گزاره درست هستند .  را "  و  " می‌خوانیم. برای هر دو گزاره‌ای چهار وضعیت ممکن از مقادیر درستی وجود دارد:
1-   درست و  درست باشد
2-  درست و  غلط باشد
3-  غلط و  درست باشد
4-  غلط و  غلط باشد
ترکیب عطفی  و  در مورد یک درست و در سایر موارد غلط است. هنگامی که  گزاره‌ای باشد که «بیرون باران می‌بارد» و  گزاره‌ای باشد که «یک جبههٔ هوای سرد در اطراف کانزاس است»،  تنها زمانی درست است که بیرون باران ببارد و یک جبههٔ هوای سرد در اطراف کانزاس باشد. اگر بیرون باران نبارد یا جبههٔ هوای سرد در کانزاس نباشد  غلط خواهد بود.
ترکیب فصلی از آن جهت که یک گزاره مرکب از دو گزاره ساده‌تر تولید می‌کند مشابه ترکیب عطفی است. ترکیب فصلی را به  نمایش می‌دهیم که
" یا " خوانده می‌شود. این گزاره بیان می‌کند که یا  یا
 یا هردو درست هستند؛ بنابراین در مثال‌های بالا ترکیب فصلی  و  در تمام موارد غیر از مورد چهارم درست است. طبق مثال قبلی ترکیب فصلی بیان می‌کند که یا باران می‌بارد یا یک جبهه هوای سرد بر فراز کانزاس است (توجه شود که ترکیب فصلی باید به نوعی استفاده از واژه "یاً را شبیه‌سازی کند اما بیشتر شبیه "یا عمومی" است، که برای نشان دادن صحیح بودن حداقل یکی از دو گزاره استفاده می‌شود. پس ترکیب فصلی با "یا انحصاری" در زبان انگلیسی که نشان دهنده درست بودن دقیقاً یکی از دو گزاره است تفاوت دارد. به عبارت دیگر "یا انحصاری" زمانی که هر دو گزاره
 و  درست باشند غلط خواهد بود (مانند مورد اول). مثالی از یا انحصاری به شکل زیر خواهد بود: "شما می‌تواند پاستا یا سالاد بخورید، نه هر دو را". معمولاً در گفتگوهای عادی زبانی عبارت "ولی نه هر دو" حذف می‌شود اما به‌طور ضمنی مورد نظر است. در ریاضیات همیشه منظور از یا همان "یا عمومی است"، در صورتی که "یا انحصاری مورد نظر باشد به‌طور صریح، احتمالا با استفاده از "xor" مشخص می‌شود)
ترکیب شرطی نیز دو گزاره ساده‌تر را با هم ترکیب می‌کند و آن را با  نمایش می‌دهیم که خوانده می‌شود "اگر  آنگاه
". گزاره سمت چپ "شرط مقدم" و گزاره سمت راست "شرط موخر" خوانده می‌شود (از آنجا که ترکیب فصلی و عطفی شرکت پذیر هستند چنین مشخصه‌ای برای آن‌ها تعریف نمی‌شود).

بسته بودن نسبت به عملیات

منطق گزاره‌ای نسبت به عملگرهای درستی نگهدار بسته است. یعنی برای هر گزاره ,  هم یک گزاره است. برای مثال برای هر دو گزاره   ,  هم یک گزاره است که به‌طور مشابه برای ترکیب فصلی، ترکیب شرطی و ترکیب دو شرطی هم برقرار است. این بیان می‌کند که از آنجا که
 یک گزاره است می‌تواند با گزاره‌ای دیگر عطف شود. برای نمایش دادن این رابطه باید با استفاده از پرانتزها مشخص کنیم که کدام گزاره‌ها با هم عطف می‌شوند. برای نمونه  یک رابطه خوش ساخت نیست زیرا نمی‌دانیم که داریم  با  عطف می‌کنیم یا  با . بنابراین یا باید بنویسیم   تا اولی را نمایش دهیم با باید بنویسیم  تا نشان دهیم که شکل دوم مد نظر بوده‌است. با ارزیابی شرایط درستی در می‌یابیم که هر دو عبارت شرایط درستی یکسانی دارند و به‌طور جامع تر هر گزاره‌ای که با چینش دلخواهی از ترکیب ای عطفی ساخته شود، صرف نطر از جایگاه پرانتزها مقادیر درستی ثابتی خواهد داشت. این به خاطر آن است که ترکیب عطفی خاصیت پخشی دارد اما این موضوع نباید باعث شود وجود پرانتزها را بی‌دلیل بدانیم. به عنوان نمونه مقادیر درستی عبارت  با عبارت   یکسان نیست، بنابراین این‌ها عبارت‌های متفاوتی هستند که با توجه به قرارگیری پرانتزها از هم متمایز می‌شوند. خواننده می‌تواند این موضوع را با استفاده از جدول درستی تحقیق کند.
نکته: برای هر تعداد دلخواه از ورتنده‌های گزاره‌ای می‌توانیم مجموعه متناهی از حالت‌های ممکن برای مقادیر درستی آن‌ها را ارائه دهیم. یک راه ساده برای تولید این لیست استفاده از جداول درستی است. برای هر مجموعه  تایی از ورتنده‌های گزاره‌ای از حروف , , …,  استفاده می‌کنیم. در زیر این لیست  ردیف خالی می‌گذاریم. زیر  نیمهٔ اول ردیف‌ها را با «درست» (T) و نیمهٔ دوم را با «غلط» (F) پر می‌کنیم. زیر  یک چهارم را با T، یک چهارم بعدی را با F، یک چهارم سوم را با T و در نهایت یک چهارم آخر را با F پر می‌کنیم. ستون بعدی برای هر یک هشتم ردیف‌ها، ستون بعد تر برای هر یک شانزدهم و در نهایت ستون آخر برای هر ردیف بین مقادیر T و F نوسان می‌کند. این فرایند یک لیست کامل از نگاشت‌های درستی ممکن برای گزاره‌های اولیه را ارائه می‌دهد.

اثبات‌ها در حساب گزاره‌ای

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