- 1البطاقات الأربعماذا يطلب الاستلزام فعلًا؟
- 2مختبر الداراتبوابات «و» و«أو» و«لا» تملأ جدول الحقيقة
- 3جزيرة الفرسان والمحتالينتحدٍّ بستّة مستويات، والحاسوب يجرّب كل الاحتمالات
- 4مبارزة المكمّمات«لكل… يوجد» ليست «يوجد… لكل»
- 5صيّاد الأمثلة المضادّةنمطٌ يصمد أربعين مرّة ثم ينهار
- 6برج هانويالاستدلال بالتراجع في يدك
البطاقات الأربع
لكل بطاقة وجهان. ترى وجهًا واحدًا فقط، وأمامك قاعدة. اختر البطاقات التي يجب قلبها، ولا شيء غيرها، لتعرف هل القاعدة محترمة. هذا اختبارٌ وضعه عالم النفس بيتر واسون سنة 1966، وما زال يُربك أغلب من يجيب عنه.
- جرّب الصيغة المجرّدة أوّلًا ثم صيغة الفواتير. أيّهما بدت لك أسهل؟ وهل الجواب مختلف منطقيًّا؟
الجواب
البنية واحدة تمامًا: بطاقة المقدّمة الصحيحة (E، أو فاتورة تتجاوز العتبة) وبطاقة التالي الخاطئ (7، أو فاتورة غير موقَّعة). لكنّ أغلب الناس يجدون صيغة الفواتير أسهل، لأنهم يبحثون فيها تلقائيًّا عن «المخالف». والمنطق يطلب هذا البحث نفسه في الصيغة المجرّدة.
- لماذا لا تهمّ البطاقة K؟
الجواب
K ليس حرفًا صوتيًّا، فمقدّمة الاستلزام خاطئة عنده. والاستلزام الذي مقدّمته خاطئة صحيح مهما كان الوجه الآخر. فلا يمكن لهذه البطاقة أن تُسقط القاعدة.
الاستلزام \(P \Rightarrow Q\) لا يكون خاطئًا إلا في حالة واحدة: \(P\) صحيحة و\(Q\) خاطئة. فلاختبار قاعدة نبحث عن هذه الحالة وحدها، في البطاقات التي تُظهر \(P\) وفي التي تُظهر نفي \(Q\).
| \(P\) | \(Q\) | \(P \Rightarrow Q\) | البطاقة التي تمثّل الحالة |
|---|---|---|---|
| 1 | 1 | 1 | E وراءها زوجي |
| 1 | 0 | 0 | E وراءها فردي: المخالف |
| 0 | 1 | 1 | K وراءها زوجي |
| 0 | 0 | 1 | K وراءها فردي |
وقلبُ البطاقة 7 هو اختبار العكس النقيض \(\neg Q \Rightarrow \neg P\): إذا لم يكن العدد زوجيًّا فيجب ألّا يكون الحرف صوتيًّا. والقضيّتان متكافئتان.
مختبر الدارات
كل حاسوب مبنيّ من بوابات صغيرة: «و» و«أو» و«لا». على اليمين ثلاثة مفاتيح \(P\) و\(Q\) و\(R\)، وعلى اليسار مصباح. انقر المفاتيح لتغيير قيمها، وانقر البوابات لتبديل نوعها، وانقر الدوائر الصغيرة لتشغيل النفي. الجدول يمتلئ وحده: سطرٌ لكل إعداد للمفاتيح.
- أنجز مهمّة الاستلزام. ما الصيغة التي حصلت عليها؟
الجواب
\(\neg P \vee Q\): بوابة «أو» مع نفي \(P\)، والبوابة الثانية على «تمرير». فالاستلزام \(P \Rightarrow Q\) يكافئ \(\neg P \vee Q\)، والجدولان متطابقان سطرًا سطرًا.
- أنجز مهمّة «ينطفئ فقط عندما يكون \(P\) و\(Q\) صحيحين معًا» بالشرط المفروض. ماذا تستنتج؟
الجواب
الحلّ \(\neg P \vee \neg Q\). وهذه الدارة تعطي جدول \(\neg(P \wedge Q)\) نفسه: هذا قانون دي مورغان. وبالمثل \(\neg(P \vee Q)\) تكافئ \(\neg P \wedge \neg Q\).
- اختر المهمّة الأخيرة (التكافؤ). هل وجدت حلًّا؟ اضغط «كم دارة تنجز هذه المهمّة؟».
الجواب
الحاسوب يجرّب الإعدادات الـ\(192\) كلّها فلا يجد حلًّا واحدًا. التكافؤ \(P \Leftrightarrow Q\) يحتاج أن تُستعمل \(P\) و\(Q\) مرّتين، مثل \((P \wedge Q) \vee (\neg P \wedge \neg Q)\)، وهذه الدارة لا تقرأ كل مفتاح إلا مرّة. والبحث الشامل هنا برهانٌ على الاستحالة، لأن عدد الحالات منتهٍ.
جزيرة الفرسان والمحتالين
على جزيرة نوعان من السكّان: الفارس لا يقول إلا قضيّة صحيحة، والمحتال لا يقول إلا قضيّة خاطئة. تلتقي ببعضهم فيقولون جملًا. انقر على كل ساكن لتعيين نوعه، ثم تحقّق. القاعدة الذهبية: عبارة كل ساكن صحيحة إذا وفقط إذا كان فارسًا.
كل لغز هنا جدول حقيقة صغير. لكل توزيع ممكن للأنواع (\(2^{n}\) توزيعًا لـ \(n\) ساكنًا) نقوّم العبارات، ونُبقي التوزيعات التي يتطابق فيها صدق كل عبارة مع نوع صاحبها. هذا ما يفعله الحاسوب. وأنت تفعل الشيء نفسه بذكاء أكبر: «لو كان أنيس فارسًا لـ…» هو الاستدلال بفصل الحالات، و«هذا يؤدّي إلى تناقض» هو الاستدلال بالخلف.
مبارزة المكمّمات
متجرٌ صغير، وأربعة زبائن، وأربعة منتجات. الخانة الخضراء تعني أن الزبون يشتري المنتج. انقر الخانات لتغيير الجدول، وراقب أيّ القضايا الأربع صحيحة. ثم بارز الحاسوب: أنت تدافع عن قضيّة، وهو يبحث عن ثغرة.
- غيّر الجدول حتى تصير «يوجد منتج يشتريه كل زبون» صحيحة. ماذا حدث للقضيّة الأولى؟
الجواب
صارت صحيحة حتمًا: المنتج المشترك يصلح جوابًا لكل زبون. فإذا كانت الثانية صحيحة كانت الأولى صحيحة.
- هل تستطيع جعل الثانية صحيحة والأولى خاطئة؟
الجواب
لا، مهما غيّرت. وهذا معنى «الثانية تستلزم الأولى». أمّا الأولى صحيحة والثانية خاطئة فممكن، وهو الجدول الابتدائي.
- في المبارزة، من يلعب عند «لكل» ومن يلعب عند «يوجد»؟
الجواب
عند «لكل» يختار الخصم (الحاسوب) أصعب حالة عليك، وعند «يوجد» تختار أنت. فالترتيب يحدّد من يرى اختيار الآخر قبل أن يختار: في «لكل زبون يوجد منتج» ترى الزبون ثم تختار، وفي «يوجد منتج لكل زبون» تلتزم بمنتجك قبل أن ترى أيّ زبون.
نرمز بـ \(A(z, m)\) إلى «الزبون \(z\) يشتري المنتج \(m\)». القضيّتان \(\forall z,\ \exists m,\ A(z,m)\) و\(\exists m,\ \forall z,\ A(z,m)\) تختلفان بالترتيب وحده. ونفي الأولى هو \(\exists z,\ \forall m,\ \neg A(z,m)\): زبونٌ لا يشتري أيّ شيء. النفي يقلب كل مكمّم وينفي ما بعده، والمثال المضادّ هو الشاهد على هذا النفي.
صيّاد الأمثلة المضادّة
أمامك أربعة ادّعاءات كلّية. بعضها يصمد طويلًا ثم ينهار، وبعضها لا ينهار أبدًا. اختبر قيمًا بيدك أو أطلق البحث الآلي. مثالٌ مضادّ واحد يكفي لإسقاط ادّعاء كلّي.
- في الادّعاء الأول، لماذا يسقط حتمًا عند \(n = 40\)؟
الجواب
\(40^{2} + 40 + 41 = 40 \times 41 + 41 = 41 \times 41\). وبالطريقة نفسها، القيمة عند \(n = 41\) هي \(41 \times 43\). فالادّعاء صمد للقيم من \(0\) إلى \(39\)، أي أربعين مرّة، ثم سقط.
- في ادّعاء قوى 2، اختبر \(n = 4\). لماذا لا يُعدّ مثالًا مضادًّا مع أن \(2^{4} - 1 = 15\) ليس أوّليًّا؟
الجواب
الادّعاء استلزام: «إذا كان \(n\) أوّليًّا فإن…». والعدد \(4\) ليس أوّليًّا، فالمقدّمة خاطئة والاستلزام صحيح عند \(4\). المثال المضادّ يجب أن يحقّق المقدّمة ويخالف النتيجة: \(n = 11\) أوّلي و\(2^{11} - 1 = 2047 = 23 \times 89\).
- في ادّعاء القسمة على 6، أطلق البحث الآلي. لم يجد الحاسوب مثالًا مضادًّا حتى \(300\). هل هذا برهان؟
الجواب
لا: ثلاثمئة مثال موافق لا تبرهن قضيّة على \(\mathbb{N}\) كلّها. والبرهان هنا قصير: \(n^{3} - n = (n-1)\,n\,(n+1)\) جداء ثلاثة أعداد متتالية، وفيها دائمًا عددٌ زوجي وعددٌ مضاعف لـ \(3\).
- في مناطق الدائرة، ماذا يحدث لو وُضعت النقاط الستّ على رؤوس مسدّس منتظم؟
الجواب
تلتقي الأقطار الثلاثة الكبرى في المركز، فتضيع منطقة واحدة: \(30\) منطقة. والصيغة \(\binom{n}{4} + \binom{n}{2} + 1\) تخصّ النقاط في وضع عامّ، وتعطي \(31\) عند \(n = 6\).
والآن بالحاسوب: الشيفرة التالية تبحث عن أوّل مثال مضادّ للادّعاء الأول. غيّر \(41\) إلى \(17\) ثم إلى \(11\) وراقب أين يسقط الادّعاء كل مرّة. هل ترى نمطًا؟
لدحض \(\forall n,\ P(n)\) يكفي شاهدٌ واحد على \(\exists n,\ \neg P(n)\). ولإثباتها لا تكفي أمثلة موافقة مهما كثرت: يلزم برهان. وعندما تكون القضيّة استلزامًا، يجب أن يحقّق المثال المضادّ المقدّمة ويخالف التالي.
برج هانوي
انقل البرج كلّه من العمود الأيمن إلى العمود الأيسر. القواعد: قرصٌ واحد في كل حركة، ولا يوضع قرص فوق قرص أصغر منه. انقر عمودًا لأخذ قرصه العلوي، ثم انقر العمود الذي تضعه فيه.
- شغّل الحلّ الآلي بخمسة أقراص وراقب القرص الأكبر. متى يتحرّك؟ وكم مرّة؟
الجواب
يتحرّك مرّة واحدة، في الحركة رقم \(16\) من \(31\): بالضبط في المنتصف. قبلها نُقلت الأقراص الأربعة الأخرى إلى العمود الأوسط (\(15\) حركة)، وبعدها تُنقل فوقه (\(15\) حركة أخرى).
- والقرص الأصغر، كم مرّة يتحرّك مع \(n\) أقراص؟
الجواب
\(2^{n-1}\) مرّة: يتحرّك في كل حركة فردية الرقم. مع خمسة أقراص يتحرّك \(16\) مرّة من \(31\).
لنقل \(n + 1\) قرصًا: ننقل \(n\) قرصًا إلى الوسط، ثم الأكبر إلى الهدف، ثم الـ\(n\) قرصًا فوقه. فإذا رمزنا بـ \(T_n\) إلى أقلّ عدد من الحركات، فإن \(T_{n+1} = 2T_n + 1\). ولنبرهن \(T_n = 2^{n} - 1\) بالاستدلال بالتراجع:
- الأساس: \(T_1 = 1 = 2^{1} - 1\).
- الوراثة: نفرض \(T_n = 2^{n} - 1\). عندئذٍ \(T_{n+1} = 2(2^{n} - 1) + 1 = 2^{n+1} - 1\).
الأساس يُثبت الحالة الأولى، والوراثة تنقل الصحّة من كل رتبة إلى التي تليها، فالقضيّة صحيحة من أجل كل \(n \geq 1\). (ويبقى أن نبيّن أنّ عددًا أقلّ من \(2T_n + 1\) غير ممكن: القرص الأكبر لا يتحرّك قبل أن تُنقل كل الأقراص التي فوقه إلى عمود واحد، فيلزم \(T_n\) حركة على الأقل قبل حركته و\(T_n\) بعدها.)
والآن بالحاسوب: هذه دالة تستدعي نفسها، تمامًا كما في البرهان. شغّلها لترى حركات ثلاثة أقراص، ثم عدد الحركات حتى عشرة أقراص.
اختبر حدسك
قاعدة متجر: «إذا كان الزبون يحمل بطاقة وفاء فإنه يحصل على تخفيض». حصلت سليمة على تخفيض. ماذا نستنتج؟
ما نفي القضيّة «في كل قسم يوجد طالب نال علامة كاملة»؟
ما العكس النقيض للقضيّة «إذا كان المنتج مستوردًا فإن سعره مرتفع»؟
في جزيرة الفرسان والمحتالين، يقول أنيس: «إمّا أن أكون محتالًا أو أن يكون بشير فارسًا» (بمعنى «أو» الرياضية). ما نوعاهما؟
نبرهن أن «\(3^{n}\) عدد زوجي» تستلزم «\(3^{n+1}\) عدد زوجي» من أجل كل \(n\). ماذا نستنتج؟
برج هانوي بعشرة أقراص. كم حركة على الأقل؟
للمفاهيم واحدًا واحدًا: شروحات هذا الفصل