لغة المنطق الاقتراحي

ملخص

في هذه المذكرة، يتم مراجعة لغة المنطق الاقتراحي كلغة فوقية تُستخدم للحصول على تعبيرات صالحة من اللغة الأساسية المكونة من رمزين. يتم شرح قواعد التركيب النحوي، مفاهيم المتغيرات الاقتراحية والمُوَصِّل، وكذلك يتم تقديم النفي المشترك، واستخدام الأقواس وإعادة الترتيب لتسهيل قراءة التعبيرات. بالإضافة إلى ذلك، يتم ذكر نطق التعبيرات المنطقية الاقتراحية. وأخيرًا، يتم تلخيص لغة المنطق الاقتراحي كأداة أساسية في الرياضيات والمنطق، ويتم التفكير في إمكانية العثور على “لغة أساسية من الأساس” التي يمكن من خلالها إعادة بناء كل شيء آخر.

أهداف التعلم:

بعد إكمال هذا القسم، من المتوقع أن يكون الطالب قادرًا على:

1. فهم مفهوم اللغة الفوقية وتطبيقها في المنطق الاقتراحي.
2. استيعاب قواعد التركيب النحوي للغة المنطق الاقتراحي.
3. معرفة مفهوم المتغير الاقتراحي واستخدامه في بناء التعبيرات.
4. فهم استخدام المُوَصِّل والنفي المشترك في لغة المنطق الاقتراحي.
5. تعلم كيفية استخدام الأقواس وإعادة الترتيب لتسهيل قراءة التعبيرات.
6. معرفة نطق التعبيرات في لغة المنطق الاقتراحي.
7. تلخيص لغة المنطق الاقتراحي كأداة أساسية في الرياضيات والمنطق.
8. التفكير في إمكانية العثور على “لغة أساسية من الأساس” التي يمكن من خلالها إعادة بناء كل شيء آخر.
9. تطبيق المفاهيم التي تم تعلمها في بناء التعبيرات المنطقية الاقتراحية.
10. استخدام لغة المنطق الاقتراحي لفهم وحل المشاكل الرياضية والمنطقية.

الفهرس

لغة المنطق الاقتراحي: الأبجديات وسلاسل الرموز
لنبدأ برمز واحد فقط
لنضف رمزًا ثانيًا
لغة المنطق الاقتراحي: التركيب النحوي
أمثلة على مراجعة التركيب النحوي
اتفاقيات التدوين
المتغيرات الفوقية والمُوَصِّل \downarrow
أمثلة على استخدام النفي المشترك
إعادة الترتيب والأقواس
الموصلات المشتقة
نطق التعبيرات المنطقية الاقتراحية
التلخيص والتأملات حول لغة المنطق الاقتراحي
الماتريكس وراء الماتريكس وراء فهم كل الأشياء

لغة المنطق الاقتراحي: الأبجديات وسلاسل الرموز

لنبدأ برمز واحد فقط

لبناء لغة المنطق الاقتراحي، سنبدأ دراستنا من أبسط الأبجدية: التي تحتوي على رمز واحد فقط. لا يهم الشكل الذي يتخذه، بل الحقيقة أنه فريد. إذا كتبنا باستخدام هذه الأبجدية، فإن الشيء الوحيد الذي يميز سلسلة من الرموز عن أخرى هو عدد المرات التي يتكرر فيها هذا الرمز. لذلك، إذا كان لدينا القدرة على كتابة سلاسل من الرموز بطول يصل إلى N، فلن نتمكن إلا من كتابة N سلاسل مختلفة. كما ترى، هذه الأبجدية محدودة للغاية وليس هناك الكثير مما يمكن قوله عنها.

لنضف رمزًا ثانيًا

إذا أضفنا رمزًا ثانيًا إلى أبجديتنا، تصبح الكتابة أكثر ثراءً مما كانت عليه في الأبجدية السابقة. الآن يمكننا أن نقدر كيفية ترتيب الرموز، على سبيل المثال إذا كان 0 و1 هما رموزنا، يمكننا التمييز بين 01 و10. كلتا السلسلتين تتضمنان نفس الرموز، ولكن بترتيب مختلف. إذا كانت أطول سلسلة يمكننا كتابتها هي بطول N =1,2,3,\cdots، فيمكننا كتابة 2^1=2 سلاسل بطول 1، 2^2=4 سلاسل بطول 2، 2^3=8 سلاسل بطول 3، وهكذا بشكل عام 2^N سلاسل مختلفة بطول N.

تمرين: اكتب على ورقة جميع السلاسل المختلفة التي يمكن كتابتها باستخدام الرموز بين 1 وN. كم عدد السلاسل التي سيتم كتابتها في المجمل؟

الحل: إذا كان S_N هو مجموع جميع السلاسل، بطول 1, 2, 3, وهكذا حتى نصل إلى N، فقد رأينا بالفعل أن:

\displaystyle S_N=2^1 + 2^2 + \cdots +2^{N-1} + 2^N

بضرب التعبير السابق في 2، نحصل على:

\displaystyle 2 S_N=2^2 + 2^3 + \cdots + 2^N + 2^{N+1}

وبالتالي:

\displaystyle S_N=2 S_N - S_N = 2^N-1

نتيجة لذلك، سيكون العدد الإجمالي للسلاسل المكتوبة على الورقة هو 2^N-1.

لغة المنطق الاقتراحي: القواعد النحوية

لقد رأينا أنه، باستخدام رمزين، يمكننا التمييز بين سلسلة وأخرى بناءً على طولها وترتيب الرموز. هذا مهم لأنه يسمح لنا بتعريف القواعد النحوية للأبجدية التي قمنا ببنائها. القواعد النحوية هي مجموعة من القواعد التي تفصل بين سلاسل الرموز إلى فئتين: تعبيرات وغير تعبيرات. إذا كان \mathcal{L}_2 هو مجموعة جميع السلاسل التي يمكن تكوينها باستخدام الرموز 0 و1، فإن القواعد النحوية لـ \mathcal{L}_2 هي مجموعة فرعية \mathcal{SL}_2\subset\mathcal{L}_2.

يمكننا تعريف مجموعة \mathcal{SL}_2 بالقواعد التكرارية التالية:

1. 00, 11 \in \mathcal{SL}_2
2. إذا كانت \alpha, \beta \in \mathcal{SL}_2، فإن 01\alpha\beta \in \mathcal{SL}_2

باستخدام هاتين القاعدتين يمكننا بناء تعبيرات من اللغة والتحقق مما إذا كانت سلسلة معينة تعبيرًا في اللغة أم لا. اللغة هي أبجدية مع قواعد نحوية مرتبطة بها. اللغة التي تم تقديمها هنا سنسميها “اللغة الأساسية ذات الرمزين”، أو \mathcal{B}_2.

أمثلة على مراجعة القواعد النحوية

لجعل هذه الأفكار أكثر سهولة في الفهم، دعونا نستعرض الأمثلة التالية:

مثال: نظرًا لأن 0000 و1111 موجودان في \mathcal{SL}_2، فإن 0100 00 01 0011 01 110000 و0111111111 موجودان في \mathcal{SL}_2؛ ولذلك، فهي تعبيرات في \mathcal{B}_2. يتم إثبات ذلك بتطبيق القواعد التي قدمناها للتو.

نهاية المثال \blacksquare

تمرين: في المثال السابق، رأينا كيفية بناء تعبيرات من تعبيرات أساسية أخرى. هذا ليس مهمة معقدة؛ ومع ذلك، في العملية العكسية التي تتعلق بإثبات ما إذا كان تعبير معين تعبيرًا أم لا، قد نواجه شيئًا أكثر تحديًا.

حدد، باستخدام القواعد النحوية، ما إذا كانت السلاسل التالية تعبيرات في \mathcal{B}_2:

1. {}012100

2. 101100

3. {}0100010000

4. 0101000011

5. {}01010000010000

6. 01010010000100101000011

الحل: قبل رؤية الحل، أنصحك بمحاولة القيام بذلك بنفسك أولاً، ثم مقارنة النتائج. إذا كنت قد فعلت ذلك بالفعل، فتابع 😊

1. 012100.

   كما نرى، تتضمن هذه السلسلة الرمز 2، الذي لا يوجد في \mathcal{L}_2؛ لذلك لا يمكن أن تكون هذه السلسلة جزءًا من \mathcal{SL}_2، وبالتالي ليست تعبيرًا في \mathcal{B}_2.

2. 101100.

   هنا نرى أن هذه السلسلة تبدأ بـ10. من القواعد النحوية يمكننا استنتاج أن جميع السلاسل التي تتجاوز طولها 2 تبدأ بالضرورة بـ01، وبالتالي لا يمكن أن تكون تعبيرًا في \mathcal{B}_2.

3. 0100010000

   تبدأ هذه السلسلة بـ01، لذلك تجتاز الاختبار الأول. من هنا، لكي تكون تعبيرًا في \mathcal{L}_2، يجب أن تكون الأجزاء المميزة باللون الأزرق قابلة للتفكيك بشكل فريد إلى تعبيرين.

   0100010000

   إذا لم يكن التفكيك فريدًا على الرغم من الالتزام بالقواعد النحوية، فإن القواعد النحوية المعرفة تكون غامضة وبالتالي يجب تصحيحها.

   بتحليل الجزء الأزرق، لدينا الفواصل المحتملة التالية:

   00010000	00010000	00010000
   00010000	00010000	00010000
   00010000

   في هذا الجزء يجب أن نلاحظ أنه إذا لم يكن الجزء الذهبي هو 0000 أو 1111، فيجب أن يبدأ الجزء الأزرق المقابل بـ01 لكي تكون السلسلة كاملة تعبيرًا، لذلك يمكن إجراء الاستبعادات التالية:

   0{}0010000❌	00010000✅	000{}10000❌
   00010000❌	00010000❌	00010000❌
   00010000❌

   لهذا السبب فإن الفصل الوحيد الذي يصمد أمام هذا التحليل هو 00010000، حيث أن الجزء الذهبي هو تعبير والجزء الأزرق يتم فصله بشكل فريد ومتسق مع القواعد النحوية. وأخيرًا، تقبل السلسلة 0100010000 تفكيكًا فريدًا ومتسقًا مع القواعد النحوية، وهو 0100010000، وبالتالي فهي تعبير في لغة \mathcal{B}_2.

4. 0101000011

   لهذه السلسلة يمكننا إجراء الفصل التالي، الذي سأحدده بالألوان:

   010100001111

   وفقًا للقواعد النحوية، لكي تكون السلسلة التي يزيد طولها عن 2 تعبيرًا، يجب أن تبدأ بـ01، ثم يتبع ذلك تعبيران، أحدهما ملون بالأزرق والآخر بالذهبي. من السهل أن نرى أن هذا الفصل فريد، لأنه إذا تغير طول المنطقة الزرقاء أو الذهبية، فلن تكون كلا الجزأين تعبيرًا في نفس الوقت.

5. 01010000010000

   بمراجعة السلسلة من اليمين إلى اليسار يمكننا العثور على الفصل التالي:

   \underbrace{01\underbrace{01\overbrace{00}\overbrace{00}}_{{expresión}}\underbrace{01\overbrace{00}\overbrace{00}}_{{expresión}}}_{{expresión}}

6. 01010010000100101000011

   عين حادة ستلاحظ أن هذه السلسلة طولها 23 ومن المستحيل بناء سلسلة بطول فردي باستخدام قواعد \mathcal{L}_2، التي تبني تعبيرات عن طريق تجميع سلاسل بطول زوجي. جميع سلاسل \mathcal{SL}_2 لها طول زوجي، ولذلك، 01010010000100101000011 ليست تعبيرًا في \mathcal{B}_2.

نهاية التمرين \blacksquare

اتفاقيات التدوين

العمل مع الأصفار والواحدات يمكن أن يكون مربكًا لإدراكنا ويمكن أن يدفعنا لارتكاب أخطاء. لجعل العملية أكثر ملاءمة للطريقة التي يدرك بها البشر الأشياء، يمكننا استخدام اتفاقيات التدوين وبعض الرموز الفوقية.

المتغيرات الفوقية والموصل \downarrow

الرمز الفوقي هو رمز يستخدم لتمثيل سلاسل الرموز في لغة الهدف. على سبيل المثال، عندما تم تعريف القواعد النحوية لـ\mathcal{SL}_2 لـ\mathcal{L}_2، تم استخدام الرموز \alpha و\beta لتمثيل تعبيرات \mathcal{B}_2. تُعرف هذه الرموز باسم المتغيرات الفوقية لـ\mathcal{B}_2: وهي رموز فوقية، عندما يتم استبدالها جميعًا بتعبيرات من اللغة، تولد من خلال القواعد النحوية تعبيرًا آخر من اللغة، كما تنص عليه القاعدة الثانية المتعلقة بعناصر \mathcal{SL}_2:

إذا كان \alpha,\beta \in \mathcal{SL}_2، فإن 01\alpha\beta \in\mathcal{SL}_2

لهذا السبب، يقال إن هذه المتغيرات الفوقية هي تعبيرات فوقية لـ\mathcal{B}_2.

لتسهيل الكتابة فيما بعد، سنستخدم الرمز الفوقي \downarrow لتمثيل السلسلة 01. هذا الرمز الفوقي هو ما نسميه موصلًا ويعرف باسم النفي المشترك لأسباب دلالية.

بهذا، يمكننا التعبير عن القواعد النحوية لـ\mathcal{SL}_2 بطريقة فوق لغوية من خلال القواعد التكرارية التالية:

1. جميع المتغيرات الفوقية لـ\mathcal{B}_2 هي تعبيرات فوقية لـ\mathcal{B}_2

2. إذا كانت \alpha و\beta متغيرات فوقية لـ\mathcal{B}_2، فإن \downarrow\alpha\beta هو تعبير فوقي لـ\mathcal{B}_2

بهذه القواعد، يمكننا كتابة تعبيرات فوقية، وعند استبدال جميع متغيراتها الفوقية بتعبيرات وموصلات في شكلها الممثل بالأصفار والواحدات، نحصل على تعبير من \mathcal{B}_2. كل تعبير فوقي من هذا النوع يشير إلى عائلة لا نهائية من التعبيرات لـ\mathcal{B}_2: مجموعة جميع التعبيرات لـ\mathcal{B}_2 التي يمكن تمثيلها بهذا الهيكل. هذا هو بالضبط ما يعنيه أن يكون لديك لغة رسمية.

أمثلة على استخدام النفي المشترك

مثال: من خلال التعبير الفوقي \downarrow\alpha\downarrow\beta\gamma يمكن الحصول على التعبيرات التالية من خلال الاستبدال:

1. باستبدال \alpha := 00، \beta := 011100 و\gamma := 010011

   نصل إلى التعبير:

   010001011100010011

2. إذا استبدلنا \alpha := 011100، \beta := 0111011100 و\gamma := 0111010011

   يتم إنتاج:

   010111000101110111000111010011

التعبير الفوقي \downarrow\alpha\downarrow\beta\gamma ليس فقط أسهل في الاستيعاب من أي تعبير آخر يفي بصيغته، ولكنه أيضًا يمثل جميع التعبيرات التي يمكن الحصول عليها من خلال استبدال متغيراته الفوقية بتعبيرات.

نهاية المثال \blacksquare

عند استبدال متغير فوقي، يتم استبداله في جميع الأماكن التي يظهر فيها.

مثال: لنأخذ بعين الاعتبار التعبير الفوقي \downarrow\downarrow\alpha\beta\downarrow\alpha\gamma

1. إذا استبدلنا \alpha:=11، نحصل على:

   \downarrow\downarrow 11\beta\downarrow 11\gamma

2. إذا استبدلنا الآن \beta:=011100، ستكون النتيجة:

   \downarrow\downarrow 11011100\downarrow 11\gamma

3. وإذا قمنا الآن بالتغيير \gamma:=011111، نحصل على:

   \downarrow\downarrow 11011100\downarrow 11011111

4. وأخيرًا، بتغيير \downarrow:=01، نصل إلى هذا التعبير:

   0101110111000111011111

نهاية المثال \blacksquare

النطق بالتعبيرات في المنطق القضي

على الرغم من أنه ليس ضروريًا للقيام بالمنطق، إلا أنه من المهم أن نأخذ في الاعتبار أن تواصلنا لا يعتمد فقط على الرموز المكتوبة، بل لدينا أيضًا الميل الطبيعي لنطق الأشياء في لغتنا الطبيعية. لذلك، هناك نطق للتعبيرات في لغة المنطق القضي تستدعي أفكارًا مشابهة لتلك التي تتعامل مع نظرائها في المنطق القضي. هذه النطق هي كما يلي:

خلاصة وتأملات حول لغة المنطق القضي

بهذا الجزء الأخير يكتمل بناء لغة المنطق القضي، التي يمكن تلخيصها كـ”لغة فوقية” تتيح الحصول على تعبيرات صحيحة في اللغة الأساسية المكونة من رمزين. لغة المنطق القضي هي لغة رسمية، حيث تحدد هيكل (أو شكل) التعبيرات في اللغة الأساسية، وكل تعبير منها يحدد شكل عائلة لا نهائية من التعبيرات في اللغة الأساسية. كما ذكرنا سابقًا، القواعد النحوية للغة رسمية تكون صارمة للغاية، لكنها دقيقة وواضحة: لا توجد غموض فيها.

المصفوفة وراء المصفوفة وراء فهم جميع الأشياء

أمر أخير. المنطق القضي والرياضيات يعتمدان إلى حد كبير على المنطق القضي، والذي بدوره يُبنى من لغة أساسية مكونة من أصفار وآحاد. هل يعني هذا أننا وصلنا إلى “المصفوفة” وراء المنطق والرياضيات؟ من الممكن. لكن من الممكن أيضًا النظر في لغة أساسية للغة الأساسية، يمكن من خلالها إعادة بناء كل شيء آخر؛ ومع ذلك، للعثور على مثل هذه اللغة، سنحتاج إلى اكتشاف مفاهيم أكثر أساسية من مفاهيم الترتيب والكمية (التي استخدمت لإنشاء اللغة الأساسية الأولى). العثور على لغة أساسية للأساس يتطلب التأمل في الجوانب الأكثر أساسية لما يعنيه “فهم الأشياء”. إذا تعمقت أكثر، إذا تمكنت من الوصول إلى الجذور، يمكننا القول إنك قد رأيت “المصفوفة وراء المصفوفة وراء فهم جميع الأشياء”، ومن الممكن أن تستمر هذه العملية التأسيسية إلى ما لا نهاية، مما يمنح كل خطوة تأسيسية طبقة جديدة من العمق في المعرفة.