دالة بول

في الرياضيات، **دالة بُول **هي دالة 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 متعلقة بالمتغير xi&nbsp; إذا يوجد اعداد ثابتة 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)\ne 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 \ge k 
* دالة الأكثرية (majority function)  Maj_n(x)=1 \iff x_1+x_2+\cdots+x_n \ge \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 إذا وفقط إذا Gx يحوي مخطط كامل مع 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  بحيث أنَّ كل Ai هو أحد المجموعات:  \{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 هما دالتين بوليتين حينها:
# (f^d)^d=f
# (\overline f)^d=\overline{f^d}
#  (f \lor g)^d=f^d\land g^d 
#  (f \land g)^d=f^d \lor g^d 
#  f \le g \iff g^d \le 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 \le y  إذا  \forall i x_i\le y_i  . دالة بول احادية التوجه إذا  x\le y \Rightarrow f(x)\le 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

تصنيف:بنى البرمجة
تصنيف:بوابات منطقية
تصنيف:تعمية
تصنيف:جبر منطقي
تصنيف:حسابيات ثنائية
تصنيف:رياضيات