المبحث الاول:الأسس الرياضية للجبر البولياني

1-1-المقدمة

الجبر البولياني Boolean Algebra

لاحظ الإنسان منذ القدم أن الكثير من المسائل الفكرية و المنطقية لا تجد الحل إلا في جواب واحد من اثنين (خطأ أم صواب). قادت الصفة الثنائية في التفكير "أرسطو طاليس" للبحث عن الحقيقة وسط مجموعة من الافتراضات. وقد اقترب ديموركان Demorgan من اكتشاف الصلة بين المنطق و الرياضيات’ إلا أن بول Boole حقق عام 1854 العلاقة بينهما ووضع جبرا جديدا سمي بعد ذلك باسمه (الجبر البولي) أو الجبر البولياني Boolean Algebra وفي عام 1938 نشر شانون Shannon بحثاً عن استخدام قوانين الجبر البولياني في العمليات المنطقية للأجهزة المستخدمة لتمثيل الحالات الثنائية واًصبحت وسيلة فعالة لتحليل وتصميم الدوائر الرقمية,[4,6]

إن العمليات الأساسية في الجبر البولياني هي علاقة "النفي "(NOT) وعلاقة "أو" (OR) وعلاقة "مع" (AND) وعلاقة" أو" المقصورة (XOR).

إذا كان X وY متغيرين فأن (X) NOT تكتب بـ وX OR Y تكتب X+Y و

X AND Y تكتب X.Y و X xor Y تكتب X ÅY ويمكن تمثيل هذه العمليات بجدول الحقائق رقم (1- 1):-

جدول (1-1) يوضح العمليات الأساسية في الجبر البولياني

x	y		x+y	x.y	X Åy
0	0	1	0	0	0
0	1	1	1	0	1
1	0	0	1	0	1
1	1	0	1	1	0

1-2- قوانين الجبر البولياني

يمكن تمثيل أهم القوانين الرياضية للجبر البولياني بالعلاقات الآتية: [ 5 ]

X + 0 = X X.0 = 0

X + = 1 X. = 0

X + X = X X.X = X

X + 1 = 1 X.1 = X

= X

X+Y=Y+X X.Y=Y.X

X+(Y+Z)=(X+Y)+Z X.(Y.Z)=(X.Y).Z

X.(Y+Z)=X.Y+X.Z x+y.z=(x+y)(x+z)

X+XY=X X.(X+Y)=X

=

ولذلك فان الجبر البولياني كأي نظام رياضي، يعرف على مجموعة من العناصر ومجموعة من العمليات. هناك عدة بديهيات وفرضيات لتعريف الجبر البولياني على المجموعة {0,1} B= وتحوي عمليتين ثنائيتين هما OR, AND.

وبما أن الجبر البولياني نظام رياضي لذلك تطبق عليه جميع الخواص لأي نظام، ومنها خاصية الانغلاق (closure) وخاصية التجميع (associatitive) وخاصية الإبدال (commutative) وخاصية العنصر المحايد (identity element) وخاصية النظير (inverse) وقانون التوزيع

(distribution).

 

-3-1 فرضيات هونتكتون Huntington

قدم. V. Huntington E. [ 13 ] فرضيات لتعريف الجبر البولياني بصورة مفصلة، معرفة على المجموعة {0,1} =B مع عمليتين ثنائيتين هما OR, AND ومن الفرضيات الآتية:ـ

-1-3-1 خاصية الانغلاق CLOSURE))

ليكن X,Y Є B فيكون X+Y Є B و X.Y Є B صائبة لجميع عناصر B.

-2-3-1خاصية العنصر المحايد (IDENTITY ELEMENT)

ليكن X, Y Є B فيكون X+0=X و X.1=X صائبة

أي أن 0 هو العنصر المحايد لعمليةOR

وان 1 هو العنصر المحايد لعملية AND

-3-3-1 خاصية الإبدال (COMMUTATIVE)

ليكن X, Y Є B فتكون X+Y=Y+X و X.Y=Y.X صائبة.

-4-3-1 خاصية التوزيع (DISTRIBUTIVE)

ليكن x,y,z Є B

أ-خاصية توزيع AND على OR أي أن:-

x.(y+z)=x.y+x.z

ويمكن ملاحظة ذلك من خلال الجدول رقم (1-2):-

جدول رقم (1 - 2) يوضح خاصية توزيع AND على OR

X y z	Y+z	x.(y+z)	x.y	x.z	x.y+x.z
0 0 0	0	0	0	0	0
0 0 1	1	0	0	0	0
0 1 0	1	0	0	0	0
0 1 1	1	0	0	0	0
1 0 0	0	0	0	0	0
1 0 1	1	1	0	1	1
1 1 0	1	1	1	0	1
1 1 1	1	1	1	1	1

X+(y.z)=(x+y).(x+z)

ب ـ خاصية توزيع OR على AND أي أن

ويمكن ملاحظة ذلك من خلال الجدول (1-3):ـ

جدول رقم (1-3) يوضح خاصية توزيع OR على AND

X y z	y.z	X+(y.z)	X+y	X+z	(x+y).(x+z)
0 0 0	0	0	0	0	0
0 0 1	0	0	0	1	0
0 1 0	0	0	1	0	0
0 1 1	1	1	1	1	1
1 0 0	0	1	1	1	1
1 0 1	0	1	1	1	1
1 1 0	0	1	1	1	1
1 1 1	1	1	1	1	1

-5-3-1 لكل عنصر X Є B يوجد عنصر متممه هو Є B

أي أن:ـ

أ - عملية OR

X+ = 1

ويمكن ملاحظة الأتي:

0+= 0+1 = 1

1+= 1+0 = 1

ب - عملية AND

X. = 0

ويمكن ملاحظة الآتي:-

0. = 0.1 = 0

1. = 1.0 = 0

1-4- أوجه الاختلاف بين الجبرين البولياني والاعتيادي

يمكن ملاحظة بعض الفرو قات بين الجبر البولياني والجبـر الاعتيـادي (Algebra Ordinary) والتي تشمل النقاط الآتية:ـ [5]

1- قانون توزيع عملية OR على AND X+(y.z)=(x+y).(x+z) يكون مقبولا في الجبر البولياني لكنه مرفوض في الجبر الاعتيادي.

2 – لا يمتلك الجبر البولياني نظيراً جمعياً ونظيراً ضربياً, لذلك لا توجد عمليتا الطرح والقسمة في الجبر البولياني عكس مما موجود في الجبر الاعتيادي.

3 - توجد الخاصيتان =1+ X, =0X. في الجبر البولياني فقط ولا توجد هاتان الخاصيتان في الجبر الاعتيادي.

4 – يعرف الجبر البولياني على مجموعة منتهية عناصرها {1,0} بينما يعرف الجبر الاعتيادي على مجموعة غير منتهية.

5-1 هدف البحث

يهدف البحث إلى إيجاد طرائق لحل المعادلات البوليانية الخطية واللاخطية وتحديد فعالياتها حول استخدامها عمليا في مجال الرياضيات التطبيقية

المبحث الثاني

قبل التطرق لطرق تبسيط المعادلات البوليانية لابد من عرض بعض التعاريف الاساسية

2-1- تعاريف أساسية

تعريف (2-1):ـ حد الضرب (product term) هو عبارة عن متغير واحد أو الضرب المنطقي لعدة متغيرات وربما تكون هذه المتغيرات على صورة المتممة(Complement).

تعريف (2-2):ـ حد الجمع (sum term) هو عبارة عن متغير واحد أو مجموعة متغيرات وربما تكون هذه المتغيرات على صورة المتممة (Complement).

تعريف (2-3):ـ صيغة مجموع حدود الضرب (sum of product expression) هو عبارة عن الإضافة لعدد من الحدود الناتجة عن ضرب المتغيرات فيما بينها.

تعريف (2-4):ـ صيغة ضرب المجموع (product of sum expression) هو عبارة عن مجموع عدة حدود مضروبة منطقياً مع بعضها البعض.

تعريف (2-5):ـ (Derivation of product of sum expression) هو عبارة عن بناء جدول يحتوي على قيم المدخلات والمخرجات وبناء عمود إضافي في داخل الجدول للحدود فتحتوي على المتغيرات بصيغة المتممة وغير المتممة ويكون التعبير المطلوب هو ضرب للحدود الناتجة من جمع الحدود من الأسطر (Rows) التي يكون مخرجها صفراً.

تعريف (2-6):ـ المعادلة البوليانية (Boolean Equation) ذات (n) من المتغيرات هي معادلة تحتوي على (n) من المدخلات الثنائية (Binary inputs) ومخرج ثنائي واحد

(Single binary output) حيث أن هناك ( ) من المعادلات البوليانية الممكنة المختلفة

لـ (n) من المتغيرات. إن التمثيل العام للمعادلة البوليانية والذي يسمى ANF

(Algebric Normal Form) هو كالآتي:ـ

F (X₁, X2… X_n) = a₀ Åå a_ix_i Å..... Ååa_ijx_ix_j Å....Å a_1..n x₁x₂…X_n

(2-1)………. حيث أن GF(2) Є a₀,a_i,-------, a_{1..n j}

تعريف (2-7):ـ المعادلة البوليانية (Boolean Equation) هي معادلة على شكل F(X)=G(X) حيث أن X=(x₁, x₂, …, x_n) هو متجه من المتغيرات البوليانية. واًن F وG هي تعبيرات على تلك المتغيرات وحل تلك المعادلة هي نقطة X^*Є B بحيث تحقق F(X^*)=G(X^*).B : متغير بولياني [7]

تعريف (2-8):ـ معادلةDNF (Disjunctive Normal Form) هي معادلة بوليانية على شكل F(X)= 0 حيث أن F هي DNF وتحقق الشروط الآتية:ـ [ 4،7]

1- في كل حد من حدود المعادلة توجد عملية (AND) بين المتغيرات.

2- العملية التي تربط الحدود جميعها هي عملية (OR).

3- يجب ظهور المتغير أو متممه في الحد الواحد.

4- لا توجد أقواس تفصل بين الحدود ولا توجد عمليات بوليا نية أخرى.

تعريف (2 - 9):ـ التعبير البولياني يدعى CNF (Condition Normal Form) إذا تحققت الشروط الآتية:ـ [6]

1- في كل حد من حدود المعادلة توجد عملية (OR) بين المتغيرات.

2- العملية التي تربط الحدود جميعها هي عملية (AND).

3- يجب ظهور المتغير أو متممه في الحد الواحد.

4- توجد أقواس تفصل بين الحدود ولا توجد عمليات بوليانية أخرى.

مثال (2-1): لو كان لدينا التعبير البوليانيF ’حيث أن F= XYZ + XYZ + XYZ

والتعبير البولياني Gحيث أن G= (X+Y+Z) (X+Y+Z) (X+Y+Z)

أيهما يدعى DNF أو CNF.

الحـــــــــل: التعبير البوليانيF يدعى DNF لأنه يحقق جميع شروط تعريف (9-2).

آما التعبير البوليانيG يدعى CNF لأنه يحقق جميع شروط تعريف (10-2).

مثال (2-2): لو كان لدينا ثلاثة متغيراتZ,Y,X كمدخلات ثنائية

جدوّل هذه القيم ثم جد حد الضرب ((product term &حد الجمع (sum term).

الـــــــــحل:

Inputs X y z	Product term (min term))	sum term (max term))
0 0 0		X+y+z
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

من خلال الجدول نجد أن maxterm هي متممة minterm

مثال(4-2): اشتق المعادلة البوليانية من خلال اعتماد حاصل جمع الضروب

للتحويل من عملية (XOR) الى عملية(OR) في المعادلةالبوليانية الآتية:

X₂X₃ X₁ X₃ Å X₂ Å X₃ Å X₂ ,X₂,X₃) = F₃(X₁

الحل:

X2 X3 X1	X3 Å X2	X3 X2	X 1X 2X 3	X2,X3)= F3(X1
0 0 0	0	0	0	0
0 0 1	1	0	0	1
0 1 0	1	0	0	1
0 1 1	0	1	0	1
1 0 0	0	0	0	0
1 0 1	1	0	0	1
1 1 0	1	0	0	1
1 1 1	0	1	1	0

لذلك يمكن استنتاج صورة أخرى للمعادلة من خلال اعتماد حاصل جمع الضروب فنحصل على الآتي:

F₃(X₁,X₂,X₃)= X₁X₂X₃ + X₁X₂X₃ + X₁X₂X₃ + X₁X₂X₃ + X₁X₂X₃

2-2- طرائق تبسيط المعادلات البوليانية

إن الهدف الأساس من عمليات التبسيط هو إيجاد ابسط شكل للمعادلة البوليانية من خلال اختزال عدد المتغيرات ضمن المعادلة وذلك باستخدام أساسيات الجبر البولياني للوصول الى حالة مبسطة. أن هذه العملية تصبح اكثر صعوبة عندما يزداد عدد المتغيرات ضمن المعادلة لذلك ظهرت الحاجة الى إيجاد طرائق وأساليب تساعد على زيادة سرعة تنفيذ عمليات التبسيط مع الوصول الى ابسط شكل للمعادلة البوليانية ومن هذه الطرائق.[4,7]

1-2-2- الطريقة الجبرية Algebratic Method

وهي طريقة تستخدم فيها قوانين الجبر البولياني، ولكن من عيوب هذه الطريقة هو عدم احتوائها على خوارزمية ثابتة توصل الى افضل صيغة مبسطة:

مثال (2-5): بسط المعادلة البوليانية مستخدماً الطريقة الجبرية:

F(X₁,X₂,X₃)= X₁X₂+ X₁X₃+ X₂X₃

الحل:

F(X₁,X₂,X₃)= X₁X₂+ X₁X₃+ X₂X₃

=X₁X₂+₁X₃+ X₂X₃(X₁+₁) (X₁+ ₁=1)

=X₁X₂+₁X₃+X₁X₂X₃+₁X₂X₃

=(X₁X₂+ ₁X₂X₃)+( ₁X₃+ ₁X₂X₃)

=X₁X₂ (1+ X₃)+ X₁X₃(1+ X₂)

=X₁X₂+ ₁X₃ (1+ X₃ =1), (1+ X₂=1)

 

-2-2-2 الطريقة التخطيطية MethodThe map

تتلخص خطوات هذه الطريقة برسم مخططات وفق طريقة معينة استناداً إلى نظريات جبرية والتي يتم بموجبها تبسيط المعادلة البوليانية بسهولة. من مساوئ هذه الطريقة هو صعوبة استخدامها لأكثر من ستة متغيرات [3,9] وأهم طريقة من الطرائق التخطيطية هي طريقة مخطط كار نوف Karnuph Map

-3-2-2طريقة مخطط كارنوف MethodKarnuph Map

تتلخص هذه الطريقة بخطوتين

أ – صنع مخطط من المربعات وتمثيل كل حد من حدود المعادلة البوليانية اللاخطية داخل المربعات بوضع (1) داخل المربعات بدل الحد المذكور وتحويل كل حد من حدود المعادلة ما يقابله من الأرقام الثنائية.

ب – أي مربعين متجاورين يتحدان للحصول على حد جديد.

الشكل (2-2) يوضح مخطط كار نوف لمتغيرين وثلاثة واًربعة متغيرات.

1 0

0
1

10 11 01 00

0
1

10 11 01 00

00
01
11
10

مثال (2-6):- بسط المعادلة البوليانية مستخدما مخطط كار نوف.

F(X,Y,Z)= ++ +

الحـــل:

بما أن المعادلة البوليانية أعلاه تحتوي على ثلاثة متغيرات لذلك يوجد (2³=8) من المربعات. تحتوي المعادلة على أربعة حدود، كل حد من حدود المعادلة نمثله بالمخطط ونضع بدل الحد المذكور بـ(1) داخل المربعات، ونحول كل حد من الحدود الأربعة ما يقابله من الأرقام الثنائية فمثلا الحد(xyz) يقابله العدد (011) من الأرقام الثنائية.

			00 01 11 10

 

XYZ	XYZ	XYZ	XYZ

 

0 1

0 1

 

 

 

 

4-2-2- الطريقة الجدولية

 

وهي طريقة يمكن استخدامها لأي عدد من المتغيرات ولا يفضل استخدامها للمعادلات البوليانية ذات المتغيرات القليلة لما يتطلب من جهد مقارنة مع الطريقة السابقة (الطريقة التخطيطية) ومن أهم الطرائق الجدولية [9].هي طريقة كوين ماكلوسكي Quine-Mecluskey

5-2-2طريقة كوين مايكلوسكي Quine- Mecluskey Method

أن الفكرة الأساسية لهذه الطريقة هي تطبيق العلاقة xy+xy=x بصورة متكررة الى أن يتم الحصول على مجموعة الحلول الأولية وبعد ذلك اختيار التعبير الأصغر من هذه الحدود.

1-5-2-2:- خوارزمية كوين ماكلوسكي لتوليد الحدود الأولية

اً – عبر عن كل حد من الحدود الدنيا للمعادلة بتمثيله تمثيلا ثنائيا رقميا.

ب – تصنيف الحدود حسب تسلسل عدد الواحدات الموجودة في التمثيل الثنائي تصاعديا.

ج – فصل كل مجموعة من الحدود المتشابهة في عدد الواحدات بوضع خط بين كل مجموعة

د – نجعل i=0 وعدد الواحدات بداية تسلسل المقارنة.

هـ – قارن كل الحدود التي تسلسلها (i) مع كل الحدود التي تسلسلها(i+1) إذا كان أي زوج من الحدود قابلا للتوحيد، ضع الحد الجديد الموحد باستخدام التمثيل الثنائي مع وضع علامة

( ) أمام الحدين المتحدين.

و – زد (i) بمقدار (1) وكرر تطبيق الخطوة (هـ) وزيادة (i) بمقدار (1) الى أن تنتهي مقارنة جميع الحدود.

ز – نأخذ القائمة الجديدة ونكرر تطبيقات الخطوات د, هـ, و.

ح – يتوقف تطبيق هذه العملية عندما لايمكن تشكيل أي قائمة جديدة.

ط – جميع الحدود غير مؤشرة بعلامة ( ) تعتبر حدود أولية ضامنة.

2-5-2-2:خوارزمية اختيار التعبير الأصغر

اً – بناء جدول جديد مكون من مصفوفة الأسطر فيها الحدود الأولية والأعمدة هي الحدود الصغرى وضع في سطر الحدود الأولية وتحت أعمدة حدودها الصغرى علامة(x).

ب – أيجاد جميع الحدود الأولية الضامنة الضرورية في جدول الحدود الأولية وذلك بفحص جميع أعمدة الجدول وتأشير الحد الذي يحتوي على علامة تقاطع x)) واحدة فقط بدائرة مغلقة معوضع علامة( ) بجانب جميع الحدود الأولية الضامنة الضرورية أن وجدت وتأشير الحدود الصغرى الممثلة بأعمدتها العلامة( ) والتي ضمن السطر الضروري المؤشر.

ج – فحص جميع الأعمدة والأسطر المتبقية وتأشير السطر الذي يحتوي على اكبر عدد من علامات x ) ( أي السطر الذي يتكون من اكبر عدد من الحدود الصغرى المتبقية مع تأشير الحد الأولي مع حدودها الصغرى.

د – تكرار الخطوة الثالثة الى إن يتم تأشير كافة الحدود الصغرى.

هـ – التمثيل الأصغر هو كافة الحدود الضامنة التي تم تاًشيرها.

مثال(2-7): بسط الدالة

الحـل:

حيث أن 1 يقابل بالتمثيل الثنائي 0001, 3 يقابل بالتمثيل 0011, 7 يقابل بالتمثيل 0111 و 11 يقابل بالتمثيل الثنائي 1011, 15 يقابل بالتمثيل الثنائي 1111 إذا تأملنا جيدا التمثيل الثنائي للحدود الصغرى, فأننا سنلاحظ أن الشرط الضروري لاتحاد الحدين الأصغرين هو أن يكون تمثيلها الثنائي يختلف بموقع واحد فقط.

فعلى سبيل المثال يكون تمثيل الحدين الأصغرين الاثنين كما مبين في الجدول الآتي:-

الحد الأصغر	التمثيل الثنائي للحد الأصغر	الحد الناتج من الاتحاد
	0001 0011	00-1

والحد الناتج من اتحاد هذين الحدين الأصغرين يمثل بـ(00-1) وخط الشارحة (-) يدل على المتغير المحذوف ( ) نتيجة لاتحاد الحدين وتكوين الحد الجديد ().

مثال(1-8): بسط المعادلة البوليانية الآتية بطريقة كوين – مايكلوسكي

الحل:

أولا: لتوليد الحدود الأولية

نرتب الحدود الصغرى للمعادلة F كما مبين بالقائمة 1 وتتم المقارنة بين كل الحدود التي تسلسلها (i) مع الحدود التي تسلسلها ( i+1 ) كما مبين بالقائمة 2، القائمة 3

الجدول رقم (2-1) يمثل خطوات إيجاد الحدود الأولية الضامنة وبذلك تصبح جميع الحدود غير المؤشرة بعلامة ( ) تعتبر حدوداً أولية ضامنة

	القائمة 2 أرقام الحدود التمثيل الثنائي w x y z 1 , 9 4 , 6 8 , 9 8 , 10 - 0 0 1 0 1 - 0 1 0 0 - 1 0 - 0 6 , 7 9 , 11 10 , 11 0 1 1 - 1 0 - 1 1 0 1 - 7 , 15 11 , 15 - 1 1 1 1 - 1 1

 

القائمة 3 التمثيل الثنائي w x y z أرقام الحدود 1 0 - - 1 0 - - 8 ,9 ,10 , 11 8 ,9 ,10 , 11

القائمة 1

 

أرقام الحدود	التمثيل الثنائي w x y z
1 4 8	0 0 0 1 0 1 0 0 1 0 0 0
6 9 10	0 1 1 0 1 0 0 1 1 0 1 0
7 11	0 1 1 1 1 0 1 1
15	1 1 1 1

 

الجدول رقم (2-2) يمثل الحدود الأولية الضامنة

 

أرقام الحدود	التمثيل الثنائي w x y z	الحد الناتج
1, 9	- 0 0 1
4, 6	0 1 - 0
6, 7	0 1 1 -
7, 15	- 1 1 1
11, 15	1 - 1 1
8, 9, 10, 11	1 0 - -	W X

ثانيا: اختيار التعبير الأصغر

تتضمن الخطوة الثانية في هذه الطريقة استخدام رسم التضمين الأولي اختيار التعبير الأصغر من مجموعة التضمينات الأولية. وفي هذه الخطوة تدرج الحدود الدنيا للمعادلة في أعلى الرسم والتضمينات الأولية على الجانب الأيسر. فإذا كان التضمين الأولي يغطي حداً أدنى مع حدين توضع علامة (x) في موضع التقاطع التضمين الأولي الصف والعمود لذلك الحد ويبين الجدول رقم (2-3) رسم التضمينات الأولية من الجدول السابق رقم (2-5) يسمى التضمين الأولي المفرد الذي يغطي الحد الأدنى بتضمين أولي ضروري

(essential prime implicates) ومن السهل إيجاده من خلال رسم التضمينات الأولية.

جدول رقم (2-3) يوضح رسم الحدود الأولية الضامنة

الحد الناتج	أرقام الحدود	1 4 6 7 8 9 10 11 15
	1, 9	x x
	4, 6	x x
	6, 7	x x
	7, 15	x x
	11, 15	x x
	8, 9, 10, 11	x x x x

فإذا كان أي عمود في الرسم يحتوي على (x) واحدة فقط, فان الصف الناظر له هو تضمين أولى ضروري (essential-prime-implicates) تحتوي الأعمدة (1, 4, 8, 10)

في الجدول رقم (2-3) على x واحدة فقط لذلك فان التضمينات الأولية () هي تضمينات أولية ضرورية.

وثم تشطب الأعمدة في الجدول السابق المناظرة لكل الحدود الدنيا والتي تغطى بواسطة هذا التضمين الأولى كما موضح في الجدول رقم (2-4)

الجدول رقم(2-4)

الحد الناتج	أرقام الحدود	1 4 6 7 8 9 10 11 15
	1, 9	Ä x
	4, 6	Ä x
	6, 7	X X
	7, 15	X x
	11, 15	x x
	8, 9, 10, 11	Ä x Ä x

بعد ذلك نختار اقل مجموعة من التضمينات الأولية لكي نغطي الأعمدة المتبقية وفي هذا المثال

(xyz) يغطي العمودين الباقيين.

وبذلك يصبح الحد الأدنى لجمع الضروب Product minimum sum

هو

المبحث الثالث

حلول المعادلات البوليانية equations Solution of Boolean

قبل التطرق إلى طرائق حل المعادلات لابد من معرفة بعض التعاريف والمبرهنات المهمة التي تعتبر أساساً لحل المعادلات.

3-1- المعادلة البوليانية

تقسم المعادلة البوليانية الى نوعين:

أ- المعادلة البوليانية الخطية

أشار(kebjork,1974), (Dodos, 1978 A).[1,8] أن المعادلة تكون خطية إذا كان كل حد من حدودها لا يحتوي على أكثر من متغير واحد فقط، كما أن كل متغير يظهر للقوى (1).

(First power) فقط وكذلك يمكن التعبير عنها بأنها خطية هي أنها تمتلك في جميع عملياتها

(Exclusive or).

كما يمثل عدد (n) من المعادلات الخطية أو اللاخطية التي تحتوي على(n) من المجاهيل بمنظومة (n) من المعادلات الخطية أو اللاخطية. ويمكن معرفة حل هذه المعادلات على أنها مصفوفة تتكون من (nxn) من القيم بحيث عند تعويض المتغيرات بهذه القيم تحقق المعادلات.

بالإضافة إلى ذلك فان هناك ثلاثة أنواع من الحلول لمنظومات المعادلات البوليانية الخطية بشكل عام هي:

-1 قد يكون لمنظومة المعادلات حل وحيد.

-2قد يكون لمنظومة المعادلات أكثر من حل.

- 3قد لا يكون هناك حل لمنظومة المعادلات.

ويطلق على المنظومات من النوع الثاني والثالث بالمنظومات المفردة (singular)

تعريف (3-1): - المعادلة البوليانية تدعى (Consistent) إذا كان لها حل

و (inconsistent) إذا لم يكن لها حل. ] 7 [

تعريف(3-2):- وزن هامنك (Hamming weight) وزن المعادلة البوليانية

هو وزن هامنك لصورة المعادلة F والذي يساوي عدد الواحدات في جدول حقائق المعادلة F ويرمز لـه wt(F) .2] [

تعريف(3-3): - المسافة بين معادلتين بوليانيتين(Distance) يعبر عن المسافة

بين معادلتين بوليانيتين G,F تنتميان إلى الفضاء F_n.

و(F, G Є Fn) بالعلاقة الآتية. ] 2 [

…..(3-1)

حيث أن i=1, 2 …………. n تمثل عدد بتات المعادلة

تعريف (3- 4):-درجة لاخطية المعادلة البوليانية (Nonlinearlty Degree N_f)

وهي اقصر مسافة بين المعادلة وبين جميع المعادلات الخطية في

نفس الفضاء، ويمكن تمثيلها بالعلاقة الآتية:] [2

(3-2)..

مبرهنة (3-1):-

المعادلة البوليانية التي يحوي مخرجها على عدد متساوي من الواحدات والأصفار تكون معادلة خطية.

مبرهنة (3-2):-

المسافة بين معادلتين خطيتين مثل α,β تنتميان إلى فضاء المعادلات الخطية L_nبالعلاقة الآتية: ] 2 [

(3-3)…..

ب- المعادلة البوليانية اللاخطية:-

هي المعادلات البوليانية التي تعتمد على أكثر من متغير بولياني وتستخدم عمليات بوليانية لاخطية (OR الـ AND) بين هذه المتغيرات.ولذلك فأن أي معادلة بوليانية تحتوي على إحدى هاتين العمليتين تعتبر معادلة بوليانية لاخطية.

وعلى سبيل المثال:

F(X₁,X₂)=X₁.X₂

F(X₁,X₂,X₃)=X_2Å X₁.X₂.X₃

F(X₁,X₂,X₃,X₄)=X_{2 Å} X_{3 Å} X₁.X₂.X₃.X₄

مبرهنة (3-3): المعادلة 0 = (_n F(x₁,x_2,...,x تكونConsistent إذا وفقط إذا

أما 0 = (0 _{و n-1} F(x₁,x_2,...x أو 0 =(1 _{و n-1} F(x₁,x_2,...x

تكون Consistent أيضا. ] 7 [

مبرهنة (3-4):- المعادلة 0 = (_n F(x₁,x_2,...,x تكون Consistent إذا وفقط إذا كانت المعادلة اللاخطية

0= (1 و _n-1 F(x1,x2,...,x (,0 _n-1 F(x1,x2,..,.x Consistent

أيضا. ] 7 [

مبرهنة (3-5): إذا كانت النقطة هي حل للمعادلة

0= (,1 _{1 -n} F(x₁,x_2,...x (,0 _{1 -n} F(x₁,x_2,...x وكـانت أو فـــان هو حل للمعادلة

0 = (x _n, _{1 -n} F(x₁,x_2,...x.[7]

2-3- طرائق حل المعادلة البوليانية الخطية

قبل التطرق لحل المعادلة البوليانية لا بد من معرفة الفضاء ( Space (الذي يعبر عنه مجموعة من المعادلات البوليانية لـ (n) من المتغيرات ويعرف كالآتي:-

ويعرف فضاء جميع المعادلات البوليانية التي تربط n من البتات الى n من البتات

وتعرف المجموعة الجزئية للمعادلات البوليانية الخطية ضمن الفضاء F_n. كالآتي

ويكون عدد هذه المعادلات البوليانيه الخطية ضمن الفضاء F_n. هو

يكون عدد المعادلات البوليانية الخطية واللاخطية في الفضاء F_n. من العلاقة الآتية:

أما عدد المعادلات البوليانية اللاخطية هو (F_n-L_n).

3-3- خوارزمية الحذف لكاوس Gauss elimination method

اًعتماداً على طريقة الحذف لكاوس(Gauss elimination method) لحل أنظمة من المعادلات الخطية لأنها مباشرة وعامة وغير خاصة بالإضافة إلى ذلك إنها تحتاج إلى عدد اقل من العمليات الحسابية.

أوضح كل من (Dodes, 1978)، (Alcebjrok,1974) بأنه يمكن تمثيل الأنظمة التي تحتوي على المعادلات الخطية كما يأتي:

 

_أو AX=C

حيث أن A هي مصفوفة أبعادهاnxn وعناصرها a_ij ويطلق عليها مصفوفة المعاملات Coefficients Matrix)) أما X فيدعى عمود المجاهيل وC يدعى عمود الثوابت تعتمد الخوارزمية على تحويل معاملات المجاهيل إلى أصفار وصولا إلى المصفوفة ذات المثلث السفلي الصفري.

يحذف العمود الأول للسطر الثاني بضرب معاملات المعادلة الأولى بـ وطرح المعادلة الأولى من المعادلة الثانية. بعدها بحذف العمود الاول للمعادلة الثالثة بضرب معاملات المعادلة الأولى بـ وطرح المعادلة ألاولى من العمود الثالث تستمر بهذه العملية إلى أن يصبح المثلث السفلي الأيسر لمصفوفة المعادلات صفرا

يمكن حل المعادلات بعد عمليات الحذف بشكل معكوس ابتداء من آخر معادلة ووصولا إلى أول معادلة. بعدها يتم الحصول على قيم المجاهيل بواسطة التعويض الخلفي

(Backward Substitution)

4-3 طرائق حل المعادلة البوليانية اللاخطية:

1 - طرائق حذف المتغير Variable elimination procedure

2 - طرائق التفرع procedure Branching

3 - طرائق التجمع (الإجماع) procedure Consensus

4 - استخدام البرمجة الرياضية Mathematical Programming Approaches

في هذه البحث سيتم عرض طرائق حذف المتغيرVariable elimination procedure وطرائق التفرعprocedure Branching بصورة مفصلة مع وجود بعض الأمثلة التي سيتم ذكرها[7].

 

1- طرائق حذف المتغير PROCEDUREVARIABLE ELIMINATION

وهي طريقة لحل المعادلة البوليانية اللاخطية والتي تطبق فيها مبرهنة (3-4) ومبرهنة (3-5)

مثال (1-3): لتكن معادلة DNF متمثلة بالصيغة الآتية:

F₃ (x_1,x_2,x₃₎=0 .......... (1)

حيث أن:

x₁ x₃ +x₂ x₃ …(2) x₁ x₂ x₃ +x ₁ x₂ x₃+x₁ x₂+ = F₃

الحل:

نطبق مبرهنة (3-4) على المعادلة F3(x1,x2,x3)=0

أذن المعادلة F3(x1,x2,x3)=0 تكون consistent

إذا وفقط إذا المعادلة F₂(x_1,x_2,)=0 تكون consistent أيضاً.

وبذلك تصبح المعادلة F₃كآلاتي:-

F₂(x_1,x₂)=F₃(x_1,x_2,0) F₃(x_1,x_2,1)

F₂(x_1,x₂)=(x₁x₂ +x₁x₂)(x₁x₂+x₁+x₂).. ...(3)

ثم نطبق مبرهنة (3-4) مرة أخرى على المعادلة F₂

أذن المعادلةF₂(x_1, x2)=0 تكون consistent إذا وفقط إذا كانت المعادلة F₁(x₁)=0 consistent أيضاً.

وبذلك تصبح المعادلة التي رقمها (3) كالآتي:

F₁(x₁)= F₂(x_1,0) F₂(x_1,1)

F₁(x₁)=(X₁) (x₁+X₁+1)(x₁)(0+X₁+0)

F₁(x₁)=(X₁) (X₁)=X_{1.. …………………….} (4)

ثم نطبق مبرهنة (3-4) مرة أخرى على المعادلة F₁ أذن المعادلة 0 F₁(x₁)=

تكون consistent إذا فقط إذا كانت المعادلة 0 F₀= consistent أيضا.وبذلك تصبح المعادلة التي رقمها (4) كالآتي:

F₁(1) F₁(0) F₀=

F₀= 1.0

0…………. (5) F₀=

وبذلك اصبح واضحاً أن 0 F₀= تكون consistent

وبذلك نستطيع أن نطبق مبرهنة (3-5) لإيجاد النقطة (^* X₃,X₂^*,^*X₁) التي تحقق المعادلة

0 F₃=

ليكن:

X₁^* = F₁ (0)= 0 =1

F₂(x₁^*,0) = F₂(1,0)=0 =^* X₂

=F₃(x₁^*,x^*_2,0) = F₃(1,0,0)=0 ^* X₃

أذن تكو ن النقطة (1,0,0) = (x^*₁,x₂^*,x^*₃) هي حل للمعادلة F₃ وهي تحقق المعادلة F₃

مثال (2-3): لتكن معادلة DNF متمثلة بالصيغة الآتية:

F₃(x_1, x2, x3) =0........ (1) حيث أن

 

الحل:

 

يمكن بناء جدول الحقائق لهذه المعادلة وكآلاتي:

x1 x2 x3	x1Åx2	1Åx1Åx2	x1 x3	x2 x3	F3=
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 1 1 1 1 0 0	1 1 0 0 0 0 1 1	0 0 0 0 0 1 0 1	0 0 0 1 0 0 0 1	1 1 0 1 0 1 1 1

يمكن استنتاج صورة أفضل للمعادلة من خلال اعتماد حاصل جمع الضرب فنحصل على الآتي:

F₃=X₁ X₂ X₃ +X₁ X₂ X₃ +X₁ X₂ X₃ + X₁ X₂ X₃ + X₁ X₂ X₃ + X₁ X₂ X₃ ----(3)

نطبق مبرهنة (3-4) على المعادلة =0 F₃(X₁ X₂ X₃)

وبذلك تصبح المعادلة =0 F₃(X₁ X₂ X₃) التي رقمها (3) كالآتي: -

F₃(X₁, X₂,1) ₃(X₁,X₂, 0) F F₂=

X₁X₂ + X₁ X₂+ X₁X₂) ---------------- (4) X₁ X₂+) X₁ X₂₎+ X₁ X₂+) F₂=

ثم نطبق مبرهنة (3-4) مرة أخرى على المعادلة F₂ أذن المعادلة

تكون consistent إذا وفقط إذا المعادلة =0 F₂(X₁,X₂) تكون consistent أيضاً.

وبذلك تصبح المعادلة F₃ التي رقمها (4) كالأتي: F₁=F₂ (X_1, 0) F₂ (X_1, 1)

F₁=(X₁)(X₁₊X₁)(X₁)(X ₁+X₁)

F₁=X_1.X₁

F₁=0----------------------------------------- (5)

ثم نطبق مبرهنة (3-4) مرة أخرى على المعادلةF₁ إذن المعادلة F₁ (X₁)=0 تكونconsistent أيضا وبذلك تصبح المعادلة F₁ التي رقمها (5) كالآتي:

F₀=F₁ (0) F₁ (1)

F₀=0. 0

F₀=0-------------------------------------------------- (6)

وبذلك اًصبح واضحاً أن تكون consistent وبذلك نستطيع أن نطبق مبرهنة (5-3) لإيجاد النقطة (X^*_1,X^*_2,X^* ₃) التي تحقق المعادلة F₃=0 ليكن:

أذن تكون النقطة (0,1,0) =(^*₃ X^*₁,X₂*,X) هي حل للمعادلة F₃ وهي تحقق المعادلة أعلاه.

2- طرائق التفرع Branching Procedure

تتضمن هذه الطريقة المحاور والاتجاهات الطبيعية لحل المعادلات البوليانية اللاخطية.وقد اقترح الباحثان Davis & Putnamقوانين تتعلق بمتغيرات المعادلة البوليانية والتي تكون على الصيغة الآتية: [9 ]

حيث, F_2, F₀ F₁ هي DNF وتتضمن هذه القوانين بتثبيت أحد المتغيرات إلى قيمة خاصة بدون التأثير على تماسك المعادلة البوليانية اللاخطية.تعتبر هذه القوانين ذات اتجاهين هما

أ- قوانين الحرف الواحد Unit Literal Rules

لكل i=1,2 ------ n

ا ً- إذا كانت F على الشكل الأتي:-

(2)--------------- ₂ F=X_i+X _i+F

فان المعادلة تكون inconsistent

ب- إذا كانت F على الشكل الآتي:

(3)-------------------- ₂ F=X_i+F

عندها يمكن فرض X_i=1 أي أن X _i=0

جـ- إذا كانت F على الشكل الآتي:

(4)------------------- ₂ F=X_i+F

عندها يمكن فرض X_i=0 أي أن X _i=1

 

ب- قوانين تعدد الحروفMonotone Literal Rules

لكل i=1,2 ------n

اً - إذا ظهر المتغير Xi وحيداً على صيغة المتغير في المعادلة F

حيث F تكون على الشكل الآتي:

(5)-------------- ₂ F=X_iF₁+F

عندها يمكن فرض X _i=0 أي أن _i=1 X

ب- إذا ظهر المتغير X_i وحيداً على صيغة المتممة في المعادلة F

حيث F تكون على الشكل الآتي:

(6)-------------- ₂ F=X_iF₀+F

عندها يمكن فرض _i=1 X أي أن _i=0 X

ويمكن توضيح هذه القوانين بالأمثلة الآتية:

مثال (3-3): لتكن معادلة DNF متمثلة بالصيغة الآتية:

=0---------------------------------- (1) F₃(X₁ X₂ X₃)

حيث أن

X₁ X₂ X₃----------------(2) X₂ X₃ Å X₁ X₃ Å X₁ X₂ Å 1Å F₃=

الحل:

X₁ X₂ X₃ X₂ X₃ Å X₁ X₃ Å X₁ X₂ Å 1Å F₃=

يمكن بناء الحقائق لهذه المعادلة كالآتي:

X1 X2 X3	X1 X2	1ÅX1X2	X1 X3	X2 X3	X1 X2 X3	F3=
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 0 0 0 0 1 1	1 1 1 1 1 1 0 0	0 0 0 0 0 1 0 1	0 0 0 1 0 0 0 1	0 0 0 0 0 0 0 1	1 1 1 0 1 0 0 1

يمكن استنتاج صورة افضل للمعادلة من خلال اعتماد حاصل جمع الضروب فنحصل على الآتي:

F₃=X₁ X₂ X₃ +X₁ X₂ X₃ +X₁ X₂ X₃ + X₁ X₂ X₃ + X₁ X₂ X₃ ………..(3)

نطبق قوانين literal rules Unit وبذلك نجعل X₃=1 أي أن X₃=0 وبذلك تصبح المعادلة رقم (3) كالآتي:

………… (4)... F₂= X₁X₂+ X₁X₂

ثم نطبق قوانين literal rules Unit مرة أخرى وبذلك نجعل X₂=1 أي أن

X₂=1 وبذلك تصبح المعادلة رقم (4) كالآتي:

F₁= X₁-------------------------------- (5)

ثم نطبق قوانين literal rules Monotone وبذلك نجعل X₁=0 أي أن

X₁=1 وبذلك تصبح المعادلة رقم (5) كالآتي:

F₀= 0-------------------------------- (6)

وحسب مبرهنة (3-5) ليكن

X₁* = F(0)=0

F2(x₁*,0) = F₂(0,0)=1.1+0.0=1=* X₂

= F3(x₁*,x₂*,0) = F₃(0,1,0)=0 +0+1+0+0=1 * X₃

وبذلك تكون النقطة (0_,0,1)=(^* X₃ ^* X₂ X₁^*) هي حل للمعادلة F₃

مثال(4-3): لتكن معادلة DNF متمثلة بالصيغة الآتية:

=0---------------------------------- (1) F₃(X₁ X₂ X₃)

حيث أن

X₁ X₂ X₃------------------(2) X₂ X₃ Å X₁ X₂ Å X₁Å X₂ Å F₃=

الحل:

يمكن بناء جدول الحقائق لهذه المعادلة وكالآتي:

X1 X2 X3	X1Å X2	X1X2	X2 X3	X1 X2 X3	F3
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 1 1 1 1 0 0	0 0 0 0 0 0 1 1	0 0 0 1 0 0 0 1	0 0 0 0 0 0 0 1	0 0 1 0 1 1 1 1

يمكن استنتاج صورة افضل للمعادلة من خلال اعتماد حاصل جمع الضروب فنحصل على الآتي:

X₁ X₂ X₃+ X₁ X₂ X₃ + X₁ X₂ X₃+ X₁ X₂ X_{3---------------}(3) X₃ X₁ X₂ F₃=

نطبق قوانين literal rules Unit وبذلك نجعل1 =X₃ أي أن 0 =X₃

وبذلك تصبح المعادلة رقم (3) كالآتي:

X₁ X_{2 ----------------------} (4) + X₁ X₂ F₂=

ثم نطبق literal rules Unit وبذلك نجعل 1 =X₂ أي أن 0 =X₂

وبذلك تصبح المعادلة رقم (4) كالآتي: F₁=X_{1---------------------------------}(5)

نطبق قوانين literal rules Monotone وبذلك نجعل= 0 X₁ أي أن X₁= 1 وبذلك تصبح المعادلة رقم (5) كالآتي:

F₀=0 ------------------------------- (6)

وحسب مبرهنة (3-5) ليكن

X^*₁=F₁(0)=0

X^*₂=F₂(X₁^*,0) =F₂(0,0) =0

X^*₃=F₃(X^*₁,X^*₂,0) =F₃(0,0,0) =0

وبذلك تكون النقطة(0,0,0) =(X^*_2,X^*₃ X^*₁,) هي حل للمعادلة البوليانية F₃

المبحث الرابع : المناقشة والاستنتاجات والتوصيات

1-4المناقشة والاستنتاجات

1- إن العمل على زيادة عدد المتغيرات البوليانية الداخلة في تكوين المعادلة البوليانية يعمل على الزيادة الآسية السريعة لعدد المعادلات الناتجة.وهذا يسبب زيادة في التعقيد للتعامل مع هذه المسألة مما يؤدي بطبيعة الحال الى تعقيد الحل الناتج من هذه الطريقة

2- هنالك حالات (عند استخدام طريقة بايبر لحساب معكوس المصفوفة) لا تضمن وجود حل وحيد للمصفوفة الخاصة بمجموعة المعادلات البوليانية الخطية الناتجة.وهذا مما يؤدي الى عدم إيجاد حل للمعادلة البوليانية.

2-4- التوصيات

1-دراسة تحليلية لبعض الطرائق التي لم يتم التركيز عليها في البحث لحل المعادلة البوليانية اللاخطية مثل

Consensus Procedure)، Mathematical Programming approaches )

2- أيجاد المعادلات البوليانية الخطية واللاخطية عندما يكون n=4

3- بناء خوارزميات لتسهيل عملية حل المعادلات حاسوبياً ضمن ازمان تعقيد مقبولة في الحاسبة (polynomial time).

المصادر Reference

[1] Gernund Dahlquist Akebjrok, “Numerical Methods”, 1974.

[2] J.pierzyk and G.finkelstein, Tow Effective Non –Linear

[3] HURST.S.L., “Logical proceesing of digital signals”, NewYork, 1978.

[ 4] Dietemeger D.L, “Logic Design of Digital systems” Allyn and Bacan Inc,1979.

.[5] M. Morris Mano, “ Digital Design”

[6] Math forum Home // math library //, Quick refrence // math form//

Ask Dr Math, 1994-2002

[7] Chapter 2, “Boolean Equations”,http://Webster.cs-ucr-edu/AoA /windows/ HTML / Digital Design, 2002.

[8]-عبد الكريم مرهج، " معالجة المعادلات البوليانية الخطية واللاخطية"، أطروحة ماجستير مقدمة الى قسم علوم الحاسبات في الجامعة التكنولوجية،1989.

[9]-محمد صفر صديق، "تحليل تعقيدات المعادلات البوليانية "، أطروحة ماجستير مقدمة الى قسم علوم الحاسبات في الجامعة التكنولوجية،1990.