الدلالة في المنطق الاقتراحي
ملخص
في هذه الحصة، يتم دراسة الدلالة في المنطق الاقتراحي، وتحديدًا تعيين قيم الحقيقة لعبارة وكيفية انتشارها من عبارة إلى أخرى عبر الروابط المنطقية. يتم تقديم مفهوم جداول الحقيقة، وعرض جداول الحقيقة للروابط المشتقة مثل النفي، التوازي، التوافق، التضمين، التضمين المزدوج، والتوازي الحصري. بالإضافة إلى ذلك، يتم تقديم تعريف للتعيين على مجموعة من العبارات الذرية وتوضيح كيفية انتشارها بشكل طبيعي على جميع العبارات التي يمكن إنشاؤها من هذه المجموعة. أخيرًا، يتم تحديد تعريفات العبارات الصحيحة، الممكنة وغير الممكنة، وتقديم أمثلة على التوتولوجيات والتناقضات. ومع ذلك، يتم الإشارة إلى أن حساب جداول الحقيقة للعبارات المعقدة يمكن أن يكون غير فعال، ولذلك يتم ذكر البحث عن طرق بديلة لحل مشاكل الصحة أو القابلية للتحقق.
أهداف التعلم:
بنهاية هذه الحصة سيكون الطالب قادرًا على
- شرح الدلالة في المنطق الاقتراحي
- استخدام جداول الحقيقة لتمثيل تعيينات قيم الحقيقة للعبارات في المنطق الاقتراحي
- نمذجة عبارة مع تعيين في المنطق الاقتراحي
- تطبيق القواعد الدلالية للمنطق الاقتراحي لتحديد ما إذا كانت العبارة توتولوجيا، تناقضًا أو احتمالًا
الفهرس
حول تعيينات قيم الحقيقة
دلالة الروابط في المنطق الاقتراحي
التعيينات في المنطق الاقتراحي
النماذج في المنطق الاقتراحي
مشكلة الكفاءة الكامنة في الدلالة في المنطق الاقتراحي
حول تعيينات قيم الحقيقة
سبق أن استعرضنا البنية النحوية والأنظمة الاستدلالية في المنطق الاقتراحي. وبينما كان هذا مفيدًا في مراجعة الطريقة التي يمكن بها الحصول على عبارات معينة من أخرى، لم نقل شيئًا حول تعيينات قيم الحقيقة. نظرًا لأننا قلنا كل ما يجب قوله حول تقنيات الاستدلال في المنطق الاقتراحي، سنبدأ دراستنا للدلالة في المنطق الاقتراحي، حيث نستعرض كيفية انتشار تعيينات قيم الحقيقة من عبارة إلى أخرى.
دلالة الروابط في المنطق الاقتراحي
يتم تقديم دلالة الروابط من خلال جداول الحقيقة، لأنها توفر طريقة بسيطة ومنظمة لتمثيل جميع التعيينات الممكنة على عبارة.
جدول الحقيقة للنفي المشترك
سنبدأ أولاً بالربط الأساسي الأكثر أهمية، وهو النفي المشترك. جدوله هو:
| \alpha | \beta | (\alpha\downarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
القيم “1” و “0” تعني “صحيح” و “خاطئ” على التوالي. كل صف في جدول الحقيقة هو تعيين ممكن على المتغيرات (أو العبارات الذرية) التي تشكل العبارة المراد دراستها. وبالمثل، كل عمود يحتوي على عبارة مكونة من هذه المتغيرات يعرض النتائج المحتملة لهذه التعيينات. من خلال تفسير هذا الجدول، نرى أن \alpha\downarrow\beta صحيحة فقط عندما تكون \alpha و\beta كلاهما خاطئين في نفس الوقت، وخاطئة في أي حالة أخرى. لهذا السبب، يُسمى الرابط \downarrow بـ النفي المشترك.
جداول الحقيقة للروابط المشتقة
من دلالة النفي المشترك، يمكن استنتاج دلالة الروابط الأخرى عبر تعريفاتها. وهذه هي:
| النفي: | \neg \alpha | := | (\alpha\downarrow\alpha) |
| التوازي الشامل: | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| التوافق: | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| التضمين: | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| التضمين المزدوج: | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| التوازي الحصري: | (\alpha \underline{\vee} \beta) | := | \neg(\alpha\leftrightarrow \beta) |
من هذه التعريفات، يمكن حساب جداول الحقيقة للروابط الأخرى:
النفي
| \alpha | \neg \alpha |
| 0 | 1 |
| 1 | 0 |
من هنا يأتي أن رابط النفي يتميز بقدرته على عكس قيمة الحقيقة للعبارة التي يتم تطبيقه عليها.
التوازي الشامل
| \alpha | \beta | (\alpha\vee\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
لهذا السبب التوازي الشامل (أو ببساطة “التوازي”) بين عبارتين يكون صحيحًا إذا كانت واحدة على الأقل من العبارتين صحيحة، ويكون خاطئًا عندما تكون كلتا العبارتين خاطئتين في نفس الوقت.
التوافق
| \alpha | \beta | (\alpha\wedge\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
كنتيجة لذلك، التوافق بين عبارتين يكون صحيحًا فقط إذا كانت كلتا العبارتين صحيحتين في نفس الوقت، ويكون خاطئًا في أي حالة أخرى. لهذا السبب، يمكن أيضًا أن يُطلق على هذا الرابط اسم “الإثبات المشترك”.
التضمين
| \alpha | \beta | (\alpha\rightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
من ثم يلخص جدول الحقيقة للتضمين مفهوم أن العبارة الصحيحة لا يمكن أن تتضمن إلا عبارة صحيحة، ولكن العبارة الخاطئة يمكن أن تتضمن أي شيء.
التضمين المزدوج
| \alpha | \beta | (\alpha\leftrightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
التضمين المزدوج يشكل عبارة صحيحة طالما أن العبارتين المكونتين لهما نفس قيم الحقيقة، ويكون خاطئًا في أي حالة أخرى.
التوازي الحصري
| \alpha | \beta | (\alpha\underline{\vee}\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
التوازي الحصري بين عبارتين يكون صحيحًا عندما تكون واحدة فقط من العبارتين صحيحة، ويكون خاطئًا في أي حالة أخرى.
التعيينات في المنطق الاقتراحي
مع ما تم وصفه سابقًا لدينا مفهوم بسيط لماهية التعيين؛ ومع ذلك، بالنسبة للتطورات التي سنراها لاحقًا سنحتاج إلى شيء أكثر دقة. إذا كان S=\{A_1, A_2, \cdots, A_n\} مجموعة من العبارات الذرية وكان \mathcal{F}(S) مجموعة من جميع العبارات التي يمكن إنشاؤها من العبارات في S، فإن التعريف التالي ينطبق:
تعريف: التعيين على S هو دالة \mathcal{A}: S \longrightarrow \{0,1\}
بعبارة أخرى، التعيين على S يوفر قيمة حقيقة لكل عبارة ذرية في S. يتسع تعيين \mathcal{A} لـ S بشكل طبيعي ليشمل جميع العناصر في \mathcal{F}(S). إذا كانت لدينا عبارة F\in \mathcal{F}(S)، فإن التعيين \mathcal{A} على S يتوافق مع صف واحد فقط في جدول الحقيقة لـ F ويقال أن \mathcal{A}(F) هو قيمة الحقيقة لـ F في ذلك الصف.
يتسع التعيين \mathcal{A} لـ S أيضًا لبعض العبارات التي لا توجد في \mathcal{F}(S). إذا كانت F_0 عبارة غير موجودة في \mathcal{F}(S) و S_0 مجموعة من الصيغ الفرعية الذرية لـ F_0، فإن كل الامتدادات لـ \mathcal{A} لـ S\cup S_0 لها نفس القيمة لـ F_0، ثم يُعرَّف \mathcal{A}(F_0) بتلك القيمة.
مثال: إذا كانت A و B عبارات ذرية وكان \mathcal{A} تعيينًا على \{A,B\} معرَّفة من خلال \mathcal{A}(A)=1 و \mathcal{A}(B)=0، فإن:
\mathcal{A}(A\wedge B)=0 و\mathcal{A}(A\vee B)=1
وعلى الرغم من عدم تحديد تعيين على متغير C، يمكن القول أن:
\mathcal{A}(A\wedge (C\vee \neg C))=1 و\mathcal{A}(B\vee (C\wedge \neg C))=0
يحدث هذا مع العبارتين الأخيرتين لأنه بغض النظر عن تعيين C، سيكون دائمًا:
\mathcal{A}(C\vee\neg C)=1 و\mathcal{A}(C\wedge\neg C)=0
وهو ما يمكننا مراجعته بسرعة بحساب جداول الحقيقة الخاصة بها.
| C | \neg C | (C\wedge \neg C) | (C \vee \neg C) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
■ نهاية المثال
النماذج في المنطق الاقتراحي
فلنعتبر تعيينًا \mathcal{A} على مجموعة من العبارات S. إذا كانت F\in S بحيث \mathcal{A}(F)=1، فإنه يقال أن التعيين \mathcal{A} يشكل نموذجًا لـ F، أو أن العبارة F مدعومة من قبل التعيين \mathcal{A} ونمثل ذلك بالكتابة
\mathcal{A}\models F.
وبناءً على ذلك، يتم وضع التعريفات التالية:
تعريف: يقال أن العبارة صحيحة عندما تكون مدعومة من قبل أي تعيين. إذا كانت F صحيحة، يتم الكتابة \models F . كما يُطلق على العبارات الصحيحة اسم التوتولوجيا.
مثال: العبارة (C\vee \neg C)، التي رأيناها من قبل، هي توتولوجيا.
■ نهاية المثال
تعريف: يقال أن العبارة قابلة للتحقق إذا كانت مدعومة من قبل أي تعيين. العبارات القابلة للتحقق التي ليست توتولوجيا تُسمى احتمالات.
تعريف: يقال أن العبارة غير قابلة للتحقق إذا لم تكن مدعومة من قبل أي تعيين. العبارات غير القابلة للتحقق تُسمى تناقضات. إذا كانت F تناقضًا، يُكتب \not\models F .
مثال: العبارة (C\wedge \neg C)، التي رأيناها من قبل، هي تناقض..
■ نهاية المثال
أمثلة على التوتولوجيا والتناقضات
افترض أننا نريد معرفة ما إذا كانت العبارة صحيحة أم لا. ما طرحناه الآن هو مشكلة اتخاذ قرار ضمن دلالة المنطق الاقتراحي. مشكلة اتخاذ القرار هي أي مشكلة يكون لها نتيجة “نعم” أو “لا” عند تقديم مدخلات معينة. إذا أعطيتنا عبارة F ونسأل ما إذا كانت صحيحة أم لا، فإننا نواجه مشكلة اتخاذ قرار نطلق عليها اسم مشكلة الصحة. وبالمثل، إذا سألنا ما إذا كانت قابلة للتحقق أم لا، فإننا نواجه مشكلة القابلية للتحقق. في المنطق الاقتراحي، تقدم جداول الحقيقة نهجًا منهجيًا لحل هذه المشاكل: إذا كانت جميع قيم الحقيقة الممكنة لـ F هي “1”، فإن F تكون صحيحة؛ إذا كانت بعض القيم فقط هي “1”، فإنها قابلة للتحقق؛ وأخيرًا، إذا كانت جميع القيم “0”، فإنها غير قابلة للتحقق.
مثال: لنأخذ العبارة ((A\wedge (A \rightarrow B)) \rightarrow B). لتحديد ما إذا كانت هذه العبارة صحيحة، قابلة للتحقق أو تناقضية، نقوم بحساب جدول الحقيقة لها.
| A | B | (A\rightarrow B) | (A\wedge(A\rightarrow B)) | ((A\wedge(A\rightarrow B))\rightarrow B) |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
من خلال ذلك نرى أن ((A\wedge(A\rightarrow B))\rightarrow B) لها قيمة الحقيقة “1” لجميع التعيينات الممكنة، وبالتالي تكون العبارة توتولوجيا.
■ نهاية المثال
مثال: لننظر الآن في العبارة (((A\rightarrow B)\rightarrow A)\wedge \neg A). حساب جدول الحقيقة لا يعطينا ما هو موضح أدناه:
| A | B | (A\rightarrow B) | ((A\rightarrow B)\rightarrow A) | \neg A | (((A\rightarrow B)\rightarrow A)\wedge \neg A) |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
ومن ثم يكون النتيجة تناقضًا.
■ نهاية المثال
مشكلة الكفاءة الكامنة في الدلالة في المنطق الاقتراحي
نظريًا، يمكننا تحديد ما إذا كانت العبارة صحيحة، احتمالية أو غير قابلة للتحقق ببساطة عن طريق حساب جدول الحقيقة الخاص بها، وهو ليس صعبًا بشكل خاص؛ ولكن، سهولة التنفيذ تأتي على حساب الكفاءة. إذا كانت لدينا عبارة F مكونة من n عبارات ذرية، فسنحتاج إلى حساب جدول حقيقة يحتوي على 2^n صفوف؛ لذلك، إذا كانت F مكونة من 23 عبارة ذرية، فسيحتوي جدول الحقيقة الخاص بها على 8,388,608 صفوف يجب حسابها. بهذه الطريقة، على الرغم من أنها ميكانيكية وسهلة التنفيذ، يبدأ الحساب بسرعة في أن يصبح غير ممكن مع زيادة تعقيد العبارات. ولهذا السبب، سيكون أحد أهدافنا المستقبلية هو إيجاد طريقة لحل مشاكل الصحة أو القابلية للتحقق دون الحاجة إلى حساب جداول الحقيقة. البحث عن هذه الطرق هو أحد المشاكل الرئيسية في أي منطق.