الرياضيات المتقطعة

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

المقرر الأول يغطي ستة موضوعات: المنطق، والمجموعات، والعدّ، والمخططات، ونظرية الأعداد، والبرهان. والمنطق يأتي أولًا، لأن كل موضوع آخر مكتوب به. اختر أداة ربط في الأسفل وبدّل قيمتي p وq.

المنطق: العبارات وأدوات الربط

العبارة جملة إما صائبة وإما خاطئة، مثل «7 عدد أولي» أو «السماء تمطر». ويبني المنطق عبارات أكبر من عبارات أصغر بعدد قليل من أدوات الربط، وجدول الصواب يسرد النتيجة لكل تركيب من المدخلات.

اثنتان من هذه تفاجئان الناس. الفصل المنطقي شامل: «p أو q» صائبة حين تكون الاثنتان صائبتين، بخلاف «شاي أم قهوة؟» في الكلام اليومي. أما الصورة الحصرية فلها اسمها الخاص، الفصل الحصري.

والأخرى الاستلزام. p → q خاطئة في صف واحد فقط، حين تكون p صائبة وq خاطئة. فكّر فيها وعدًا: «إذا أمطرت، سأحضر مظلة». ولا يُنقض الوعد إلا إذا أمطرت ولم تكن هناك مظلة. وفي يوم جاف لم يُنقض الوعد، أيًا كان ما تحمله، فتُعدّ العبارة صائبة.

العبارات المتكافئة

تكون عبارتان متكافئتين حين تتطابق جداول صوابهما في كل صف. في الأداة، اختر الفصل وانفِ p: العمود الخاص بـ ¬p ∨ q مطابق للعمود الخاص بـ p → q، فالعبارتان تقولان الشيء نفسه.

وأنفع التكافؤات قانونا دي مورغان، اللذان يبيّنان كيف يمر النفي عبر الوصل والفصل:

¬(p ∧ q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p ∧ ¬q

وبالكلمات: «ليس الاثنتان معًا» هي نفسها «إحداهما على الأقل خاطئة»، و«لا هذه ولا تلك» هي نفسها «الاثنتان خاطئتان». ويستعمل المبرمجون هذين القانونين كل يوم لإعادة كتابة شرط مثل «ليس (مسجّل الدخول وموثَّق)».

المنطق والمجموعات فكرة واحدة

اقرأ p على أنها «x في A» وq على أنها «x في B». عندئذ يكون الوصل هو التقاطع، والفصل هو الاتحاد، والنفي هو المتممة، وكل جدول صواب شكل فن مظلل، ولهذا ترسم الأداة شكلًا بجانب الجدول. ويصير قانونا دي مورغان قاعدتين عن المجموعات:

(A ∩ B)′ = A′ ∪ B′

وصفحة رموز المجموعات تظلل كل واحدة من هذه على شكل تنقر عليه.

العدّ

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

قاعدة الضرب. إذا أمكن إجراء اختيار بـ m طريقة واختيار ثانٍ بـ n طريقة، فيمكن إجراء الاثنين بـ m × n طريقة. رمز PIN من 4 أرقام له 10 خيارات لكل رقم، فهناك 10^4 = 10000 رمز ممكن.

التوافيق. عدد طرق اختيار k أشياء من n، حين لا يهم الترتيب، يُكتب C(n, k). اختيار 3 إضافات من 8:

C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56

البسط يعدّ الاختيارات المرتبة، والقسمة على 3 × 2 × 1 تزيل الترتيبات الستة التي كان يمكن أن تُختار بها الإضافات الثلاث نفسها.

في نادٍ 6 أعضاء. كم زوجًا مختلفًا من الأعضاء يمكن اختياره لتنظيم فعالية؟

الإجابة 6 × 5 مقسومًا على 2، أي 15. وإن حصلت على 30، فقد عددت كل زوج مرتين، مرة بكل ترتيب.

المخططات

المخطط (ويُسمّى أيضًا البيان) مجموعة من النقاط، تُسمّى الرؤوس، تصل بينها خطوط، تُسمّى الأضلاع. وهو يمثّل أي شيء مصنوع من وصلات: الطرق بين المدن، والأصدقاء في شبكة اجتماعية، والروابط بين صفحات الويب.

نتيجة أولى: إذا صافح 5 أشخاص بعضهم بعضًا مرة واحدة، فهناك C(5, 2) = 10 مصافحات. كل شخص يصافح 4 أيدٍ، وهذا يعطي 5 × 4 = 20 طرف مصافحة، ولكل مصافحة طرفان، فـ 20 / 2 = 10. وهذه الحجة هي مبرهنة المصافحة: مجموع درجات كل الرؤوس يساوي ضعف عدد الأضلاع.

نظرية الأعداد والبرهان

الحساب المعياري حساب على وجه ساعة. 17 mod 5 يساوي 2، وهو باقي قسمة 17 على 5. وبعد تسع ساعات من الساعة 8 تكون الساعة 5، لأن 17 mod 12 يساوي 5. والفكرة نفسها، بأعداد كبيرة جدًا، هي طريقة عمل تشفير RSA الذي تقوم عليه المواقع الآمنة.

البرهان بالاستقراء يثبت أن عبارة صحيحة لكل عدد صحيح n بخطوتين: تحقق منها عند n = 1، ثم بيّن أنها إذا صحت لعدد n فإنها تصح أيضًا لـ n + 1. وبه تثبت مثلًا أن

1 + 2 + ... + n = n(n + 1) / 2

لكل n، لا للقيم التي جربتها فقط.

فيمَ تُستعمل الرياضيات المتقطعة

• البرمجة: كل جملة if منطق، وقانونا دي مورغان يعيدان كتابة الشروط.
• قواعد البيانات: الاستعلام الذي يربط الجداول أو يرشّحها عمليات على المجموعات.
• الخوارزميات: العدّ يخبرك كم خطوة يحتاج البرنامج كلما كبر المدخل.
• الشبكات والخرائط: أقصر الطرق والشبكات الاجتماعية مسائل مخططات.
• الأمن: التشفير يقوم على نظرية الأعداد والحساب المعياري.
• العتاد: المعالج مبني من بوابات منطقية، وهي جداول صواب في السيليكون.

هل الرياضيات المتقطعة صعبة؟

صعوبتها من نوع مختلف عن الجبر والتفاضل والتكامل. فيها صيغ قليلة تُحفظ والحساب فيها بسيط، لكن أسئلة كثيرة تطلب منك أن تبرهن شيئًا بدل أن تحسبه، وكتابة حجة مقنعة مهارة جديدة لمعظم الطلاب.

وأكثر ما يساعد هو حل حالات صغيرة يدويًا قبل البحث عن النمط: ارسم شكل فن، واكتب جدول الصواب، واسرد كل حالة. والرموز تبدو ثقيلة في البداية، لكن معظمها هو الرموز التي في هذه الصفحة وفي صفحة رموز المجموعات.