خلاصة الفصل

\في أبسط المستويات، قد تجمع عبارة ما بين عبارات أبسط منها باستخدام الروابط المنطقية (logical connectives). وكثيرًا ما نستعين بمتغيرات ونُكمِّم على تلك المتغيرات. إن تحديد ما إذا كانت عبارة ما صادقة أم كاذبة، بالاعتماد على هذه الروابط المنطقية وعلى المكمِّمات، هو كلّ ما تتناوله المنطقيات. ومن ثمّ يمكننا أن نقرّر ما إذا كانت عبارتان متكافئتان منطقيًا، أو ما إذا كانت عبارة أو أكثر تستلزم (منطقيًا) عبارة أخرى.

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

وثمّة سبب آخر يجعل فهم المنطق نافعًا. ففهم البنية المنطقية لعبارة ما يوحي عادةً بكيفية كتابة برهان لتلك العبارة.

وهذا لا يعني أنّ كتابة البراهين أمر مباشر دائمًا. لنعد إذًا إلى حدس غولدباخ (Goldbach conjecture):

كلّ عدد زوجي أكبر من 2 يمكن كتابته على صورة مجموع عددين أوّليين.

لن نحاول إثبات هذه العبارة هنا، لكن يمكننا على الأقلّ أن نصف كيف قد يبدو البرهان، انطلاقًا من الصيغة المنطقية للعبارة. ولعلّه يكون من الأفضل أن نكتب العبارة بحيث تُبرز المكمِّمات والروابط المنطقية:

لكلّ الأعداد الصحيحة $n\text{,}$ إذا كان $n$ زوجيًا أكبر من 2، فإنّ هناك عددين صحيحين $p$ و $q$ بحيث يكون $p$ و $q$ أوّليين، و $n = p+q\text{.}$

فكيف يبدو البرهان المباشر؟ وبما أنّ العبارة تبدأ بمكمِّم كليّ، فإنّنا سنبدأ فتقول: «لتكن $n$ عددًا صحيحًا اعتباطيًّا». أمّا بقية العبارة فتتعلّق بتضمين (implication). وفي البرهان المباشر نفترض جزء «إذا»، أي أنّ السطر التالي سيكون: «افترض أنّ $n$ أكبر من 2 وأنّه زوجي». ولا أعرف ما يأتي بعد ذلك، لكنّنا سنحتاج في النهاية إلى إيجاد عددين أوّليين $p$ و $q$ (بحسب $n$ ) وشرح سبب معرفتنا بأنّ $n = p+q\text{.}$

أو ربما نجرّب البرهان بالتناقض (proof by contradiction). وللعمل على ذلك، نفترض أوّلًا نفي (negation) العبارة التي نرغب في إثباتها. فما هو هذا النفي؟ ومن خلال ما درسناه، ينبغي أن نتمكّن من تمييزه، وهو:

هناك عدد صحيح $n$ بحيث يكون $n$ زوجيًا أكبر من $2\text{,}$ ولكن لكلّ الأعداد الصحيحة $p$ و $q\text{,}$ إمّا أن يكون $p$ أو $q$ غير أوّلي، أو أن يكون $n \ne p+q\text{.}$

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

تمارين: مراجعة الفصل

1.

أكمل جدول الحقيقة (truth table) للعبارة $\neg P \imp (Q \wedge R)\text{.}$

2.

لنفترض أنّك تعرف أنّ العبارة «إذا لم يكن بيتر طويل القامة، فإنّ كوينسي ممتلئBody وروبرت نحيف» خاطئة. فما الذي، إن وُجد، يمكنك استنتاجه عن بيتر وروبرت إذا كنت تعرف أنّ كوينسي ممتلئBody بالفعل؟ اشرح (يمكنك أن تشير إلى السؤال 1.6.1).

3.

هل العبارتان $P \imp (Q \vee R)$ و $(P \imp Q) \vee (P \imp R)$ متكافئتان منطقيًا؟ اشرح إجابتك.

4.

هل قاعدة الاستدلال (deduction rule) التالية قاعدة صحيحة؟ اشرح.

	$P \imp Q$
	$P\imp R$
$\therefore$	$P \imp (Q \wedge R)\text{.}$

5.

اكتب النفي والعكس (converse) وعكس المقدم (contrapositive) لكلٍّ من العبارات التالية.

إذا انقطعت الكهرباء، فإنّ الطعام سيُفسد.
إذا كان الباب مغلقًا، فإنّ الضوء مُطفأ.
$\forall x (x \lt 1 \imp x^2 \lt 1)\text{.}$
لكلّ الأعداد الطبيعية $n\text{,}$ إذا كان $n$ أوّليًا، فإنّ $n$ وحيد (solitary).
لكلّ الدوالّ $f\text{,}$ إذا كانت $f$ قابلة للاشتقاق، فإنّ $f$ متّصلة.
لكلّ الأعداد الصحيحة $a$ و $b\text{,}$ إذا كان $a\cdot b$ زوجيًا، فإنّ $a$ و $b$ زوجيّان.
لكلّ عدد صحيح $x$ ولكلّ عدد صحيح $y\text{,}$ يوجد عدد صحيح $n$ بحيث إن كان $x > 0$ فإنّ $nx > y\text{.}$
لكلّ الأعداد الحقيقية $x$ و $y\text{,}$ إذا كان $xy = 0$ فإنّ $x = 0$ أو $y = 0\text{.}$
لكلّ طالب في مقياس «Math 228»، فإنّ لم يفهم التضمينات فإنّه سيرسب في الامتحان.

6.

تأمّل العبارة: «لكلّ الأعداد الصحيحة $n\text{,}$ إذا كان $n$ زوجيًا و $n \le 7\text{,}$ فإنّ $n$ سالب أو $n \in \{0,2,4,6\}\text{.}$ »

هل العبارة صادقة؟ اشرح السبب.
اكتب نفي العبارة. هل هو صادق؟ اشرح.
اذكر عكس المقدم للعبارة. هل هو صادق؟ اشرح.
اذكر عكس العبارة. هل هو صادق؟ اشرح.

7.

تأمّل العبارة: $\forall x (\forall y (x + y = y) \imp \forall z (x\cdot z = 0))\text{.}$

اشرح ما تقوله العبارة بالكلمات. هل هذه العبارة صادقة؟ واحرص على بيان ما تختاره ليكون مجال الخطاب (universe of discourse).
اكتب عكس العبارة، بالكلمات وبالرموز. هل العكس صادق؟
اكتب عكس المقدم للعبارة، بالكلمات وبالرموز. هل عكس المقدم صادق؟
اكتب نفي العبارة، بالكلمات وبالرموز. هل النفي صادق؟

8.

بسّط كلًّا ممّا يأتي.

$\neg (\neg (P \wedge \neg Q) \imp \neg(\neg R \vee \neg(P \imp R)))\text{.}$
$\neg \exists x \neg \forall y \neg \exists z (z = x + y \imp \exists w (x - y = w))\text{.}$

9.

تأمّل العبارة: «لكلّ الأعداد الصحيحة $n\text{,}$ إذا كان $n$ فرديًّا، فإنّ $7n$ فرديّ.»

اثبت العبارة. أيّ نوع من البراهين تستخدم؟
اثبت العكس. أيّ نوع من البراهين تستخدم؟

10.

لنفترض أنّك كسرت وعاء مدخراتك وأمسكت بحفنة من 22 عملة (من فئات السنت (pennies)، والخمسة (nickels)، والعشرة (dimes)، والربع (quarters)).

اثبت أنّ لديك ستّ عملات على الأقلّ من فئة واحدة.
لنفترض أنّ عدد السنتات التي لديك فردي. اثبت أنّ لديك عددًا فرديًّا من إحدى فئات العملات الأخرى على الأقلّ.
كم عملة تحتاج أن تمسكها لتتأكّد من أنّك تملك إمّا 4 عملات من فئة واحدة، أو 4 عملات من فئات مختلفة كلّها؟ اثبت إجابتك.

11.

تصادف أربعة أغوال (trolls) يلعبون البريج، فيعلنون:

الغول 1: كلّ الأغوال هنا يرى نذّالًا واحدًا على الأقلّ. الغول 2: أرى غولًا واحدًا على الأقلّ يرى نذّالين فحسب. الغول 3: بعض الأغوال يخافون المعز. الغول 4: كلّ الأغوال يخافون المعز.

هل هناك أغوال لا تخاف من المعز؟ وتذكّر، بالطبع، أنّ كلّ الأغوال إمّا فرسان (knights) يُفصحون دائمًا عن الحقيقة، أو نذّالون (knaves) يكذبون دائمًا.

السابق البراهين حول البنى المنفصلة التالي نظرية الرسوم البيانية