دالة بوليانية

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من الوظيفة البوليانية)
اذهب إلى: تصفح، ‏ ابحث

في الرياضيات، الدالة البوليانية هي دالة مع n متغيرات نقول أنَّ f تقبل متجه اذا 1 =(f(a ونقول انها ترفضه اذا 0 =(f(a . دالة بوليانية ليست بالضرورة متعلقة بكل متغيراتها ونقول أنَّ الدالة f متعلقة بالمتغير xi  اذا يوجد اعداد ثابتة بحيث أنَّ :

بما أنَّه يوجد متجهات في فإن عدد الدوال البوليانية هو .

دوال بوليانية متناظرة[عدل]

دالة بوليانية نقول عنها متناظرة (symmetric) اذا اعتمدت فقط على عدد ال-1 في المُدخل وليس على مكانها اي على توزيعها على المتغيرات , لذا فانه يوجد دوال كهذه , امثلة لدوال كهذه :

  • دالة الحفة (threshold function)
  • دالة الاكثرية (majority function)
  • دالة الزوجية (parity function)
  • دالة العد (modular function)

ترجمة الخصائص[عدل]

يمكن ترجمة كل خاصية او صفة إلى دالة بوليانية ملائمة وهذه الصفة يمكن ان تحقق او لا , مثال : الصفة "العدد أولي" ملائم للدالة PRIME بحيث :

عدد اولي .

ولنترجم خصائص المُخططات (graphs) على المجموعة نُعرف لكل ضلع متغير وهذا المتغير 1 اذا و-0 خلاف هذا . لذا اي مُتجه قيمه 0-1 بطول يعطينا مُخطط G . عندها خاصية يمكن ترجمتها بشكل مناسب , بشكل عام :

خاصية مُخطط

مثال :

دالة المخطط الكامل (the clique function) او (Clique(n,k : وهذه الدالة تقبل متجه x اذا وفقط اذا Gx يحوي مخطط كامل مع k رؤوس .

مصفوفة بوليانية[عدل]

مصفوفة بوليانية هي مصفوفة بحيث أنَّ كل الخلايا قيمتها اما 0 او 1 .

اذا (f(x,y دالة بوليانية مع 2n متغيرات حينها يمكن النظر اليها على انها مصفوفة ,A, بكبر بحيث أن كل سطر وعامود موسوم بواسطة مُتجه من , ويتحقق : (A[x,y]=f(x,y .

عمليات بوليانية[عدل]

العمليات البوليانية الاساسية هي :

  • عملية النقض (negation) ويرمز لها ب- NOT : وفي بعض الاحيان :
  • عملية الضم (conjuction) , ويرمز لها ب- AND :
  • عملية الفصل (disjunction) , ويرمز لها ب- OR :
  • عملية الزوجية (parity) , ويرمز لها ب-XOR :
  • عملية الاستلزام (implication) وهي

من هذه العمليات يمكن تركيب دوال بوليانية اكثر تعقيدا من دوال بسيطة .

مثال :

لنفرض أنَّ حينها يمكن أن نبني دالة جديدة :

المكعب الثنائي[عدل]

المعكب الثنائي هو مجموعة كل المتجهات ( اي ) ويمكن التعبير عنه بواسطة مُخطط (GRAPH) بحيث أنه يوجد لهذا المكعب رؤوس وكل رأس موسوم بواسطة مُتجه(vector) من المجموعة ويوجد ضلع بين رأسين اذا اختلف المتجهين اللذان هما وسما الرأسين في مكان واحد . لذا فانه يوجد اضلاع في هذا المخطط , كما انَّه مخطط ثنائي . نرمز لمكعب مع رؤوس ب- .

HypercubeCycles.png

A هو مُكعب جزئي بُعده d هو مجموعة شكلها كالتالي : بحيث أنَّ كل Ai هو أحد المجموعات : بالاضافة إلى أنه فقط ل- d من المجموعات يتحقق التالي : .

كل دالة بوليانية يمكن النظر اليها على انها تلوين (coloring) بلونين . المخطط الثنائي الجزئي نحصل عليه بازالة كل الاضلاع التي رؤوسها تشترك بنفس اللون . الكثافة في المخطط له فائدة في تعقيد الدوائر البوليانية للدالة f .

الاشكال الطبيعية[عدل]

هنالك شكلان طبيعيان للدوال البوليانية : CNF , DNF . لعل اكثر الوسائل بديهية لتمثيل دالة بوليانية هو جدول الحقيقة الخاص بالدالة اي قائمة بكل الازواج لكل . هذه الطريقة اغلب الاحيان غير ملائمة , وسيلة اكثر ملائمة هي DNF و-CNF .

متغير بسيط (literal) هو المتغير البولياني او ضده اي اما ان يكون او . بشكل عام الترميز التالي شائع الاستخدام : و- لذا فانه لكل سلسلة يتحقق التالي :

احادي الحدود (monomial) هو AND متغيرات بسيطة , والتعبير (clause) هو or متغيرات بسيطة . مثال :

  • هو احادي الحدود .
  • هو تعبير .

DNF هو OR آحاد الحدود و- CNF هو AND تعابير . كل دالة بوليانية (f(x يمكن التعبير عنها بواسطة (DNF D(x او (CNF C(x :

ثنائي الدالة البوليانية[عدل]

لكل دالة بوليانية يمكن تعريف دالة بوليانية اخرى وتسمى هذه الدالة ثنائي f . وهي كالتالي :

لهذه الدالة عدة تطبيقات بشكل طبيعي منها في نظرية التصويت (voting theory) .

لهذه الدالة كثير من الخصال منها :

لنفرض أن f,g هما دالتين بوليانيتين حينها :

الدوال البوليانية على انها نظام مجموعات[عدل]

لكل مجموعة جزئية S من المجموعة نعرف دالة التشخيص (Characteristic function) والتي تحقق:

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

دوال بوليانية احادية التوجه[عدل]

لكل مُتجهين نكتب اذا . دالة بوليانية احادية التوجه اذا . لو نظرنا ل- f على انها علاقة اي حينها الدالة f احادية الاتجاه اذا وفقط اذا حينها لكل يتحقق .

امثلة لدوال احادية الاتجاه هي AND OR , دالة الحفة ,...

أنظر أيضا[عدل]

المراجع[عدل]

  • Stasys Jukna , "Boolean Function Complexity:Advances and Frontiers", Springer