دالة بول

دالة بول
في الرياضيات، دالة بُول هي دالة مع n متغيرات نقول أنَّ f تقبل متجه إذا 1 =(f(a ونقول انها ترفضه إذا 0 =(f(a . دالة بول ليست بالضرورة متعلقة بكل متغيراتها ونقول أنَّ الدالة f متعلقة بالمتغير xi إذا يوجد اعداد ثابتة بحيث أنَّ:
بما أنَّه يوجد متجهات في فإن عدد دوال بول هو .
دوال بول المتناظرة
دالة بول نقول عنها متناظرة إذا اعتمدت فقط على عدد ال-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 , دالة الحفة ,...
انظر أيضا
جبر بول
رابطة منطقية
جدول الحقيقة
المراجع
Stasys Jukna , "Boolean Function Complexity:Advances and Frontiers", Springer
بنى البرمجة
بوابات منطقية
تعمية
جبر منطقي
حسابيات ثنائية
رياضيات