دالة بول

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

معلومات عامة

صنف فرعي من	Boolean-valued function (en)
سُمِّي باسم	جورج بول
يدرسه	جبر بول
المجال المقابل	مجال منطقي
ممثلة بـ	الأشكال العادية للجبر المنطقي

في الرياضيات، دالة بُول هي دالة $f(x)=f(x_{1},\cdots ,x_{n})$ مع n متغيرات $f:\{0,1\}^{n}\to \{0,1\}$ نقول أنَّ f تقبل متجه $a\in \{0,1\}^{n}$ إذا 1 =(f(a ونقول انها ترفضه إذا 0 =(f(a . دالة بول ليست بالضرورة متعلقة بكل متغيراتها ونقول أنَّ الدالة f متعلقة بالمتغير x_i  إذا يوجد اعداد ثابتة $a_{1},\cdots ,a_{i-1},a_{i+1},\cdots ,a_{n}\in \{0,1\}$ بحيث أنَّ:

$f(a_{1},\cdots ,a_{i-1},0,a_{i+1},\cdots ,a_{n})\neq f(a_{1},\cdots ,a_{i-1},1,a_{i+1},\cdots ,a_{n})$

بما أنَّه يوجد $2^{n}$ متجهات في $\{0,1\}^{n}$ فإن عدد دوال بول $f:\{0,1\}^{n}\to \{0,1\}$ هو $2^{2^{n}}$.

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

دالة بول نقول عنها متناظرة إذا اعتمدت فقط على عدد ال-1 في المُدخل وليس على مكانها أي على توزيعها على المتغيرات، لذا فانه يوجد $2^{n+1}$ دوال كهذه، امثلة لدوال كهذه:

• دالة الحفة (threshold function) $Th_{k}^{n}(x)=1\iff x_{1}+x_{2}+\cdots +x_{n}\geq k$
• دالة الأكثرية (majority function) $Maj_{n}(x)=1\iff x_{1}+x_{2}+\cdots +x_{n}\geq \left\lceil {\frac {n}{2}}\right\rceil$
• دالة الزوجية (parity function) $\oplus _{n}(x)=1\iff x_{1}+x_{2}+\cdots +x_{n}=1{\pmod {2}}$
• دالة العد (modular function) $Mod_{k}(x)=1\iff x_{1}+x_{2}+\cdots +x_{n}=0{\pmod {k}}$

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

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

عدد اولي $PRIME(x)=1\iff \sum _{i=0}^{n}x_{i}\cdot 2^{i}$ .

ولنترجم خصائص المُخططات (graphs) على المجموعة $[n]=\{1,\cdots ,n\}$ نُعرف لكل ضلع متغير $x_{ij}$ وهذا المتغير 1 إذا $(i,j)\in E(G)$ و-0 خلاف هذا. لذا أي مُتجه قيمه 0-1 بطول ${\binom {n}{2}}$ يعطينا مُخطط G . عندها خاصية يمكن ترجمتها بشكل مناسب، بشكل عام:

خاصية مُخطط $f(x)=1\iff$

مثال:

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

مصفوفة بول

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

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

عمليات بول

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

• عملية النقض (negation) ويرمز لها ب- NOT : $\neg x=1-x$ وفي بعض الاحيان: ${\bar {x}}$
• عملية الضم (conjuction), ويرمز لها ب- AND : $x\land y=x\cdot y$
• عملية الفصل (disjunction), ويرمز لها ب- OR : $x\lor y=1-(1-y)\cdot (1-x)$
• عملية الزوجية (parity), ويرمز لها ب-XOR : $x\oplus y=x(1-y)+y(1-x)=(x+y){\pmod {2}}$
• عملية الاستلزام (implication) وهي $x\to y=\neg x\lor y$

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

مثال:

لنفرض أنَّ $f(x,y)=\neg x+(x\lor y)$ حينها يمكن أن نبني دالة جديدة: $f'(x,y,z)=\neg f(x,y)\land z$

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

المعكب الثنائي هو مجموعة كل المتجهات (أي $\{0,1\}^{n}$) ويمكن التعبير عنه بواسطة مُخطط (GRAPH) بحيث أنه يوجد لهذا المكعب $2^{n}$ رؤوس وكل رأس موسوم بواسطة مُتجه (vector) من المجموعة $\{0,1\}^{n}$ ويوجد ضلع بين رأسين إذا اختلف المتجهين اللذان هما وسما الرأسين في مكان واحد. لذا فانه يوجد $n\ 2^{n}$ اضلاع في هذا المخطط، كما انَّه مخطط ثنائي. نرمز لمكعب مع $2^{n}$ رؤوس ب- $Q_{n}$ .

A هو مُكعب جزئي بُعده d هو مجموعة شكلها كالتالي: $A=A_{1}\times A_{2}\times \cdots \times A_{n}$ بحيث أنَّ كل A_i هو أحد المجموعات: $\{0\},\{1\},\{0,1\}$ بالإضافة إلى أنه فقط ل- d من المجموعات يتحقق التالي: $A_{i}=\{0,1\}$ .

كل دالة بول $f:\{0,1\}^{n}\to \{0,1\}$ يمكن النظر اليها على انها تلوين (coloring) $Q_{n}$ بلونين. المخطط الثنائي الجزئي $G_{f}$ نحصل عليه بازالة كل الاضلاع التي رؤوسها تشترك بنفس اللون. الكثافة في المخطط $G_{f}$ له فائدة في تعقيد دوائر بول للدالة f .

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

هنالك شكلان طبيعيان لدوال بول: CNF , DNF . لعل أكثر الوسائل بديهية لتمثيل دالة بول هو جدول الحقيقة الخاص بالدالة أي قائمة بكل $2^{n}$ الازواج $(a,f(a))$ لكل $a\in \{0,1\}^{n}$ . هذه الطريقة اغلب الاحيان غير ملائمة، وسيلة أكثر ملائمة هي DNF و-CNF .

متغير بسيط (literal) هو متغير بول أو ضده أي اما ان يكون $x_{i}$ أو $\neg x_{i}$. بشكل عام الترميز التالي شائع الاستخدام: $x_{i}^{1}=x_{i}$ و- $x_{i}^{0}=\neg x_{i}$ لذا فانه لكل سلسلة $a=(a_{1},\cdots ,a_{n})$ يتحقق التالي:

$x_{i}^{1}(a)={\begin{cases}1,&{\mbox{if }}a_{i}=1\\0,&{\mbox{if }}a_{i}=0\end{cases}}\ ,x_{i}^{0}(a)={\begin{cases}0,&{\mbox{if }}a_{i}=1\\1,&{\mbox{if }}a_{i}=0\end{cases}}$

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

• $x\land y\land \neg z$ هو احادي الحدود.
• $x\lor y\lor \neg x\lor z$ هو تعبير.

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

$C(x)=\bigvee _{a:f(a)=1}\bigwedge _{i=1}^{n}x_{i}^{a_{i}}\quad D(x)=\bigwedge _{b:f(b)=0}\bigvee _{i=0}^{n}x_{i}^{1-b_{i}}.$

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

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

$f^{d}(X)={\overline {f({\overline {X}})}}$

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

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

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

1. $(f^{d})^{d}=f$
2. $({\overline {f}})^{d}={\overline {f^{d}}}$
3. $(f\lor g)^{d}=f^{d}\land g^{d}$
4. $(f\land g)^{d}=f^{d}\lor g^{d}$
5. $f\leq g\iff g^{d}\leq f^{d}$

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

لكل مجموعة جزئية S من المجموعة $\{1,2,\cdots ,n\}$ نعرف دالة التشخيص (Characteristic function) $v_{S}$ والتي تحقق:

$v_{S}(i)=1\iff i\in S$

حينها يمكن تعريف دالة البول على انها علاقة (predicate) $f:2^{[n]}\to \{0,1\}$ . ويستطيع المرئ ان ينظر إلى دالة بول $f:2^{[}n]\to \{0,1\}$ على انها عائلة المجموعات الجزئية التالية: ${\mathcal {F}}_{f}=\{S|f(S)=1\}$ .

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

لكل مُتجهين $x,y\in \{0,1\}^{n}$ نكتب $x\leq y$ إذا $\forall ix_{i}\leq y_{i}$ . دالة بول احادية التوجه إذا $x\leq y\Rightarrow f(x)\leq f(y)$ . لو نظرنا ل- f على انها علاقة أي $f:2^{[n]}\to \{0,1\}$ حينها الدالة f احادية الاتجاه إذا وفقط إذا $f(S)=1$ حينها لكل $S\subseteq T$ يتحقق $f(T)=1$ .

امثلة لدوال احادية الاتجاه هي AND OR , دالة الحفة $TH_{k}^{n}(x)$ ,...

انظر أيضا

• جبر بول
• رابطة منطقية
• جدول الحقيقة

المراجع

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