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

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من الوظيفة البوليانية)
اذهب إلى: تصفح، ‏ ابحث

في الرياضيات، الدالة البوليانية هي دالة 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  اذا يوجد اعداد ثابتة 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}.

دوال بوليانية متناظرة[عدل]

دالة بوليانية نقول عنها متناظرة (symmetric) اذا اعتمدت فقط على عدد ال-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 \and y=x\cdot y
  • عملية الفصل (disjunction) , ويرمز لها ب- OR :  x \or 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 \or y

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

مثال :

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

المكعب الثنائي[عدل]

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

HypercubeCycles.png

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 \and y \and \neg z هو احادي الحدود .
  •  x \or y \or \neg x \or 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 \or g)^d=f^d\and g^d
  4.  (f \and g)^d=f^d \or g^d
  5.  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