ElementsMathematiquesAppliqueesV001

LMENTS DE MATHMATIQUES APPLIQUES

version 0.01

8 Novembre 2009

Ce document est sous licence Creative Commons version 3.0 France paternit; pas dutilisation commerciale; partage des conditions initiales lidentique http://creativecommons.org/licenses/by-nc-sa/3.0/deed.fr

Table des matires

Table des matires i Avant-propos iii Introduction v

1

I1 2 3 4 5 6 7

A RITHMTIQUEThorie de la dmonstration 3 Nombres 29 Oprateurs arithmtiques 61 Thorie des ensembles 77 Thorie des nombres 109 Probabilits 125 Statistiques 137

233

II8 9 10 11 12 13 14 15

A LGBRECalcul Algbrique 235 Algbre et gomtrie ensemblistes 259 Analyse fonctionnelle 273 Topologie 299 Thorie de la mesure 311 Calcul diffrentiel et intgral 319 Suites et sries 387 Calcul vectoriel 433

481

III16 17 18 19

C HIMIEChimie quantique 483 Chimie molculaire 497 Chimie analytique 505 Chimie thermique 509

517

IVA

A NNEXESRepres biographiques 519

525

V

R FRENCES ET

INDEXES

Rfrences 527 Index gnral 529 Index des noms propres 533

Avant-propose prsent document a t conu de faon ce que les connaissances requises pour le parcourir soient les plus lmentaires. Pour le consulter, il sut de savoir raisonner, dobserver et davoir du temps. ce titre, il doit pouvoir se substituer de nombreuses rfrences et permettre ainsi toute personne curieuse de parfaire ses connaissances dans ce domaine.

L

NaissanceForce est de constater quun ouvrage assez complet, dtaill et pdagogique, si possible daccs gratuit et portatif et prsentant une vue densemble des notions de mathmatiques appliques, comprenant des dmonstrations, nest actuellement pas disponible. Un tel ouvrage orirait, en plus, une notation homogne ainsi que la possibilit damliorations ou de complments suggrs par le lecteur attentif. Certes, dans le but de partager ce savoir mathmatique, il peut paratre paradoxal de vouloir augmenter la liste, dj longue, des ouvrages disponibles dans les bibliothques, dans le commerce et sur internet. Il faut donc en mesure de prsenter une argumentation solide qui justie la cration dun tel document. Voici donc les quelques arguments qui paraissent susceptibles dtre numrs : 1. le partage de la connaissance ; 2. le caractre volutif et pratique dun document lectronique libre, en fonction de la demande ; 3. une prsentation rigoureuse avec des dmonstrations simplies ; 4. la possibilit pour les tudiants, les professeurs et plus gnralement les lecteurs, de rutiliser les sources ; 5. une notation homogne, dans tout louvrage, pour les oprateurs mathmatiques, un langage clair et rigoureux sur lensemble des sujets abords ; 6. larchivage des sources dun tel document en vue dune traduction en un nouveau language issu des nouvelles technologies de linformation. Les informations dtailles dans ce document ne sont pas nouvelles mais malheureusement, elles ne sont pas non plus toujours facilement accessibles. Datant de plusieurs dizaines dannes au minimum, elles ne sont normalement plus soumises une quelconque proprit intellectuelle et peuvent tre librement distribues. Le choix de prsenter lensemble des concepts par ordre logique et non par ordre de ncessit a eu les consquences suivantes : 1. il faudra parfois admettre provisoirement certaines ides, quitte les comprendre plus tard ; 2. il sera certainement ncessaire pour le lecteur de parcourir au moins deux fois lensemble de louvrage. Lors de la premire lecture, on apprhende lessentiel et lors de la deuxime lecture, on comprend les dtails ; 3. il faut accepter certaines rptitions ainsi que les nombreuses rfrences croises et remarques complmentaires. Certains savent que pour chaque thorme et modle mathmatique, il existe souvent plusieurs dmonstrations. A t choisie celle qui semblait la plus simple.A LTEX

Parmi les possibilits disponibles pour le dveloppement dun tel document, la seule qui semble A pertinente actuellement est L TEX. Ce language associe qualit visuelle et honntet typographique mais permet aussi, par son principe de fonctionnement mme, la cration de documents lectroniques au sein desquels il est possible de naviguer facilement. Une solution purement base sur la

iv

AVANT- PROPOS

technologie internet (html, xml, mathml...) ne semble ne pas avoir atteint un niveau de maturit susant quand le contenu scientique est important. Qui plus est, ce systme est libre et par consquent accessible tout le monde, et permet de travailler manire compltement autonome. Une attention toute particulire est porte aux illustrations, grce lutilisation de lextension PSTricks, qui permet de conserver une homognit. Il sagit aussi dun choix prenne puisque les sources sont utilisables sous tout type de systme dexploitation et pourront tre traduites, au cas o lavenir lexige, dans un format plus moderne. Lun des principes fondamentaux de LaTeX est la sparation du contenu et de la mise en forme. A L TEXcalcule la mise en page, numrote chapitres, sections, tableaux et gures, cre les rfrences bibliographiques, les indexes, la table des matires et les rfrences croises avec un minimum dinterventions. Bien que cette caractristique soit dcouple du choix du programme de traitement texte, il A savre que L TEXralise un travail remarquable concernant la prise en compte des rgles typographiques relatives chaque langue. La langue franaise a donc ses propres conventions, dtailles pour la plupart dans le document : http://jacques-andre.fr/faqtypo/lessons.pdf et respectes, dans la mesure du possible, dans cet ouvrage.

UtilisationCe document contient des renvois hypertextes qui permettent une lecture ecace et uide. Il peut sagir par exemple, au sein du texte principal, dun renvoi une rfrence bibliographique qui contient les dtails appropris pour un approfondissement ultrieur. Il peut sagir aussi dun renvoi une dnition explique dans une autre page : dans ce cas prcis, cest dans la marge que le lien apparat an quil conserve un sens pour une version imprime. Enn, lindex et la table des matires autorisent un saut directement la page slectionne par le lecteur. Un comportement similaire existe pour les quations, les gures et les tableaux. Pour un ouvrage de cette proportion, il semble important de souligner cet aspect. On notera lexistence de la commande Alt + dans Acrobat Reader qui permet de revenir la page lue prcdente et qui nexiste pas dans tous les lecteurs de documents pdf. Pour la lgret du document et lecture amliore, les polices et les graphiques sont conservs sous forme vectorielle.

RemerciementsDans lordre alphabtique : Rafal Guglielmetti, passionn du dveloppement web et tudiant en mathmatiques lcole Polytechnique Fdrale de Lausanne, pour le dveloppement et lamlioration du code du forum ; Lon Harmel, ingnieur diplm en lectromcanique avec une spcialisation en lectronique et automaticit, responsable au laboratoire de recherches physiques chez A.C.E.C, pour lapport de la documentation qui a servi la rdaction des chapitres de physique quantique corpusculaire, ondulatoire, de physique quantique des champs et de calcul spinoriel et relativit gnrale ; Vincent Isoz, ingnieur diplm en physique avec une spcialisation en gnie nuclaire. Responsable et crateur/dveloppeur du site http://www.sciences.ch/ et rdacteur de la plus grande partie du contenu. Ruben Ricchiuto, ingnieur physicien et mathmaticien luniversit de Genve, pour sa prcieuse aide et disponibilit en physique des plasmas, lectromagntisme, physique quantique, statistiques, topologie, analyse et chimie quantique, et encore beaucoup dautres domaines relatifs aux mathmatiques pures.

Introductionmniprsentes dans lindustrie 1 , ou dans les services 2 , les mathmatiques appliques apparaissent aussi dans de nombreux autres secteurs. Elles interviennent dans notre vie quotidienne et contribuent la rsolution de problmatiques actuelles : nergie, sant, environnement, climatologie, optimisation, dveloppement durable... Leur grand succs prend racine dans leur fantastique dispersion dans le monde rel, volutif et contingent, et leur intgration croissante toutes les activits humaines. Nous voluons lentement donc vers une situation o les mathmaticiens nauront plus le monopole des mathmatiques, mais o des conomistes, gestionnaires et marchands feront tous des mathmatiques. Ceux qui entrevoient la mathmatique applique que comme un outil ou comme lennemi des croyances religieuses, ou encore comme un domaine scolaire rbarbatif, sont lgion. Il est cependant peut-tre utile de rappeler que, comme le disait Galile, Le livre de la Nature est crit dans le langage des mathmatiques. Cest dans cet esprit que ce document aborde la mathmatique applique pour les tudiants en sciences de la nature, de la terre et de la vie, ainsi que pour tous ceux qui exercent une profession lie ces diverses matires, y compris la philosophie, ou pour toute personne curieuse de sinformer de limplication des sciences dans la vie quotidienne. La frontire entre la philosophie et les sciences pures et exactes est trs tnue. Comme le relate Platon dans le Phdon, Socrate ses dernires heures sest entour de ses amis et disciples, dont deux pythagoriciens Cbs et Simmias considrs comme interlocuteurs privilgis. Ce nest pas un hasard puisquil convient alors de philosopher, dj, en sinspirant du modle pythagoricien qui fait des mathmatiques une voie ncessaire daccs la vrit, seule capable de se frayer un chemin able pour aborder des sujets aussi importants que ceux de lme et de sa destine. Le choix de traiter lingnierie ici comme une branche de la mathmatique applique provient certainement du fait que lensemble des domaines de la physique et la mathmatique sont ce jour tellement peu discernables que la mdaille de Fields 3 a t dcerne en 1990 au physicien E. Witten, qui a utilis des ides issues de la physique pour redmontrer un thorme mathmatique. Cette tendance nest certainement pas fortuite, car nous pouvons observer que toute science, ds quelle cherche atteindre une comprhension plus dtaille du sujet quelle tudie, voit nalement toujours sa course aboutir dans les mathmatiques pures. Ainsi pouvons-nous prsager dans un futur lointain, la convergence de toutes les sciences (pures, exactes ou sociales) vers la mathmatique pour la modlisation 4 . Il peut parfois nous paratre dicile de transmettre le sentiment de beaut mathmatique de la nature, de son harmonie la plus profonde et de la mcanique lgante de lunivers, ceux qui ne connaissent que les rudiments du calcul formel. Le physicien R. Feynmann a parl une fois de deux cultures : les gens qui ont, et ceux qui nont pas eu une comprhension susante des mathmatiques pour apprcier la structure scientique de la nature. Pour lanecdote, on prtend quun roi ayant demand Euclide de lui enseigner la gomtrie se plaignit de sa dicult. Euclide rpondit : Il ny a pas de voie royale. Les physiciens et mathmaticiens ne peuvent se convertir un autre langage. Si vous voulez apprendre connatre la nature, lapprcier sa juste valeur, vous devez comprendre son langage. Elle se rvle sous cette unique forme. Au mme titre, aucune discussion intellectuelle ne vous permettra de communiquer un sourd ce que vous ressentez vraiment en coutant de la musique. De mme, toutes les discussions du monde resteront impuissantes transmettre une comprhension intime de la nature ceux de lautre culture. Les philosophes et thologiens peuvent essayer de vous donner des ides qualitatives sur lUnivers. Le fait que la mthode scientique ne puisse convaincre le monde entier de sa justesse et de sa puret, trouve peut-tre sa cause dans lhorizon limit de certaines gens qui sont amen simaginer que lhomme ou quun autre concept intuitif, sentimental ou arbitraire est le centre de lUnivers.

O

1. 2. 3. 4. ment

On peut par exemple citer larospatiale, limagerie mdicale, la cryptographie, les transports, la chimie,... banques, assurances, ressources humaines, projets, logistique, architecture, tlcommunications... Il sagit de la plus haute rcompense de nos jours dans le domaine de la mathmatique. Lire titre dexemple le document Lexplosion des mathmatiques disponible dans la rubrique tlchargedu site.

vi

I NTRODUCTION

MthodesLa science est lensemble des eorts systmatiques pour acqurir des connaissances sur notre environnement monde, pour les organiser et les synthtiser en lois et thories vriables et ayant pour principal objectif dexpliquer le "comment" des choses. Les scientiques doivent soumettre leurs ides et rsultats la vrication et la reproduction indpendante de leurs pairs. Ils doivent abandonner ou modier leurs conclusions lorsque confrontes des vidences plus compltes ou direntes. La crdibilit de la science sappuie sur ce mcanisme dautocorrection. Lhistoire de la science montre que ce systme fonctionne depuis trs longtemps et ce mme trs bien par rapport tous les autres. Dans chaque domaine, les progrs ont t spectaculaires. Toutefois, le systme a parfois des rats quil faut corriger avant que les petites drives ne saccumulent. Cet avertissement, et les rappels qui vont suivre, doivent servir le scientique se remettre en question en faisant un bon usage de ce que nous pouvons considrer aujourdhui comme les bonnes mthodes de travail pour rsoudre des problmes ou dvelopper des modles thoriques. Dans ce but, le tableau 1 rcapitule les direntes tapes du travail en mathmatique ou physique thorique.Mathmatique Poser lhypothse, la conjecture ou la proprit dmontrer de manire formelle ou en langage commun Dnir les axiomes qui vont donner les points de dpart et tablir des restrictions aux dveloppements 5 . Dans la mme ide, le mathmaticien dnit le vocabulaire spcialis reli des oprateurs mathmatiques 6 Des axiomes poss, tirer directement des lemmes ou des proprits dont la validit en dcoule directement et qui prparent au dveloppement du thorme cens valider lhypothse ou la conjecture de dpart Une fois le ou les thormes dmontrs en tirer des corollaires et encore des proprits Tester la force ou lutilit de sa ou ses conjectures ou hypothses en dmontrant la rciproque du thorme ou en la comparant avec des exemples dautres thories mathmatiques pour voir si lensemble forme un tout cohrent Dventuelles remarques peuvent tre indiques Physique Poser correctement et de manire dtaille le ou les problmes rsoudre de manire formelle ou en langage commun Dnir ou noncer les postulats ou principes ou encore les hypothses et suppositions qui vont donner les points de dpart et tablir des restrictions aux dveloppements Une fois le modle thorique dvelopp vrier les quations dimensionnelles pour dceler une ventuelle erreur dans les dveloppements

Chercher les cas limites, dont les singularits font partie, du modle pour en vrier la validit intuitive Tester exprimentalement le modle thorique obtenu et soumettre le travail comparaison avec dautres quipes indpendantes. Le nouveau modle doit prvoir des rsultats exprimentaux observs et jamais observs. Si le modle est valid alors il prend ociellement le statut de thorie Dventuelles remarques peuvent tre indiques

TABLEAU 1 Les diffrentes tapes du travail scientique

Remarques 1. Attention, il est trs facile de faire des nouvelles thories physiques en alignant des mots. Cela sappelle de la "philosophie" et les grecs ont pens aux atomes comme cela. Ca peut donc mener une vraie thorie. Par contre il est bien plus dicile de faire une "thorie prdictive", cest--dire avec des quations qui permettent de prdire le rsultat dune exprience. 2. Toutefois ce qui spare la mathmatique de la physique est que, en mathmatique, lhypothse est toujours vraie. Le discours mathmatique nest pas une dmonstration dune vrit extrieure chercher, mais vise uniquement la cohrence. Ce qui doit tre juste est le raisonnement.

Prsentons les quatre principes de la mthode de Descartes qui, rappelons-le, est considr comme le premier scientique de lhistoire de par sa mthode danalyse :5. Parfois par abus, proprits, conditions et axiomes sont confondus alors que le concept daxiome est beaucoup plus prcis et profond. 6. Il ne faut pas cependant oublier que la validit dun modle ne dpend pas du ralisme de ses hypothses mais bien de la conformit de ses implications avec la ralit.

vii

1. Ne recevoir jamais aucune chose pour vraie que je ne la connusse videmment tre telle. Cest--dire, dviter soigneusement la prcipitation et la prvention, et de ne comprendre rien de plus en mes jugements que ce qui se prsenterait si clairement et si distinctement mon esprit, que je neusse aucune occasion de le mettre en doute ; 2. De diviser chacune des dicults que jexaminerais, en autant de parcelles quil se pourrait, et quil serait requis pour les mieux rsoudre ; 3. De conduire par ordre mes penses, en commenant par les objets les plus simples et les plus aiss connatre, pour monter peu peu comme par degrs jusques la connaissance des plus composs, et supposant mme de lordre entre ceux qui ne se prcdent point naturellement les uns les autres ; 4. Et le dernier, de faire partout des dnombrements si entiers et des revues si gnrales, que je fusse assur de ne rien omettre.

Sur les sciencesIl est important que soient dnis rigoureusement les dirents types de sciences dvelopps au cours de lhistoire. Eectivement, il semble quau 21e sicle un abus de langage sinstaure et quil ne devienne plus possible pour la population de distinguer la qualit intrinsque dune science dune autre.Remarque tymologiquement le mot science vient du latin scienta (connaissance) dont la racine est le verbe scire qui signie savoir.

Cet abus de langage vient probablement du fait que les sciences pures et exactes perdent leurs illusions duniversalit et dobjectivit, dans le sens o elles sauto-corrigent. Ceci ayant pour consquence que certaines sciences sont relgues au second plan et tentent den emprunter les mthodes, les principes et les origines pour crer une confusion quant leurs distinctions. En soi, la science cependant ne produit pas de vrit absolue. Par principe, une thorie scientique est valable tant quelle permet de prdire des rsultats mesurables et reproductibles. Mais les problmes dinterprtation de ces rsultats font partie de la philosophie naturelle. tant donn la diversit des phnomnes tudier, au cours des sicles sest constitu un nombre grandissant de disciplines comme la chimie, la biologie, la thermodynamique, etc. Toutes ces disciplines priori htroclites ont pour socle commun la physique, pour langage les mathmatiques et comme principe lmentaire la mthode scientique. Ainsi, un petit rafrachissement semble ncessaire :Dnition 0.1 Nous dnissons par science pure, tout ensemble de connaissances fondes sur un raisonnement rigoureux valable quel que soit le facteur (arbitraire) lmentaire choisi nous disons alors indpendant de la ralit sensible et restreint au minimum ncessaire. Il ny a que la mathmatique qui puisse tre classie dans cette catgorie. Dnition 0.2 Nous dnissons par science exacte ou science dure, tout ensemble de connaissances fondes sur ltude dune observation, observation qui aura t transcrite sous forme symbolique. Principalement, le but des sciences exactes est non dexpliquer le pourquoi mais le comment.Remarque Les deux dnitions prcdentes sont souvent incluses dans la dnition de sciences dductives ou encore de sciences phnomnologiques.

Dnition 0.3 Nous dnissons par science de lingnieur, tout ensemble de connaissances tho-

riques ou pratiques appliques aux besoins de la socit humaine tels que : llectronique, la chimie, linformatique, les tlcommunications, la robotique, larospatiale, biotechnologies...Dnition 0.4 Nous dnissons par science, tout ensemble de connaissances fondes sur des tudes

ou observations de faits dont linterprtation na pas encore t retranscrite ni vrie avec la rigueur mathmatique caractristique des sciences qui prcdent, mais qui applique des raisonnements comparatifs statistiques. Sont inclues dans cette dnition la mdecine 7 , la sociologie, la psychologie, lhistoire, la biologie...7. Il faut cependant prendre garde au fait que certaines parties de la mdecine tudient des phnomnes descriptifs sous forme mathmatique tels que les rseaux de neurones ou autres phnomnes associs des causes physiques connues.

viii

I NTRODUCTION

Selon le philosophe K. Popper, une thorie nest scientiquement acceptable que si, telle quelle est prsente, elle peut tre falsiable, cest dire soumise des tests exprimentaux. La connaissance scientique est ainsi par dnition lensemble des thories qui ont jusqualors rsist la falsication. La science est donc par nature soumise en permanence la remise en question.Dnition 0.5 Nous dnissons par science molle ou para-sciences, tout ensemble de connaissances

ou de pratiques qui sont actuellement fondes sur des faits invriables (non reproductibles scientiquement) ni par lexprience, ni par la mathmatique. Sont inclues dans cette dnition lastrologie, la thologie, le paranormal, la graphologie...Dnition 0.6 Nous dnissons par sciences phnomnologiques ou sciences naturelles, toute science qui nest pas inclue dans les dnitions prcdentes : lhistoire, la sociologie, la psychologie, la zoologie, la biologie... Dnition 0.7 Le scientisme est la doctrine fondamentale suivant laquelle il ny a de vrit que

dans la science. Ce qui est intressant dans cette doctrine, cest que cest certainement une des seules qui demande aux gens de devoir rchir par eux-mmes et de comprendre lenvironnement qui les entoure en remettant continuellement tout en question et sans ne jamais rien accepter comme acquis.

TerminologieLe tableau mthodique 1 contient des termes qui peuvent vous sembler inconnus ou barbares. Cest la raison pour laquelle il nous semble fondamental de prsenter les dnitions de ces derniers, ainsi que de quelques autres tout aussi importants qui peuvent viter des confusions malheureuses.Dnition 0.8 Au-del de son sens ngatif, lide de problme renvoie la premire tape de la dmarche scientique. Formuler un problme est ainsi essentiel sa rsolution et permet de comprendre correctement ce qui fait problme et de voir ce qui doit tre rsolu.

Le concept de problme est intimement reli au concept dhypothse dont nous allons voir la dnition ci-dessous.Dnition 0.9 Une hypothse est toujours, dans le cadre dune thorie dj constitue ou sousjacente, une supposition en attente de conrmation ou dinrmation qui tente dexpliquer un groupe de faits ou de prvoir lapparition de faits nouveaux.

Ainsi, une hypothse peut tre lorigine dun problme thorique quil faudra formellement rsoudre.Dnition 0.10 Le postulat en physique correspond frquemment un principe dont ladmission

est ncessaire pour tablir une dmonstration nous sous-entendons que cela est une proposition non-dmontrable.Dnition 0.11 Un principe (parent proche du postulat) est donc une proposition admise comme

base dun raisonnement ou une rgle gnrale thorique qui guide la conduite des raisonnements quil faudra eectuer. En physique, il sagit galement dune loi gnrale rgissant un ensemble de phnomnes et vrie par lexactitude de ses consquences.Remarque Le mot principe est utilis avec abus dans les petites classes ou coles dingnieurs par les professeurs ne sachant, ne voulant ou ne pouvant pas dmontrer une relation.

Lquivalent du postulat ou du principe en mathmatiques est laxiome.Dnition 0.12 Un axiome est une vrit ou proposition vidente par elle-mme dont ladmission

est ncessaire pour tablir une dmonstration.Remarque Les axiomes doivent toujours tres indpendants entre eux on ne doit pas pouvoir dmontrer lun partir de lautre et non contradictoires nous disons galement parfois quils doivent tre consistants.

ix Dnition 0.13 Le corollaire est une proposition rsultant dune vrit dj dmontre. Nous pou-

vons galement dire quun corollaire est une consquence ncessaire et vidente dun thorme.Dnition 0.14 Un lemme constitue une proposition dduite dun ou de plusieurs postulats ou

axiomes et dont la dmonstration prpare celle dun thorme.Remarque Le concept de lemme, tout comme celui de corollaire, est malheureusement lexclusivit des mathmatiques.

Dnition 0.15 Une conjecture constitue une supposition ou opinion fonde sur la vraisemblance dun rsultat mathmatique.Remarque Beaucoup de conjectures jouent un rle un peu comparable des lemmes, car elles sont des passages obligs pour obtenir dimportants rsultats.

Dnition 0.16 Par-del son sens faible de conjecture, une thorie ou thorme est un ensemble

articul autour dune hypothse et tay par un ensemble de faits ou dveloppements qui lui confrent un contenu positif et rendent lhypothse bien fonde.Dnition 0.17 Une singularit est une indtermination dun calcul qui intervient par lapparition

dune division par le nombre zro. Ce terme est aussi bien utilis en mathmatique quen physique.Dnition 0.18 Une dmonstration constitue un ensemble de procdures mathmatiques suivre

pour dmontrer le rsultat dj connu ou non dun thorme.Dnition 0.19 Si le mot paradoxe signie tymologiquement contraire lopinion commune. Le sophisme quant lui, est un nonc volontairement provocateur, une proposition fausse reposant sur un raisonnement apparemment valide. Ainsi parle-t-on du fameux paradoxe de Znon alors quil ne sagit que dun sophisme. Le paradoxe ne se rduit pas de la fausset, mais implique la coexistence de la vrit et de la fausset, au point quon ne parvient plus discriminer le vrai et le faux. Le paradoxe apparat alors problme insoluble ou aporie.Remarque Ajoutons que les grands paradoxes, par les interrogations quils ont suscites, ont fait progresser la science et amen des rvolutions conceptuelles de grande ampleur, en mathmatique comme en physique thorique (les paradoxes sur les ensembles et sur linni en mathmatique, ceux la base de la relativit et de la physique quantique).

Science et foiNous verrons quen science, une thorie est normalement incomplte, car elle ne peut dcrire exhaustivement la complexit du monde rel. Il en est ainsi de toutes les thories, comme celle du Big Bang (cf. chapitre dAstrophysique) ou de lvolution des espces (cf. chapitre de Dynamique Des Populations ou de Thorie Des Jeux). Il convient de distinguer dirents courants scientiques : le ralisme est une doctrine selon laquelle les thories physiques ont pour objectif de dcrire la ralit telle quelle est en soi, dans ses composantes inobservables ; linstrumentalisme est une doctrine selon les thories sont des outils servant prdire des observations mais qui ne dcrivent pas la ralit en soi ; le ctionnalisme est le courant selon lequel le contenu rfrentiel des thories est un leurre, utile seulement pour assurer larticulation linguistique des quations fondamentales. Mme si aujourdhui les thories scientiques ont le soutien de beaucoup de spcialistes, les thories alternatives ont des arguments valables et nous ne pouvons totalement les carter. Pour autant, la cration du monde en sept jours dcrite par la Bible ne peut plus tre perue comme un possible, et bien des croyants reconnaissent quune lecture littrale est peu compatible avec ltat actuel de nos connaissances et quil est plus sage de linterprter comme une parabole. Si la science ne fournit jamais de rponse dnitive, il nest plus possible de ne pas en tenir compte. La foi, quelle soit religieuse, superstitieuse, pseudo-scientique ou autre, a au contraire pour objectif de donner des vrits absolues dune toute autre nature puisquelle relve dune conviction personnelle invriable. En fait, lune des fonctions des religions est de fournir du sens des

x

I NTRODUCTION

phnomnes qui ne sont pas explicables rationnellement. Les progrs de la connaissance entranent donc parfois une remise en cause des dogmes religieux par la science. A contrario, sauf prtendre imposer sa foi aux autres, il faut se der de la tentation naturelle de qualier de fait scientiquement prouv les extrapolations des modles scientiques au-del de leur champ dapplication. Le mot science est de plus en plus utilis pour soutenir quil existe des preuves scientiques l o il ny a que croyance. Selon ses dtracteurs cest le cas du mouvement de scientologie. Selon ces derniers, nous devrions plutt parler de sciences occultes. Les sciences occultes et sciences traditionnelles existent depuis lAntiquit, elles consistent en un ensemble de connaissances et de pratiques mystrieuses ayant pour but de pntrer et dominer les secrets de la nature. Au cours des derniers sicles, elles ont t progressivement exclues du champ de la science. Le philosophe K. Popper sest longuement interrog sur la nature de la dmarcation entre science et pseudo-science. Aprs avoir remarqu quil est possible de trouver des observations pour conrmer peu prs nimporte quelle thorie, il propose une mthodologie fonde sur la rfutabilit. Une thorie doit selon lui, pour mriter le qualicatif de scientique, pouvoir garantir limpossibilit de certains vnements. Elle devient ds lors rfutable, donc, et alors seulement, apte intgrer la science. Il surait en eet dobserver un de ces vnements pour invalider la thorie, et orienter par consquent sur une amlioration de celle-ci.

A RITHMTIQUE

1

Thorie de la dmonstration 3Crise des fondements 4 Raisonnement hypothtico-dductif 7 Calcul propositionnel 7 Calcul des prdicats 16 Dmonstrations 20

2 3

Nombres 29Bases numriques 30 Types de nombres 31

Oprateurs arithmtiques 61Relations binaires 61 Lois fondamentales de larithmtique 66 Polynmes arithmtiques 73 Valeur absolue 73 Rgles de calcul 74

4

Thorie des ensembles 77Axiomatique de Z ERMELO -F RAENKEL 79 Oprations ensemblistes 85 Fonctions et applications 90 Structures algbriques 94 Homomorphismes 105

5 6 7

Thorie des nombres 109Principe du bon ordre 109 Principe dinduction 110 Divisibilit 111

Probabilits 125Univers des vnements 125 Analyse combinatoire 130 Chanes de M ARKOV 134

Statistiques 137chantillons 138 Moyennes 138 Types de variables 148 Lois de distributions 156 Estimateurs de vraisemblance 198 Intervalles de conance 204 Loi faible des grands nombres 210 Fonction caractristique 213 Thorme central limite 215 Tests dhypothse 218 Calculs derreurs/incertitudes 228

1Thorie de la dmonstrationous avons choisi de commencer ltude de la mathmatique applique par la thorie qui nous semble la plus fondamentale et la plus importante dans le domaine des sciences pures et exactes. La thorie de la dmonstration et du calcul propositionnel, ou logique, a trois objectifs dans le cadre de ce site : 1. apprendre au lecteur comment raisonner et dmontrer et cela indpendamment de la spcialisation tudie ; 2. dmontrer quune dmonstration (son processus) est indpendante du langage utilis ; 3. se prparer la thorie de la logique et au thorme dincompltude de Gdel ainsi quaux automates (cf. chapitre dInformatique Thorique). Le dernier point est le plus passionnant car si nous dnissons une religion comme un systme de pense qui contient des armations indmontrables, alors elle contient des lments de foi, et Gdel nous enseigne que les mathmatiques sont non seulement une religion, mais que cest la seule religion capable de prouver quelle en est une 1 2 . Souvent, quand un tudiant arrive dans une classe suprieure, il a surtout appris calculer, utiliser des algorithmes. Il a trs peu appris raisonner. Pour tous les raisonnements, le support visuel est fort, et les personnes qui ne voient pas quen traant telle ou telle courbe droite la solution apparat ou qui ne voient pas dans lespace sont trs pnalises. Lors des tudes secondaires, nous manipulons dj des objets inconnus, mais cest surtout pour faire des calculs, et quand nous raisonnons sur des objets reprsents par des lettres, nous pouvons remplacer ceux-ci visuellement par un nombre rel, un vecteur, etc. partir dun certain niveau, nous demandons aux personnes de raisonner sur des structures plus abstraites, et donc de travailler sur des objets inconnus qui sont des lments dun ensemble lui-mme inconnu, par exemple les lments dun groupe quelconque. Ce support visuel nexiste alors plus. Chap4 Nous demandons ainsi souvent aux tudiants de raisonner, de dmontrer des proprits, mais personne ne leur a jamais appris raisonner convenablement, crire des preuves. Si nous demandons un tudiant de licence de mathmatiques ce quest une dmonstration, il a quelque dicult rpondre. Il peut dire que cest un texte dans lequel on trouve des mots cls : donc, parce que, si, si et seulement si, prenons un x tel que, supposons que, cherchons une contradiction, etc. Mais il est incapable de donner la grammaire de ces textes ni mme ces rudiments, et dailleurs, ses enseignants, sils nont pas suivi de cours, en seraient probablement incapables aussi. Pour comprendre cette situation, rappelons que pour parler un enfant na pas besoin de connatre la grammaire. Il imite son entourage avec succs : un enfant de six ans sait utiliser des phrases dj compliques quant la structure grammaticale sans avoir jamais appris les rgles courantes de grammaire. La plupart des enseignants ne connaissent pas non plus la grammaire du raisonnement leur processus dimitation a fonctionn correctement et ils raisonnent sans erreur. Lexprience montre que ce processus dimitation est susamment bien intgr par les trs bons tudiants mais reste utopique chez la plupart.1. Il est fortement conseill de lire en parallle ce chapitre, ceux sur la thorie des automates et de lalgbre de Boole disponibles dans la section dinformatique thorique du site. 2. Il faut prendre cette thorie comme une curiosit sympathique qui namne fondamentalement pas grand chose except des mthodes de raisonnement. Par ailleurs, son objectif nest pas de dmontrer que tout est dmontrable mais que toute dmonstration peut se faire sur un langage commun partir dun certain nombre de rgles.

N

4

T HORIE DE LA DMONSTRATION

Tant que le degr de complexit est faible, la grammaire ne sert rien, mais quand il augmente ou quand on ne comprend pas pourquoi quelque chose est faux, il devient ncessaire de faire un peu de grammaire pour pouvoir progresser. Les enseignants et les tudiants connaissent bien la situation suivante : dans un devoir, le correcteur a barr toute une page dun grand trait rouge et mis faux dans la marge. Quand ltudiant demande ce qui est faux, le correcteur ne peut que dire des choses du genre a na aucun rapport avec la dmonstration demande, rien nest juste, ..., ce qui naide videmment pas ltudiant comprendre. Cela vient en partie, du fait que le texte rdig par ltudiant utilise les mots voulus mais dans un ordre plus ou moins alatoire et quon ne peut donner de sens lassemblage de ces mots. De plus, lenseignant na pas les outils ncessaires pour pouvoir expliquer ce qui ne va pas. Il faut donc les lui donner ! Ces outils existent mais sont assez rcents. La thorie de la dmonstration est une branche de la logique mathmatique dont lorigine est la crise des fondements : il y a eu un doute sur ce que nous avions le droit de faire dans un raisonnement mathmatique. Des paradoxes sont apparus, et il a alors t ncessaire de prciser les rgles de dmonstration et de vrier que ces rgles ne sont pas contradictoires. Cette thorie est apparue il y a environ un sicle, ce qui est trs peu puisque lessentiel des mathmatiques enseignes en premire moiti de luniversit est connu depuis deux ou trois cents ans.

1.1 Crise des fondements1.1.1 IntroductionPour les premiers Grecs, la gomtrie tait considre comme la forme la plus haute du savoir, une puissante cl pour les mystres mtaphysiques de lUnivers. Elle tait plutt une croyance mystique, et le lien entre le mysticisme et la religion tait rendu explicite dans des cultes comme ceux des Pythagoriciens. Aucune culture na depuis di un homme pour avoir dcouvert un thorme gomtrique ! Plus tard, les mathmatiques furent considres comme le modle dune connaissance a priori dans la tradition aristotlicienne du rationalisme. Ltonnement des Grecs pour les mathmatiques ne nous a pas quitt, on le retrouve sous la traditionnelle mtaphore des mathmatiques comme Reine des Science. Il sest renforc avec les succs spectaculaires des modles mathmatiques dans la science, succs que les Grecs navaient pas prvus. Depuis la dcouverte par Isaac Newton du calcul intgral et de la loi du carr inverse de la gravit, la n des annes 1600, les sciences phnomnales et les plus hautes mathmatiques taient restes en troite symbiose au point quun formalisme mathmatique prdictif tait devenu le signe distinctif dune science dure. Aprs Newton, pendant les deux sicles qui suivirent, la science aspira ce genre de rigueur et de puret qui semblaient inhrentes aux mathmatiques. La question mtaphysique semblait simple : les mathmatiques possdaient une connaissance a priori parfaite, et parmi les sciences, celles qui taient capables de se mathmatiser le plus parfaitement taient les plus ecaces pour la prdiction des phnomnes . La connaissance parfaite consistait donc dans un formalisme mathmatique qui, une fois atteint par la science et embrassant tous les aspects de la ralit, pouvait fonder une connaissance empirique a posteriori sur une logique rationnelle a priori. Ce fut dans cet esprit que Jean-Antoine Nicolas de Cartitat, marquis de Condorcet (philosophe et mathmaticien franais), entreprit dimaginer la description de lUnivers entier comme un ensemble dquation direntielles partielles se rsolvant les unes par les autres. La premire faille dans cette image inspiratrice apparut dans la seconde moiti du 19e sicle, quand Riemann et Lobachevsky prouvrent sparment que laxiome des parallles dEuclide pouvait tre remplac par dautres qui produisaient des gomtries consistantes (nous reviendrons sur ce terme plus loin). La gomtrie de Riemann prenait modle sur une sphre, celle de Lobachevsky, sur la rotation dun hyperbolode. Limpact de cette dcouverte a t obscurci plus tard par de grands chamboulements, mais sur le moment, il fut un coup de tonnerre dans le monde intellectuel. Lexistence de systmes axiomatiques mutuellement inconsistants, et dont chacun pouvait servir de modle lUnivers phnomnal, remettait entirement en question la relation entre les mathmatiques et la thorie physique. Quand on ne connaissait quEuclide, il ny avait quune gomtrie possible. On pouvait croire que les axiomes dEuclide constituaient un genre de connaissance parfaite a priori sur la gomtrie

1.1 Crise des fondements

5

dans le monde phnomnal. Mais soudain, nous avons eu trois gomtries, embarrassantes pour les subtilits mtaphysique. Pourquoi aurions-nous choisir entre les axiomes de la gomtrie plane, sphrique et hyperbolique comme descriptions de la gomtrie du rel ? Parce que toutes les trois sont consistantes, nous ne pouvons en choisir aucune comme fondement a priori - le choix doit devenir empirique, bas sur leur pouvoir prdictif dans une situation donne. Bien sr, Les thoriciens de la physique ont longtemps t habitus choisir des formalismes pour poser un problme scientique. Mais il tait admis largement, si ce nest inconsciemment, que la ncessit de procder ainsi ad hoc tait fonction de lignorance humaine, et, quavec de la logique ou des mathmatiques assez bonnes, on pouvait dduire le bon choix partir de premiers principes, et produire des descriptions a priori de la ralit, qui devaient tre conrmes aprs coup par une vrication empirique. Cependant, la gomtrie euclidienne, considre pendant plusieurs centaines dannes comme le modle de la perfection axiomatique des mathmatiques, avait t dtrne. Si lon ne pouvait connatre a priori quelque chose daussi fondamental que la gomtrie dans lespace, quel espoir restait-il pour une pure thorie rationnelle qui embrasserait la totalit de la nature ? Psychologiquement, Riemann et Lobachevsky avaient frapp au cur de lentreprise mathmatique telle quelle avait t conue jusqualors. De plus, Riemann et Lobachevsky remettaient la nature de lintuition mathmatique en question. Il avait t facile de croire implicitement que lintuition mathmatique tait une forme de perception, une faon dentrevoir le noumne platonicien derrire la ralit. Mais avec deux autres gomtries qui bousculaient celle dEuclide, personne ne pouvait plus tre sr de savoir quoi le noumne ressemblait. Les mathmaticiens rpondirent ce double problme avec un excs de rigueur, en essayant dappliquer la mthode axiomatique toutes les mathmatiques. Dans la priode pr-axiomatique, les preuves reposaient souvent sur des intuitions communment admises de la ralit mathmatique, qui ne pouvaient plus tre considres automatiquement comme valides. La nouvelle faon de penser les mathmatiques conduisait une srie de succs spectaculaires. Pourtant cela avait aussi un prix. La mthode axiomatique rendait la connexion entre les mathmatiques et la ralit phnomnale toujours plus troite. En mme temps, des dcouvertes suggraient que les axiomes mathmatiques qui semblaient tre consistants avec lexprience phnomnale pouvait entraner de vertigineuses contradictions avec cette exprience. La majorit des mathmaticiens devinrent rapidement des formalistes, soutenant que les mathmatiques pures ne pouvaient qutre considres philosophiquement comme une sorte de jeu labor qui se jouait avec des signes sur le papier 3 . La croyance platonicienne en la ralit noumnale des objets mathmatiques, lancienne manire, semblait bonne pour la poubelle, malgr le fait que les mathmaticiens continuaient se sentir comme les platoniciens durant le processus de dcouverte des mathmatiques. Philosophiquement, donc, la mthode axiomatique conduisait la plupart des mathmaticiens abandonner les croyances antrieures en la spcicit mtaphysique des mathmatiques. Elle produisit aussi la rupture contemporaine entre les mathmatiques pures et appliques. La plupart des grands mathmaticiens du dbut de la priode moderne Newton, Leibniz, Fourier, Gauss et les autres soccupaient aussi de science phnomnale. La mthode axiomatique avait couv lide moderne du mathmaticien pur comme un super esthte, insoucieux de la physique. Ironiquement, le formalisme donnait aux purs mathmaticiens un mauvais penchant lattitude platonicienne. Les chercheurs en mathmatiques appliques cessrent de ctoyer les physiciens et apprirent se mettre leur trane. Ceci nous emmne au dbut du 20e sicle. Pour la minorit assige des platoniciens, le pire tait encore venir. Cantor, Frege, Russell et Whitehead montrrent que toutes les mathmatiques pures pouvaient tre construites sur le simple fondement axiomatique de la thorie des ensembles. Cela convenait parfaitement aux formalistes : les mathmatiques se runiaient, du moins en principe, partir dun faisceau de petits jeux dtachs dun grand. Les platoniciens aussi taient satisfaits, sil en survenait une grande structure, cl de vote consistante pour toutes les mathmatiques, la spcicit mtaphysique des mathmatiques pouvait encore tre sauve.3. Cest la thorie qui sous-tend la prophtique qualication des mathmatiques de systme contenu nul par R. Heinlein.

6


Dune faon ngative, pourtant, un platonicien eut le dernier mot. K. Gdel mit son grain de sable dans le programme formaliste daxiomatisation quand il dmontra que tout systme daxiomes assez puissant pour inclure les entiers devait tre soit inconsistant contenir des contradictions soit incomplet trop faible pour dcider de la justesse ou de la fausset de certaines armations du systme. Et cest plus ou moins o en sont les choses aujourdhui. Les mathmaticiens savent que de nombreuses tentatives pour faire avancer les mathmatiques comme une connaissance a priori de lUnivers doivent se heurter de nombreux paradoxes et limpossibilit de dcider quel systme axiomatique dcrit les mathmatiques relles. Ils ont t rduits esprer que les axiomatisations standard ne soient pas inconsistantes mais incompltes, et se demander anxieusement quelles contradictions ou quels thormes indmontrables attendent dtre dcouverts ailleurs. Cependant, sur le front de lempirisme, les mathmatiques taient toujours un succs spectaculaire en tant quoutil de construction thorique. Les grands succs de la physique du 20e sicle la relativit gnrale et la physique quantique poussaient si loin hors du royaume de lintuition physique, quils ne pouvaient tre compris quen mditant profondment sur leurs formalismes mathmatiques, et en prolongeant leurs conclusions logiques, mme lorsque ces conclusions semblaient sauvagement bizarres. Quelle ironie. Au moment mme o la perception mathmatique en venait paratre toujours moins able dans les mathmatiques pures, elle devenait toujours plus indispensable dans les sciences phnomnales. loppos de cet arrire-plan, lapplicabilit des mathmatiques la science phnomnale pose un problme plus pineux quil napparat dabord. Le rapport entre les modles mathmatiques et la prdiction des phnomnes est complexe, pas seulement dans la pratique mais dans le principe. Dautant plus complexe que, comme nous le savons maintenant, il y a des faons daxiomatiser les mathmatiques qui sexcluent ! Mais pourquoi existe-t-il seulement de bons choix de modle mathmatique ? Cest--dire, pourquoi y a-t-il un formalisme mathmatique, par exemple pour la physique quantique, si productif quil prdit rellement la dcouverte de nouvelles particules observables ? Pour rpondre cette question nous observerons quelle peut, aussi bien, fonctionner comme une sorte de dnition. Pour beaucoup de systme phnomnaux, de tels formalismes prdictifs exacts nont pas t trouvs, et aucun ne semble plausible. Les potes aiment marmonner sur le cur des hommes, mais on peut trouver des exemples plus ordinaires : le climat, o le comportement dune conomie suprieure celle dun village, par exemple, systmes si chaotiquement interdpendants que la prdiction exacte est eectivement impossible.

1.1.2 ParadoxesDs lantiquit, certains logiciens avaient constat la prsence de nombreux paradoxes au sein de la rationalit. En fait, nous pouvons dire que malgr leur nombre, ces paradoxes ne sont que les illustrations dun petit nombre de structures paradoxales. Attardons nous exposer titre de culture de gnrale les plus connus.Paradoxe 1.1 (Paradoxe de la classe des classesRussell) Il existe deux types de classes : celles qui se contiennent elles-mmes (ou classes rexives : la classe des ensembles non-vides, la classe des classes...) et celles qui ne se contiennent pas elles-mmes (ou classes irrexives : la classe des travaux rendre, la classe des oranges sanguines...). La question est la suivante : la classe des classes irrexives est-elle elle mme rexive ou irrexive ? Si elle est rexive, elle se contient et se trouve range dans la classe des classes irrexives quelle constitue, ce qui est contradictoire. Si elle est irrexive, elle doit gurer dans la classe des classes irrexives quelle constitue et devient ipso facto rexive, nous sommes face une nouvelle contradiction. Paradoxe 1.2 (Paradoxe du bibliothcaireGonseth) Dans une bibliothque, il existe deux types de catalogues. Ceux qui se mentionnent eux-mmes et ceux qui ne se mentionnent pas. Un bibliothcaire doit dresser le catalogue de tous les catalogues qui ne se mentionnent pas eux-mmes. Arriv au terme de son travail, notre bibliothcaire se demande sil convient ou non de mentionner le catalogue quil est prcisment en train de rdiger. ce moment, il est frapp de perplexit. Si ne le mentionne pas, ce catalogue sera un catalogue qui ne se mentionne pas et qui devra ds lors gurer dans la liste des catalogues ne se mentionnant pas eux-mmes. Dun autre ct, sil le mentionne, ce catalogue deviendra un catalogue qui se mentionne et qui ne doit donc pas gurer dans ce catalogue, puisque celui-ci est le catalogue des catalogues qui ne se mentionnent pas.

1.2 Raisonnement hypothtico-dductif

7

Paradoxe 1.3 (Paradoxe du menteur (variante)) Dnissons provisoirement le mensonge comme

laction de formuler une proposition fausse. Le pote crtois pimnide arme : Tous les Crtois sont des menteurs , soit la proposition P. Comment dcider de la valeur de vrit de P ? Si P est vraie, comme pimnide est Crtois, P doit tre fausse. Il faut donc que P soit fausse pour pouvoir tre vraie, ce qui est contradictoire. P est donc fausse. Remarquons quon ne peut pas en dduire, comme dans le vritable paradoxe du menteur, que P doit aussi tre vraie.

1.2 Raisonnement hypothtico-dductifLe raisonnement hypothtico-dductif est, nous le savons, la capacit qua lapprenant de dduire des conclusions partir de pures hypothses et pas seulement dune observation relle. Cest un processus de rexion qui tente de dgager une explication causale dun phnomne quelconque (nous y reviendrons lors de nos premiers pas en physique). Lapprenant qui utilise ce type de raisonnement commence par formuler une hypothse et essaie ensuite de conrmer ou dinrmer son hypothse selon le schma synoptique 1.1. QLa procdure dductive consiste tenir pour vrai,dnitions hypothses

processus de dduction

rsultats thoriques

processus dobservations empiriques

modication des hypothses

conrme

ne conrme pas

acceptation provisoire rejet F IGURE 1.1 Schma synoptique de raisonnement hypothtico-dductif

titre provisoire, cette proposition premire que nous appelons, en logique le prdicat (voir plus bas) et en tirer toutes les consquences logiquement ncessaires, cest--dire en rechercher les implications 4 .Exemple 1.1 Soit la proposition P : X est un homme, elle implique la proposition suivante Q :

X est mortel. Lexpression P Q est un implication prdicative (do le terme prdicat). Il ny a pas dans cet exemple de cas o nous puissions noncer P sans Q. Cet exemple est celui dune implication stricte, telle que nous la trouvons dans le syllogisme (gure logique du raisonnement).

1.3 Calcul propositionnelLe calcul propositionnel ou logique propositionnelle est un prliminaire absolument indispensable pour aborder une formation en sciences, philosophie, droit, politique, conomie, etc. Ce type4. Des spcialistes ont montr que le raisonnement hypothtico-dductif slabore progressivement chez lenfant, partir de 6-7ans, et que ce type de raisonnement nest utilis systmatiquement, en partant dune fonction propositionnelle stricte qu partir de 11-12 ans.

8


de calcul autorise des procdures de dcision ou tests. Ceux-ci permettent de dterminer dans quel cas une expression (proposition) logique est vraie et en particulier si elle est toujours vraie 5 6 .Dnition 1.1 Une expression toujours vraie quel que soit le contenu linguistique des variables qui la composent est appele une expression valide, une tautologie ou encore une loi de la logique propositionnelle. Dnition 1.2 Un expression toujours fausse est appele une contradiction ou antologie. Dnition 1.3 Une expression qui est parfois vraie, parfois fausse est appele une expression contin-

gente.Dnition 1.4 Nous appelons assertion une expression dont nous pouvons dire sans ambigut sil elle est vraie ou fausse. Dnition 1.5 Le langage objet est le langage utilis pour crire les expressions logiques. Dnition 1.6 Le mtalangage est le langage utilis pour parler du langage objet dans la langue

courante.

1.3.1 PropositionsDnition 1.7 En logique, une proposition est une armation qui a un sens. Cela veut dire que nous pouvons dire sans ambigut si cette armation est vraie (V) ou fausse (F). Cest ce que nous appelons le principe du tiers exclu. Exemple 1.2 Je mens nest pas une proposition. Si nous supposons que cette armation est

vraie, elle est une armation de sa propre invalidit, donc nous devrions conclure quelle est fausse. Mais si nous supposons quelle est fausse, alors lauteur de cette armation ne ment pas, donc il dit la vrit, aussi la proposition serait vraie.Dnition 1.8 Une proposition en logique binaire o les propositions sont soit vraies, soit fausses nest donc jamais vraie et fausse la fois. Cest que nous appelons le principe de non-contradiction.

Ainsi, une proprit sur lensemble E des propositions est une application P de E dans lensemble des valeurs de vrit : P : E (V, F ) (1.1)

Nous parlons de sous-ensemble associ lorsque la proposition engendre uniquement une partie E de E et inversement.Exemple 1.3 Dans E = N, si P (x) snonce x est pair, alors P = (0, 2, 4, . . . , 2k, . . .) ce qui estChap4 bien seulement un sous-ensemble associe de E mais de mme cardinal .

Dnition 1.9 Soit P une proprit sur lensemble E. Une proprit Q sur E est une ngation de P si et seulement si, pour tout x E : Q(x) est F si P (x) est V ; P (x) est V si P (x) est F .

Nous pouvons rassembler ces conditions dans une table dite table de vrit dont un exemple est donn dans le tableau 1.1. En dautres termes, P et Q ont toujours des valeurs de vrit contraires. Nous noterons ce genre dnonc Q est une ngation de P : Q P (1.2)

Remarque Les expressions doivent tre des expressions bien formes (souvent abrg ebf ). Par dnition, toute variable est une expression bien forme, alors P est une expression bien forme. Si P et Q sont des expressions bien formes, alors P Q est une expression bien forme (lexpression je mens nest pas bien forme car elle se contredit elle-mme).5. Il existe des expressions qui ne sont eectivement pas des assertions. Par exemple, lnonc : cet nonc est faux , est un paradoxe qui ne peut tre ni vrai, ni faux. 6. Soit un expression logique A. Si celle-ci est une tautologie, nous la notons frquemment A et sil lexpression est une contradiction, nous la notons A .

o le symbole est le connecteur de ngation.

1.3 Calcul propositionnel

9

P V F

Q F V

TABLEAU 1.1 Exemple de table de vrit

1.3.2 ConnecteursIl y a dautres types de connecteurs en logique. Soit P et Q deux proprits dnies sur le mme ensemble E. P Q (P ou Q) est une proprit sur E dnie par : P Q est vraie si au moins lune des proprits P , Q est vraie ; P Q est fausse sinon. Nous pouvons crer la table de vrit du connecteur OU ou connecteur de disjonction : P V V F F Q V F V F P Q V V V F

TABLEAU 1.2 Table de vrit du connecteur OU ()

Il est facile de se convaincre que, si les parties P , Q de E sont respectivement associes aux proprits P , Q que P Q (voir thorie des ensembles) est associ P Q. P P QQ (1.3)

P QP Q Le connecteur est associatif. Pour sen convaincre, il sut de faire une table vrit o nous vrions que : [P (Q R)] [(P Q) R] (1.4)

Il existe galement le connecteur ET ou connecteur de conjonction pour que que soient P , Q deux proprits dnies sur E, P Q est une proprit sur E dnie par : P Q est vraie si toutes les deux proprits P, Q sont vraies ; P Q est fausse sinon. Nous pouvons crer la table de vrit du connecteur : P V V F F Q V F V F P Q V F F F

TABLEAU 1.3 Table de vrit du connecteur ET ()

Il est galement facile de se convaincre que, si les parties P , Q de E sont respectivement associes aux proprits P , Q que P Q (voir thorie des ensembles) est associ P Q : P P QQ (1.5)

P QP Q

10


Le connecteur est associatif. Pour sen convaincre, il sut aussi de faire une table vrit o nous vrions que : [P (Q R)] [(P Q) R] (1.6)

Les connecteurs , sont distributifs lun sur lautre. laide dune simple table de vrit, nous prouvons que : [P (Q R)] [(P Q) (P R)] ainsi que : [P (Q R)] [(P Q) (P R)] Une ngation de P Q est [(P ) (Q)] une ngation de P Q est [(P ) (Q)] tel que : (P Q) [(P ) (Q)] (P Q) [(P ) (Q)] (1.9) (1.8) (1.7)

nouveau, ces proprits peuvent se dmontrer par une simple table de vrit 7 . Revenons maintenant sur le connecteur dimplication logique not 8 . Soient P , Q deux proprits sur E. P Q est une proprit sur E dnie par : P Q est fausse si P est vraie et Q fausse ; P Q est vraie sinon. En dautres termes, P implique logiquement Q signie que Q est vrai pour toute valuation pour laquelle P est vraie. Limplication reprsente donc le si... alors... La table de vrit de limplication est indique dans le tableau 1.4. Si P Q, pour que Q soit vraie, il sut que P soit vraie : P V V F F Q V F V F P Q V F V V

TABLEAU 1.4 Table de vrit de limplication

eectivement limplication sera vraie si P est vraie ou fausse selon la table de vrit. Donc P est une condition susante de Q. Dun autre ct, P Q est quivalent Q P . Donc, si Q est fausse, il est impossible que P soit vraie. Finalement, Q est une condition ncessaire de P .Exemple 1.4 Soit la proposition : Si tu obtiens ton diplme, je tachte un ordinateur. Parmi tous les cas, un seul correspond une promesse non tenue : celui o lenfant son diplme, et na toujours pas dordinateur (deuxime ligne dans le tableau). Et le cas o il na pas le diplme, mais reoit quand mme un ordinateur ? Il est possible quil ait t longtemps malade et a rat un semestre, et le pre a le droit dtre bon. Que signie cette promesse, que nous crirons aussi : Tu as ton diplme je tachte un ordinateur ? Exactement ceci : Si tu as ton diplme, cest sr, je tachte un ordinateur (je ne peux pas ne pas lacheter) Si tu nas pas ton diplme, je nai rien dit Exemple 1.5 De toute proposition fausse nous pouvons dduire toute propositions (deux dernires lignes). Cest un exemple plutt anecdotique : dans un cours de Russell portant sur le fait que dune proposition fausse, toute proposition peut tre dduite, un tudiant lui posa la question suivante :7. Pour voir les dtails de tous les oprateurs logiques, le lecteur devra se rendre dans le chapitre dAlgbre De Boole (cf. section dInformatique Thorique) o lidentit, la double ngation, lidempotence, lassociativit, la distributivit, les relations de De Morgan sont prsentes plus formellement. 8. Dans certains ouvrages sur le calcul propositionnel, ce connecteur est not et dans le cadre de la thorie de la dmonstration nous lui prfrons souvent le symbole .


11

Prtendez-vous que de 2 + 2 = 5, il sensuit que vous tes le pape ? Oui , t Russell Et pourriez-vous le prouver ? , demanda ltudiant sceptique Certainement ! , rplique Russell, qui proposa sur le champ la dmonstration suivante : 1. Supposons que 2 + 2 = 5 2. Soustrayons 2 de chaque membre de lgalit, nous obtenons 2 = 3 3. Par symtrie, 3 = 2 4. Soustrayant 1 de chaque ct, il vient 2 =1

Maintenant le pape et moi sommes deux. Puisque 2 = 1, le pape et moi sommes un. Par suite, je suis le pape. Le connecteur dimplication est essentiel en mathmatiques, philosophie, etc. Cest un des fondements de toute dmonstration, preuve ou dduction. Le connecteur dimplication a les proprits suivantes : P Q [(Q) (P )] P Q [(P ) Q] consquence de la dernire proprit : (P Q) [P (Q)] (P Q) (P Q) (Q P ) (1.11) (1.10)

Le connecteur dquivalence logique ou bi-conditionnel not ou signiant par dnition que : (1.12) en dautres termes, la premire expression a la mme valeur pour toute valuation de la deuxime. Ce que nous pouvons vrier laide dune table de vrit 1.5. P Q signie bien que P et Q P V V F F Q V F V F P Q V F V V QP V V F V P Q V F F V

TABLEAU 1.5 Table de vrit de lquivalence

ont toujours la mme valeur de vrit ou encore P et Q sont quivalents. Cest vrai si P et Q ont mme valeur, faux dans tout cas contraire. Bien videmment (cest une tautologie) : (P Q) [(P ) (Q)] (1.13)

La relation P Q quivaut donc ce que P soit une condition ncessaire et susante de Q et ce que Q soit une condition ncessaire et susante de P . Par consquent, les conditions de type ncessaire, susant, ncessaire et susant peuvent tre reformules avec les termes seulement si, si, si et seulement si. Ainsi : 1. P Q traduit le fait que Q est une condition ncessaire pour P ou dit autrement, P est vraie seulement si Q est vraie (dans le table de vrit, lorsque P Q prend la valeur 1 on constate bien que P vaut 1 seulement si Q vaut 1 aussi). On dit aussi, si P est vraie alors Q est vraie. 2. P Q ou ce qui revient au mme Q P traduit le fait que Q est une condition susante pour P ou dit autrement, P est vraie si Q est vraie (dans le table de vrit, lorsque Q P prend la valeur 1 on constate bien que P vaut 1 si Q vaut 1 aussi). 3. P Q traduit le fait que Q est une condition ncessaire et susante pour P ou dit autrement, P est vraie si et seulement si Q est vraie (dans le table de vrit, lorsque P Q prend la valeur 1 on constate bien que P vaut 1 si Q vaut 1 et seulement si Q vaut 1).

12


Remarque Lexpression si et seulement si correspond donc une quivalence logique et ne peut tre utilise pour dcrire un implication.

La premire tape du calcul propositionnel est donc la formalisation des noncs du langage naturel. Pour raliser ce travail, le calcul propositionnel fournit nalement trois types doutils : 1. Les variables propositionnelles (P, Q, R, . . .) symbolisent des propositions simples quelconques. Si la mme variable apparat plusieurs fois, elle symbolise chaque fois la mme proposition. 3. Les signes de ponctuation se rduisent aux seules parenthses ouvrante et fermante qui organisent la lecture de manire viter toute ambigut.Description La ngation est un oprateur qui ne porte que sur une proposition, il est unaire ou monadique. Il ne pleut pas scrit P . Cet nonc est vrai si et seulement si P est faux. Lusage classique de la ngation est caractris par la loi de double ngation : P est quivalent P . La conjonction ou produit logique est un oprateur binaire, elle met en relation deux propositions. Tout homme est mortel ET Ma voiture perd de lhuile scrit (P Q). Cette dernire expression est vraie si et seulement si P est vrai et Q est vrai. La disjonction ou somme logique est, elle aussi, un oprateur binaire. (P Q) est vrai si et seulement si P est vrai ou Q est vrai. Nous pouvons comprendre ce OU de deux faons : soit de manire inclusive, soit de manire exclusive. Dans le premier cas, (P Q) est vrai si P est vrai, si Q est vrai ou si P et Q sont tous deux vrais. Dans le second cas, (P Q) est vrai si P est vrai ou si Q est vrai mais pas si les deux le sont. La disjonction du calcul propositionnel est le OU inclusif et on donne au OU exclusif le nom dalternative. Limplication est galement un oprateur binaire. Elle correspond, en gros, au schma linguistique Si...alors... : si jai le temps, jirai au cinma scrit P Q. P Q est faux si P est vrai et Q est faux. Si le consquent (ici Q) est vrai, limplication (P Q) est vraie. Lorsque lantcdent (ici P ) est faux, limplication est toujours vraie. Cette dernire remarque peut tre comprise si lon se rfre des noncs de type : Si on pouvait mettre Paris en bouteille, on utiliserait la tour Eiel comme bouchon. En rsum, une implication est fausse si et seulement si son antcdent est vrai et son consquent est faux. La bi-implication est, elle aussi, binaire : elle symbolise les expressions ...si et seulement si... et ...est quivalent ... Lquivalence entre deux propositions est vraie si celles-ci ont la mme valeur de vrit. La biimplication exprime donc aussi une forme didentit et cest pourquoi elle est souvent utilise dans les dnitions.TABLEAU 1.6 Rcapitulatif des symboles

2. Les cinq oprateurs logiques :, , , ,

Symbole

Utilisation P

(P Q)

(P Q)

(P Q)

(P Q)

Il est possible dtablir des quivalences entre ces oprateurs. Nous avons dj vu comment le biconditionnel pouvait se dnir comme un produit de conditionnels rciproques, voyons maintenant dautres quivalences : (P Q) (P Q) (P Q) (P Q) (P Q) (P Q) Les oprateurs classiques , , peuvent donc tre dnis laide de , grce aux lois dquivalence entre oprateurs. Sont noter galement les deux relations de De Morgan (cf. chapitre (P Q) (P Q)

(1.14)


13

dAlgbre de Boole) : (P Q) (P Q) (P Q) (P Q) Elles permettent de transformer la disjonction en conjonction et vice-versa : (P Q) (P Q) (P Q) (P Q) (1.16) (1.15)

1.3.3 Procdures de dcisionNous avons introduit prcdemment les lments de base nous permettant doprer sur des expressions partir de proprits (variables propositionnelles) sans toutefois dire grand chose quant la manipulation de ces expressions. Alors, il convient maintenant de savoir quen calcul propositionnel quil existe deux manires dtablir quune proposition est un loi de la logique propositionnelle. Nous pouvons 9 : 1. employer des procdures non axiomatises ; 2. recourir des procdures axiomatiques et dmonstratives.

Procdures de dcisions non axiomatises Plusieurs de ces mthodes existent mais nous nous limiterons ici la plus simple et la plus parlante dentre elles, celle du calcul matriciel, souvent appele aussi mthodes des tables de vrit. La procdure de construction est comme nous lavons vu prcdemment assez simple. Eectivement, la valeur de vrit dune expression complexe est fonction de la valeur vrit des noncs plus simples qui la composent, et nalement fonction de la valeur de vrit des variables propositionnelles qui la composent. En envisageant toutes les combinaisons possibles des valeurs de vrit des variables de propositionnelles, nous pouvons dterminer les valeurs de vrit de lexpression complexe. Les tables de vrit permettent donc de dcider, propos de toute proposition, si celle-ci est une tautologie (toujours vraie), une contradiction (toujours fausse) ou une expression contingente (parfois vraie, parfois fausse). Nous pouvons ainsi distinguer quatre faons de combiner les variables propositionnelles, les parenthses et les connecteurs dnis dans le tableau 1.7. La mthode des tables de vrit permet denom 1 2 3 4 nonc mal form tautologie contradiction nonc contingent description non-sens : ni vrai, ni faux nonc toujours vrai nonc toujours faux nonc parfois vrai, parfois faux exemple (P )Q (P P ) (P Q) P Q

TABLEAU 1.7 Variables propositionnelles

dterminer le type dexpression bien forme face auquel nous nous trouvons. Elle nexige en principe aucune invention, cest une procdure mcanique. Les procdures axiomatises, en revanche, ne sont pas entirement mcaniques. Inventer une dmonstration dans le cadre dun systme axiomatis demande parfois de lhabilit, de lhabitude ou de la chance. Pour ce qui est des tables de vrit, voici la marche suivre : lorsquon se trouve face un expression bien forme, ou fonction de vrit, nous commenons par dterminer combien de variables propositionnelles distinctes nous avons aaire. Ensuite, nous examinons les dirents arguments qui constituent cette expression. Nous construisons alors un tableau comprenant 2n ranges (n tant le nombre de variables) et un nombre de colonnes gal au nombre darguments plus des colonnes pour lexpression elle-mme et ses autres composantes. Nous attribuons alors aux variables les direntes combinaisons de vrit et de fausset qui peuvent leur tre confres (la vrits est exprime dans la table par un 1 et la9. Dans de nombreux ouvrages ces procdures sont prsentes avant mme la structure du langage propositionnel. Nous avons choisi de faire le contraire pensant que lapproche serait plus aise.

14


fausset par un 0). Chacune des ranges correspond un monde possible et la totalit des ranges constitue lensemble des mondes possibles. Il existe, par exemple, un mode possible dans lequel P est une proposition vraie tandis que Q est fausse.

Procdures de dcisions axiomatises Laxiomatisation dune thorie implique, outre la formalisation de celle-ci, que nous partions dun nombre ni daxiomes et que, grce la transformation rgle de ces derniers, que nous puissions obtenir tous les thormes de cette thorie. Nous pardons donc de quelques axiomes dont la vrit est pose (et non dmontre). Nous dterminons des rgles de dduction permettant de manipuler les axiomes ou toute expression obtenue partir de ceux-ci. Lenchanement de ces dductions est une dmonstration qui conduit un thorme, une loi. Nous allons sommairement prsenter deux systmes axiomatiques, chacun tant constitu daxiomes utilisant deux rgles dites rgles dinfrence (rgles intuitives) particulires :Rgle 1.1 (modus ponens) Si nous avons prouv A et A B, alors nous pouvons dduire B. A Exemple 1.6 De x > y et (x > y) (y < x) nous pouvons dduire (y < x)

est appel la prmisse mineure et A B la prmisse majeure de la rgle du modus ponens.

Rgle 1.2 (substitution) Nous pouvons dans un schma daxiome remplacer une lettre par une

formule quelconque, pourvue que toutes les lettres identiques soient remplaces par des formules identiques. Donnons titre dexemple, deux systmes axiomatiques : le systme axiomatique de Whitehead et Russell, le systme axiomatique de Lukasiewicz.Systme axiomatique de W HITEHEAD et R USSELL Il adopte comme symboles primitifs , et

dnit , , partir de ces derniers de la manire suivante : (A B) (A B) (A B) (A B) (B A) (A B) A B

(1.17)

Nous avions dj prsent plus haut quelque uns de ces lments. Ce systme comprend cinq axiomes, assez vidents en soi plus les deux rgles dinfrence. Les axiomes sont donns ici en utilisant des symboles non primitifs, comme le faisaient Whitehead et Russell 10 :Axiome 1.1 (A A) A Axiome 1.2 B (A B)

Axiome 1.3 (A B) (B A)

Axiome 1.4 (A (B C)) (B (A C))

Exemple 1.7 Pour prouver A A, nous pouvons procder ainsi :

Axiome 1.5 (B C) ((A B) (A C))

(B C) ((A B) (A C)) ((A A) A) ((A (A A)) (A A)) (A (A A)) (A A) (A A) (A A)

(B C) ((A B) (A C)) (B C) ((A B) (A C))

A (A A)

B (A B)

axiome A2

(1.18a) (1.18b) (1.18c) (1.18d) (1.18e) (1.18f) (1.18g) (1.18h) (1.18i) (1.18j)

(1) et subst. axiome A5 (ncessaire) (3) et subst. (4) et dnition de (5) et subst. (6) modus ponens (2) et (8) (8) modus ponens

AA A A

10. Ces cinq axiomes ne sont pas indpendants les uns des autres ; le quatrime peut tre obtenu partir des quatre autres.


15

Systme axiomatique de L UKASIEWICZ Il comprend les trois axiomes suivants, plus les deux rgles

dinterfrences :Axiome 1.6 (A B) (B C) (A C)) Axiome 1.7 A (A B) Axiome 1.8 (A A) A

Voici des preuves des deux premiers axiomes, dans le systme de Whitehead et Russell. Ce sont les formules (6) et (16) de la drivation suivante : (A (B C)) (B (A C)) axiome A4 (1) et subst. A4 sur (2) et modus ponens (4) et subs. (5) par df. de (3) par df. de (1.19a) (1.19b) (1.19c) (1.19d) (1.19e) (1.19f) (1.19g) (1.19h) (1.19i) (1.19j) (1.19k)

((B C) ((A B) (A))) ((A B) ((B C) (A C))) (A B) ((B C) (A C)) (A B) ((B C) (A C)) (A B) ((B C) (A C)) (A B) ((B C) (A C))

B (B A) B (B A)

((A B) (B A)) (B (B A)) B (B A)

(B (A B)) ((A B) (B A)) (B (B A))

(6) et subs.

(7) modus ponens (8) modus ponens (9) et subs. (10) et df. de

B (B A) B (B A) A (A B)

(B (B A)) (B (B A)) B (B A)

A4 + subst. avec (11) (1.19l) (12) et modus ponens (1.19m) (1.19n) (1.19o) (1.19p)

(13) et df. de (14) et df. de (16) et subst.

Ces axiomatisations permettent de retrouver comme thorme toutes les tautologies ou lois de la logique propositionnelle. De par tout ce qui a t dit jusqu maintenant, nous pouvons tenter de dnir ce quest une preuve.Dnition 1.10 Une suite nie de formules B1 , B2 , . . . , Bn est appele preuve partir des hypothses A1 , A2 , . . . , An si pour chaque i : Bi est lune des hypothses A1 , A2 , . . . , An ou Bi est une variante dun axiome ou Bi est infre (par application de la rgle du modus ponens) partir de la prmisse majeure Bj et de la prmisse mineure Bk o j, k < i ou Bi est infre (par application de la rgle de substitution) partir dune prmisse antrieure Bj , la variable remplace napparaissant pas dans A1 , A2 , . . . , An

Une telle suite de formules, Bm tant la formule nale de la suite, est appele plus explicitement preuve de Bm partir des hypothses A1 , A2 , . . . , An , ce que nous notons par 11 : A1 , A2 , . . . , An Bm (1.20)

1.3.4 QuanticateursNous devons complter lutilisation des connecteurs du calcul propositionnel par ce que nous appelons des quanticateurs si nous souhaitons pouvoir rsoudre certains problmes. Eectivement,11. Il faut noter que lorsque nous essayons de prouver un rsultat partir dun certain nombre dhypothses, nous essayons pas de prouver les hypothses elles-mmes.

16


le calcul propositionnel ne nous permet pas darmer des choses gnrales sur les lments dun ensemble par exemple. Dans ce sens, la logique des propositionnelle ne rete quune partie du raisonnement. Le calcul des prdicats au contraire permet de manipuler formellement des armations telles quil existe un x tel que [x a une voiture amricaine] ou pour tous les x [si x est une teckel, alors x est petit] ; en somme, nous tendons les formules composes an de pouvoir armer des quantications existentielles (il existe...) et des quantication universelle (pour tout...). Les exemples que nous venons de donner font intervenir des propositions un peu particulires comme x a une voiture amricaine . Il sagit ici de propositions comportant une variable. Ces propositions sont en fait lapplication dune fonction x. Cette fonction, cest celle qui associe x a une voiture amricaine x. Nous dnoterons cette fonction par ab a une voiture amricaine et nous dirons que cest une fonction propositionnelle, car cest une fonction dont la valeur est une proposition, ou encore, un prdicat. Les quanticateurs existentiels et universels vont donc de pair avec lemploi de fonctions propositionnelles. Le calcul des prdicats est cependant limit dans les formules existentielles et universelles. Ainsi, nous nous interdisons des formules comme il existe une armation de x telle que... En fait, nous ne nous autorisons quantier que des individus. Cest pour cela que la logique des prdicats est dite une logique de premier ordre. Avant de passer ltude du calcul des prdicats nous devons dnir :Dnition 1.11 Le quanticateur universel : (pour tout) Dnition 1.12 Le quanticateur existentiel : (il existe)

Nous utilisons parfois le symbole ! pour dire brivement il existe un et un seul : x R, !y R , x = ln(y) + (1.21)

Nous allons voir que la thorie de la dmonstration et des ensembles, est lexacte transcription des principes et rsultats de la Logique.

1.4 Calcul des prdicatsDans un cours de mathmatiques, il faut dmontrer les proprits de dirents types dobjets (entiers, rels, matrices, suites, fonctions continues, courbes...). Pour pouvoir prouver ces proprits, il faut bien sr que les objets sur lesquels nous travaillons soient clairement dnis. En logique du premier ordre et, en particulier, en thorie de la dmonstration, les objets que nous tudions sont les formules et leurs dmonstrations. Il faut donc donner une dnition prcise de ce que sont ces notions. Les termes et les formules forment la grammaire dune langue, simplie lextrme et calcule exactement pour dire ce que nous voulons sans ambigut et sans dtour inutile.

1.4.1 GrammaireDnition 1.13 (Termes) Les termes dsignent les objets dont nous voulons prouver des proprits

(nous reviendrons un peu plus loin beaucoup plus en dtail sur ces derniers) : en algbre, les termes dsignent les lments dun groupe (ou anneau, corps, espace vectoriel, etc.). Nous manipulons aussi des ensembles dobjets (sous-groupe, sous-espace vectoriel, etc). Les termes qui dsignent ces objets, dun autre type, seront appels termes du second ordre ; en analyse, les termes dsignent les rels ou des fonctions.Dnition 1.14 (Formules) Les formules reprsentent les proprits des objets que nous tudions :

en algbre, nous pourrons crire des formules pour exprimer que deux lments commutent, quun sous-espace vectoriel est de dimension 3, etc. en analyse, nous crirons des formules pour exprimer la continuit dune fonction, la convergence dune suite, etc. en thorie des ensembles, les formules pourront exprimer linclusion de deux ensembles, lappartenance dun lment un ensemble, etc.

1.4 Calcul des prdicats

17

Dnition 1.15 (Dmonstrations) Les dmonstrations permettent dtablir quune formule est vraie.

Le sens prcis de ce mot aura lui aussi besoin dtre dni. Plus exactement, elles sont des dductions sous hypothses, elles permettent de mener du vrai au vrai, la question de la vrit de la conclusion tant alors renvoye celle des hypothses, laquelle ne regarde pas la logique mais repose sur la connaissance que nous avons des choses dont nous parlons.

1.4.2 LangagesEn mathmatique, nous utilisons, suivant le domaine, dirents langages qui se distinguent par les symboles utiliss. La dnition 1.16 exprime simplement quil sut de donner la liste de ces symboles pour prciser le langage.Dnition 1.16 (Langage) Un langage est la donne dune famille (pas ncessairement nie) de symboles. Nous en distinguons trois sortes : symboles, termes et formules.

Nous utilisons quelques fois le mot vocabulaire ou le mot signature la place du mot langage. Le mot prdicat peut tre utilis la place du mot relation. Nous parlons alors de calcul des prdicats au lieu de logique du premier ordre (ce que nous avons tudi prcdemment).

Symboles Il existe dirents types de symboles que nous allons tacher de dnir : Chap4 les symboles de constante : le n pour llment neutre en thorie des ensembles ; les symboles de fonction ou foncteurs : chaque symbole de fonction est associ un entier strictement positif que nous appelons son arit : cest le nombre darguments de la fonction. Si larit est 1 (resp. 2, . . . , n), nous disons que la fonction est unaire (resp. binaire, ..., n-aire) Le foncteur binaire de multiplication dans les groupes.Dnition 1.17 (symboles de relation) De la mme manire, chaque symbole de relation est

associ un entier positif ou nul (son arit) qui correspond son nombre darguments et nous parlons de relation unaire, binaire, n-aire (comme par exemple le symbole de relation =).Dnition 1.18 (variables individuelles) Dans toute la suite, nous nous donnerons un ensemble

inni V de variables. Les variables seront notes comme il lest par tradition x, y, z ventuellement indexes. cela il faut rajouter les connecteurs et quanticateurs que nous avons longuement prsent plus haut et sur lesquels il est pour linstant inutile de revenir. Un symbole de constante peut tre vu comme un symbole de fonction 0 argument (darit nulle). Nous considrons (sauf mention contraire) que chaque langage contient le symbole de relation binaire = (lire gal) et le symbole de relation zro argument dnot (lire bottom ou absurde) qui reprsente le faux. Dans la description dun langage, nous omettrons donc souvent de les mentionner. Le symbole est souvent redondant. Nous pouvons en eet, sans lutiliser, crire une formule qui est toujours fausse. Il permet cependant de reprsenter le faux dune manire canonique et donc dcrire des rgles de dmonstration gnrales. Le rle des fonctions et des relations est trs dirent. Comme nous le verrons plus loin, les symboles de fonction sont utiliss pour construire les termes (les objets du langage) et les symboles de relation pour construire les formules (le proprits de ces objets). n remarque

Termes Les termes reprsentent les objets associs au langage. Soit L un langage :Dnition 1.19 Lensemble I des termes sur L est le plus petit ensemble contenant les variables,

les constantes et stable (on ne sort pas de lensemble) par lapplication des symboles de fonction de L des termes.Dnition 1.20 (Terme clos) Un terme clos est un terme qui ne contient pas de variables (donc

par extension, seulement des constantes).

18


Dnition 1.21 Pour obtenir une dnition plus formelle, nous pouvons crire :

I0 = (t) o t est une variable ou un symbole de constante et, pour tout k N : Ik+1 = Ik (f (t1 , . . . , tn )/ti Ik )

(1.22)

(1.23)

o f est une fonction darit n (rappelons que larit est le nombre darguments de la fonction). Ainsi, pour chaque arit, il y a un degr densemble de termes. Nous avons nalement : I = IkkN

(1.24)

Dnition 1.22 Nous appellerons hauteur dun terme t le plus petit k tel que t Ik

La dnition 1.22 signie que les variables et les constantes sont des termes et que si f est un symbole de fonction n-aire et t1 , . . . , tn sont des termes alors f (t1 , . . . , tn ) est un terme en soi aussi. Lensemble I des termes est dni par la grammaire : I = V |SC |SF (I, . . . , I) (1.25) Cette expression se lit de la manire suivante : un lment de lensemble I que nous sommes en train de dnir est soit un lment de V (variables), soit un lment de SC (lensemble des symboles de constantes), soit lapplication dun symboles de fonction f SF n lments (constantes ou variables) de I. Attention, le fait que f soit de la bonne arit est seulement implicite dans cette notation. De plus, lcriture SF (I, . . . , I) ne signie pas que tous les arguments dune fonction sont identiques mais simplement que ces arguments sont des lments de I. Il est souvent commode de voir un terme (expression) comme un arbre dont chaque nud est tiquet par un symbole de fonction (oprateur ou fonction) et chaque feuille par une variable ou une constante. Dans la suite, nous allons sans cesse dnir des notions (ou prouver des rsultats) par rcurrence sur la structure ou la taille dun terme.Dnition 1.23 Pour prouver une proprit P sur les termes, il sut de prouver P pour les variables

et les constantes et de prouver P (f (t1 , . . . , tn )) partir de P (t1 ), . . . , P (tn ). Nous faisons ainsi ici une preuve par induction sur la hauteur dun terme. Cest une technique que nous retrouverons dans les chapitres suivants.Dnition 1.24 Pour dnir une fonction sur les termes, il sut de la dnir sur les variables et les constantes et de dire comment nous obtenons (f (t1 , . . . , tn )) partir de (t1 ), . . . , (tn ). Nous faisons ici encore une dnition par induction sur la hauteur dun terme. Exemple 1.8 La taille (nous disons aussi la longueur) dun terme t (note (t)) est le nombre de symboles de fonction apparaissant dans t. Formellement : (x) = (c) = O si x est une variable et c est une constante (f (t1 , . . . , tn )) = 1 + 1 i n (ti ) La preuve par induction sur la hauteur dun terme sera souvent insusante. Nous pourrons alors prouver une proprit P sur les termes en supposant la proprit vraie pour tous les termes de taille p < n et en la dmontrant ensuite pour les termes de taille n. Il sagira alors dune preuve Chap4 par rcurrence sur la taille du terme .

Formules Les formules sont construites partir des formules dites atomiques en utilisant des connecteurs et des quanticateurs. Nous utiliserons les connecteurs et les quanticateurs suivants : connecteur unaire de ngation ; connecteurs binaires de conjonction et disjonction ainsi que dimplication , , ; quanticateurs : qui se lit il existe et qui se lit pour tout. Cette notation des connecteurs est standard. Elle est utilise pour viter les confusions entre les formules et le langage courant (le mtalangage).

1.4 Calcul des prdicats

19

Dnition 1.25 Soit L un langage, les formules atomiques de L sont les formules de la forme

R(t1 , . . . , tn ) o R est un symbole de relation n-aire de L et t1 , . . . , tn sont des termes de L. Nous notons Atom lensemble des formules atomiques. Si nous notons SR lensemble des symboles de relation, nous pouvons crire lensemble des termes mis en relations par lexpression : Atom = SR (I, . . . , I)

(1.26)

Lensemble F des formules de la logique du premier ordre de L est donc dni par la grammaire (o x est une variable) : F = Atom|F F |F F |F F |F F |xF |xF (1.27)

o il faut lire : lensemble des formules est le plus petit ensemble contenant les formules et tel que si F1 et F2 sont des formules alors F1 F2 ... sont des formules et quelles peuvent tre en relation en relation entre elles.Exemple 1.9 Les symboles de relation du langage propositionnel sont des relations darit 0 (mme le symbole = est absent), les quanticateurs sont alors inutiles (puisquune formule ne peut pas contenir des variables). Nous obtenons alors le calcul propositionnel dni par :

CP = VP ||CP |CP CP |CP CP |CP CP

(1.28)

Remarquons la prsence du symbole botton signiant le faux que nous navions pas mentionn lors de notre tude de la logique propositionnelle. Nous ferons attention ne pas confondre termes et formules. sin(x) est un terme (fonction), x = 3 est une formule. Mais sin(x) (x = 3) nest rien : nous ne pouvons, en eet, mettre un connecteur entre un terme et une formule (aucun sens). Pour dnir une fonction sur les formules, il sut de dnir sur les formules atomiques et de dire comment on obtient (F1 F2 ) (resp. (F1 ), (QxF1 )) partir de (F1 ) et (F2 ) (resp. (F1 )) Pour prouver une proprit P sur les formules, il sut de prouver P pour les formules atomiques et de prouver P (F1 F2 ) (resp. P (F1 ), P (QxF1 )) partir de P (F1 ) et P (F2 ) (resp. P (F1 )). Pour prouver une proprit P sur les formules, il sut de supposer la proprit vraie pour toutes les formules de taille p < n et de la dmontrer pour les formules de taille n.Dnition 1.26 Une sous-formule dune formule (ou expression) F est lun de ses composants, in

extenso une formule partir de laquelle F est construite. Formellement, nous dnissons lensemble SF (F ) des sous-formules F par : Si F est atomique, SF (F ) = (F ) Si F = F1 F2 avec (, , ), SF (F ) = (F ) SF (F1 ) SF (F2 ) Si F = F1 ou QxF1 avec Q (, ), SF (F ) = (F ) SF (F1 )Dnition 1.27 Une formule F de L nutilise quun nombre ni de symboles de L. Ce sous-ensemble est appel le langage de la formule et not L(F ). Dnition 1.28 La taille (ou la longueur) dune formule F (note (F )) est le nombre de connec-

teurs

ou de quanticateurs apparaissant dans F . Formellement : (F ) = 0 si F est une formule atomique (F1 F2 ) = 1 + (F1 ) + (F2 ) o {, , } (F1 ) = (QxF1 ) = 1 + (F1 ) avec Q {, }

Dnition 1.29 Loprateur principal (nous disons aussi le connecteur principal) dune formule est

dni par : Si A est atomique, alors elle na pas doprateur principal Si A = B alors est loprateur principal de A Si A = B C o (, , ), alors est loprateur principal de A Si A = QxB o A (, ), alors Q est loprateur principal de ADnition 1.30 Soit F une formule. Lensemble V L(F ) des variables libres de F et lensemble V M (F ) des variables muettes (ou lies) de F sont dnis par rcurrence sur (F ).

20


Une occurrence dune variable donne est dite variable lie ou variable muette dans une formule F si dans cette mme formule, un quanticateur y fait rfrence. Dans le cas contraire, nous disons avoir une variable libre 12 . Pour prciser les variables libres possibles dune formule F , nous noterons F [x1 , . . . , xn ]. Cela signie que les variables libres de F sont parmi x1 , . . . , xn in extenso si y est libre dans F , alors y est lun des xi mais les xi napparaissent pas ncessairement dans F . Nous pouvons dnir les variables muettes ou libre de manire plus formelle : 1. Si F = R(t1 , . . . , tn ) est atomique alors V L(F ) est lensemble des variables apparaissant dans les ti et nous avons V M (F ) = 2. Si F = F1 F2 o (, , ) : V L(F ) = V L(F1 ) V L(F2 ) alors V M (F ) = V M (F1 ) V M (F2 ) 3. si F = F1 alors V L(F ) = V L(F1 ) et V M (F ) = V M (F1 ) 4. si F = QxF1 avec Q {, } : V L(F ) = V L(F1 ) {x} et V M (F ) = V M (F1 ) {x}Exemple 1.10 Soit F : x (x y = y x) alors V L(F ) = {y} et V M (F ) = {x} Exemple 1.11 Soit G : {x y (x z = z x)} {x = z z} alors V L(F ) = {x, z} et V M (F ) = {x, y} Dnition 1.31 Nous disons que les formules F et G sont -quivalentes si elles sont (syntaxique-

ment) identiques un renommage prs des occurrences lies des variables.Dnition 1.32 (formule close) Une formule close est une formule sans variables libres. Dnition 1.33 Soit F une formule, x une variable et t un terme. F [x := t] est la formule obtenue en remplaant dans F toutes les occurrences libres de x par t, aprs renommage ventuel des occurrences lies de F qui apparaissent libres dans t.

Nous noterons dans les exemples vus quune variable peut avoir la fois des occurrences libres et des occurrences lies. Nous navons donc pas toujours V L(F ) V M (F ) = . Nous ne pouvons pas renommer y en x dans la formule y(x y = y x) et obtenir la formule x(x x = x x) : la variable x serait capture. Nous ne pouvons donc pas renommer des variables lies sans prcautions : il faut viter de capturer des occurrences libres. La notion de formule dnie ici est la notion de formule de logique du premier ordre. Certaines formules ne sont pas des formules du premier ordre (le nombre de quanticateurs ne doivent pas tres dpendant dune variable !).

1.5 Dmonstrations1.5.1 IntroductionLes dmonstrations que lon trouve dans les ouvrages de mathmatiques sont des assemblages de symboles mathmatiques et de phrases contenant des mots cls tels que : donc, parce que, si, si et seulement si, il est ncessaire que, il sut de, prenons un x tel que, supposons que, cherchons une contradiction, etc. Ces mots sont supposs tre compris par tous de la mme manire, ce qui nest en fait, pas toujours le cas. Dans tout ouvrage, le but dune dmonstration est de convaincre le lecteur de la vrit de lnonc. Suivant le niveau du lecteur, cette dmonstration sera plus ou moins dtaille : quelque chose qui pourra tre considr comme vident dans un cours de licence pourrait ne

Documents

ElementsMathematiquesAppliqueesV001