تم النشر اليوم 2024/06/15 | دالة بول

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

يمكن ترجمة كل خاصية أو صفة إلى دالة بول ملائمة وهذه الصفة يمكن ان تحقق أو لا، مثال: الصفة «العدد أولي» ملائم للدالة PRIME بحيث: عدد اولي P
R
I
M
E
(
x
)
=
1 ⟺
∑ i
=
0
n x i
⋅ 2 i
{displaystyle PRIME(x)=1iff sum _{i=0}^{n}x_{i}cdot 2^{i}} .
ولنترجم خصائص المُخططات (graphs) على المجموعة [
n
]
=
{
1
,
⋯
,
n
}
{displaystyle [n]={1,cdots ,n}} نُعرف لكل ضلع متغير
x i
j
{displaystyle x_{ij}} وهذا المتغير 1 إذا (
i
,
j
)
∈
E
(
G
)
{displaystyle (i,j)in E(G)} و-0 خلاف هذا. لذا أي مُتجه قيمه 0-1 بطول
(
n
2
) {displaystyle {binom {n}{2}}} يعطينا مُخطط G . عندها خاصية يمكن ترجمتها بشكل مناسب، بشكل عام: خاصية مُخطط f
(
x
)
=
1 ⟺ {displaystyle f(x)=1iff }
مثال: دالة المخطط الكامل (the clique function) أو (Clique(n,k: وهذه الدالة تقبل متجه x إذا وفقط إذا Gx يحوي مخطط كامل مع k رؤوس.

عمليات بول

عمليات بول الأساسية هي: عملية النقض (negation) ويرمز لها ب- NOT: ¬
x
=
1
−
x
{displaystyle neg x=1-x} وفي بعض الاحيان:
x
¯ {displaystyle {bar {x}}}
عملية الضم (conjuction), ويرمز لها ب- AND: x
∧
y
=
x
⋅
y
{displaystyle xland y=xcdot y}
عملية الفصل (disjunction), ويرمز لها ب- OR: x
∨
y
=
1
−
(
1
−
y
)
⋅
(
1
−
x
)
{displaystyle xlor y=1-(1-y)cdot (1-x)}
عملية الزوجية (parity), ويرمز لها ب-XOR: x
⊕
y
=
x
(
1
−
y
)
+
y
(
1
−
x
)
=
(
x
+
y
)
(
mod 2
) {displaystyle xoplus y=x(1-y)+y(1-x)=(x+y){pmod {2}}}
عملية الاستلزام (implication) وهي x
→
y
=
¬
x
∨
y
{displaystyle xto y=neg xlor y}
من هذه العمليات يمكن تركيب دوال بول أكثر تعقيدا من دوال بسيطة. مثال: لنفرض أنَّ f
(
x
,
y
)
=
¬
x
+
(
x
∨
y
)
{displaystyle f(x,y)=neg x+(xlor y)} حينها يمكن أن نبني دالة جديدة:
f
′ (
x
,
y
,
z
)
=
¬
f
(
x
,
y
)
∧
z
{displaystyle f'(x,y,z)=neg f(x,y)land z}

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

لكل دالة بول يمكن تعريف دالة بول أخرى
f d
{displaystyle f^{d}} وتسمى هذه الدالة ثنائي f . وهي كالتالي:
f d
(
)
= f
(
¯
) ¯
{displaystyle f^{d}(X)={overline {f({overline {X}})}}}
لهذه الدالة عدة تطبيقات بشكل طبيعي منها في نظرية التصويت (voting theory). لهذه الدالة كثير من الخصال منها: لنفرض أن f,g هما دالتين بوليتين حينها: ( f d ) d
=
f
{displaystyle (f^{d})^{d}=f}
(
f
¯ ) d
= f d
¯
{displaystyle ({overline {f}})^{d}={overline {f^{d}}}}
(
f
∨
g ) d
= f d
∧ g d
{displaystyle (flor g)^{d}=f^{d}land g^{d}}
(
f
∧
g ) d
= f d
∨ g d
{displaystyle (fland g)^{d}=f^{d}lor g^{d}}
f
≤
g ⟺
g d
≤ f d
{displaystyle fleq giff g^{d}leq f^{d}}

مصفوفة بول

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

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

دالة بول نقول عنها متناظرة إذا اعتمدت فقط على عدد ال-1 في المُدخل وليس على مكانها أي على توزيعها على المتغيرات، لذا فانه يوجد
2 n
+
1
{displaystyle 2^{n+1}} دوال كهذه، امثلة لدوال كهذه: دالة الحفة (threshold function) T h k
n
(
x
)
=
1 ⟺
x 1
+ x 2
+
⋯
+ x n
≥
k
{displaystyle Th_{k}^{n}(x)=1iff x_{1}+x_{2}+cdots +x_{n}geq k}
دالة الأكثرية (majority function) M
a j n
(
x
)
=
1 ⟺
x 1
+ x 2
+
⋯
+ x n
≥ ⌈
n
2
⌉ {displaystyle Maj_{n}(x)=1iff x_{1}+x_{2}+cdots +x_{n}geq leftlceil {frac {n}{2}}rightrceil }
دالة الزوجية (parity function)
⊕ n
(
x
)
=
1 ⟺
x 1
+ x 2
+
⋯
+ x n
=
1
(
mod 2
) {displaystyle oplus _{n}(x)=1iff x_{1}+x_{2}+cdots +x_{n}=1{pmod {2}}}
دالة العد (modular function) M
o d k
(
x
)
=
1 ⟺
x 1
+ x 2
+
⋯
+ x n
=
0
(
mod k
) {displaystyle Mod_{k}(x)=1iff x_{1}+x_{2}+cdots +x_{n}=0{pmod {k}}}

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

لكل مُتجهين x
,
y
∈
{
0
,
1 } n
{displaystyle x,yin {0,1}^{n}} نكتب x
≤
y
{displaystyle xleq y} إذا ∀
i x i
≤ y i
{displaystyle forall ix_{i}leq y_{i}} . دالة بول احادية التوجه إذا x
≤
y
⇒
f
(
x
)
≤
f
(
y
)
{displaystyle xleq yRightarrow f(x)leq f(y)} . لو نظرنا ل- f على انها علاقة أي f
: 2 [
n
]
→
{
0
,
1
}
{displaystyle f:2^{[n]}to {0,1}} حينها الدالة f احادية الاتجاه إذا وفقط إذا f
(
S
)
=
1
{displaystyle f(S)=1} حينها لكل S
⊆
T
{displaystyle Ssubseteq T} يتحقق f
(
T
)
=
1
{displaystyle f(T)=1} . امثلة لدوال احادية الاتجاه هي AND OR , دالة الحفة T H k
n
(
x
)
{displaystyle TH_{k}^{n}(x)} ,…

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

المعكب الثنائي هو مجموعة كل المتجهات (أي {
0
,
1 } n
{displaystyle {0,1}^{n}} ) ويمكن التعبير عنه بواسطة مُخطط (GRAPH) بحيث أنه يوجد لهذا المكعب
2 n
{displaystyle 2^{n}} رؤوس وكل رأس موسوم بواسطة مُتجه (vector) من المجموعة {
0
,
1 } n
{displaystyle {0,1}^{n}} ويوجد ضلع بين رأسين إذا اختلف المتجهين اللذان هما وسما الرأسين في مكان واحد. لذا فانه يوجد n
2 n
{displaystyle n 2^{n}} اضلاع في هذا المخطط، كما انَّه مخطط ثنائي. نرمز لمكعب مع
2 n
{displaystyle 2^{n}} رؤوس ب-
Q n
{displaystyle Q_{n}} .
A هو مُكعب جزئي بُعده d هو مجموعة شكلها كالتالي: A
= A 1
× A 2
×
⋯
× A n
{displaystyle A=A_{1}times A_{2}times cdots times A_{n}} بحيث أنَّ كل Ai هو أحد المجموعات: {
0
}
,
{
1
}
,
{
0
,
1
}
{displaystyle {0},{1},{0,1}} بالإضافة إلى أنه فقط ل- d من المجموعات يتحقق التالي:
A i
=
{
0
,
1
}
{displaystyle A_{i}={0,1}} . كل دالة بول f
:
{
0
,
1 } n
→
{
0
,
1
}
{displaystyle f:{0,1}^{n}to {0,1}} يمكن النظر اليها على انها تلوين (coloring)
Q n
{displaystyle Q_{n}} بلونين. المخطط الثنائي الجزئي
G f
{displaystyle G_{f}} نحصل عليه بازالة كل الاضلاع التي رؤوسها تشترك بنفس اللون. الكثافة في المخطط
G f
{displaystyle G_{f}} له فائدة في تعقيد دوائر بول للدالة f .

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

لكل مجموعة جزئية S من المجموعة {
1
,
2
,
⋯
,
n
}
{displaystyle {1,2,cdots ,n}} نعرف دالة التشخيص (Characteristic function)
v S
{displaystyle v_{S}} والتي تحقق:
v S
(
i
)
=
1 ⟺ i
∈
S
{displaystyle v_{S}(i)=1iff iin S}
حينها يمكن تعريف دالة البول على انها علاقة (predicate) f
: 2 [
n
]
→
{
0
,
1
}
{displaystyle f:2^{[n]}to {0,1}} . ويستطيع المرئ ان ينظر إلى دالة بول f
: 2 [
n
]
→
{
0
,
1
}
{displaystyle f:2^{[}n]to {0,1}} على انها عائلة المجموعات الجزئية التالية:
F f
=
{
S | f
(
S
)
=
1
}
{displaystyle {mathcal {F}}_{f}={S|f(S)=1}} .

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

هنالك شكلان طبيعيان لدوال بول: CNF , DNF . لعل أكثر الوسائل بديهية لتمثيل دالة بول هو جدول الحقيقة الخاص بالدالة أي قائمة بكل
2 n
{displaystyle 2^{n}} الازواج (
a
,
f
(
a
)
)
{displaystyle (a,f(a))} لكل a
∈
{
0
,
1 } n
{displaystyle ain {0,1}^{n}} . هذه الطريقة اغلب الاحيان غير ملائمة، وسيلة أكثر ملائمة هي DNF و-CNF . متغير بسيط (literal) هو متغير بول أو ضده أي اما ان يكون
x i
{displaystyle x_{i}} أو ¬ x i
{displaystyle neg x_{i}} . بشكل عام الترميز التالي شائع الاستخدام:
x i
1
= x i
{displaystyle x_{i}^{1}=x_{i}} و-
x i
0
=
¬ x i
{displaystyle x_{i}^{0}=neg x_{i}} لذا فانه لكل سلسلة a
=
( a 1
,
⋯
, a n
)
{displaystyle a=(a_{1},cdots ,a_{n})} يتحقق التالي: x i
1
(
a
)
=
{ 1
,
if a i
=
1
0
,
if a i
=
0

, x i
0
(
a
)
=
{ 0
,
if a i
=
1
1
,
if a i
=
0
{displaystyle x_{i}^{1}(a)={begin{cases}1,&{mbox{if }}a_{i}=1\0,&{mbox{if }}a_{i}=0end{cases}} ,x_{i}^{0}(a)={begin{cases}0,&{mbox{if }}a_{i}=1\1,&{mbox{if }}a_{i}=0end{cases}}}
احادي الحدود (monomial) هو AND متغيرات بسيطة، والتعبير (clause) هو or متغيرات بسيطة. مثال: x
∧
y
∧
¬
z
{displaystyle xland yland neg z} هو احادي الحدود.
x
∨
y
∨
¬
x
∨
z
{displaystyle xlor ylor neg xlor z} هو تعبير.
DNF هو OR آحاد الحدود و- CNF هو AND تعابير. كل دالة بول (f(x يمكن التعبير عنها بواسطة (DNF D(x أو (CNF C(x: C
(
x
)
= ⋁ a
:
f
(
a
)
=
1 ⋀ i
=
1
n x i a i D
(
x
)
= ⋀ b
:
f
(
b
)
=
0 ⋁ i
=
0
n x i
1
− b i
.
{displaystyle 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}}.}

شرح مبسط

في الرياضيات، دالة بُول[1] هي دالة

f
(
x
)
=
f
(

x

1

,
⋯
,

x

n

)

{displaystyle f(x)=f(x_{1},cdots ,x_{n})}

مع n متغيرات

f
:
{
0
,
1

}

n

→
{
0
,
1
}

{displaystyle f:{0,1}^{n}to {0,1}}

نقول أنَّ f تقبل متجه

a
∈
{
0
,
1

}

n

{displaystyle ain {0,1}^{n}}

إذا 1 =(f(a ونقول انها ترفضه إذا 0 =(f(a .[2][3][4] دالة بول ليست بالضرورة متعلقة بكل متغيراتها ونقول أنَّ الدالة f متعلقة بالمتغير xi إذا يوجد اعداد ثابتة

a

1

,
⋯
,

a

i
−
1

,

a

i
+
1

,
⋯
,

a

n

∈
{
0
,
1
}

{displaystyle a_{1},cdots ,a_{i-1},a_{i+1},cdots ,a_{n}in {0,1}}

بحيث أنَّ: