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

في الرياضيات، الدالة البُولية هي دالة مع n متغيرات نقول أنَّ f تقبل متجه إذا 1 =(f(a ونقول انها ترفضه إذا 0 =(f(a .[1][2][3] دالة بوليانية ليست بالضرورة متعلقة بكل متغيراتها ونقول أنَّ الدالة 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) من المجموعة ويوجد ضلع بين رأسين إذا اختلف المتجهين اللذان هما وسما الرأسين في مكان واحد. لذا فانه يوجد اضلاع في هذا المخطط، كما انَّه مخطط ثنائي. نرمز لمكعب مع رؤوس ب- .

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 , دالة الحفة ,...

انظر أيضا

المراجع

  1. "معلومات عن دالة بوليانية على موقع jstor.org"، jstor.org، مؤرشف من الأصل في 9 يناير 2020.
  2. "معلومات عن دالة بوليانية على موقع babelnet.org"، babelnet.org، مؤرشف من الأصل في 19 ديسمبر 2019.
  3. "معلومات عن دالة بوليانية على موقع bigenc.ru"، bigenc.ru، مؤرشف من الأصل في 19 ديسمبر 2019.
  • Stasys Jukna , "Boolean Function Complexity:Advances and Frontiers", Springer
  • بوابة فلسفة
  • بوابة تعمية
  • بوابة رياضيات
  • بوابة علم الحاسوب
  • بوابة منطق
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.