تجارب رياضية · المنطق

لماذا يخطئ أغلب الناس في أربع بطاقات؟

جملةٌ من نوع «إذا… فإن…» تبدو بسيطة، ومع ذلك يخطئ فيها أغلب من يُسألون عنها. في هذه الصفحة ستّ تجارب: تقلب فيها بطاقات، وتبني دارات تضيء مصباحًا، وتحقّق في جزيرة لا يقول سكّانها إلا الصدق أو الكذب، وتبارز الحاسوب بالمكمّمات، وتصطاد أمثلة مضادّة، ثم تنقل برجًا قرصًا قرصًا.

6 تجارب تفاعلية تحدٍّ بستّة مستويات بايثون في المتصفّح
  1. 1البطاقات الأربعماذا يطلب الاستلزام فعلًا؟
  2. 2مختبر الداراتبوابات «و» و«أو» و«لا» تملأ جدول الحقيقة
  3. 3جزيرة الفرسان والمحتالينتحدٍّ بستّة مستويات، والحاسوب يجرّب كل الاحتمالات
  4. 4مبارزة المكمّمات«لكل… يوجد» ليست «يوجد… لكل»
  5. 5صيّاد الأمثلة المضادّةنمطٌ يصمد أربعين مرّة ثم ينهار
  6. 6برج هانويالاستدلال بالتراجع في يدك
1
التجربة الأولى

البطاقات الأربع

لكل بطاقة وجهان. ترى وجهًا واحدًا فقط، وأمامك قاعدة. اختر البطاقات التي يجب قلبها، ولا شيء غيرها، لتعرف هل القاعدة محترمة. هذا اختبارٌ وضعه عالم النفس بيتر واسون سنة 1966، وما زال يُربك أغلب من يجيب عنه.

توقّع قبل أن تحرّك
قبل أن تلمس البطاقات: هل يجب قلب البطاقة التي تحقّق الجزء الثاني من القاعدة (العدد الزوجي، أو الفاتورة الموقَّعة)؟ اكتب نعم أو لا مع سبب.
لا. القاعدة لا تقول شيئًا عمّا وراء العدد الزوجي: قد يكون وراءه حرفٌ صوتي أو غيره، ولا تسقط القاعدة في الحالتين. وهذا هو الخطأ الأكثر شيوعًا في هذا الاختبار.
جرّب بنفسك
  1. جرّب الصيغة المجرّدة أوّلًا ثم صيغة الفواتير. أيّهما بدت لك أسهل؟ وهل الجواب مختلف منطقيًّا؟
    الجواب

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

  2. لماذا لا تهمّ البطاقة K؟
    الجواب

    K ليس حرفًا صوتيًّا، فمقدّمة الاستلزام خاطئة عنده. والاستلزام الذي مقدّمته خاطئة صحيح مهما كان الوجه الآخر. فلا يمكن لهذه البطاقة أن تُسقط القاعدة.

ما الذي رأيناه؟

الاستلزام \(P \Rightarrow Q\) لا يكون خاطئًا إلا في حالة واحدة: \(P\) صحيحة و\(Q\) خاطئة. فلاختبار قاعدة نبحث عن هذه الحالة وحدها، في البطاقات التي تُظهر \(P\) وفي التي تُظهر نفي \(Q\).

\(P\)\(Q\)\(P \Rightarrow Q\)البطاقة التي تمثّل الحالة
111E وراءها زوجي
100E وراءها فردي: المخالف
011K وراءها زوجي
001K وراءها فردي

وقلبُ البطاقة 7 هو اختبار العكس النقيض \(\neg Q \Rightarrow \neg P\): إذا لم يكن العدد زوجيًّا فيجب ألّا يكون الحرف صوتيًّا. والقضيّتان متكافئتان.

2
التجربة الثانية

مختبر الدارات

كل حاسوب مبنيّ من بوابات صغيرة: «و» و«أو» و«لا». على اليمين ثلاثة مفاتيح \(P\) و\(Q\) و\(R\)، وعلى اليسار مصباح. انقر المفاتيح لتغيير قيمها، وانقر البوابات لتبديل نوعها، وانقر الدوائر الصغيرة لتشغيل النفي. الجدول يمتلئ وحده: سطرٌ لكل إعداد للمفاتيح.

جرّب بنفسك
  1. أنجز مهمّة الاستلزام. ما الصيغة التي حصلت عليها؟
    الجواب

    \(\neg P \vee Q\): بوابة «أو» مع نفي \(P\)، والبوابة الثانية على «تمرير». فالاستلزام \(P \Rightarrow Q\) يكافئ \(\neg P \vee Q\)، والجدولان متطابقان سطرًا سطرًا.

  2. أنجز مهمّة «ينطفئ فقط عندما يكون \(P\) و\(Q\) صحيحين معًا» بالشرط المفروض. ماذا تستنتج؟
    الجواب

    الحلّ \(\neg P \vee \neg Q\). وهذه الدارة تعطي جدول \(\neg(P \wedge Q)\) نفسه: هذا قانون دي مورغان. وبالمثل \(\neg(P \vee Q)\) تكافئ \(\neg P \wedge \neg Q\).

  3. اختر المهمّة الأخيرة (التكافؤ). هل وجدت حلًّا؟ اضغط «كم دارة تنجز هذه المهمّة؟».
    الجواب

    الحاسوب يجرّب الإعدادات الـ\(192\) كلّها فلا يجد حلًّا واحدًا. التكافؤ \(P \Leftrightarrow Q\) يحتاج أن تُستعمل \(P\) و\(Q\) مرّتين، مثل \((P \wedge Q) \vee (\neg P \wedge \neg Q)\)، وهذه الدارة لا تقرأ كل مفتاح إلا مرّة. والبحث الشامل هنا برهانٌ على الاستحالة، لأن عدد الحالات منتهٍ.

تحقّق من فهمك
كم سطرًا في جدول حقيقة قضيّة فيها أربع قضايا بسيطة؟ وكم دالة منطقية مختلفة يمكن بناؤها من قضيّتين فقط؟
أربع قضايا تعطي \(2^{4} = 16\) سطرًا. ولقضيّتين أربعة أسطر، وفي كل سطر قيمتان ممكنتان للنتيجة، فعدد الجداول الممكنة \(2^{4} = 16\) دالة منطقية، منها «و» و«أو» والاستلزام والتكافؤ.
3
التجربة الثالثة

جزيرة الفرسان والمحتالين

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

النجوم: ثلاث إن أصبت من المحاولة الأولى، واثنتان من الثانية، وواحدة بعدها أو إن استعنت بالحاسوب.
ما الذي رأيناه؟

كل لغز هنا جدول حقيقة صغير. لكل توزيع ممكن للأنواع (\(2^{n}\) توزيعًا لـ \(n\) ساكنًا) نقوّم العبارات، ونُبقي التوزيعات التي يتطابق فيها صدق كل عبارة مع نوع صاحبها. هذا ما يفعله الحاسوب. وأنت تفعل الشيء نفسه بذكاء أكبر: «لو كان أنيس فارسًا لـ…» هو الاستدلال بفصل الحالات، و«هذا يؤدّي إلى تناقض» هو الاستدلال بالخلف.

تحقّق من فهمك
ساكنٌ يقول: «أنا محتال». ما نوعه؟
لا يمكن لأيّ ساكن أن يقولها. لو كان فارسًا لكانت عبارته صحيحة، فهو محتال: تناقض. ولو كان محتالًا لكانت عبارته خاطئة، فهو فارس: تناقض. فهذه الجملة لا تصدر عن أحد في الجزيرة.
4
التجربة الرابعة

مبارزة المكمّمات

متجرٌ صغير، وأربعة زبائن، وأربعة منتجات. الخانة الخضراء تعني أن الزبون يشتري المنتج. انقر الخانات لتغيير الجدول، وراقب أيّ القضايا الأربع صحيحة. ثم بارز الحاسوب: أنت تدافع عن قضيّة، وهو يبحث عن ثغرة.

توقّع قبل أن تحرّك
«كل زبون يوجد منتج يشتريه» و«يوجد منتج يشتريه كل زبون». هل للجملتين المعنى نفسه؟ إن لم يكن، فأيّهما تستلزم الأخرى؟
لا. الأولى تسمح لكل زبون بمنتجه الخاصّ، والثانية تطلب منتجًا واحدًا مشتركًا بين الجميع. الثانية تستلزم الأولى، والعكس خاطئ: الجدول الابتدائي مثالٌ مضادّ.
جرّب بنفسك
  1. غيّر الجدول حتى تصير «يوجد منتج يشتريه كل زبون» صحيحة. ماذا حدث للقضيّة الأولى؟
    الجواب

    صارت صحيحة حتمًا: المنتج المشترك يصلح جوابًا لكل زبون. فإذا كانت الثانية صحيحة كانت الأولى صحيحة.

  2. هل تستطيع جعل الثانية صحيحة والأولى خاطئة؟
    الجواب

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

  3. في المبارزة، من يلعب عند «لكل» ومن يلعب عند «يوجد»؟
    الجواب

    عند «لكل» يختار الخصم (الحاسوب) أصعب حالة عليك، وعند «يوجد» تختار أنت. فالترتيب يحدّد من يرى اختيار الآخر قبل أن يختار: في «لكل زبون يوجد منتج» ترى الزبون ثم تختار، وفي «يوجد منتج لكل زبون» تلتزم بمنتجك قبل أن ترى أيّ زبون.

ما الذي رأيناه؟

نرمز بـ \(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)\): زبونٌ لا يشتري أيّ شيء. النفي يقلب كل مكمّم وينفي ما بعده، والمثال المضادّ هو الشاهد على هذا النفي.

5
التجربة الخامسة

صيّاد الأمثلة المضادّة

أمامك أربعة ادّعاءات كلّية. بعضها يصمد طويلًا ثم ينهار، وبعضها لا ينهار أبدًا. اختبر قيمًا بيدك أو أطلق البحث الآلي. مثالٌ مضادّ واحد يكفي لإسقاط ادّعاء كلّي.

توقّع قبل أن تحرّك
ضع نقاطًا على دائرة وصِل كل نقطتين بوتر. بنقطة واحدة منطقة واحدة، وبنقطتين منطقتان، ثم 4 ثم 8 ثم 16. كم منطقة بستّ نقاط؟
31 لا 32. النمط «يتضاعف في كل مرّة» صمد خمس مرّات ثم سقط. العدد الصحيح للنقاط في وضع عامّ (لا تلتقي ثلاثة أوتار في نقطة واحدة) يُحسب بصيغة أخرى تمامًا. اختر الادّعاء الرابع وتحقّق.
جرّب بنفسك
  1. في الادّعاء الأول، لماذا يسقط حتمًا عند \(n = 40\)؟
    الجواب

    \(40^{2} + 40 + 41 = 40 \times 41 + 41 = 41 \times 41\). وبالطريقة نفسها، القيمة عند \(n = 41\) هي \(41 \times 43\). فالادّعاء صمد للقيم من \(0\) إلى \(39\)، أي أربعين مرّة، ثم سقط.

  2. في ادّعاء قوى 2، اختبر \(n = 4\). لماذا لا يُعدّ مثالًا مضادًّا مع أن \(2^{4} - 1 = 15\) ليس أوّليًّا؟
    الجواب

    الادّعاء استلزام: «إذا كان \(n\) أوّليًّا فإن…». والعدد \(4\) ليس أوّليًّا، فالمقدّمة خاطئة والاستلزام صحيح عند \(4\). المثال المضادّ يجب أن يحقّق المقدّمة ويخالف النتيجة: \(n = 11\) أوّلي و\(2^{11} - 1 = 2047 = 23 \times 89\).

  3. في ادّعاء القسمة على 6، أطلق البحث الآلي. لم يجد الحاسوب مثالًا مضادًّا حتى \(300\). هل هذا برهان؟
    الجواب

    لا: ثلاثمئة مثال موافق لا تبرهن قضيّة على \(\mathbb{N}\) كلّها. والبرهان هنا قصير: \(n^{3} - n = (n-1)\,n\,(n+1)\) جداء ثلاثة أعداد متتالية، وفيها دائمًا عددٌ زوجي وعددٌ مضاعف لـ \(3\).

  4. في مناطق الدائرة، ماذا يحدث لو وُضعت النقاط الستّ على رؤوس مسدّس منتظم؟
    الجواب

    تلتقي الأقطار الثلاثة الكبرى في المركز، فتضيع منطقة واحدة: \(30\) منطقة. والصيغة \(\binom{n}{4} + \binom{n}{2} + 1\) تخصّ النقاط في وضع عامّ، وتعطي \(31\) عند \(n = 6\).

والآن بالحاسوب: الشيفرة التالية تبحث عن أوّل مثال مضادّ للادّعاء الأول. غيّر \(41\) إلى \(17\) ثم إلى \(11\) وراقب أين يسقط الادّعاء كل مرّة. هل ترى نمطًا؟

ما الذي رأيناه؟

لدحض \(\forall n,\ P(n)\) يكفي شاهدٌ واحد على \(\exists n,\ \neg P(n)\). ولإثباتها لا تكفي أمثلة موافقة مهما كثرت: يلزم برهان. وعندما تكون القضيّة استلزامًا، يجب أن يحقّق المثال المضادّ المقدّمة ويخالف التالي.

6
التجربة السادسة

برج هانوي

انقل البرج كلّه من العمود الأيمن إلى العمود الأيسر. القواعد: قرصٌ واحد في كل حركة، ولا يوضع قرص فوق قرص أصغر منه. انقر عمودًا لأخذ قرصه العلوي، ثم انقر العمود الذي تضعه فيه.

توقّع قبل أن تحرّك
كم حركة على الأقل لنقل 3 أقراص؟ و4 أقراص؟ وتقول أسطورة إن رهبانًا ينقلون 64 قرصًا بحركة كل ثانية، وإن العالم ينتهي عندما يفرغون. كم يلزمهم؟
7 حركات لثلاثة أقراص، و15 لأربعة. وعمومًا \(2^{n} - 1\). ولـ 64 قرصًا: \(2^{64} - 1 \approx 1{,}8 \times 10^{19}\) ثانية، أي نحو 585 مليار سنة. عمر الكون نحو 14 مليار سنة فقط.
جرّب بنفسك
  1. شغّل الحلّ الآلي بخمسة أقراص وراقب القرص الأكبر. متى يتحرّك؟ وكم مرّة؟
    الجواب

    يتحرّك مرّة واحدة، في الحركة رقم \(16\) من \(31\): بالضبط في المنتصف. قبلها نُقلت الأقراص الأربعة الأخرى إلى العمود الأوسط (\(15\) حركة)، وبعدها تُنقل فوقه (\(15\) حركة أخرى).

  2. والقرص الأصغر، كم مرّة يتحرّك مع \(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\) بعدها.)

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

تحقّق من فهمك
«برهانٌ» مشهور: «كل الخيول من لون واحد. الأساس: حصانٌ واحد له لون واحد. الوراثة: في مجموعة من \(n + 1\) حصانًا، نُخرج حصانًا فيبقى \(n\) من لون واحد، ونُخرج آخر فيبقى \(n\) من لون واحد، والمجموعتان تتقاطعان، فالكلّ من لون واحد.» أين الخطأ؟
الوراثة لا تصحّ من \(n = 1\) إلى \(n = 2\). مع حصانين، المجموعتان بعد الإخراج هما \(\{A\}\) و\(\{B\}\)، ولا تتقاطعان. فالسلسلة تنقطع عند أوّل حلقة. يجب أن تصحّ الوراثة من أجل كل \(n\) ابتداءً من الأساس.

اختبر حدسك

قاعدة متجر: «إذا كان الزبون يحمل بطاقة وفاء فإنه يحصل على تخفيض». حصلت سليمة على تخفيض. ماذا نستنتج؟

التالي \(Q\) صحيح، والاستلزام \(P \Rightarrow Q\) صحيح سواء أكانت \(P\) صحيحة أم خاطئة (سطران من الجدول). فقد يكون التخفيض بسبب عرض موسمي. استنتاج «تحمل بطاقة» خلطٌ بين الاستلزام وعكسه، وهو خطأ البطاقة 4 نفسه. ولا شيء هنا يخالف القاعدة.

ما نفي القضيّة «في كل قسم يوجد طالب نال علامة كاملة»؟

القضيّة \(\forall c,\ \exists t,\ K(c,t)\)، ونفيها \(\exists c,\ \forall t,\ \neg K(c,t)\). الخيار الأول أقوى من النفي (يطلب ذلك في كل الأقسام). والثالث نفي «كل طالب نال علامة كاملة» لا نفي القضيّة. والرابع يتعلّق بكل الأقسام معًا.

ما العكس النقيض للقضيّة «إذا كان المنتج مستوردًا فإن سعره مرتفع»؟

العكس النقيض لـ \(P \Rightarrow Q\) هو \(\neg Q \Rightarrow \neg P\)، وهو مكافئ لها. الخيار الأول هو العكس \(Q \Rightarrow P\)، والثاني \(\neg P \Rightarrow \neg Q\)، وكلاهما غير مكافئ للقضيّة. والرابع هو نفيها \(P \wedge \neg Q\).

في جزيرة الفرسان والمحتالين، يقول أنيس: «إمّا أن أكون محتالًا أو أن يكون بشير فارسًا» (بمعنى «أو» الرياضية). ما نوعاهما؟

لو كان أنيس محتالًا لكانت عبارته صحيحة (جزؤها الأول صحيح)، والمحتال لا يقول قضيّة صحيحة: تناقض. فأنيس فارس، وعبارته صحيحة، وجزؤها الأول خاطئ، فالجزء الثاني صحيح: بشير فارس. وهي عبارة المستوى 3 نفسها، لأن \(\neg P \vee Q\) يكافئ \(P \Rightarrow Q\).

نبرهن أن «\(3^{n}\) عدد زوجي» تستلزم «\(3^{n+1}\) عدد زوجي» من أجل كل \(n\). ماذا نستنتج؟

الوراثة صحيحة فعلًا (\(3^{n+1} = 3 \times 3^{n}\)، وجداء عدد زوجي في عدد صحيح زوجي). لكن \(3^{0} = 1\) فردي، ولا توجد رتبة يصحّ عندها الأساس: \(3^{n}\) فردي دائمًا. فالوراثة وحدها لا تبرهن شيئًا.

برج هانوي بعشرة أقراص. كم حركة على الأقل؟

\(T_{10} = 2^{10} - 1 = 1023\). النموّ مضاعَف لا خطّي، فالجواب \(20\) (حركتان لكل قرص) بعيد جدًّا، و\(100\) تخمين مربّع. و\(512 = 2^{9}\) هو عدد حركات القرص الأصغر وحده.

للمفاهيم واحدًا واحدًا: شروحات هذا الفصل