تعتبر مادة (التراكيب المنفصلة) أو ما يعرف باللغة الانجليزية ب ( discrete structures ) من المواد الأساسية في علم الحاسوب، فهي مادة متفق على أهمية وجودها في أي برنامج دراسي يؤدي إلى منح شهادة جامعية في علم الحاسوب، في معظم جامعات العالم إن لم يكن جميعها.
والحقيقة أنه يوجد أكثر من هدف من تدريس (التراكيب المنفصلة). ومن أهم هذه الأهداف أنها تهيء لطالب علم الحاسوب الأسس الرياضية المتينة التي يحتاج إليها عند دراسة المواد المتقدمة في علم الحاسوب مثل (تراكيب البيانات) و(خوارزميات الحاسوب)، َاضافة الى أنها تعلمهم كيف يفكرون بطريقة رياضية منطقية.
ونظرا للنقص الشديد في المراجع العربية في هذا الموضوع ، فقد رأيت أنه من الضروري إعداد هذا الكتاب لمساعدة الأستاذ والطالب في العملية التعليمية لمادة (التركيب المنفصلة).
وهناك اختلافات في وجهات نظر المختصين في هذا المجال. ولكني بعد الاطلاع على عدد من مناهج الجامعات العالمية، وبالخصوص كتاب كنث روزن Kenneth Rosen (وهو مرجع أساسي لهذا الكتاب):
Discrete Mathematics and Its Applications
وجدت أنه من الأنسب أن أتبع التسلسل التالي:
1. علم المنطق
2. الفئات
3. الدوال
4. المتواليات
5. الاستنتاج الرياضي
6. طرق العد
7. العلاقات
8. الأشكال
9. الأشجار
وأعتقد أن في هذا التسلسل ما يكفي أو يزيد عن الوعاء الزمني لفصل دراسي كامل (حوالي 14 أسبوعا بواقع ساعتين نظري وساعتين عملي).
والدروس العملية في هذه المادة مهمة ، فهي تعمق فهم الطالب للدروس النظرية، وتعطيه خبرة أكثر في البرمجة بصفته متخصصا في علم الحاسوب. وفي هذه الدروس يكتب الطالب برامج بلغة باسكال أو سي أو غيرها مثل:
• برامج تطبع جداول الصدق للمؤثرات المنطقية.
• برامج تحسب العمليات على الفئات مثل التقاطع والاتحاد وغير ذلك.
• برامج لحساب الدوال
• برامج تحسب مجموع متوالية مع المقارنة بالقانون
• برامج لحساب التوافيق والتباديل
• برامج لاختبار نوع العلاقة
أملي أن يجد طلاب هذا المقرر في هذا الكتاب معينا لهم في دراستهم للتراكيب المنفصلة، مستفيدين من تعدد الأمثلة والتمارين والاختبارات المحلولة.
د. عمر زرتي
8 تمارين 5 70
الباب الثالث: الدوال كصمتك 1111
1 مقدمة 73
2 دالة واحد لواحد 1-1 76
3 الدالة الفوقية 00140 77
4 معكوس الدالة عير10116 79
5 الدالة المركية «متتعهصنة 0116 تمع 81
6 رمسم الدالة ممتاعصية م له اميضيع 84
7 تمارين 6 86
الباب الرابع: المتواليات 5601060625
1 _مقدمة 89
2 امثلة لبعض المتواليات 90
4 . مجموع المتوالية 92
6 برنامج لمتوالية 94
7 _تمارين (© 95
الباب الخامس: الاستنتاج الرياضي
التراكيب المفصلة 5110811185 1180118 7 :
1 مقدمة 97
2 مجموع جلي الفردية 98
الباب السادس : . طرق العد ع(0(7110©
1 مقدمة 103
2 قاعدة الجبمع 103
3 قاعدة الضرب 104
64 ارين (9) 109
6 التواقيق مسمتةاةستاسم. 114
7 مث بامكال عاوصمتن [وعفوط 16
8 تمارين (10) 118
الباب السابع : العلاقات و((0) 18612
1 مقدمة 121
2 أمثلة 122
3 لدالة ومتاعمية 123
4 أنواع العلاقات 126
6 تمثيل العلاقات باستخدام المصفوفات 130
7 تمارين (11) 134
9 فصيلة التكافؤً 01045 ع01781606او15 139
0 رامج لاختبار العلاقات 141
1 تمارين (12) 143
2 الترتيب الجزئي 0:06:68 لمتتوط 144
3 الترتيب الكلي ع توه 1012 147
4 الترتيب الحسن ع1178611-0:06:10 148
5 تمارين (13) 149
الباب الثامن :| الأشكال مططرد«:6
1 مقدمة ل 151
2 الأشكال الكاملة مطتي ع1عام 0 152
3 تطبيقات الأشكال في شبكات الحاسوب 208
4 نظرية التصاقع تمعد ع ستعلهطة1صقط 157
5 تمارين (14) 158
6 تمثيل الأشكال مداطري0 ع متا0ت 1860165 158
7 تمارين (15) 166
8 تمثيل العلاقات بالاشكال الموجهة 170
0 الاتصال بواتاءع 6000 17
1 الأشكال ذات القسمين 182
2 تمارين (17) 185
3 الأشكال المستوية 186
التراكيب المفصلة 51016011185 1180118 )9 ٍ
4 الأشكال المميزة ممترميع لمنطونة» 189
5 متمارين (18) 191
الباب التاسع : الأشجار | #عع«71
1 مقدمة 193
2 تعريفات 194
3 أمثلة تطيقية للاشجار 200
5 تمارين 208
ملحق :
2. إجابة تمارين(2) 216
3. إجابة تمارين(3) 223
7.إجابة تمارين(17) 260
التراكيب المفصلة 5110611185 180118 ).0 :
الباب الأول
المنطق عنع1.0
إذا حاول أحد أن يققعك بشيء ما أو يبرهن نظرية ما فإه يستعمل المنطق
للوصول إلى هدفه. ولكن كيف تعرف أن أسلوبه 'منطقي" وأنه يتبع قواعد المنطق
الفرضية (أو العبارة المنطقية) هي جملة مفيدة قابلة لأن تكون إما صائبة
8) القاهرة عاصمة مصر.
الباب الأ
©) القمر أكبر من الشمس.
) المثلث له أربعة أضلاع.
©) اليوم عيد ميلادي.
فيمكن أن تكون صائبة أو خاطئة بناء على متى تم قولها.
0 ما اسمك ؟
تن كلية العلوم.
عامة فإن جمل الاستفهام والتعجب والأمر لاتعتبر فرضيات منطقية.
المتغير المنطقي هو متغير قيمته إما 11106 أو 0188 ونستخدمه كرمز للعبارة
المنطقية باستخدام حرف واحد ؛ وعادة ما نستخدم الأحرف:
لهذا الغرض ٠
التراكيب المفصلة 51116111185 1180118 )0 :
كما تستخدم الاختصار
عقل 2 1
وبستخدم المتغير المنطقي في بعض لغات البرمجة مثل لغة باسكال حيث يسسى
متغير بوولي 38018:ة1 13001608 نسبة إلى العالم الرياضي جورج بوول
©8001 060:86 ._مؤسس علم الجبر المنطقي.
مثل : ما هي قيم المتغيرات المنطقية 0 و 0 في الجمل التالية بلغة باسكال :
الإجابة هي أن المتغير المنطقي 0 تتعين له قيمة 1016 أما المتغير المنطقي 0
فتتعين له القيمة 1056 .
استخدام المؤثرات المنطقية 00881015 10810681 يساعدنا في تبسيط كتابة
الجمل المنطقية المعقّدة 000005111005 00:/0010110. في هذا الباب سوف
ندرس المؤثرزرت
118881101 008010 مؤثر النفي ٠
٠ مؤثر الامج «متتعرره «متامستزدصم
٠ مؤثر لفصل ١متتعره صمت منزكتك
* مؤثر الاسنتباط «تمتوععره ممتاوعتادرس
ينفي الجملة المنطقية . ©( ( ونرمز له 0 وأحيانا نستخدم الرمز 0 - أو
0 07 بنفس المعنى) وهو «متصععمه نهد لأنه يؤثر على
العبارة المنطقية الواحدة فيغير قيمتها من 7 15 © 12
ويمكن تلخيص ذلك فيما يعرف بجدول الصواب عاططة7 100
ن جميع القيم التي يمكن أن تعين
ومنه نستطيع حساب القيمة المنطقية
لكل عملية منطقية يوجد جدول صواب
للمتغير وما يقابل ذلك نتيجة هذه العملية
لعبارة مركبة من عبارات بسيطة .
جدول الصولب للعبارة 0
وصل أمتعمه «مناعسنزدم أر رابط دمج . ممناعمسزدهه