1. Notions de logique

∑Résumé du cours

Propositions et connecteurs

Une proposition est un énoncé vrai (V) ou faux (F). Connecteurs : négation ¬P, conjonction P ∧ Q (« et »), disjonction P ∨ Q (« ou »), implication P ⇒ Q (fausse seulement si P vraie et Q fausse), équivalence P ⇔ Q.

Lois de Morgan : ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q ; ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q. Contraposée : (P ⇒ Q) ⇔ (¬Q ⇒ ¬P).

Quantificateurs

∀ « pour tout », ∃ « il existe », ∃! « il existe un unique ». Négation : ¬(∀x, P(x)) ⇔ ∃x, ¬P(x) ; ¬(∃x, P(x)) ⇔ ∀x, ¬P(x). L’ordre de ∀ et ∃ compte.

Raisonnements

• Par contraposée : pour P ⇒ Q, on montre ¬Q ⇒ ¬P.
• Par l’absurde : on suppose le contraire et on aboutit à une contradiction.
• Par disjonction des cas.
• Par contre-exemple : pour réfuter un « ∀ ».
• Par équivalences successives.
• Par récurrence.

✎Exemples corrigés

?Teste-toi

Clique sur la bonne réponse.

1. P ⇒ Q est fausse quand…

   a) P vraie et Q fausseb) P fausse et Q vraiec) P et Q fausses
   Réponse

   a) P vraie et Q fausse — C’est le seul cas.

2. ¬(P ∧ Q) ⇔ …

   a) ¬P ∧ ¬Qb) ¬P ∨ ¬Qc) P ∨ Q
   Réponse

   b) ¬P ∨ ¬Q — Loi de Morgan.

3. Pour réfuter « ∀x, P(x) », il suffit…

   a) d’un contre-exempleb) d’une récurrencec) de la contraposée
   Réponse

   a) d’un contre-exemple — Un seul x qui ne vérifie pas P suffit.

∑ملخص الدرس

العبارات والروابط

العبارة نص إما صحيح (V) أو خاطئ (F). الروابط: النفي ¬P، العطف P ∧ Q («و»)، الفصل P ∨ Q («أو»)، الاستلزام P ⇒ Q (خاطئ فقط إذا كانت P صحيحة و Q خاطئة)، التكافؤ P ⇔ Q.

قانونا موركان: ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q ؛ ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q. المضادة للعكس: (P ⇒ Q) ⇔ (¬Q ⇒ ¬P).

المكممات

∀ «لكل»، ∃ «يوجد»، ∃! «يوجد وحيد». النفي: ¬(∀x, P(x)) ⇔ ∃x, ¬P(x) ؛ ¬(∃x, P(x)) ⇔ ∀x, ¬P(x). ترتيب ∀ و ∃ مهم.

أنواع الاستدلال

• بالمضادة للعكس: لإثبات P ⇒ Q، نبيّن ¬Q ⇒ ¬P.
• بالخلف: نفترض العكس ونصل إلى تناقض.
• بفصل الحالات.
• بالمثال المضاد: لدحض «∀».
• بالتكافؤات المتتالية.
• بالترجع.

✎أمثلة محلولة

?اختبر نفسك

اضغط على الجواب الصحيح.

1. يكون P ⇒ Q خاطئًا عندما…

   أ) P صحيحة و Q خاطئةب) P خاطئة و Q صحيحةج) P و Q خاطئتان
   الجواب

   أ) P صحيحة و Q خاطئة — إنها الحالة الوحيدة.

2. ¬(P ∧ Q) ⇔ …

   أ) ¬P ∧ ¬Qب) ¬P ∨ ¬Qج) P ∨ Q
   الجواب

   ب) ¬P ∨ ¬Q — قانون موركان.

3. لدحض «∀x, P(x)» يكفي…

   أ) مثال مضادب) استدلال بالترجعج) المضادة للعكس
   الجواب

   أ) مثال مضاد — يكفي x واحد لا يحقق P.