Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Introduction à la logique mathématique Par Le Zéro www.openclassrooms.com Licen

Introduction à la logique mathématique Par Le Zéro www.openclassrooms.com Licence Creative Commons 7 2.0 Dernière mise à jour le 13/05/2012 Sommaire 2 Sommaire ........................................................................................................................................... 1 Lire aussi ............................................................................................................................................ 3 Introduction à la logique mathématique ............................................................................................. 3 Propositions logiques ........................................................................................................................................................ 3 Définition ..................................................................................................................................................................................................................... 4 Quelques exemples .................................................................................................................................................................................................... 4 À retenir ....................................................................................................................................................................................................................... 4 Opérateurs de base ........................................................................................................................................................... 4 La négation .................................................................................................................................................................................................................. 5 La conjonction ............................................................................................................................................................................................................. 6 La disjonction .............................................................................................................................................................................................................. 7 Lois de Morgan ............................................................................................................................................................................................................ 9 Implications et équivalences ............................................................................................................................................. 9 Notion d'implication ..................................................................................................................................................................................................... 11 Equivalence ............................................................................................................................................................................................................... 13 Quantificateurs ................................................................................................................................................................ 13 Le quantificateur universel ........................................................................................................................................................................................ 14 Le quantificateur existenciel ...................................................................................................................................................................................... 14 Plusieurs quantificateurs ........................................................................................................................................................................................... 15 Raisonnons ! ................................................................................................................................................................... 15 Exemple et contre exemple ....................................................................................................................................................................................... 16 La contraposée .......................................................................................................................................................................................................... 17 Le raisonnement par l'absurde .................................................................................................................................................................................. 19 Le raisonnement par récurrence ............................................................................................................................................................................... 23 Q.C.M. ............................................................................................................................................................................. 24 Partager ..................................................................................................................................................................................................................... 2/25 www.openclassrooms.com Introduction à la logique mathématique Par Le Zéro Mise à jour : 13/05/2012 Difficulté : Facile Durée d'étude : 3 heures À la limite de la philosophie, la logique est une branche fondamentale des mathématiques qui permet d'établir la valeur de vérité de propositions et de construire des raisonnements mathématiques. Ce tutoriel constitue une initiation à cette branche primordiale des mathématiques. Nous définirons les notions de proposition et d'opérateur, construirons des tables de vérité, expliquerons les notions d'implication, d'implication réciproque et d'équivalence avant d'aborder les différents types de raisonnements que l'on peut suivre en mathématiques. Le tout sera saupoudré de nombreux exercices accessibles à partir de zéro ou presque ! C'est parti ! Sommaire du tutoriel : Propositions logiques Opérateurs de base Implications et équivalences Quantificateurs Raisonnons ! Q.C.M. Propositions logiques Définition Une proposition logique (ou assertion) est une affirmation formée d'un assemblage de symboles et de mots, portant sur des objets mathématiques, à laquelle on peut clairement attribuer la valeur vraie ou la valeur faux. On note une proposition. Par définition A satisfait les 3 principes (ou axiomes) suivants : Principe d'identité : est Autrement dit si est vrai alors est vrai et si est faux alors est faux. Principe de non contradiction : ne peut pas à la fois être vrai et faux Principe du tiers exclus : Soit est vrai, soit est faux. Il n'existe pas d'autre valeur de vérité en logique mathématique. Ces trois principes constituent le fondement de tout raisonnement mathématique. Le dernier point mérite que l'on s'y attarde un instant : Soit la proposition « Le carré d'un nombre réel est strictement positif » . Alors ? V rai ou faux ? L'intuition première serait de répondre "ça dépend du nombre", c'est le cas pour la plupart des nombres mais c'est faux pour zéro (car ). Le problème est que cette réponse est en contradiction avec le principe du tiers exclus. Il faut donc attribuer clairement à cette proposition la valeur vrai ou la valeur faux. Sommaire 3/25 www.openclassrooms.com Étant donné qu'il existe au moins un nombre (ici zéro) pour lequel cette proposition est fausse, on dira que la proposition est fausse. Quelques exemples : « Le nombre de lettres dans l'alphabet français est 10. » La proposition est fausse. : « » La proposition est vraie. : « » n'est pas une proposition logique complète car elle contient une variable libre . On ne sait pas ce qu'est (un point ? un nombre entier ? un vecteur ? une étoile de l'univers ?). On ne peut donc pas attribuer de valeur de vérité à la proposition . : « Soit un nombre réel, alors » La proposition est fausse. En effet est une proposition logique car on a défini la variable comme étant un nombre réel. Mais elle est fausse car par exemple est un nombre réel et . On utilise ici un contre exemple pour prouver que la proposition C' est fausse. Ce type de raisonnement sera approfondi dans la dernière partie. À retenir Les propositions logiques ne peuvent prendre que deux valeurs : VRAI ou FAUX (d'où le nom de logique bivalente) Il faut bien faire la distinction entre une proposition (qui est une phrase) et sa valeur (qui est soit VRAI soit FAUX). Opérateurs de base Les opérateurs permettent de construire de nouvelles propositions à partir d'une ou de plusieurs propositions initiales. Commençons par le premier (et le plus simple !) d'entre eux l'opérateur « NON ». La négation Apprenons à dire non ! Soit A une proposition. On définit une proposition « non A » que l'on note ¬A (avec une sorte de petit L allongé vers le bas) Si A est vraie alors ¬A est fausse. Si A est fausse alors ¬A est vraie. Pour ceux qui font de la programmation, l'opérateur « NON » (noté ¬ en maths) est souvent noté « ! » en informatique. On peut établir la table de vérité de l'opérateur de négation à partir de sa définition. Définition : Introduction à la logique mathématique 4/25 www.openclassrooms.com Une table de vérité est un tableau définissant la valeur d'une fonction logique pour chacune des combinaisons possibles des entrées. Construction : Dans la première colonne, je place toutes les valeurs que peut prendre A (c'est à dire V rai ou Faux). Dans la seconde colonne, je place la valeur de vérité de ¬A correspondante. A ¬A VRAI FAUX FAUX VRAI Par convention et pour faciliter la lecture de grandes tables, on écrit 0 pour la valeur FAUX et 1 pour la valeur VRAI. A ¬A 1 0 0 1 Il est important de bien comprendre comment construire une table de vérité, nous nous en servirons de nombreuses fois dans ce cours. Ce connecteur est assez intuitif dans la mesure ou nous l'utilisons quotidiennement. Quelques exemples : A : « Paris est la capitale de la France » (1) ¬A : « Paris n'est pas la capitale de la France » (0) B : « π est un nombre entier » (0) ¬B : « π n'est pas un nombre entier » (1) C : « 5 est un nombre impair » (1) ¬C : « 5 est un nombre pair » (0) Ce premier opérateur doit maintenant vous paraître assez simple. Pour construire des raisonnements logiques on a besoin d'utiliser des opérateurs permettant de lier deux propositions logiques entre elles (on les appelle des opérateurs binaires). La conjonction Le premier d'entre eux est l'opérateur « ET ». Soient A et B deux propositions. On définit une nouvelle proposition « A ET B » que l'on note « A ∧ B » (Avec une sorte de v à l'envers) Cette nouvelle proposition est vraie lorsque A et B sont vraies en même temps fausse dans tous les autres cas En informatique cet opérateur est souvent noté &&. Introduction à la logique mathématique 5/25 www.openclassrooms.com On déduit de cette définition la table de vérité de la proposition « A ∧ B » A B A ∧ B 1 1 1 1 0 0 0 1 0 0 0 0 Les deux première colonnes permettent de lister tous les cas possibles pour les valeurs de vérité de A et de B. La dernière colonne associe la valeur de vérité de la proposition « A ∧ B ». Il est important de bien comprendre la table de vérité de l'opérateur « ET » car il est utilisé dans de nombreux raisonnements. Quelques exemples : A : « 5 est un nombre inférieur à 10 ET 5 est pair » Soit A' : « 5 est un nombre inférieur à 10 » A' est vraie Soit A'' : « 5 est pair » A'' est fausse La proposition A est la proposition « A' ∧ A'' » D'après la table de vérité de l'opérateur binaire « ET », on en déduit que la proposition A est fausse . B : « La lettre A est une voyelle et T est une consonne. » En résonnant de même, on en déduit que la proposition B est vraie. La disjonction Le deuxième opérateur binaire que nous allons étudier est l'opérateur « OU » Soient A et B deux propositions. On définit une nouvelle proposition « A OU B » que l'on note « A ∨ B » (On retourne le symbole ∧). Cette proposition est : fausse lorsque A et B sont fausses en même temps vraie sinon Autrement dit, la proposition « A ∨ B » est vraie uniquement si A ou B est vraie (ou les deux !). En informatique, on utilise souvent la notation ||. Introduction à la logique mathématique 6/25 www.openclassrooms.com Exercice 1 : Essayez d'établir la table de vérité de cet opérateur. Prenez un petit bout de papier sur votre bureau dérangé, armez-vous d'un crayon et mettez-vous au travail ! Je vous conseille de vous inspirer de la table de vérité de l'opérateur « ET » Correction : Secret (cliquez pour afficher) Cette table se construit de la même manière que la précédente. J’espère que vous n'avez pas eu trop de mal ! Sinon essayez de bien comprendre le fonctionnement des tables de vérité, la prochaine fois sera la bonne ! A uploads/Philosophie/ introduction-a-la-logique-mathematique 1 .pdf