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

1. تذكر تعريف الحرف والأشكال الطبيعية الاقترانية والانفصالية.
2. تحديد الهياكل الخاصة بالتعبير في CNF وDNF.
3. استخدام CNF أو DNF لتبسيط التعبيرات في المنطق الاقتراحي.

الفهرس
تعريف الحرف
تعريف الأشكال الطبيعية
نظرية الأشكال الطبيعية

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

تعريف الحرف (الليترال)

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

تعريف الأشكال الطبيعية

التعبير F يكون في الشكل الطبيعي الاقتراني (CNF) عندما يمكن كتابته على شكل اقتران بين انفصالات الحروف، أي:

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

وبالمثل، سيكون لدينا شكل طبيعي انفصالي (DNF) إذا كُتب على شكل انفصال بين اقترانات الحروف:

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

نظرية الأشكال الطبيعية

جميع التعبيرات في المنطق الاقتراحي مكافئة لتعبير في CNF وآخر في DNF.

البرهان:

يمكن إثبات ذلك عن طريق الاستقراء على تعقيد الصيغ F.

• الحالة الأساسية: إذا كان F تعبيرًا ذريًا، فيمكن كتابته في CNF وDNF في نفس الوقت، لأن: F\equiv F_D \equiv F_C، حيث F_C:=((F\vee F)\wedge (F\vee F)) و F_D:=((F\wedge F)\vee (F\wedge F))
• خطوة الاستقراء: لتكن G و H تعبيرين أيين، حيث تتحقق نتائج النظرية لهما؛ أي أن هناك H_C و G_C في CNF، و H_D و G_D في DNF بحيث:

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  لذا يمكننا كتابة:

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} ; \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD} ; \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  بدون فقدان العمومية، إذا F:= \neg G، فإننا باستخدام نظرية الاستبدال حول قوانين دي مورغان المعممة نحصل على:

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \bigwedge_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  من ناحية أخرى، إذا F:=G\wedge H، فإنه حسب نظرية الاستبدال:

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  وهو شكل طبيعي اقتراني. وبالمثل، إذا F:=H\vee G, فحينها:

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  أي أنه شكل طبيعي انفصالي.

  لذلك، الاستقراء مكتمل وجميع التعبيرات في المنطق الاقتراحي يمكن كتابتها في FND وCNF.

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