همارزی گزارهها (اثبات بازگشتی): تبدیل گامبهگام گزاره به شکلهای سادهتر معادل
۱. مفهوم همارزی گزاره و قوانین پایه
در منطق ریاضی، دو گزاره $P$ و $Q$ را همارز گوییم هرگاه در همه حالتهای ممکن، مقدار درستی آنها یکسان باشد. این همارزی را با نماد $P \equiv Q$ یا $P \leftrightarrow Q$ نشان میدهیم. روش اثبات بازگشتی یعنی با اعمال قوانین منطقی روی یک گزاره، بدون تغییر معنی آن، آن را به گزارهای سادهتر تبدیل کنیم تا سرانجام به شکل استاندارد یا خیلی ساده برسیم. مهمترین قوانین همارزی که در این روش استفاده میشوند عبارتند از:
$P \vee F \equiv P$ (قوانین همانی)، $P \wedge T \equiv P$،
$P \vee \neg P \equiv T$ (قانون طرد شق ثالث)، $P \wedge \neg P \equiv F$ (قانون تناقض)،
$\neg(\neg P) \equiv P$ (نقیض مضاعف)،
$\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ و $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ (قوانین دمورگان).
۲. اثبات بازگشتی: گامهای گامبهگام سادهسازی
در روش اثبات بازگشتی، ما گزاره را به عنوان یک عبارت در نظر گرفته و در هر گام، یک قانون همارزی را روی یک زیرگزاره (یا کل گزاره) اعمال میکنیم تا شکل آن سادهتر شود. این فرایند تا رسیدن به سادهترین شکل ممکن (اغلب فرم نرمال فصلی4 یا فرم نرمال عطفی5) ادامه مییابد. در زیر یک مثال گامبهگام آورده شده است:
گام ۱: اعمال قانون جذب6 روی $P \vee (P \wedge Q) \equiv P$
نتیجه: $P \wedge (\neg Q \vee P)$
گام ۲: اعمال قانون جذب دوباره (این بار $P \wedge (\neg Q \vee P) \equiv P$)
نتیجه نهایی: $P$
بنابراین گزاره اولیه با متغیر $P$ همارز است.
برای اثبات همارزی دو گزاره $A$ و $B$ با روش بازگشتی، میتوانیم $A$ را گامبهگام به $B$ تبدیل کنیم یا هردو را به یک گزارهٔ سوم سادهتر تبدیل نماییم. این روش بهویژه وقتی تعداد متغیرها زیاد است (مثلاً $3$ یا $4$ متغیر) از جدول حقیقت با $8$ یا $16$ سطر، بسیار کارآمدتر است.
۳. جدول قوانین اصلی همارزی برای اثبات بازگشتی
| نام قانون | شکل همارزی (به زبان ریاضی) |
|---|---|
| نقیض مضاعف | $\neg(\neg P) \equiv P$ |
| دمورگان (عطف) | $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ |
| دمورگان (فصل) | $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ |
| جذب | $P \vee (P \wedge Q) \equiv P$ , $P \wedge (P \vee Q) \equiv P$ |
| توزیعپذیری | $P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$ |
| شرطی (استلزام) | $P \to Q \equiv \neg P \vee Q$ |
۴. کاربرد عملی: اثبات همارزی در یک مسئله روزمره
فرض کنید در یک سیستم امنیتی، شرط دسترسی به این صورت تعریف شده است: «اگر کاربر رمز درست وارد کند ($P$) و (یا اثر انگشت او تأیید شود ($Q$) یا کارت هوشمند او معتبر باشد ($R$))». یعنی گزاره $P \wedge (Q \vee R)$. حال امنیتسامانه ادعا میکند این شرط معادل گزاره $(P \wedge Q) \vee (P \wedge R)$ است. برای اثبات با روش بازگشتی از قانون توزیعپذیری استفاده میکنیم:
بدین ترتیب همارزی دو گزاره اثبات میشود. این نشان میدهد که شرط دسترسی را میتوان به صورت «(رمز درست و اثر انگشت تأیید) یا (رمز درست و کارت معتبر)» نیز نوشت که معادل همان گزاره اولیه است.
۵. چالشهای مفهومی
پاورقی
2 قانون توزیعپذیری (Distributive law): قاعدهای که بر اساس آن $P \wedge (Q \vee R)$ با $(P \wedge Q) \vee (P \wedge R)$ و همچنین $P \vee (Q \wedge R)$ با $(P \vee Q) \wedge (P \vee R)$ همارز است.
3 قانون حذف مضاعف نقیض (Double negation elimination): قاعدهای که میگوید نقیض نقیض یک گزاره معادل خود گزاره است: $\neg \neg P \equiv P$.
4 فرم نرمال فصلی (Disjunctive Normal Form - DNF): فرمی از یک گزاره که به صورت فصل (یا) چند عبارت عطفی (و) از متغیرها یا نقیض متغیرها نوشته میشود.
5 فرم نرمال عطفی (Conjunctive Normal Form - CNF): فرمی از یک گزاره که به صورت عطف (و) چند عبارت فصلی (یا) از متغیرها یا نقیض متغیرها نوشته میشود.
6 قانون جذب (Absorption law): دو همارزی $P \vee (P \wedge Q) \equiv P$ و $P \wedge (P \vee Q) \equiv P$ که در سادهسازی گزارهها بسیار کاربردی است.