دالة بول

مصفوفة بول

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

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

عمليات بول

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

خاصية مُخطط

مثال:

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

المكعب الثنائي

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

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

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

عملية الاستلزام (implication) وهي

• من هذه العمليات يمكن تركيب دوال بول أكثر تعقيدا من دوال بسيطة.
• مثال:
• لنفرض أنَّ حينها يمكن أن نبني دالة جديدة:

دوال بول المتناظرة

إضافةً إلى ذلك، دالة بول نقول عنها متناظرة إذا اعتمدت فقط على عدد ال-1 في المُدخل وليس على مكانها أي على توزيعها على المتغيرات، لذا فانه يوجد دوال كهذه، امثلة لدوال كهذه:

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

دوال بول أحادية التوجه

• امثلة لدوال احادية الاتجاه هي AND OR , دالة الحفة ,...
• انظر كذلك
• جبر بول
• رابطة منطقية
• جدول الحقيقة

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

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

• لكل دالة بول يمكن تعريف دالة بول أخرى وتسمى هذه الدالة ثنائي f . وهي كالتالي:
• لهذه الدالة عدة تطبيقات بشكل طبيعي منها في نظرية التصويت (voting theory).
• لهذه الدالة كثير من الخصال منها:
• لنفرض أن f,g هما دالتين بوليتين حينها:

دوال بول على انها نظام مجموعات

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

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

ترجمة الخصائص

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

عدد اولي .

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

الاشكال الطبيعية

هو احادي الحدود.

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

هو تعبير.

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

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

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