Remerciez-le!

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

Chapitre 4 : Logique et techniques de démonstration en mathématiques Nous rappe

Chapitre 4 : Logique et techniques de démonstration en mathématiques Nous rappelons ou introduisons dans ce chapitre préliminaire quelques éléments de logique et de vocabulaire mathématique indispensables à la compréhension des démonstrations des chapitres suivants 1 Assertions Dans le cadre d'une théorie mathématique donnée, une assertion est une phrase mathématique à laquelle on peut attribuer une, et une seule, valeur booléenne, à savoir vrai (V en abrégé) ou faux (F en abrégé). Certaines assertions sont déclarées vraies a priori : ce sont les axiomes ; sinon, la véracité d'une assertion doit résulter d'une démonstration. Les assertions démontrées sont appelées théorèmes ou propositions suivant leur importance. Un lemme est un résultat préalable utile à une démonstration plus conséquente, tandis qu'un corollaire est une assertion vraie qui découle d'un résultat précédent. 1.1 Opérations sur les assertions À une assertion, on peut associer sa négation, à deux assertions, leur disjonction ou leur conjonction. Les valeurs booléennes de ces assertions associées dépendent des valeurs des assertions de départ et sont données par les définitions suivantes Définition 1.1 La négation d'une assertion (P ) se note (non P ). L'assertion (non P ) est vraie si et seulement si (P ) est fausse. Définition 1.2 Étant données deux assertions (P) et (Q), on appelle disjonction de ces deux assertions l'assertion (P ou Q) qui est vraie si et seulement si l'une au moins des assertions est vraie. Définition 1.3 Étant données deux assertions (P) et (Q), on appelle conjonction de ces deux assertions l'assertion (P et Q) qui est vraie si et seulement si les deux assertions sont simultanément vraies. À ces trois opérations ou connecteurs, on ajoute les opérations d'implication et d'équivalence Définition 1.4 Étant données deux assertions (P ) et (Q), on définit l'assertion « (P ) implique (Q) », appelée implication et notée (P ⇒ Q), de la manière suivante : l'assertion (P ⇒ Q) est vraie quand (P ) est fausse ou lorsque (P ) et (Q) sont vraies. On dit encore que « (P ) est une condition suffisante pour (Q) » et que « (Q) est une condition nécessaire pour (P ) » L'assertion (P ) est appelée l'hypothèse et (Q) la conséquence Définition 1.5 Étant données deux assertions (P ) et (Q), on définit l'assertion « (P ) équivaut à (Q) », appelée équivalence et notée (P ⇔ Q), de la manière suivante : l'assertion (P ⇔ Q) est vraie si (P ) et (Q) sont toutes les deux vraies ou fausses. On dit encore que « (P ) et (Q) sont équivalentes » ou que « (P ) est une condition nécessaire et suffisante pour (Q) » 1.2 Tables de vérité La définition des assertions précédentes est résumée dans les tables de vérité ci-dessous (P) (non P) V F F V (P) (Q) (P ou Q) V V F F V F V F V V V F (P) (Q) (P et Q) V V F F V F V F V F F F Les opérations que nous venons d'introduire peuvent être répétées pour former des assertions dépendant d'assertions initiales (P1), (P2), (P3), etc. Deux assertions ainsi construites sont dites synonymes si elles ont le même tableau de vérité Exemple. Montrons que lorsque l'on a simultanément (P ⇒ Q) et (Q ⇒ P ), on a (P ⇔ Q) On établit pour cela le tableau de vérité suivant (P) (Q) (P ⇔Q) V V F F V F V F V F F V (P) (Q) (P ⇒Q) V V F F V F V F V F V V (P) (Q) (P ⇒Q) (Q ⇒P) (Q ⇒P) et (Q ⇒P) (P ⇔Q) V V F F V F V F V F V V V V F V V F F V V F F V Quelques synonymies classiques. Soient (P ), (Q) et (R) trois propositions On a alors (non (P ou Q)) est équivalente à (non P et non Q), (non (P et Q)) est équivalente à (non P ou non Q), (P ⇒ Q) est équivalente à (non Q ⇒ non P ), (P ou (Q et R)) est équivalente à ((P ou Q) et (P ou R)), (P et (Q ou R)) est équivalente à ((P et Q) ou (P et R)) La preuve de ces affirmations est laissée en exercice au lecteur (il suffit d'écrire les tableaux de vérité) 2 Quantificateurs Les quantificateurs sont des symboles utilisés pour écrire des énoncés. Une phrase quantifiée est une assertion mathématique contenant un ou des quantificateurs. Le symbole ∃ désigne le quantificateur existentiel. Ainsi, ∃x se lit « il existe au moins un élément x » et ∃!x signifie « il existe un et un seul élément x ». Le symbole ∀ désigne le quantificateur universel et ∀x signifie « pour tout élément x ». La lettre affectée par un quantificateur est muette et peut être remplacée par n'importe quelle autre lettre n'ayant pas déjà une signification dans l'énoncé Exemple. La notation x ∈ E signifie « x appartient à E». La négation d'une phrase quantifiée se définit comme suit : (non (∀x ∈ E, P (x))) ⇔ (∃x ∈ E, non P (x)), (non (∃x ∈ E, P (x))) ⇔ (∀x ∈ E, non P (x)). 3 La démonstration en mathématiques Dans le cadre d'une théorie mathématique, une démonstration consiste, en général, à établir une proposition de la forme (H ⇒ C) avec (H) vraie (sinon, il n'y a rien à faire), ou bien à montrer qu'une assertion (C) est vraie. On dispose pour cela non seulement de (H) mais aussi de toutes les propositions de la théorie concernée déjà établies. On met alors en évidence une suite d'assertions (P0), (P1),... , (Pn), où (P0) est (H) et (Pn) est (C), telles que la vérité de chaque (Pi), i =1,...,n, puisse être déduite des précédentes par l'intermédiaire des propositions établies et des règles logiques. Il existe plusieurs types de démonstration : la démonstration directe, la démonstration par l'absurde, la démonstration par contraposé et la démonstration par récurrence. 3.1 Démonstration directe La démonstration directe de (H ⇒ C) consiste à établir successivement des assertions intermédiaires pour arriver à (C) en partant de (H). Exemple. Démontrons directement que, pour tout entier naturel n, on a n est impair ou n 2 est pair Notons (P ) l'assertion « l'entier n est impair » et (Q) l'assertion « l'entier n2 est pair ». Dans ce cas, (H) est « n est un entier naturel » et (C) est (P ou Q). Nous avons à établir que (P ou Q) est vraie. Si «n est impair», on a (P ou Q) est vraie. Si « n est pair », alors il existe un entier p tel que n =2p Il s'ensuit que n 2 =4p 2, et donc n 2 est pair et il s’ensuit que (P ou Q) est vraie. 3.2 Démonstration par contraposée La démonstration par contraposée s'appuie sur la règle logique : (P ⇒ Q) est équivalente à (non Q ⇒ non P ). Exemple. Soit n un entier naturel. Démontrons que si n 2 est pair alors n l'est aussi Dans cet exemple, (P ) est l'assertion « n2 est pair » et (Q) est l'assertion « n est pair ». La négation de (Q) est alors « n est impair ». Supposons (non Q) vraie. Dans ce cas, n =2k +1, k étant un entier, et donc n 2 =4k 2 +4k +1 est impair. 3.3 Démonstration par l'absurde La démonstration par l'absurde qu'une assertion (P ) est vraie consiste à supposer que (P ) est fausse et à montrer que (non P ⇒ Q) est vraie, avec (Q) une assertion dont on sait qu'elle est fausse d'où une contradiction Il en résulte que (P ) est vraie car (non P ⇒ Q) est équivalente à (non Q ⇒ P ) (on pourra vérifier cette affirmation en exercice) Exemple. Démontrons que le réel 2 est irrationnel. Ici, l'assertion (P ) est « 2 est irrationnel ». La négation de (P ) est donc « 2 est rationnel ». Nous la supposons vraie et il existe alors deux entiers naturels p et q (avec 0 q ≠ ) premiers entre eux tels que 2 p q = , nous déduisons que 2 2 2 p q = est pair et donc que p est pair (voir l'exemple précédent). Écrivant ensuite p =2k avec k entier, il s'ensuit que q 2 =2k 2, montrant ainsi que q 2 est pair et donc q est pair. Les nombres p et q ont 2 comme diviseur commun, ce qui est contradictoire avec le fait que p et q sont premiers entre eux. 3.4 Démonstration par récurrence La démonstration par récurrence s'utilise pour prouver des propositions dont l'énoncé dépend d'un entier naturel n. Elle s'appuie sur une propriété (admise) particulière de l'ensemble des entiers naturels  3.4.1 Théorème : Toute partie A de , contenant l'entier p et telle que, pour tout n appartenant à A, uploads/Philosophie/ chapitre-4-logiques-et-techniques-de-demontration-en-mathematiques.pdf