النتيجة الدلالية والتكافؤ الدلالي
الملخص
في هذه الدرس، سندرس النتيجة الدلالية والتكافؤ الدلالي في المنطق الاقتراحي، وهو استمرار طبيعي لما درسناه سابقًا. سنتعلم كيفية الحصول على مفهوم النتيجة الدلالية من توزيع القيم الصادقة وكيف يرتبط هذا المفهوم بنظرية الاستنتاج. بالإضافة إلى ذلك، سنشاهد أمثلة عملية لاستخدام جداول الحقيقة للحصول على خصائص مفيدة مثل حذف الاقتران وإدخال الفصل. سنستكشف أيضًا مفهوم التكافؤ الدلالي وسنرى كيف يرتبط بالخصائص التي نعرفها بالفعل. أخيرًا، سنوضح كيف أن استخدام النماذج وتقنيات الاستنتاج يمكن أن يبسط دراسة مشاكل النتيجة والتكافؤ الدلالي.
أهداف التعلم:
بنهاية هذا الدرس سيكون الطالب قادرًا على
- فهم مفهوم النتيجة الدلالية.
- فهم التفسيرات المختلفة للرمز ⊨.
- فهم إثبات نظرية الاستنتاج في نسختها الدلالية واستخدامها في دراسة النتيجة والتكافؤ الدلالي.
- فهم تعريف التكافؤ الدلالي وعلاقته بالقيم الصادقة.
- تطبيق نظرية الاستنتاج في نسختها الدلالية لتحويل مشاكل النتيجة إلى مشاكل الصلاحية.
- تطبيق الخصائص المفيدة في استخدام جداول الحقيقة لإثبات التكافؤات الدلالية.
- تطبيق قوانين الامتصاص، التوزيع وقوانين دي مورغان في تبسيط التعبيرات المعقدة.
- تحليل العلاقة بين النماذج والاستنتاجات في دراسة المنطق الاقتراحي.
الفهرس
التعيينات والنماذج
نظرية الاستنتاج (النسخة الدلالية)
استخدام نظرية الاستنتاج في دراسة النتيجة والتكافؤ الدلالي
التكافؤ الدلالي والخصائص
الخلاصة
دراسة النتيجة الدلالية والتكافؤ الدلالي هو استمرار طبيعي لما فعلناه عند مراجعة دلالات المنطق الاقتراحي. الآن سنراجع كيفية الحصول على مفهوم النتيجة الدلالية من توزيع القيم الصادقة وكيف ينشأ من هذا بشكل طبيعي نسخة دلالية من نظرية الاستنتاج. من هذا سيتم عرض أمثلة عملية لاستخدام جداول الحقيقة للحصول على بعض الخصائص المفيدة. يمكنك مشاهدة كل هذا أيضًا على قناة اليوتيوب.
التعيينات والنماذج
لنبدأ أولاً بتعريف ضروري للتطورات التي سنراها في هذه المقالة، تعريف النتيجة الدلالية.
| التعريف: التعبير G هو نتيجة دلالية لتعبير آخر F إذا كان لكل تعيين \mathcal{A} يكون فيه \mathcal{A}\models F \Rightarrow \mathcal{A}\models G. نحن نعبر عن ذلك بكتابة F\models G ونقرأه “التعبير F يعبر عن التعبير G” أو “G هو نتيجة دلالية لـ F.” |
مع هذا التعريف في اليد، يجب أن نلاحظ أن الرمز \models له في الواقع قراءات مختلفة حسب السياق:
- \mathcal{A} \models F يعني أن \mathcal{A}(F) = 1؛ أي أن “\mathcal{A} يعبر عن F“.
- G \models F يعني أنه إذا كان أي تعيين يعبر عن G، فإنه يعبر أيضًا عن F ونقرأه على أنه “F هو نتيجة لـ G.”
- \models F يعني أن F يصمد في كل تعيين؛ أي أن F هو تكرار.
وهكذا، على الرغم من أن الرمز \models يمكن أن يكون له تفسيرات متعددة، إلا أن السياق ليس غامضًا.
مفهوم النتيجة الدلالية قريب من مفهوم “الضمنية” الذي راجعناه سابقًا، بمعنى أنه إذا كان F\models G صحيحًا، فإن \models (F\rightarrow G) صحيح أيضًا. في الواقع، هذا يشبه جدًا نظرية الاستنتاج التي رأيناها قبل عدة دروس.
نظرية الاستنتاج (النسخة الدلالية)
[مشاهدة]
| النظرية: إذا كانت F و G تعبيرات عشوائية، فإن F\models G \Leftrightarrow \models (F\rightarrow G) صحيحة. | ||||||||||||||||||||||||||||||||||||||||
| البرهان: يتم الحصول على برهان هذه النظرية بسهولة بملاحظة جداول الحقيقة.
إذا ركزنا على معنى F\models G، سنرى أن هذا يعادل القول بأن \mathcal{A}\models F \Rightarrow \mathcal{A}\models G، وهو نفس الشيء مثل القول بأن \mathcal{A}\not\models F \vee \mathcal{A}\models G. الآن، إذا لاحظنا أن \mathcal{A}\not\models F هو في الواقع نفس الشيء مثل \mathcal{A}\models \neg F، فإننا نحصل على أن F\models G يعادل القول بأن \mathcal{A} \models \neg F \vee \mathcal{A}\models G. الآن، إذا صنعنا جدولًا للحقيقة لـ F \rightarrow G ووضعنا علامة خضراء على المنطقة التي تحقق فيها \mathcal{A} \models \neg F \vee \mathcal{A}\models G، فإننا سنرى التالي:
ومن هنا نستنتج أنه عندما F\models G دائمًا يحدث أن \models (F \rightarrow G)، والعكس صحيح، وهذا ليس سوى نظرية الاستنتاج ونظرية المعكوس الدلالي. |
افترض أننا نريد معرفة ما إذا كان التعبير G نتيجة لتعبير آخر F. سنشير إلى هذا باعتباره مشكلة النتيجة. باستخدام النظرية السابقة، يمكن تحويل هذه المشكلة إلى مشكلة الصلاحية، لأن “G هو نتيجة لـ F إذا وفقط إذا كان (F\rightarrow G) نظرية”.
استخدام نظرية الاستنتاج في دراسة النتيجة والتكافؤ الدلالي
من خلال جداول الحقيقة يمكن استنتاج بعض الخصائص التي تذكرنا ببعض الخصائص التي رأيناها في الماضي.
| مثال: إظهار باستخدام جداول الحقيقة أن الخصائص التالية صحيحة | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| حذف الاقتران: | (F\wedge G)\models F | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| إدخال الفصل: | F\models (F\vee G) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| التناقض: | (F\wedge\neg F)\models G | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| الحل: باستخدام نظرية الاستنتاج التي استعرضناها للتو، يمكننا تحويل مشكلة النتيجة إلى مشكلة الصلاحية. لحل مشكلة حذف الاقتران، يمكننا إعداد جدول الحقيقة التالي
بهذا نثبت أن ((F\wedge G)\rightarrow F) هو عبارة ثابتة، وبالتالي، باتباع عكس نظرية الاستنتاج، نحصل على (F\wedge G) \models F. يتم حل إدخال الفصل بطريقة مماثلة بإنشاء جدول حقيقة مناسب
هنا نلاحظ أن (F\rightarrow (F\vee G)) هو عبارة ثابتة، وبالتالي، حسب عكس نظرية الاستنتاج، نحصل على F\models (F\vee G) وأخيرًا، يتم إثبات خاصية التناقض باستخدام نفس الطريقة
من خلال هذا جدول الحقيقة، أثبتنا أن ((F\wedge \neg F)\rightarrow G) هو عبارة ثابتة، وبالتالي، حسب عكس نظرية الاستنتاج، نحصل على (F\wedge \neg F)\models G. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
التكافؤ الدلالي والخصائص
[مشاهدة]
| التعريف: إذا كانت F\models G وG\models F صحيحين في نفس الوقت، فنقول أن F وG متكافئين دلاليًا معًا. يتم تمثيل ذلك بكتابة F\equiv G. |
نتيجة لهذا التعريف، يكون التعبيران متكافئين دلاليًا إذا وفقط إذا كان لهما نفس القيم الصادقة.
| مثال: يمكن إظهار باستخدام جداول الحقيقة أن تكافؤات الدلالات المتناظرة صحيحة. |
| (F\downarrow G) \equiv (G\downarrow F) |
| (F\vee G) \equiv (G\vee F) |
| (F\wedge G) \equiv (G\wedge F) |
| (F\leftrightarrow G) \equiv (G\leftrightarrow F) |
| (F\underline{\vee} G) \equiv (G\underline{\vee} F) |
| مثال: إذا كانت F تعبيرًا عشوائيًا، \top هو تعبير ثابت و\bot هو تعبير متناقض، فيمكن إثبات التكافؤات الدلالية التالية باستخدام جداول الحقيقة: |
| (F\wedge \top) \equiv F |
| (F\vee \top) \equiv \top |
| (F\wedge \bot) \equiv \bot |
| (F\vee \bot) \equiv F |
| هذه التكافؤات تعرف بـ قوانين الامتصاص. |
| مثال: في دلالات المنطق الاقتراحي، القوانين التوزيعية للاقتضاء والتقاطع صحيحة أيضًا. |
| (F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H)) |
| (F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H)) |
| مثال: في دلالات المنطق الاقتراحي، قوانين دي مورغان صحيحة أيضًا. |
| \neg(F\wedge G) \equiv (\neg F \vee \neg G) |
| \neg(F\vee G) \equiv (\neg F \wedge \neg G) |
| تمرين: تمرين جيد هو إثبات أن قوانين الامتصاص، التوزيع وقوانين دي مورغان صحيحة باستخدام جداول الحقيقة. |
| مثال: إثبات باستخدام التكافؤات الدلالية أن التكافؤ التالي صحيح: ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D)). |
| الحل: يمكن إثبات هذا التكافؤ باستخدام جداول الحقيقة، ولكن إذا فعلنا ذلك، سنحتاج إلى التعامل مع تعبير يحتوي على 5 متغيرات اقتراحية، وهذا يعني إنشاء جدول حقيقة يحتوي على 2^5 = 32 صفًا، مما يفضل تجنبه. لتحقيق ذلك، سنستخدم التكافؤات التي أظهرناها بالفعل. أولاً، لاحظ أن (E\vee \neg E) هو تعبير ثابت. سنرمز إلى هذا التعبير الثابت بـ \top. باستخدام قوانين الامتصاص نحصل على: ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) باستخدام القوانين التوزيعية نحصل على: ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B)) أخيرًا، من خلال التماثل نحصل على: ((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D)) وبالتالي، من خلال هذه التكافؤات نحصل على: ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D)) وهذا ما أردنا إثباته. |
الخلاصة
إذا لاحظنا تطور هذا المثال الأخير، سنرى أنه مع زيادة عدد المتغيرات، تزداد تعقيد دراسة مشاكل النتيجة الدلالية والتكافؤ بشكل كبير إذا اعتمدنا على جداول الحقيقة. ومع ذلك، رأينا أن تطور فكرة النموذج أظهر شيئًا مشابهًا لتقنيات الاستنتاج التي درسناها بالفعل بالتفصيل. العلاقة بين النماذج والاستنتاجات هي ما سنراه قريبًا، والجمع بين الاثنين سيكون ما يوفر لنا في النهاية الكثير من المتاعب في دراسة المنطق.