الصيغة الطبيعية المنفصلة

في المنطق البولياني ، يُعدّ الشكل الطبيعي الانفصالي ( DNF ) شكلاً طبيعياً لصيغة منطقية تتألف من فصل العطفات؛ ويمكن وصفه أيضاً بأنه " أو" من "و" ، أو مجموع نواتج ، أو - في المنطق الفلسفي - مفهوم عنقودي . ^{[ 1 ]} يُعتبر الشكل الطبيعي الانفصالي ونظيره الشكل الطبيعي العطفي من أكثر الطرق المعيارية شيوعاً لتمثيل التعبيرات البوليانية . ويُستخدمان على نطاق واسع في تطبيقات متنوعة مثل تصميم الدوائر أو إثبات النظريات آلياً .

تُعتبر الصيغة المنطقية في صيغة الفصل الطبيعي (DNF) إذا كانت عبارة عن فصل بين عنصرين أو أكثر من عناصر الربط بين عنصر واحد أو أكثر من عناصر الربط . ^{[ 2 ] [ 3 ] [ 4 ]} وتكون صيغة الفصل الطبيعي (DNF) في صيغة الفصل الطبيعي الكاملة إذا ظهر كل متغير من متغيراتها مرة واحدة فقط في كل عنصر ربط، وظهر كل عنصر ربط مرة واحدة على الأكثر (بحسب ترتيب المتغيرات). وكما هو الحال في صيغة الربط الطبيعي (CNF)، فإن عوامل الربط الوحيدة في صيغة الفصل الطبيعي (DNF) هي " و " و (${\displaystyle \wedge }$)، أو (${\displaystyle \vee }$)، وليس (${\displaystyle \neg }$). لا يمكن استخدام عامل النفي إلا كجزء من قيمة حرفية، مما يعني أنه لا يمكن استخدامه إلا قبل متغير اقتراحي .

فيما يلي قواعد نحوية خالية من السياق لـ DNF:

لم يكمل السباق${\displaystyle \,\to \,}$( منفصل )${\displaystyle \,\mid \,}$( منفصل )${\displaystyle \,\lor \,}$لم يكمل السباق

منفصل${\displaystyle \,\to \,}$حرفي${\displaystyle \,\mid \,}$حرفي${\displaystyle \,\land \,}$منفصل

حرفي${\displaystyle \,\to \,}$عامل${\displaystyle \,\mid \,}$${\displaystyle \,\neg \,}$عامل

حيث يمثل المتغير أي متغير.

على سبيل المثال، جميع الصيغ التالية هي في صيغة DNF:

• ${\displaystyle (A\land \neg B\land \neg C)\lor (\neg D\land E\land F\land D\land F)}$
• ${\displaystyle (A\land B)\lor (C)}$
• ${\displaystyle (A\land B)}$
• ${\displaystyle (A)}$

الصيغة${\displaystyle A\lor B}$هي في حالة DNF، ولكن ليس في حالة DNF كاملة؛ النسخة المكافئة في حالة DNF الكاملة هي${\displaystyle (A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)}$.

الصيغ التالية ليست في صيغة DNF:

• ${\displaystyle \neg (A\lor B)}$بما أن عامل "أو" متداخل داخل عامل "ليس"
• ${\displaystyle \neg (A\land B)\lor C}$لأن عملية AND متداخلة داخل عملية NOT
• ${\displaystyle A\lor (B\land (C\lor D))}$، لأن عامل "أو" متداخل داخل عامل "و" ^{[ 5 ]}

في المنطق الكلاسيكي، يمكن تحويل كل صيغة اقتراحية إلى صيغة DNF ^{[ 6 ]} ...

تنصّ هذه النظرية على إمكانية تحويل جميع الصيغ المتسقة في منطق القضايا إلى الصيغة الانفصالية العادية. ^{[ 14 ] [ 15 ] [ 16 ] [ 17 ]} وتُعرف هذه النظرية بنظرية الصيغة الانفصالية العادية . ^{[ 14 ] [ 15 ] [ 16 ] [ 17 ]} وصيغتها الرسمية هي كما يلي:

نظرية الصيغة الطبيعية المنفصلة: لنفترض${\displaystyle X}$هي جملة في لغة القضايا${\displaystyle {\mathcal {L}}}$مع${\displaystyle n}$أحرف الجمل، والتي سنرمز إليها بـ${\displaystyle A_{1},...,A_{n}}$. لو${\displaystyle X}$إذا لم يكن ذلك تناقضًا، فإنه مكافئ وظيفيًا لفصل اقترانات من الشكل${\displaystyle \pm A_{1}\land ...\land \pm A_{n}}$، أين${\displaystyle +A_{i}=A_{i}}$، و${\displaystyle -A_{i}=\neg A_{i}}$[ ^{15 ]​}

يستند البرهان إلى الإجراء المذكور أعلاه لتوليد صيغ الجملة المنفصلة من جداول الحقيقة . ويكون البرهان رسميًا كما يلي:

يفترض${\displaystyle X}$هي جملة في لغة افتراضية حروفها هي${\displaystyle A,B,C,\ldots }$لكل صف من${\displaystyle X}$اكتب جدول الحقيقة الخاص بـ 's'، واكتب العطف المقابل.${\displaystyle \pm A\land \pm B\land \pm C\land \ldots }$، أين${\displaystyle \pm A}$يُعرَّف بأنه${\displaystyle A}$لو${\displaystyle A}$يأخذ القيمة${\displaystyle T}$في ذلك الصف، وهو${\displaystyle \neg A}$لو${\displaystyle A}$يأخذ القيمة${\displaystyle F}$في ذلك الصف؛ وبالمثل بالنسبة لـ${\displaystyle \pm B}$،${\displaystyle \pm C}$إلخ. ( الترتيب الأبجدي لـ${\displaystyle A,B,C,\ldots }$في العطفات، يكون الاختيار عشوائيًا تمامًا؛ يمكن اختيار أي عطف آخر بدلاً منه. الآن، شكّل فصلًا لجميع هذه العطفات التي تتوافق مع${\displaystyle T}$صفوف من${\displaystyle X}$جدول الحقيقة. هذا الفصل هو جملة في${\displaystyle {\mathcal {L}}[A,B,C,\ldots$ ;\land ,\lor ,\neg ]} , ^{[ 18 ]} وهو، بحسب المنطق أعلاه، مكافئ وظيفيًا لـ${\displaystyle X}$من الواضح أن هذا التركيب يفترض مسبقًا أن${\displaystyle X}$يأخذ القيمة${\displaystyle T}$على صف واحد على الأقل من جدول الحقيقة الخاص به؛ إذا${\displaystyle X}$لا يفعل، أي إذا${\displaystyle X}$إذا كان هذا تناقضاً ،${\displaystyle X}$يعادل${\displaystyle A\land \neg A}$وهو بالطبع جملة في${\displaystyle {\mathcal {L}}[A,B,C,\ldots$ ;\land ,\lor ,\neg ]} . ^{[ 15 ]}

تُعد هذه النظرية طريقة ملائمة لاستخلاص العديد من النتائج الميتافيزيقية المفيدة في منطق القضايا، مثل النتيجة البديهية المتمثلة في أن مجموعة الروابط${\displaystyle \{\land ,\lor ,\neg \}}$مكتمل وظيفيًا . ^{[ 15 ]}

أي صيغة منطقية مبنية من${\displaystyle n}$المتغيرات، حيث${\displaystyle n\geq 1}$.

هناك${\displaystyle 2n}$القيم الحرفية المحتملة:${\displaystyle L=\{p_{1},\lnot p_{1},p_{2},\lnot p_{2},\ldots ,p_{n},\lnot p_{n}\}}$.

${\displaystyle L}$لديه${\displaystyle (2^{2n}-1)}$المجموعات الفرعية غير الفارغة. ^{[ 19 ]}

هذا هو الحد الأقصى لعدد الروابط التي يمكن أن تحتوي عليها جملة DNF. ^{[ 13 ]}

يمكن أن يصل عدد حالات الانسحاب الكامل إلى${\displaystyle 2^{n}}$روابط، رابط واحد لكل صف من صفوف جدول الحقيقة.

المثال 1

لنفترض صيغة بمتغيرين${\displaystyle p}$و${\displaystyle q}$.

أطول مدة ممكنة للانسحاب من السباق${\displaystyle 2^{(2\times 2)}-1=15}$حروف العطف: ^{[ 13 ]}

${\displaystyle {\begin{array}{lcl}(\lnot p)\lor (p)\lor (\lnot q)\lor (q)\lor \\(\lnot p\land p)\lor {\underline {(\lnot p\land \lnot q)}}\lor {\underline {(\lnot p\land q)}}\lor {\underline {(p\land \lnot q)}}\lor {\underline {(p\land q)}}\lor (\lnot q\land q)\lor \\(\lnot p\land p\land \lnot q)\lor (\lnot p\land p\land q)\lor (\lnot p\land \lnot q\land q)\lor (p\land \lnot q\land q)\lor \\(\lnot p\land p\land \lnot q\land q)\end{array}}}$

أطول جملة DNF كاملة ممكنة تحتوي على 4 روابط: وهي مسطرة.

هذه الصيغة عبارة عن تحصيل حاصل . يمكن تبسيطها إلى${\displaystyle (\neg p\lor p)}$أو إلى${\displaystyle (\neg q\lor q)}$، والتي هي أيضاً عبارات تكرارية، بالإضافة إلى كونها عبارات DNF صحيحة.

المثال 2

كل DNF من صيغة eg${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$لديه${\displaystyle 2^{n}}$حروف العطف.

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

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

يُعدّ k-DNF أحد المتغيرات المهمة المستخدمة في دراسة التعقيد الحسابي . تُصنّف الصيغة في k-DNF إذا كانت في صيغة DNF وتحتوي كل جملة ربط على k متغيرات على الأكثر. ^{[ 20 ]}

• الشكل الجبري الطبيعي – عملية XOR لجمل AND
• صيغة بليك الكنسية – DNF بما في ذلك جميع العناصر الأولية
  • خوارزمية كوين-مكلوسكي – خوارزمية لحساب المضامين الأولية
• ثنائية الاقتران/الانفصال
• المنطق الافتراضي
• جدول الحقيقة

• أرورا، سانجيف ؛ باراك، بواز (20 أبريل 2009). التعقيد الحسابي: منهج حديث . مطبعة جامعة كامبريدج . ص  579. doi : 10.1017/CBO9780511804090 . ISBN 9780521424264.
• ديفي، بكالوريوس الآداب؛ بريستلي، هـ. أ. (1990). مقدمة في الشبكات والترتيب . كتب كامبريدج الرياضية. مطبعة جامعة كامبريدج.
• ديرشوفيتز، ناحوم ؛ جوانو، جان بيير (1990). "أنظمة إعادة الكتابة". في فان ليوين، يان (محرر). النماذج الرسمية والدلالات . دليل علوم الحاسوب النظرية. المجلد  ب. إلسيفير . الصفحات 243-320 . ISBN  0-444-88074-7.
• غريس، ديفيد؛ شنايدر، فريد ب. (22 أكتوبر 1993). مدخل منطقي للرياضيات المتقطعة . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-0-387-94115-8.
• هيلبرت، ديفيد ؛ أكرمان، فيلهلم (1999). مبادئ المنطق الرياضي . الجمعية الرياضية الأمريكية. ISBN 978-0-8218-2024-7.
• هاوسون، كولين (11 أكتوبر 2005) [1997]. المنطق مع الأشجار: مقدمة في المنطق الرمزي . روتليدج. ISBN 978-1-134-78550-6.
• بوست، إميل (يوليو 1921). "مقدمة لنظرية عامة للمسائل الأولية". المجلة الأمريكية للرياضيات . 43 (3): 163-185 . doi : 10.2307/2370324 . JSTOR 2370324 . 
• سموليان، ريموند م. (1968). منطق الدرجة الأولى . Ergebnisse der Mathematik und ihrer Grenzgebiete. المجلد.  43 (الطبعة الأولى، الطبعة الثانية 1971  طبعة). نيويورك هايدلبرغ برلين: سبرينغر-فيرلاغ . ص.  160. دوى : 10.1007/978-3-642-86718-7 . رقم ISBN 978-3-642-86718-7.
• سوبوليف، إس كيه (2020) [1994]، "الصيغة الطبيعية المنفصلة" ، موسوعة الرياضيات ، دار نشر إي إم إس
• وايتسيت، ج. إلدون (24 مايو 2012) [1961]. الجبر البولياني وتطبيقاته . شركة كورير. ISBN 978-0-486-15816-7.