Déduction logique

Objectifs

• Connaître les tables de vérité des connecteurs logiques (et, ou, non, implication, équivalence)
• Utiliser les connecteurs logiques pour exprimer des propositions
• Différencier les connecteurs logiques "si" et "seulement si"
• Utiliser les règles d'inférence pour déduire des propositions
  • Modus ponens
  • Modus tollens
  • Syllogisme hypothétique
  • Syllogisme disjonctif

Cours

Déduction logique

Enjeux de société

Proposition P

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Proposition P

  • Notation : P

  • Phrase : J'aime le chocolat.

	Q est faux	Q est vrai
P est faux	Faux	Faux
P est vrai	Vrai	Vrai

https://commons.wikimedia.org/wiki/File:Venn0101.svg

Proposition Q

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Proposition Q

  • Notation : Q

  • Phrase : J'aime la vanille.

	Q est faux	Q est vrai
P est faux	Faux	Vrai
P est vrai	Faux	Vrai

https://commons.wikimedia.org/wiki/File:Venn0011.svg

Negation de P

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Negation de P

  • Notation : ¬P

  • Phrase : Je n'aime pas le chocolat.

	Q est faux	Q est vrai
P est faux	Vrai	Vrai
P est vrai	Faux	Faux

https://commons.wikimedia.org/wiki/File:Venn1010.svg

Negation de Q

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Negation de Q

  • Notation : ¬Q

  • Phrase : Je n'aime pas la vanille.

	Q est faux	Q est vrai
P est faux	Vrai	Faux
P est vrai	Vrai	Faux

https://commons.wikimedia.org/wiki/File:Venn1100.svg

Disjonction (P ou Q)

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Disjonction (P ou Q)

  • Notation : P ∨ Q

  • Phrase : J'aime le chocolat ou la vanille.

	Q est faux	Q est vrai
P est faux	Faux	Vrai
P est vrai	Vrai	Vrai

https://commons.wikimedia.org/wiki/File:Venn0111.svg

Conjonction (P et Q)

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Conjonction (P et Q)

  • Notation : P ∧ Q

  • Phrase : J'aime le chocolat et la vanille.

	Q est faux	Q est vrai
P est faux	Faux	Faux
P est vrai	Faux	Vrai

https://commons.wikimedia.org/wiki/File:Venn0001.svg

Contradiction (P et non P)

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Contradiction (P et non P)

  • Notation : P ∧ ¬P

  • Phrase : J'aime et je n'aime pas le chocolat.

	Q est faux	Q est vrai
P est faux	Faux	Faux
P est vrai	Faux	Faux

https://commons.wikimedia.org/wiki/File:Venn0000.svg

Tautologie (P ou non P)

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Tautologie (P ou non P)

  • Notation : P ∨ ¬P

  • Phrase : J'aime ou je n'aime pas le chocolat.

	Q est faux	Q est vrai
P est faux	Vrai	Vrai
P est vrai	Vrai	Vrai

https://commons.wikimedia.org/wiki/File:Venn1111.svg

Implication (P seulement si Q)

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Implication (P seulement si Q)

  • Notation : P → Q

  • Phrase : J'aime le chocolat seulement si j'aime la vanille.

	Q est faux	Q est vrai
P est faux	Vrai	Vrai
P est vrai	Faux	Vrai

https://commons.wikimedia.org/wiki/File:Venn1011.svg

Implication réciproque (P si Q)

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Implication réciproque (P si Q)

  • Notation : P ← Q

  • Phrase : J'aime le chocolat si j'aime la vanille.

	Q est faux	Q est vrai
P est faux	Vrai	Faux
P est vrai	Vrai	Vrai

https://commons.wikimedia.org/wiki/File:Venn1101.svg

Équivalence (P si et seulement si Q)

• Soit

  • P = J'aime le chocolat.

  • Q = J'aime la vanille.

• Évaluation

  • Nom : Équivalence (P si et seulement si Q)

  • Notation : P ↔ Q

  • Phrase : J'aime le chocolat si et seulement si j'aime la vanille.

	Q est faux	Q est vrai
P est faux	Vrai	Faux
P est vrai	Faux	Vrai

https://commons.wikimedia.org/wiki/File:Venn1001.svg

Implication

• Si il pleut, alors je prends un parapluie.

  • P : Il pleut.

  • Q : Je prends un parapluie.

  • P → Q est vrai si j'ai dit la vérité.

• Si P est vrai, alors Q est vrai.

• Si P est faux, alors Q peut être vrai ou faux.

  • Si je suis élu·e, alors je rendrai les transports publics gratuits.

  • Dit la vérité tant qu'iel n'est pas élu·e.

Équivalence

• Implication dans un sens.

  • Il fait beau si je vais me promener. (beau ← promenade)

  • Il fait beau seulement si je vais me promener. (beau → promenade)

• Implication dans les deux sens.

  • Il fait beau si et seulement si je vais me promener. (beau ↔ promenade)

• P ↔ Q est vrai si P et Q sont tous deux vrais ou faux.

Exercice

Les propositions suivantes sont-elles vraies ?

• Si les poules ont des dents, alors les vaches volent.

  • Vrai, car la condition est fausse.

• Si les poules pondent des œufs, alors les vaches volent.

  • Faux, car la conclusion est fausse.

• Soit les licornes existent, soit les dragons existent.

  • Vrai, car l'un des deux est vrai.

Equivalence d'implications

• P → Q est équivalent à non P, ou Q.

  • Si je suis élu·e, alors je rendrai les transports publics gratuits.

  • Je ne suis pas élu·e ou je rendrai les transports publics gratuits.

• P → Q est équivalent à non Q → non P.

  • Si je ne rends pas les transports publics gratuits, alors je ne suis pas élu·e.

Exercice

Les propositions suivantes sont-elles équivalentes ?

• Si j'écoute de la musique, alors je chante.
  J'écoute de la musique si je chante.

  • Non, car musique → chant ≠ musique ← chant.

• Si j'écoute de la musique, alors je chante.
  Je ne chante pas si je n'écoute pas de musique.

  • Oui, car musique → chant ≡ non chant → non musique.

• Si j'écoute de la musique, alors je chante.
  Je n'écoute pas de musique ou je chante.

  • Oui, car musique → chant ≡ non musique ∨ chant.

• Si j'écoute de la musique, alors je chante.
  Je ne chante pas ou j'écoute de la musique.

  • Non, car musique → chant ≠ non chant ∨ musique.

F pour passer en plein écran ou O pour afficher la vue d'ensemble.
Versions sans animation, plein écran, imprimable.

Exercices

Notation

Que signifient les notations suivantes ?

1. P ∧ Q
2. P ∨ Q
3. ¬P
4. P → Q
5. P ↔ Q

Solution

1. P ∧ Q : P et Q
2. P ∨ Q : P ou Q
3. ¬P : non P
4. P → Q : si P alors Q
5. P ↔ Q : P si et seulement si Q

1. ¬P ∨ Q
2. P ∧ (Q ∨ R)
3. (P → Q) ∧ (Q → R)
4. (P ↔ Q) ∨ R

Solution

1. non P ou Q
2. P et (Q ou R)
3. (si P alors Q) et (si Q alors R)
4. (P si et seulement si Q) ou R

Table de vérité

Compléter la table de vérité suivante (0 pour faux, 1 pour vrai) :

P	Q	P ∧ Q	P ∨ Q	¬P	P → Q	P ↔ Q
0	0
0	1
1	0
1	1

Solution

P	Q	P ∧ Q	P ∨ Q	¬P	P → Q	P ↔ Q
0	0	0	0	1	1	1
0	1	0	1	1	1	0
1	0	0	1	0	0	0
1	1	1	1	0	1	1

Propositions

Exprimer les propositions suivantes à l'aide des connecteurs logiques :

1. Si le soleil brille, alors je vais à la plage.
2. Soit je vais à la plage, soit je vais à la montagne.
3. Je ne vais pas à la plage.
4. Je vais à la plage, seulement si je vais à la montagne.
5. Le soleil brille, si et seulement si je vais à la montagne.

Solution

1. le soleil brille → je vais à la plage
2. je vais à la plage ou je vais à la montagne
3. non je vais à la plage
4. je vais à la plage → je vais à la montagne
5. le soleil brille ↔ je vais à la montagne

Si et seulement si

Quelle est la différence entre les propositions suivantes ?

1. Je vais skier, s'il neige.
2. Je vais skier, seulement s'il neige.
3. Je vais skier, si et seulement s'il neige.

Solution

Si on traduit les propositions en logique, on obtient :

1. je vais skier ← il neige
2. je vais skier → il neige
3. je vais skier ↔ il neige

Autrement dit :

1. A chaque fois qu'il neige, je vais skier. Donc s'il neige, je vais skier, mais je peux aussi aller skier sans qu'il neige.
2. A chaque fois que je vais skier, il neige. Il peut neiger sans que j'aille skier.
3. A chaque fois qu'il neige, je vais skier, et à chaque fois que je vais skier, il neige. Je ne rate jamais une occasion d'aller skier s'il neige, et je ne vais jamais skier s'il ne neige pas.

Références

• https://fr.wikipedia.org/wiki/Connecteur_logique
• https://fr.wikipedia.org/wiki/Formule_propositionnelle#Connecteurs_de_rh%C3%A9torique,_de_philosophie_et_de_math%C3%A9matiques