Cours de logique

Philosophie Il va ainsi développer la logique des propositions et la logique

LA PHILOSOPHIE DE LA LOGIQUE

Cité 4 fois — philosophie du langage ont influencé au cours de ce siècle les positions défendues par les philosophes

Cours de logique - CNRS

Philosophie Il va ainsi développer la logique des propositions et la logique

INTRODUCTION A LA LOGIQUE

ATION Ce texte n'est pas un cours de logique ; c'est la transcription d' exposés faits et qui donna des développements plus philosophiques que mathématiques à la logique

Philosophie de la notation logique - Archipel UQAM

s grammaires formelles (Frege, Russell, Husserl et l'école de logique polonaise

Introduction à la logique - Département de philosophie UQAM

phi1007-4PDF

COURS SUR LA LOGIQUE FORMELLE - Université Jean Monnet

En réalité la logique d'Aristote avait plus un but philo- sophique C'est plus Euclide qui

LOGIQUE

Cours de deuxi`eme année de bachelier en Philosophie P Gribomont 2003-2008

PHI-111 – Introduction à la logique (3 cr) - Université de

Département de philosophie et d'éthique appliquée PHI-111 Plan de cours – Automne 2014 Lundi Ce cours est une introduction à la logique formelle L' objectif

Questions approfondies de philosophie du langage et de

cours-2014-L PDF

Roland Christophe

8 septembre 2008

Table des matieres

1 Qu'est ce que la logique? 2

1.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Le concept de theorie en mathematique . . . . . . . . . . . .

1.2.1 Les denitions . . . . . . . . . . . . . . . . . . . . . .

1.2.2 Les axiomes . . . . . . . . . . . . . . . . . . . . . . . .

1.2.3 Les theoremes . . . . . . . . . . . . . . . . . . . . . . .

1.3 Bref historique . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Le langage formel 5

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Langage formel et langage naturel . . . . . . . . . . . . . . .

2.3 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Introduction au calcul des propositions 6

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Connecteurs logiques . . . . . . . . . . . . . . . . . . . . . . .

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 . . . . . . . . . . . . . . . . . . .

3.3 Langage de la logique propositionnelle . . . . . . . . . . . . .

4 Tautologies 10

4.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Tautologies remarquables . . . . . . . . . . . . . . . . . . . .

5 Calcul des predicats 12

5.1 Les predicats . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2 Quanticateurs existenciels et universels . . . . . . . . . . . .

5.2.1 Le quanticateur existenciel . . . . . . . . . . . . . . .

5.2.2 Le quanticateur universel . . . . . . . . . . . . . . . .

5.3 Alphabet et syntaxe . . . . . . . . . . . . . . . . . . . . . . .

5.4Egalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15

1 Qu'est ce que la logique?

1.1 Denition

La logique vient du grecque"logos»qui signie"parole, discours», et par extension"rationalite», la logique est donc la science de la raison. Plus precisement, c'est la sciences qui etudie les regles que doivent respecter tout raisonnement valide, qui permet de distinguer un raisonnement valide d'un raisonnement qui ne l'est pas.

1.2 Le concept de theorie en mathematique

Un premier concept important en logique est le concept detheorie. Une theorie est un ensemble de denitions, d'axiomes (on vera un peu plus tard ce concept), de theoremes,... qui traite d'un sujet particulier.

1.2.1 Les denitions

Un element important d'une theorie sont lesdenitions. Formellement, une denition est un enonce qui introduit un nouveau symbole appeleterme a partir d'une suite de symboles deja connus, appelleassemblage. On vera en eet plus loin que nous utiliserons un langage symbolique. Toutefois, on ne peut utiliser exclusivement les symboles pour des raisons pratiques : une denition utilisant les symboles logiques exclusivement est tres"lourde»a lire, on utilise alors le langage courant. Toutefois, pour ne pas perdre toute la 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 axiomes

Ce 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'ailleurs inutile 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 qui est logique mais c'est important). Aucun axiome ne peut ^etre remis en cause dans la theorie, sans quoi on dira que cette theorie estinconsistante. Les philosophes grecques avait une denition quelque peu dierente de l'axiome : un axiome est une verite que l'on ne demontre pas car evidente en soi. Cette maniere de voir les choses pose probleme : comment quelque chose peut il ^etre"evident»? Pourquoi cet axiome est vrai? N'aurait il pas pu ^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 : 2

1.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 trace en 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 vouloir le remettre en cause, les mathematiciens pensaient qu'il etait inutile car il pouvait se demontrer a partir des autres. Cependant, toutes les tentatives pour demontrer cet axiome ont echoue. Les mathematiciens ont eu alors une idee : ils ont tentes de voir ce qui ce passait si on refutait cet axiome, c'est a dire que l'on le considere comme faux. Ils esperaient ainsi aboutir a une contradiction 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 comme Gauss et Lobachevsky. Celui ci s'amusa a remplacer le cinquieme axiome par ceci : par un point exterieur a une droite, on peut mener deux paralleles a cette droite. Il developpe a partir de ca toute une geometrie coherente mais tout a fait dierente de celle d'Euclide. C'est un exemple de geometrienon- euclidienne. Il exite dierentes sortes de geometrie non-euclidienne, l'idee de

Lobachevsky 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 pas plat : 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'axiome n'est pas le bon. Il semblait"evident»que le cinquieme d'axiome d'Euclide est vrai alors quel'on peut tres bien dire qu'il soit fauxet avoir toutefois une geometrie coherente. La plus belle preuve est qu'Einstein a montre que les geometrie non-euclidienne ont un sens physique puisque l'espace dans lequel nous vivons est courbe dans un champ de gravitation : si vous dessiner un triangle et que vous ^etes capable de mesurer ses angles avec une precision extraordinaire (ce qui est en pratique malheureusement impossible), vous ve- rez que la somme des angles ne vaut pas exactement 180 degres, la dierence sera inme mais reelle. La morale de l'histoire : il n'existe aucune verite evidente par elle m^eme en mathematique,un axiome n'est pas vrai parce qu'il est vrai mais vrai parce que l'on a decide qu'il soit vrai.

1.2.3 Les theoremes

Maintenant, a partir de ces axiomes, on peut en tirer destheoremes. Un theoreme est une assertion vraie qui est demontre a partir des axiomes (ou a partir d'autres theoremes eux m^eme demontre par des axiomes mais cela revient au m^eme). Un theoreme necessite donc une demontration. En plus de 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 ce terme 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 avec une forte probabilite), une conjecture demontre devient un theoreme, 3. corollaire : un corollaire e stune cons equenceimm ediated'un th eoreme demontre.

1.3 Bref historique

Les 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 tres longtemps, elle predomine jusqu'au MoyenAges au moins, et ce n'est que tres recemment qu'est apparu la logique moderne. C'est Frege qui a pose les bases de la logique moderne. La dierence essentielle par rapport a la logique d'Aristote est que Frege a une approche mathematique de la logique, alors que la logique d'Aristote est teintee de Philosophie. Il va ainsi developper la logique des propositions et la logique des 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 pas a 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 symboles sont derives de ce langage. Nous allons donc commencer par tenter de preciser la notion de langage en mathematique pour comprendre son inter^et.

2 Le langage formel

2.1 Introduction

L'idee d'utiliser un langage symbolique permet de simplier beaucoup de choses en mathematique. On peut donner un exemple simple : supposons que nous devions calculer"la somme de la racine carre du quotient de 27 par 3 et du produit de 2 et 7», on comprend tout de suite qu'on y voit plus clair en ecrivant : r27 3 + 27

2.2 Langage formel et langage naturel

On va donc adapter cette idee a la logique mais avant cela, il faut preciser ce que l'on entend par"langage». Il faut d'abord distinguer lelangage na- tureldulangage formel. Le langage naturel est le langage que nous utilisons dans la vie de tout les jours, qui a deux inconvenients majeurs quand on l'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, ce qui est impossible lorsqu'il y a ambiguites.

2.3 Denition

Lorsque l'on denit un langage formel, on doit denir deux choses qui caracterisent ce langage : 1. un alphabetcad un ensemble de symboles (comme dans le cas des langages 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 dit aussicha^ne de caractere) est une suite ordonnee de symboles, ces symboles appartenant a un alphabet.

Nous pouvons donc denir ce qu'est un langage formel :Unlangage formelest un ensemble de mots de longueur nie

deni par un alphabet et une syntaxe.On peut donner un exemple pour y voir plus clair et denir un langage

formel simple : on va prendre un alphabet et une syntaxe quelconque, ne voyez 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 fait que l'on dira des"formules»au lieu de dire des"mots».

3 Introduction au calcul des propositions

3.1 Introduction

La notion de"proposition»est fondamentale en logique et deja presente dans la logique d'Aristote. On peut denir cette notion tres facilement : une proposition est tout simplement une armation. Il faut faire attention que cette armation puisse ^etre vrai ou fausse, par exemple"je mens»n'est pas une proposition, en eet, si quelqu'un dit"je mens», alors si il dit la verite 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 completement vraies, soit completement fausses. Par exemple,"Il pleut»peut ^etre vrai ou faux mais pas autre chose, cette phrase peut donc ^etre consideree comme une proposition. On laisse donc de c^ote pour l'instant les phrase qui ne sont ni 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 proposition est soit vraie soit fausse mais pas autre chose. On dit que la"valeur de verite»d'une proposition est"vraie»ou"fausse». 6 Puisque nous voulons adopter un langage symbolique, nous devons notez les propositions par un simple symbole, en regle general, une proposition est notee avec une lettre majuscule. Comme nous avons dit que les mots du langage de la logique sont appeles des formules, on dira que les propositions sont des formules.

3.2 Connecteurs logiques

Le notion deconnecteur logiqueest deja presente dans la logique d'Aris- tote. C'est une notion qui apparait naturellement lorsque l'on tente de faire des raisonnements. Prenons un exemple. Considerons deux propositionsAetB. On peut imaginer que deAon peut deduireB, c'est a dire que siAest vrai, alors Best vrai lui aussi. On ecrit alors :"siAalorsB». Mais on a alors que la phrase"siAalorsB»peut ^etre vrai ou fausse. En eet, siAveut dire"ceci un cobra»etBveut dire"ceci est un serpent», alors"siAalorsB»veut dire"si ceci un cobra alors ceci est un serpent»ce qui est vrai. Mais on peut imaginer queAveut dire"ceci est un tigre»et alors"siAalorsB»devient faux. On comprend alors que lorsque l'on combine des propositions de cette maniere, on obtient des phrases qui ont aussi une valeur de verite, le principe du tiers exclu s'applique aussi a ces phrases. On va dire que ces phrases sont aussi des formules. On dit que ce sont desformules composeesalors que les propositions sont desformules atomiques. Les mots"si»et"alors»sont des connecteurs logiques (en fait il n'en forment qu'un puisqu'on les utilisent ensembles). Nous allons maintenant en voir 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 proposition A. 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:AVF FV

3.2.2 Le connecteur"ou»(disjonction)

Ce connecteur permet de former des formules comme"AouB»mais il faut faire attention que siAetBsont tout les deux vrais alors"AouB» est vrai aussi. Ce connecteur s'ecrit_.

On a donc la table de verite :

ABA_BVVV

VFV FVV FFF On a queA_Best faux siAetBsont tout les deux faux, vrai dans tout les autres cas.

3.2.3 Le connecteur"et»(conjonction)

Ce connecteur permet de former des formules comme"AetB», il est represente par le symbole^.ABA^BVVV VFF FVF FFF A^Best vrai siAetBsont tout les deux vrais, faux dans tout les autre cas.

3.2.4 Le connecteur"si... alors»(conditionnel materiel)

Il est represente par le symbole :).ABA)BVVV

VFF FVV FFV "siAalorsB»veut dire que siAest vrai,Bl'est necessairement aussi. La seule 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,BVVV VFF FVF FFV 8

3.2.6 D'autres connecteurs

Ces connecteurs ne sont pas ou peu utilises en mathematique, mais plut^ot en 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 NOT est 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 B

110
100
010 001

La porte XOR (ou exclusif) :

ABA XOR B

quotesdbs_dbs6.pdfusesText_12

[PDF] Cours de logique - CNRS