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

1. تطبيق خوارزمية FND/FNC على التعبيرات المحددة للعثور على أشكالها الطبيعية التواؤمية والتفكيكية.
2. فهم استخدام المفاتيح البسيطة والمركبة في المنطق الاقتراحي.
3. تحديد هيكل المفاتيح المركبة والصناديق السوداء.
4. استخدام جدول الحقيقة لتلخيص المعلومات حول الجهاز.
5. استخراج FND وFNC للجهاز من جدول الحقيقة الخاص به.
6. تصميم مفتاح مركب له نفس وظيفة الجهاز المعطى.

الفهرس
خوارزمية FND/FNC
خوارزمية الحصول على الشكل الطبيعي من جداول الحقيقة: الصناديق السوداء والمفاتيح المركبة
تمارين أمثلة

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

خوارزمية FND/FNC

خوارزمية FND/FNC هي سلسلة من الخطوات التي ستتيح لك اكتشاف الشكل الطبيعي المكافئ لأي تعبير في المنطق الاقتراحي سواء كان FND أو FNC (حسب الحالة). يتم ذلك على النحو التالي:

• الخطوة 1: استبدل جميع العبارات الفرعية من الشكل (F\rightarrow G) بـ (\neg F\vee G), وبالمثل مع (F\leftrightarrow G). كرر هذه الخطوة حتى تتم إزالة جميع الضمنيات والضمنيات المزدوجة من التعبير.
• الخطوة 2: إزالة النفي المزدوج وتطبيق قوانين دي مورغان حيثما كان ذلك ممكنًا. يجب تطبيق الاستبدالات التالية
  • \neg\neg G \longmapsto G
  • \neg(G\wedge H) \longmapsto (\neg G \vee \neg H)
  • \neg(G\vee H) \longmapsto (\neg G \wedge \neg H)

    عندما لا تبقى عبارات فرعية من الشكل \neg\neg G, \neg(G \wedge H) أو \neg(G \vee H), انتقل إلى الخطوة 3.

• الخطوة 3: هذه الخطوة تنقسم إلى قسمين اعتمادًا على ما إذا كنت ترغب في الوصول إلى FND أو FNC
  • إذا كنت تريد الوصول إلى FNC:

    استخدام توزيع \vee حيثما كان ذلك ممكنًا. وهذا يعني تطبيق الاستبدالات التالية:

    \left.\begin{matrix}G\vee(H\wedge K) \\ \\ (H\wedge K)\vee G \end{matrix} \right\} \longmapsto (G\vee H)\wedge (G\vee K)

    عندما لا تبقى عبارات من الشكل G\vee(H\wedge K) أو (H\wedge K)\vee G، ستكون قد وصلت إلى FNC.

  • إذا كنت تريد الوصول إلى FND:

    استخدام توزيع \wedge حيثما كان ذلك ممكنًا. وهذا يعني تطبيق الاستبدالات التالية:

    \left.\begin{matrix}G\wedge(H\vee K) \\ \\ (H\vee K)\wedge G \end{matrix} \right\} \longmapsto (G\wedge H)\vee (G\vee K)

    عندما لا تبقى عبارات من الشكل G\wedge(H\vee K) أو (H\vee K)\wedge G، ستكون قد وصلت إلى FND.

أمثلة

استخدم خوارزمية FND/FNC على التعبيرات التالية في شكلها الطبيعي التواؤمي والتفكيكي.

1. (A\rightarrow (B\rightarrow A)) [الحل]
2. ((A\vee B)\rightarrow(\neg B \wedge A)) [الحل]

خوارزمية الحصول على الشكل الطبيعي من جداول الحقيقة: الصناديق السوداء والمفاتيح المركبة

خوارزمية FND/FNC تسمح لنا باكتشاف، لأي تعبير في المنطق الاقتراحي، الشكل الطبيعي المكافئ له. ولكن هناك حالات لا يكون لدينا فيها تعبير ابتدائي للعمل معه في المقام الأول. هذا هو الحال عندما يكون لدينا نتيجة جدول الحقيقة لتعبير F ولكننا لا نعرف بنيته الاقتراحية. توضيح هذا بالكلمات هو عملية طويلة؛ ومع ذلك، يتم فهم التقنية بشكل أفضل بكثير من خلال إظهار أمثلة على كيفية تطويرها، لذلك سأترك بعض الأمثلة التي سأطورها في الفيديو، ولكن أولاً يجب مراجعة المفاهيم التالية:

• السلك: الوسيلة التي ينتقل من خلالها الإشارة
• العقدة: النقطة التي يلتقي فيها ثلاثة أسلاك أو أكثر.
• المفتاح البسيط: جهاز يقبل حالتي التشغيل (1) والإيقاف (0)، ويكون دائمًا في واحدة، وفقط واحدة، من هذه الحالات. تسمح حالة التشغيل بمرور الإشارة وتمنع حالة الإيقاف مرورها.
• المفتاح المركب: هو جهاز مكون من مفاتيح بسيطة وأسلاك.
• الصندوق الأسود: هو أي جهاز لا يمكن ملاحظة هيكله الداخلي.

يتم نمذجة المفاتيح البسيطة من خلال المتغيرات الاقتراحية، والمفاتيح المركبة من خلال تعبيرات المنطق الاقتراحي. أبسط الحالات هي تلك التي يتم الحصول عليها من روابط التفكيك والتواؤم الموضحة أدناه

مخطط التواؤم

مخطط التفكيك

تمارين أمثلة

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

   a) لخص هذه المعلومات في جدول الحقيقة [الحل]

   b) من جدول الحقيقة، استخرج FND وFNC التي تعيد إنتاج تشغيل الجهاز. [الحل]

   c) استخدم FNC أو FND التي تم الحصول عليها في الخطوة السابقة (الأبسط) لتصميم مفتاح مركب له نفس وظيفة الجهاز. [الحل]

2. نفس التمرين السابق، ولكن الآن يحتوي الجهاز على 5 مفاتيح. [تحدي للقارئ]