Chapitre 1 : Notions de logiques mathématiques PDF

AIT-IKHLEF.N Chapitre 1 : Notions de logiques mathématiques. Chapitre 1 : Notions de logiques Introduction : Le but ici est d’exposer un vocabulaire (langage rigoureux) et des propriétés utilisables et utilisées dans tous les...

AIT-IKHLEF.N Chapitre 1 : Notions de logiques mathématiques. Chapitre 1 : Notions de logiques Introduction : Le but ici est d’exposer un vocabulaire (langage rigoureux) et des propriétés utilisables et utilisées dans tous les domaines mathématiques. I) Règle de logique et tables de vérité 1) Assertion (proposition) : Une proposition est une phrase qui peut être vraie ou fausse et pas les deux en même temps. Exemple : Il pleut maintenant. On représente les deux possibilités (possibilité de phrase vraie et possibilité de phrase fausse) par un tableau dit table de vérité comme suit : Ou bien tels que : est une proposition, Vraie valeur de vérité de Vraie Fausse valeur de vérité de Fausse signifie que est une proposition vraie, signifie que est une proposition vraie. signifie que est une proposition fausse, signifie que est une proposition fausse. 2) La négation « non » : La négation de la proposition est une proposition désignant le contraire de notée non ou bien ,d’où le résultat est. Exemple : P : Il pleut maintenant. : Il ne pleut pas maintenant. On a donc : 3) Les connecteurs (opérateurs) logiques : Ils lient deux propositions , pour en donner une nouvelle proposition et qui sont donc : 3 -1 : La conjonction notée : La conjonction des deux propositions , est la proposition ( et ) notée ,qui n’est vraie que si les deux propositions et sont vraies en même temps représenté par : 1 AIT-IKHLEF.N Chapitre 1 : Notions de logiques mathématiques. Exemple : (3 est impair et 3 divise 8) est une proposition fausse. 3 -2 : La disjonction notée : La disjonction des deux propositions , est la proposition ( ou bien ) notée , qui n’est fausse que si les deux propositions et sont fausses en même temps représenté par : Lois de Morgan : On admettra :  est  est 3-3 : L’implication : Soient et deux propositions ; la proposition est notée et se lit en français « implique » on en déduit que est fausse dans le seul cas où est vraie et est fausse et on a la table de vérité suivante : Dans : a) s’appelle l’hypothèse et la conclusion. se lit aussi : « si alors » ou « si est vraie alors est vraie » ou « pour que il faut que ». b) est une condition suffisante pour et est une condition nécessaire pour c) est appelé la réciproque de. est diférente de 2 AIT-IKHLEF.N Chapitre 1 : Notions de logiques mathématiques. est qui est donc (selon la loi de Morgan) Donc est 3 - 4 : L’équivalence : Soient et deux propositions ; la proposition et est notée et on dit que : a) Les propositions précédentes et sont équivalentes. b) Les deux propositions et sont équivalentes si elles ont la même valeur de vérité. c) se lit aussi « si et seulement si » ou bien « est équivalente à » ou bien « équivalent à » Selon la définition de l’équivalence on peut écrire la table de vérité suivante : Dans : a) est une condition nécessaire suffisante pour et est une condition nécessaire suffisante pour. b) Pour mettre le symbole il faut s’assurer qu’on a les deux implications de gauche à droite et de droite à gauche. Propriétés : Soient , et trois propositions on a : 1) , 2) , ( et sont commutatives) 3) , ( et sont associatives) 4) ( est distributive pour ) 5) ( est distributive pour ) 6) ( transitive, règle essentielle pour faire une démonstration). 7) Pour montrer que est vraie, il suffit de montrer que , et sont vraies. 8) 9) 3 AIT-IKHLEF.N Chapitre 1 : Notions de logiques mathématiques. 10) 11) (définition de l’implication). 12) 13) 14) ( c’est la contraposée de ) 4) Les quantificateurs : Soit un ensemble et une proposition dont les valeurs de vérité sont en fonction d’un élément de. Exemple : dépend d’un réel , et on ne peut pas dire que est vraie ou fausse tant qu’on ne sait pas la valeur de. Définition 1 : La proposition (pour tous les éléments de , est vraie) s’écrit en abrégé ou bien proposition vraie. Exemple : vraie. Définition 2 : La proposition (il existe au moins un élément de tel que est vraie) s’écrit en abrégé ou bien proposition vraie. Exemple : vraie. s’appelle le quantificateur universel et se lit « quelque soit ». s’appelle le quantificateur existentiel et se lit « il existe au moins ». Définition 3 : La proposition (il existe un seul élément de tel que est vraie). s’écrit en abrégé ou bien proposition vraie. Exemple : vraie. se lit « il existe un unique ». 4-1 : L’écriture des phrases quantifiées : Une phrase quantifiée est une phrase qui dépend d’un quantificateur ou bien plusieurs quantificateurs. Nous considérons les hypothèses du 4) alors : La proposition (pour tous les éléments de , est vraie) s’écrit en abrégé : ou bien ou bien ou bien proposition vraie ou bien proposition vraie ou bien proposition vraie. Remarque : On peut trouver d’autres écritures abrégées. La proposition (il existe au moins un élément de tel que est vraie) s’écrit en abrégé : 4 AIT-IKHLEF.N Chapitre 1 : Notions de logiques mathématiques. ou bien ou bien ou bien proposition vraie ou bien proposition vraie ou bien proposition vraie. Remarque : On peut trouver d’autres écritures abrégées. La proposition (il existe un seul élément de tel que est vraie) s’écrit en abrégé : ou bien ou bien ou bien proposition vraie ou bien proposition vraie ou bien proposition vraie. Remarque : On peut trouver d’autres écritures abrégées. Remarques très importantes : Soit une proposition alors :  Lorsque on dit « on a » c’est-à-dire que est une proposition vraie.  Lorsque on dit « montrer » c’est-à-dire « montrer que est une proposition vraie ». 4-2 : Négations des phrases quantifiées (règle de négation) De manière évidente on a :   Pour plus d’un quantificateur dans une proposition, on peut permuter 2 quantificateurs identiques, donc si et sont des ensembles et une proposition dont les valeurs de vérité sont en fonction de et alors on peut permuter de la façon suivante :  ,  , Mais les quantificateurs différents dans une proposition ne peuvent pas être permuter, alors si et sont des ensembles et une proposition dont les valeurs de vérité sont en fonction de et alors on a :  La proposition est différente de la proposition.  La proposition est différente de la proposition. Exemple :  est une proposition vraie.  , est une proposition fausse. 5 AIT-IKHLEF.N Chapitre 1 : Notions de logiques mathématiques. On peut démontrer facilement les relations suivantes :     5) Méthodes de raisonnement mathématiques : Les méthodes de raisonnement mathématiques sont le pilier de la rigueur mathématique, pour dire qu’une proposition est vraie ou fausse on utilise d’autres propositions considérées comme vraies et d’un raisonnement logique afin de ne pas avoir de contradiction. Parmi les propositions vraies il y a :  Les axiomes : propositions supposées vraies (sans démonstration) par exemple.  Les hypothèses ou les données.  Les théorèmes : Propositions vraies (résultats importants).  Les lemmes : Propositions servant à démontrer un théorème.  Corollaire : Est une conséquence directe d’un théorème démontré. Soient et deux propositions alors on a : Les principaux types de raisonnement 5-1 : Raisonnement déductif ou implication logique : Il est fondé sur deux règles :  Toute proposition obtenue par application d’un axiome est vraie.  Soient et deux propositions, si la proposition est vraie et si est vraie alors est vraie. 5-2 : Equivalence logique : pour démontrer une équivalence il est préférable de démontrer et L’équivalence signifie que les propositions et sont à la fois vraies ou fausses. 5-3 : Raisonnement par la contraposée : Il se base sur l’équivalence logique , alors pour montrer il suffit de montrer l’implication donc on suppose que est fausse, en suite on démontre que est fausse. Exemple : Montrer que Si est pair donc il existe entier positif, tel que donc On peut déduire que est pair, finalement l’implication de la proposition est démontrée par la méthode de la contraposée. 5-4 : Raisonnement par l’absurde :( très utilisé en analyse) il se base sur le principe du tiers exclu, pour démontrer qu’une proposition est vraie on suppose qu’elle est fausse c’est-à-dire que est vraie alors par un raisonnement logique on aboutit à une absurdité ou à une contradiction, dans ce cas est fausse donc est vraie. Exemple : Montrer que 6 AIT-IKHLEF.N Chapitre 1 : Notions de logiques mathématiques. On suppose que est fausse donc est vraie donc vraie donc , , contradiction car. 5-5 : Raisonnement par récurrence : Permet de démontrer qu’une proposition dépendant de soit vraie à partir de fixé, il consiste :  Démontrer que est vraie.  Supposer que est vraie pour et démontrer que est vraie. Alors on peut conclure que est vraie pour Remarque 1 : L’écriture précédente signifie que la proposition dépend de ( est en fonction de ). Remarque 2 : Le choix de est appelé base de récurrence dépend de la relation et n’est pas nécessairement égal à. Remarque 3 : Si la formule de récurrence n’est pas donnée il faut l’établir en donnant quelques valeurs premières à la variable entière et on peut faire apparaître une relation de récurrence (ne pas simplifier pour voir comment se dégage la récurrence). 7