Next PDF List

Cours de logiqueRoland Christophe8 septembre 2008Table des matieres1 Qu'est ce que la logique? 21. 1) Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 1. 2) Le concept de theorie en mathematique . . . . . . . . . . . .2 1.2. 1) Les denitions . . . . . . . . . . . . . . . . . . . . . .2 1.2. 2) Les axiomes . . . . . . . . . . . . . . . . . . . . . . . .2 1.2. 3) Les theoremes . . . . . . . . . . . . . . . . . . . . . . .4 1. 3) Bref historique . . . . . . . . . . . . . . . . . . . . . . . . . .4 2 Le langage formel 52. 1) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 2. 2) Langage formel et langage naturel . . . . . . . . . . . . . . .5 2.

3) Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 3 Introduction au calcul des propositions 63.

1) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 3. 2) Connecteurs logiques . . . . . . . . . . . . . . . . . . . . . . .7 3.2. 1) Le connecteur"Non»(negation) . . . . . . . . . . . .7 3.2. 2) Le connecteur"ou»(disjonction) . . . . . . . . . . .7 3.2. 3) Le connecteur"et»(conjonction) . . . . . . . . . . .8 3.2. 4) Le connecteur"si alors»(conditionnel materiel) . .8 3.2. 5) Le connecteur"est equivalent a». . . . . . . . . . .8 3.2. 6) D'autres connecteurs . . . . . . . . . . . . . . . . . . .9 3. 3) Langage de la logique propositionnelle . . . . . . . . . . . . .9 4 Tautologies 104. 1) Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 4. 2) Tautologies remarquables . . . . . . . . . . . . . . . . . . . .11 5 Calcul des predicats 125. 1) Les predicats . . . . . . . . . . . . . . . . . . . . . . . . . . .12 5. 2) Quanticateurs existenciels et universels . . . . . . . . . . . .13 5.2. 1) Le quanticateur existenciel . . . . . . . . . . . . . . .13 5.2. 2) Le quanticateur universel . . . . . . . . . . . . . . . .13 5. 3) Alphabet et syntaxe . . . . . . . . . . . . . . . . . . . . . . .14 5.

4) Egalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15 11 Qu'est ce que la logique?1.

1) DenitionLa logique vient du grecque"logos»qui signie"parole, discours», etpar extension"rationalite», la logique est donc la science de la raison.

Plusprecisement, c'est la sciences qui etudie les regles que doivent respecter toutraisonnement valide, qui permet de distinguer un raisonnement valide d'unraisonnement qui ne l'est pas.1.

2) Le concept de theorie en mathematiqueUn premier concept important en logique est le concept detheorie.

Unetheorie est un ensemble de denitions, d'axiomes (on vera un peu plus tardce concept), de theoremes, qui traite d'un sujet particulier.1.2.

1) Les denitionsUn element important d'une theorie sont lesdenitions.

Formellement,une denition est un enonce qui introduit un nouveau symbole appeletermea partir d'une suite de symboles deja connus, appelleassemblage.

On veraen eet plus loin que nous utiliserons un langage symbolique.

Toutefois, onne peut utiliser exclusivement les symboles pour des raisons pratiques : unedenition utilisant les symboles logiques exclusivement est tres"lourde»alire, on utilise alors le langage courant.

Toutefois, pour ne pas perdre toutela rigueur de ces denitions, on utilise souvent les deux sortes de denition(par le langage courant et par le langage mathematique).1.2.

2) Les axiomesCe qui forme la base d'une theorie (le point de depart), sont lesaxiomes.Ce sont simplement des armations que l'on tient pour vrai.

Il est d'ailleursinutile de contester la veracite d'un axiome : un axiome est toujours vrai,par denition.

L'ensemble des axiomes d'une theorie s'appelleaxiomatique.La seule contrainte est que les axiomes ne doivent pas se contredire (ce quiest logique mais c'est important).

Aucun axiome ne peut ^etre remis en causedans la theorie, sans quoi on dira que cette theorie estinconsistante.Les philosophes grecques avait une denition quelque peu dierente del'axiome : un axiome est une verite que l'on ne demontre pas car evidenteen soi.

Cette maniere de voir les choses pose probleme : comment quelquechose peut il ^etre"evident»? Pourquoi cet axiome est vrai? N'aurait il paspu ^etre faux?La celebre histoire du cinquieme axiome d'Euclide repond a cette ques-tion.

Rappelons tout d'abord de quoi il s'agit.Euclide a enonce cinq axiomes comme base de la geometrie :21.par deux p oints,il passe une et une seul droite, 2.un segmen tde droite p eut^ etreprolong eind enimenten une droite, 3. etantdonn edeux p ointsquelconques AetB, un cercle peut ^etre traceen prenantAcomme centre et passant parB,4.tous les angles droits son t egauxen treeux, 5.par un p ointext erieur aune droite, on p eutmener une et une seule parallele a cette droite.C'est le cinquieme axiome qui nit par poser probleme.

Sans vouloirle remettre en cause, les mathematiciens pensaient qu'il etait inutile car ilpouvait se demontrer a partir des autres.

Cependant, toutes les tentativespour demontrer cet axiome ont echoue.

Les mathematiciens ont eu alors uneidee : ils ont tentes de voir ce qui ce passait si on refutait cet axiome, c'esta dire que l'on le considere comme faux.

Ils esperaient ainsi aboutir a unecontradiction ce qui aurait du m^eme coup montre la validite de l'axiome(qui n'en serait plus vraiment un puisque demontre).

Sans succes.Plusieurs mathematiciens ont commence a entrevoir la solution commeGauss et Lobachevsky.

Celui ci s'amusa a remplacer le cinquieme axiome parceci : par un point exterieur a une droite, on peut mener deux paralleles acette droite.

Il developpe a partir de ca toute une geometrie coherente maistout a fait dierente de celle d'Euclide.

C'est un exemple de geometrienon-euclidienne.

Il exite dierentes sortes de geometrie non-euclidienne, l'idee deLobachevsky conduit a une geometriehyperbolique.Voici un exemple de representation tire de wikipedia :On voit bien sur cette image que l'espace sur lequel on travaille n'est pasplat : c'est pourquoi la geometrie n'est pas euclidienne.

3) L'inter^et de tout ce qui a ete dit ici est que le concept antique d'axiomen'est pas le bon.

Il semblait"evident»que le cinquieme d'axiome d'Euclideest vrai alors quel'on peut tres bien dire qu'il soit fauxet avoir toutefois unegeometrie coherente.

La plus belle preuve est qu'Einstein a montre que lesgeometrie non-euclidienne ont un sens physique puisque l'espace dans lequelnous vivons est courbe dans un champ de gravitation : si vous dessiner untriangle et que vous ^etes capable de mesurer ses angles avec une precisionextraordinaire (ce qui est en pratique malheureusement impossible), vous ve-rez que la somme des angles ne vaut pas exactement 180 degres, la dierencesera inme mais reelle.La morale de l'histoire : il n'existe aucune verite evidente par elle m^emeen mathematique,un axiome n'est pas vrai parce qu'il est vrai mais vraiparce que l'on a decide qu'il soit vrai.1.2.

3) Les theoremesMaintenant, a partir de ces axiomes, on peut en tirer destheoremes.

Untheoreme est une assertion vraie qui est demontre a partir des axiomes (oua partir d'autres theoremes eux m^eme demontre par des axiomes mais celarevient au m^eme).

Un theoreme necessite donc une demontration.

En plusde la notion de theoreme, on a les notion suivante (moins souvent utilisees) :1.lemme : un lemme est une assertion que l'on d emontrequi se rt ala demonstration d'un theoreme plus important (ou parfois on utilise ceterme pour parler d'un theoreme d'une moindre importance),2.conjecture : prop ositionmath ematiquequ el'on supp osevrai mais sans avoir ete demontre (donc pas forcement vrai, mais quand m^eme avecune forte probabilite), une conjecture demontre devient un theoreme,3.corollaire : un corollaire e stune cons equenceimm ediated'un th eoremedemontre.1.

3) Bref historiqueLes philosophes de la Grece Antique ont poses les fondements de la lo-gique. En particuliers, Aristote expose les bases de la logique dans son ou-vrage"Organon».

La logique d'Aristote va ^etre enseignes pendant treslongtemps, elle predomine jusqu'au MoyenAges au moins, et ce n'est quetres recemment qu'est apparu la logique moderne.C'est Frege qui a pose les bases de la logique moderne.

La dierenceessentielle par rapport a la logique d'Aristote est que Frege a une approchemathematique de la logique, alors que la logique d'Aristote est teintee dePhilosophie.

Il va ainsi developper la logique des propositions et la logiquedes predicats que nous verront plus loin.Alors qu'Aristote se servait du langage courant pour faire des raison-nements logiques, Frege se sert d'un langage symbolique : l'ideographie.

4) Leibniz avait deja tente de creer un langage logique qu'il appelait"la ca-racteristique universelle»malheuresement sans succes, et il n'aboutit pasa quelque chose qui puisse le satisfaire.

Aujourd'hui le langage logique mo-derne n'est pas l'ideographie qui n'est plus utilise, mais certains symbolessont derives de ce langage.Nous allons donc commencer par tenter de preciser la notion de langageen mathematique pour comprendre son inter^et.

2) Le langage formel2.

1) IntroductionL'idee d'utiliser un langage symbolique permet de simplier beaucoupde choses en mathematique.

On peut donner un exemple simple : supposonsque nous devions calculer"la somme de la racine carre du quotient de 27par 3 et du produit de 2 et 7», on comprend tout de suite qu'on y voit plusclair en ecrivant :r273+ 272.

2) Langage formel et langage naturelOn va donc adapter cette idee a la logique mais avant cela, il faut preciserce que l'on entend par"langage».

Il faut d'abord distinguer lelangage na-tureldulangage formel.

Le langage naturel est le langage que nous utilisonsdans la vie de tout les jours, qui a deux inconvenients majeurs quand onl'utilise en mathematique :1.la complexit edes phr asesqui rend les c hosesplus compliqu es,il faut parfois plusieurs lignes et une phrase completement incomprehensible,pour dire quelque chose qui peut se resumer par une simple equation,2.le fait que les am biguitesdu langage couran tp euventconduire ades erreurs, et surtout une preuve se doit indiscutable par denition, cequi est impossible lorsqu'il y a ambiguites.2.

3) DenitionLorsque l'on denit un langage formel, on doit denir deux choses quicaracterisent ce langage :1.un alphabetcad un ensemble de symboles (comme dans le cas deslangages naturels),2.une syntaxecad un ensembles de regles qui denit quels mots appar-tiennent au langage formel.

5) Il reste a preciser ce qu'en un mot, c'est tres simple : unmot(on ditaussicha^ne de caractere) est une suite ordonnee de symboles, ces symbolesappartenant a un alphabet.Nous pouvons donc denir ce qu'est un langage formel :Unlangage formelest un ensemble de mots de longueur niedeni par un alphabet et une syntaxe.On peut donner un exemple pour y voir plus clair et denir un langageformel simple : on va prendre un alphabet et une syntaxe quelconque, nevoyez aucune logique particuliere dans le choix de l'alphabet et de la syntaxe.L'alphabet du langage est l'ensemble contenant les elements suivants :A;B;C;+;=.la syntaxe sera composes des regles suivantes :1.aucun mot n ep eutcommencer ou terminer par =, 2.aucun mot n ep eutcommencer ou terminer par +, 3.dans c haquemot, on a un et un seul sym bole"=»,4.si on c hoisitdeux sym bolescons ecutifsdans un mot, l'un des deux est une lettre et pas l'autre.Par exemple,A+B+C=A+Cest un mot possible, par contre,= +A+ +BCne l'est pas.Nous allons appliquer tout cela a la logique, en faisant attention au faitque l'on dira des"formules»au lieu de dire des"mots».

3) Introduction au calcul des propositions3.

1) IntroductionLa notion de"proposition»est fondamentale en logique et deja presentedans la logique d'Aristote.

On peut denir cette notion tres facilement : uneproposition est tout simplement une armation.

Il faut faire attention quecette armation puisse ^etre vrai ou fausse, par exemple"je mens»n'estpas une proposition, en eet, si quelqu'un dit"je mens», alors si il dit laverite il ment et si il ment il dit la verite.

C'est leparadoxe du menteur.Il faut donc avoir des armations qui puissent ^etre soit completementvraies, soit completement fausses.

Par exemple,"Il pleut»peut ^etre vraiou faux mais pas autre chose, cette phrase peut donc ^etre consideree commeune proposition.

On laisse donc de c^ote pour l'instant les phrase qui ne sontni tout a fait vrai ni tout a fait fausse.Des deux remarques precedentes, on peut deduire un principe fondamen-tal pour la logique, qu'on appellele principe du tiers exclu: une propositionest soit vraie soit fausse mais pas autre chose.

On dit que la"valeur deverite»d'une proposition est"vraie»ou"fausse».

6) Puisque nous voulons adopter un langage symbolique, nous devons notezles propositions par un simple symbole, en regle general, une proposition estnotee avec une lettre majuscule.

Comme nous avons dit que les mots dulangage de la logique sont appeles des formules, on dira que les propositionssont des formules.3.

2) Connecteurs logiquesLe notion deconnecteur logiqueest deja presente dans la logique d'Aris-tote.

C'est une notion qui apparait naturellement lorsque l'on tente de fairedes raisonnements.Prenons un exemple.

Considerons deux propositionsAetB. On peutimaginer que deAon peut deduireB, c'est a dire que siAest vrai, alorsBest vrai lui aussi. On ecrit alors :"siAalorsB».

Mais on a alors que laphrase"siAalorsB»peut ^etre vrai ou fausse.En eet, siAveut dire"ceci un cobra»etBveut dire"ceci est unserpent», alors"siAalorsB»veut dire"si ceci un cobra alors ceci est unserpent»ce qui est vrai.

Mais on peut imaginer queAveut dire"ceci estun tigre»et alors"siAalorsB»devient faux.On comprend alors que lorsque l'on combine des propositions de cettemaniere, on obtient des phrases qui ont aussi une valeur de verite, le principedu tiers exclu s'applique aussi a ces phrases.

On va dire que ces phrases sontaussi des formules.

On dit que ce sont desformules composeesalors que lespropositions sont desformules atomiques.Les mots"si»et"alors»sont des connecteurs logiques (en fait il n'enforment qu'un puisqu'on les utilisent ensembles).

Nous allons maintenant envoir d'autres et chaque connecteur sera represente par un symbole dierent.3.2.

1) Le connecteur"Non»(negation)C'est le connecteur le plus simple de tous. Considerons une propositionA.

La proposition"nonA»est vrai siAest faux, et fausse siAest vrai.Ce connecteur s'ecrit symboliquement:.On peut illustrer cela dans un tableau que l'on appelle"table de verite»:A:AVFFV3.2.

2) Le connecteur"ou»(disjonction)Ce connecteur permet de former des formules comme"AouB»mais ilfaut faire attention que siAetBsont tout les deux vrais alors"AouB»est vrai aussi.

Ce connecteur s'ecrit_.On a donc la table de verite :7ABA_BVVVVFVFVVFFFOn a queA_Best faux siAetBsont tout les deux faux, vrai dans toutles autres cas.3.2.

3) Le connecteur"et»(conjonction)Ce connecteur permet de former des formules comme"AetB», il estrepresente par le symbole^.ABA^BVVVVFFFVFFFFA^Best vrai siAetBsont tout les deux vrais, faux dans tout les autrecas.3.2.

4) Le connecteur"si alors»(conditionnel materiel)Il est represente par le symbole :).ABA)BVVVVFFFVVFFV"siAalorsB»veut dire que siAest vrai,Bl'est necessairement aussi.

Laseule maniere de contrarierA)Best d'avoirBfaux alors queAest vrai.3.2.

5) Le connecteur"est equivalent a»Le connecteur"equivalence»s'ecrit symboliquement :,et veut dire :"a la la m^eme valeur de verite que».ABA,BVVVVFFFVFFFV83.2.

6) D'autres connecteursCes connecteurs ne sont pas ou peu utilises en mathematique, mais plut^oten electronique et en informatique.

Comme on les utilise surtout en infor-matique, on utilise le"1»a la place du"V»et le"0»a la place du"F».Les"portes logiques»correspondent a ces connecteurs.

La porte NOTest le"non»logique, la porte AND est le"et»et la porte OR est le"ou».On trouve aussi la porte NOR (NOT OR) :ABA NOR B110100010001La porte XOR (ou exclusif) :ABA XOR B110101011000La porte NAND (NOT AND) :ABA NAND B1101010110013.

3) Langage de la logique propositionnelleOn peut maintenant denir le langage de la logique des propositions.On doit donc inclure les propositions (formules atomiques) ainsi toutes lesformules composees possibles.L'alphabet de la logique propositionnelle est constitue :1.d'un ensem blede form ulesatomiques, 2.des connecteurs :;_;^;);,,3.des s eparateurs(paren theses): "(»et")».

9) Les parentheses sont utiles dans les formules logiques car il faut se rendrecompte par exemple que la formule:A_Best dierente de la formule:(A_B).On peut ensuite denir la syntaxe :Syntaxe : l'ensemble des formules de la logique est le pluspetit ensemble tel que :{si Aest une formule atomique alorsAest une formule,{si Aest une formule, alors:Aest une formule,{si AetBsont des formules, alors (A_B) est une formule,{si AetBsont des formules, alors (A^B) est une formule,{si AetBsont des formules, alors (A)B) est une formule,{si AetBsont des formules, alors (A,B) est une formule.Petite remarque : pourquoi dit-on dans la denition :"le plus petitensemble»? L'explication est simple.

Si on avait la m^eme denition maissans preciser cela, on ne saurait pas par exemple, si la formuleA_ ^Bestvalide ou pas.

En eet, la denition n'implique pas que cette formule existe,mais ne l'interdit pas non plus. C'est pour cela que l'on precise"le pluspetit ensemble», sinon la denition ne serait pas correcte. 4) Tautologies4.

1) DenitionUnetautologieest une formule qui est toujours vraie, quelle que soit lavaleur de verite des formules atomiques qui la compose.

On dit aussi uneformule valide.Exemples :A)Aest une tautologie : queAsoit vrai ou faux, cette formule esttoujours vrai.

On peut le demontrer avec une table de verite.AA)AVVFVA_ :A(principe du tiers exclu) est une tautologie : on peut le demontreravec une table de verite.A:AA_ :AVFVFVVOn voit donc ici la methode de demonstration avec une table de verite : laderniere colonne ne contient que des"V», c'est donc que la formule estvalide (puisqu' elle est vrai tout le temps).104.

2) Tautologies remarquablesVoici maintenant une liste de tautologie. Elle peuvent parfois ^etre utilespour simplifer une formule.

En eet, siAetBsont des formules et que l'onaA,B, on peut remplacerAparBouBparA.IdentiteA,ADouble negationA, ::AIdempotenceA,(A_A)A,(A^A)CommutativiteA_B,B_AA^B,B^AAssociativite(A_(B_C)),((A_B)_C)(A^(B^C)),((A^B)^C)Distributivite(A_(B^C)),((A_B)^(A_C))(A^(B_C)),((A^B)_(A^C))Absorption(A_(A^B)),A(A^(A_B)),ALoi de De Morgan:(A_B),(:A^ :B):(A^B),(:A_ :B)Conditionnel materiel(A)B),(:A_B)(A)B), :(A^ :B)Contraposition(A)B),(:B) :A)Equivalence materielle11(A,B),(A)B)^(B)A)(A,B),(A^B)_(:A^ :B)Exportation-import