شكل عادي منفصل

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

التعريف

تعتبر الصيغة المنطقية في الشكل العادي المنفصل إذا كان فصل منطقي لواحد أو أكثر من العطوف المنطقية لواحد أو أكثر من الرموز(حروف). ^[1] تكون صيغة الشكل العادي المنفصل مكتملة إذا كان كل من متغيراته تظهر بالضبط مرة واحدة في كل ترابط. كما في الشكل العادي المرتبط عوامل المسألة المنطقية هم و ( $\land$ )، أو ( $\lor$ )، نفي ( $\neg$ ). عامل النفي يمكن استخدامه فقط كجزء من متغير، الذي يعني انه يسبق المتغير في المسألة.

التالي قواعد خالية من السياق لشكل العادي المنفصل:

الفصل → (عطف $\lor$ فصل)
فصل → عطف
عطف → (متغير $\land$ عطف)
عطف → متغير
حرف → $\neg$ متغير
حرف → متغير

بحيث يكون المتغير أي متغير.

جميع الامثلة التالية صيغ في الشكل العادي المنفصل:

$(A \land \neg B \land \neg C) \lor (\neg D \land E \land F)$
$(A \land B) \lor C$
$A \land B$
$A$

لكن الصيغ التالية ليست كذلك:

$\neg (A \lor B)$ , بسبب ان أو متداخلة في داخل النفي
$\neg (A \land B) \lor C$ , بسبب ان أو متداخلة في النفي
$A \lor (B \land (C \lor D))$ , بسبب ان ومتداخلة في النفي

الصيغة $A \lor B$ في الشكل العادي المنفصل، لكن ليست مكتملة، النسخة الذي تعادله في الصيغة المكتملة: $(A \land B) \lor (A \land \neg B) \lor (\neg A \land B)$ .

تحويل الصيغة إلى شكل عادي المنفصل

Karnaugh map of the disjunctive normal form (¬A∧¬B∧¬D) ∨ (¬A∧B∧C) ∨ (A∧B∧D) ∨ (A∧¬B∧¬C)

خريطة كارنوف لشكل العادي المنفصل

تحويل الصيغة إلى شكل عادي منفصل يتضمن استخدام تكافؤ المنطقي، مثل إزالة النفي المضاعف (نفي النفي إثبات)، قوانين دي مورغان ، قانون التوزيع.

كل الصيغ المنطقية يمكن تحويلها إلى ما يعادله بشكل العادي المنفصل. ^[1]^:152-153

لكن في بعض الحالات التحويل إلى شكل عادي منفصل يمكن أن يقود إلى تفجير أُسي لصيغة.

مثال، تحويل هذه الصيغة: $(X_{1} \lor Y_{1}) \land (X_{2} \lor Y_{2}) \land \dots \land (X_{n} \lor Y_{n})$ إلى شكل عادي منفصل ينتج صيغة بحدين.

كل دالة بوليانية يمكن تمثيلها بشكل واحد عادي منفصل كامل فقط (ملاحظة: تجاهل الإختلاف القائمة على الترابط والتبديل بين والمنطقية وأوالمنطقية). في المقابل شكلان عاديين منفصلان ربما يدلان على نفس الدالة البوليانية.

التعقيد الحسابي

في مسألة قابلية الارضاء المنطقية على صيغ شكل العادي المرتبط يكون مسألة NP صعبة، بسبب مبدأ الازدواجية، وكذلك مشكلة قابلية التزوير في الشكل العادي المنفصل. لذا يكون مسألة co-NP صعبة لتقرير إذا كان صيغة شكل العادي المنفصل طوطولوجي.

اقرأ ايضًا

•اختصار التوابع المنطقية بطريقة كوين ماكلوسكي، حصول على الحد الأدنى من الأشكال العادية المنفصلة لدالة بوليانية.

•جدول الحقيقة.

مصادر

^ ^أ ^ب B.A. Davey and H.A. Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.

روابط خارجية

Hazewinkel، Michiel، المحرر (2001)، "Disjunctive normal form"، Encyclopedia of Mathematics، سبرنجر، ISBN:978-1-55608-010-4

[Davey.Priestley.1990-1] أ ^ب B.A. Davey and H.A. Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.

[1]