عبد العزيز: نقل عبد الجليل 09 صفحة دالة بوليانية إلى دالة بول: نسبة إلى العالم بول

2023-07-17T13:47:42Z

نقل عبد الجليل 09 صفحة دالة بوليانية إلى دالة بول: نسبة إلى العالم بول

صفحة جديدة

في [[رياضيات|الرياضيات]]، '''دالة بُول<ref>{{استشهاد بويكي بيانات|Q108593221|صفحة=65}}</ref> '''هي دالة <math>f(x)=f(x_1,\cdots,x_n)</math> مع n متغيرات <math>f:\{0,1\}^n \to \{0,1\} </math> نقول أنَّ f تقبل متجه <math> a \in \{0,1\}^n</math> إذا 1 =(f(a ونقول انها ترفضه إذا 0 =(f(a .<ref>{{استشهاد ويب|مسار=https://www.jstor.org/topic/boolean-functions|عنوان=معلومات عن دالة بول على موقع jstor.org|ناشر=jstor.org|مسار أرشيف=https://web.archive.org/web/20200109204018/https://www.jstor.org/topic/boolean-functions/|تاريخ أرشيف=9 يناير 2020}}</ref><ref>{{استشهاد ويب|مسار=https://babelnet.org/synset?word=bn:03625290n|عنوان=معلومات عن دالة بول على موقع babelnet.org|ناشر=babelnet.org|مسار أرشيف=https://web.archive.org/web/20191219012821/https://babelnet.org/synset?word=bn:03625290n|تاريخ أرشيف=2019-12-19}}</ref><ref>{{استشهاد ويب|مسار=https://bigenc.ru/mathematics/text/1888052|عنوان=معلومات عن دالة بول على موقع bigenc.ru|ناشر=bigenc.ru|مسار أرشيف=https://web.archive.org/web/20191219012827/https://bigenc.ru/text/1888052|تاريخ أرشيف=2019-12-19}}</ref> دالة بول ليست بالضرورة متعلقة بكل متغيراتها ونقول أنَّ الدالة f متعلقة بالمتغير x<sub>i</sub>  إذا يوجد اعداد ثابتة <math>a_1,\cdots,a_{i-1},a_{i+1},\cdots,a_n \in \{0,1\}</math> بحيث أنَّ:

: <math>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)</math>

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

== دوال بول المتناظرة ==
دالة بول نقول عنها [[تناظر|متناظرة]] إذا اعتمدت فقط على عدد ال-1 في المُدخل وليس على مكانها أي على توزيعها على المتغيرات، لذا فانه يوجد <math>2^{n+1} </math> دوال كهذه، امثلة لدوال كهذه:
* دالة الحفة (threshold function) <math> Th_k^n(x)=1 \iff x_1+x_2+\cdots+x_n \ge k </math>
* دالة الأكثرية (majority function) <math> Maj_n(x)=1 \iff x_1+x_2+\cdots+x_n \ge \left \lceil \frac{n}{2} \right \rceil </math>
* دالة الزوجية (parity function) <math> \oplus_n(x)=1 \iff x_1+x_2+\cdots+x_n=1 \pmod 2</math>
* دالة العد (modular function) <math> Mod_k(x)=1 \iff x_1+x_2+\cdots+x_n=0 \pmod k </math>

== ترجمة الخصائص ==
يمكن ترجمة كل خاصية أو صفة إلى دالة بول ملائمة وهذه الصفة يمكن ان تحقق أو لا، مثال: الصفة «العدد أولي» ملائم للدالة PRIME بحيث:
: عدد اولي <math>PRIME(x)=1 \iff \sum_{i=0}^n x_i\cdot 2^i </math> .

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

مثال:

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

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

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

== عمليات بول ==
عمليات بول الأساسية هي:
* عملية النقض (negation) ويرمز لها ب- NOT : <math> \neg x =1-x </math> وفي بعض الاحيان: <math> \bar{x}</math>
* عملية الضم (conjuction), ويرمز لها ب- AND : <math>x \land y=x\cdot y </math>
* عملية الفصل (disjunction), ويرمز لها ب- OR : <math> x \lor y =1-(1-y)\cdot (1-x)</math>
* عملية الزوجية (parity), ويرمز لها ب-XOR : <math> x\oplus y = x(1-y)+y(1-x)=(x+y) \pmod 2</math>
* عملية الاستلزام (implication) وهي <math> x \to y = \neg x \lor y </math>
من هذه العمليات يمكن تركيب دوال بول أكثر تعقيدا من دوال بسيطة.

مثال:

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

== المكعب الثنائي ==
المعكب الثنائي هو مجموعة كل المتجهات (أي <math> \{0,1\}^n </math>) ويمكن التعبير عنه بواسطة مُخطط (GRAPH) بحيث أنه يوجد لهذا المكعب <math>2^n </math> رؤوس وكل رأس موسوم بواسطة مُتجه (vector) من المجموعة <math>\{0,1\}^n </math> ويوجد ضلع بين رأسين إذا اختلف المتجهين اللذان هما وسما الرأسين في مكان واحد. لذا فانه يوجد <math> n \ 2^n </math> اضلاع في هذا المخطط، كما انَّه [[مخطط ثنائي]]. نرمز لمكعب مع <math>2^n</math> رؤوس ب- <math>Q_n</math> .
[[ملف:HypercubeCycles.png|تصغير]]

A هو مُكعب جزئي بُعده d هو مجموعة شكلها كالتالي: <math> A= A_1\times A_2 \times \cdots \times A_n </math> بحيث أنَّ كل A<sub>i</sub> هو أحد المجموعات: <math> \{0\},\{1\},\{0,1\}</math> بالإضافة إلى أنه فقط ل- d من المجموعات يتحقق التالي: <math> A_i =\{0,1\}</math> .

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

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

متغير بسيط (literal) هو متغير بول أو ضده أي اما ان يكون <math> x_i</math> أو <math> \neg x_i </math>. بشكل عام الترميز التالي شائع الاستخدام: <math>x_i^1=x_i</math> و- <math>x_i^0=\neg x_i </math> لذا فانه لكل سلسلة <math>a=(a_1,\cdots,a_n)</math> يتحقق التالي:
<div style="text-align: center;">
<math> 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}
</math></div>

احادي الحدود (monomial) هو AND متغيرات بسيطة، والتعبير (clause) هو or متغيرات بسيطة. مثال:
* <math> x \land y \land \neg z </math> هو احادي الحدود.
* <math> x \lor y \lor \neg x \lor z </math> هو تعبير.

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

<div style="text-align: center;"> <math> 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} .</math> </div>
== ثنائي دالة البول ==
لكل دالة بول يمكن تعريف دالة بول أخرى <math>f^d</math> وتسمى هذه الدالة ثنائي f . وهي كالتالي:
<div style="text-align: center;"> <math> f^d(X)=\overline{f(\overline{X})}</math></div>

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

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

لنفرض أن f,g هما دالتين بوليتين حينها:
# <math>(f^d)^d=f</math>
# <math>(\overline f)^d=\overline{f^d}</math>
# <math> (f \lor g)^d=f^d\land g^d </math>
# <math> (f \land g)^d=f^d \lor g^d </math>
# <math> f \le g \iff g^d \le f^d </math>

== دوال بول على انها نظام مجموعات ==
لكل مجموعة جزئية S من المجموعة <math>\{1,2,\cdots,n\}</math> نعرف دالة التشخيص (Characteristic function) <math>v_S</math> والتي تحقق:

: <math> v_S(i)=1 \iff i\in S </math>

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

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

امثلة لدوال احادية الاتجاه هي AND OR , دالة الحفة <math>TH_k^n(x)</math> ,...

== انظر أيضا ==

{{div col}}
* [[جبر بول]]
* [[رابطة منطقية]]
* [[جدول الحقيقة]]
{{div col end}}

== المراجع ==
{{مراجع}}

* Stasys Jukna , "Boolean Function Complexity:Advances and Frontiers", Springer
{{منطق رياضي}}

{{منطق}}
{{ضبط استنادي}}
{{شريط بوابات|فلسفة|تعمية|رياضيات|علم الحاسوب|منطق}}

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

دالة بول - تاريخ المراجعة

عبد العزيز: نقل عبد الجليل 09 صفحة دالة بوليانية إلى دالة بول: نسبة إلى العالم بول