Remerciez-le!

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

ECE1-B 2015-2016 CH I : Logique et raisonnements mathématiques Dans ce chapitre

ECE1-B 2015-2016 CH I : Logique et raisonnements mathématiques Dans ce chapitre, on introduit la syntaxe et la sémantique d’éléments de base du langage mathématique. L’objectif est double : × pouvoir comprendre et écrire des phrases mathématiques simples, × donner des bases rigoureuses aﬁn de pouvoir démontrer ce type de phrases mathématiques. I. Propositions mathématiques Déﬁnition Proposition mathématique On appelle proposition mathématique un énoncé auquel on peut attri- buer une valeur de vérité (vrai ou faux). Exemple • Les énoncés suivants sont des propositions mathématiques. a) 1 + 1 = 2 Cette proposition est vraie. b) 1 + 1 = 3 Cette proposition est fausse. c) ln(1) = 1 Cette proposition est fausse. • Par contre, 1 + 1 −2 et ( √ 18)3 ne sont pas des propositions puisqu’on ne peut leur attribuer de valeur de vérité. Ce sont des expressions arithmé- tiques dont le résultat est un réel. Il est à noter qu’une proposition mathématique peut comporter des va- riables. En conséquence, il est possible que la valeur de vérité d’une propo- sition dépende du choix de ces variables. Exemple • Les énoncés suivants sont des propositions dont la valeur de vérité dépend du choix des variables. a) x + 2 ⩾4 × cette proposition est vraie pour tout x plus grand que 2, × cette proposition est fausse sinon i.e. pour tout x strictement infé- rieur à 2. b) √ x2 = x × cette proposition est vraie pour tout x plus grand que 0, × cette proposition est fausse sinon i.e. pour tout x strictement infé- rieur à 0. c) p x2 + y2 = x + y Pour connaître la valeur de vérité cette proposition, on aimerait la sim- pliﬁer, en commençant par se débarrasser de l’opérateur √. Une telle démarche est périlleuse : si on reprend la proposition précé- dente : √ x2 = x, une élévation au carré de part et d’autre du symbole d’égalité fournit l’expression : x2 = x2, qui est vraie pour tout x réel ! L’élévation au carré n’est donc pas un opérateur neutre en terme de valeur de vérité (nous reviendrons plus tard sur ce point). Sans entrer dans les détails, on peut remarquer que : × si x = 0, la proposition est vraie pour tout y ⩾0, × si y = 0, la proposition est vraie pour tout x ⩾0, × si x < 0 et y < 0, la proposition est fausse. • Par contre, 10x −(√y) n’est pas une proposition. C’est une expression arithmétique dont le résultat est un réel. On peut nommer une proposition. Si elle dépend d’une variable explici- tement donnée, on fera apparaître cette dépendance. Par exemple, on pourra noter p(x, y) la proposition p x2 + y2 = x + y. 1 ECE1-B 2015-2016 II. Connecteurs logiques II.1. Conjonction Déﬁnition Conjonction Soient p et q sont deux propositions mathématiques. • On note p ET q la proposition qui est : × vraie quand p et q sont simultanément vraies, × fausse sinon. Autrement dit, une conjonction p ET q est fausse si (au moins) l’une des deux propositions p ou q qui la compose est fausse. • L’opérateur ET permet de combiner deux propositions pour former une nouvelle proposition. Exemple Les énoncés suivants sont des propositions mathématiques. a) (x + 2 ⩾4) ET (1 + 1 = 3) La proposition 1 + 1 = 3 étant fausse indépendamment de la vealeur de x, cette conjonction est fausse pour tout x réel. b) (1 + 1 = 2) ET (x + 2 ⩾4) × cette proposition est vraie pour tout x ⩾2, × cette proposition est fausse sinon i.e. pour tout x < 2. II.2. Disjonction Déﬁnition Disjonction Soient p et q sont deux propositions mathématiques. • On note p OU q la proposition qui est : × fausse quand p et q sont simultanément fausses, × vraie sinon. Autrement dit, une disjonction p OU q est vraie si (au moins) l’une des deux propositions p ou q qui la compose est vraie. • L’opérateur OU permet de combiner deux propositions pour former une nouvelle proposition. Exemple Les énoncés suivants sont des propositions mathématiques. a) (x + 2 ⩾4) OU (1 + 1 = 3) La proposition 1 + 1 = 3 étant fausse indépendamment de la valeur de x, cette disjonction est : × vraie lorsque (x + 2 ⩾4) l’est i.e. pour tout x ⩾2, × fausse sinon i.e. pour tout x < 2. b) (1 + 1 = 2) OU (x + 2 ⩾4) La proposition 1 + 1 = 2 étant vraie indépendamment de la valeur de x, cette disjonction est vraie pour tout x réel. Remarque Il ne faut pas confondre cette déﬁnition du OU avec celle utilisée dans le langage naturel. En eﬀet, lorsqu’on vous demande au restaurant si vous sou- haitez du fromage ou du dessert, le serveur retire implicitement la possibilité de vous apporter les deux. Le « ou » du langage naturel correspond en fait au XOR (« ou » exclusif). Pour p et q deux propositions, p XOR q est vériﬁée si seulement l’une des deux propositions p et q est vraie et fausse sinon. Propriété des opérateurs ET et OU 1) p ET (q OU r) a même valeur de vérité que (p ET q) OU (p ET r) 2) p OU (q ET r) a même valeur de vérité que (p OU q) ET (p OU r) (dire que deux propositions a et b ont même valeur de vérité signiﬁe qu’elles sont fausses en même temps et qu’elles sont vraies en même temps) Démonstration. Nous traitons seulement le 1), le 2) est laissé en exercice. Pour montrer que deux propositions a et b ont même valeur de vérité, nous allons procéder comme suit : (i) nous montrons que si a est vraie alors b l’est aussi. (ii) nous montrons que si a est fausse alors b l’est aussi. 2 ECE1-B 2015-2016 Ceci démontre que les propositions sont vraies en même temps et fausses en même temps. Revenons à la démonstration consistant à démontrer que p ET (q OU r) a même valeur de vérité que (p ET q) OU (p ET r). (i) Supposons que p ET (q OU r) est vraie. Ceci signiﬁe que les propositions p et q OU r sont vraies toutes les deux. Ainsi, l’une (au moins) des propositions q ou r est vraie. On procède alors par disjonction de cas sur la valeur de vérité (par exemple) de q. × si q est vraie : alors p ET q est vraie. Ainsi, la proposition (p ET q) OU (p ET r) est vraie. × si q est fausse : alors comme q OU r est vraie, r est forcément vraie. On en déduit que p ET r est vraie. Ainsi, la proposition (p ET q) OU (p ET r) est vraie. La proposition (p ET q) OU (p ET r) est donc vraie (puisque vraie indé- pendamment de la valeur de q). (ii) Supposons que p ET (q OU r) est fausse. Ceci signiﬁe que l’une (au moins) des propositions p ou q OU r est fausse. On procède alors par disjonction de cas sur la valeur de vérité (par exemple) de p. × si p est vraie : alors q OU r est fausse. Ainsi, q et r sont fausses. On en déduit que p ET q et p ET r sont fausses. Ainsi, la proposition (p ET q) OU (p ET r) est fausse. × si p est fausse : alors p ET q est fausse et p ET r est fausse. Ainsi, la proposition (p ET q) OU (p ET r) est fausse. La proposition (p ET q) OU (p ET r) est donc fausse (puisque fausse indépendamment de la valeur de p). Remarque • Notez que (i) et (ii) permettent d’aﬃrmer que : (ii’) si b est vraie alors a est vraie. Si on suppose b vraie, alors, si a était fausse, à l’aide de (ii) on pourrait conclure que b est fausse, ce qui contredit l’hypothèse « b est vraie ». (i’) si a est fausse alors b est fausse. Si on suppose a fausse, alors, si b était vraie, à l’aide de (i) on pourrait conclure que b est vraie, ce qui contredit l’hypothèse « a est fausse ». • Réciproquement, en raisonnant de même, on peut prouver que (ii’) permet de démontrer (ii) et (i’) permet de démontrer (i). • On en conclut que l’on peut remplacer (i) par (i’) et (ii) par (ii’) lorsque l’on souhaite démontrer que deux propositions ont même valeur de vérité. II.3. Négation Déﬁnition Négation Soit p une proposition mathématique. • On note NON(p) la proposition qui est : × vraie lorsque p est fausse, × fausse lorsque que p est vraie. Exemple a) NON(x + 2 ⩾4) est une proposition qui est : × vraie si x + 2 ⩾4 est fausse i.e. si pour tout x tel que x + uploads/s3/ logique 5 .pdf