[PDF] NOTES DE COURS LOGIQUE ET TECHNIQUES DE PREUVE IFT

View - Download NOTES DE COURS LOGIQUE ET TECHNIQUES DE PREUVE IFT

Previous PDF

Next PDF

NOTES DE COURS

LOGIQUE ET TECHNIQUES DE PREUVE

IFT-10540

et MATH

´EMATIQUES POUR

INFORMATICIENS

MAT-22257

Jules Desharnais

D´epartement d"informatique et de g´enie logiciel

Universit´eLaval

Qu´ebec

Automne 2006

ii

Table des mati`eres

0 Introduction 1

1 Substitution textuelle et r`egle de Leibniz 3

1.1 Pr´eliminaires . ..................................3

1.2 Substitution textuelle ..............................5

1.3 R`egles d"inf´erence . . ..............................7

1.4 Raisonner sur l"´egalit´e..............................7

1.5 R`egle de Leibniz et ´evaluation des fonctions . .................9

1.6 Probl`emes.....................................9

2 Expressions bool´eennes 13

2.1 Syntaxe des expressions bool´eennes . . .....................13

2.2 Tables de v´erit´e .................................15

2.3´Egalit´e versus ´equivalence............................16

2.4 Satisfiabilit´e et validit´e..............................18

2.5 Mod´elisation de propositions ´enonc´ees en fran¸cais . . .............18

2.6 Probl`emes.....................................25

3 Logique propositionnelle 27

3.1 Pr´eliminaires . ..................................27

3.2´Equivalence et vrai . . ..............................28

3.3 N´egation, in´equivalence et faux .........................32

3.4 Disjonction . . ..................................36

3.5 Conjonction . . ..................................38

3.6 Implication . . ..................................42

3.7 Probl`emes.....................................46

4 Assouplissement du style de preuve 49

4.1 Une abr´eviation pour la d´emonstration d"implications............49

4.2 Techniques de d´emonstration additionnelles . .................51

4.3 Probl`emes.....................................

54

5 Application du calcul propositionnel : r´esolution d"´enigmes 55

5.1 Probl`emes.....................................59

iii ivTABLE DES MATI`ERES

6 Quantification 61

6.1 Types.......................................61

6.2 Syntaxe et interpr´etation de la quantification .................64

6.3 Lois de la quantification.............................68

6.4 Manipulation des domaines . . .........................73

6.5 Probl`emes.....................................74

7 Le calcul des pr´edicats 75

7.1 Quantification existentielle . . .........................75

7.2 Quantification universelle............................77

7.3 Monotonie et ´echange des quantificateurs . . .................81

7.4 Du fran¸cais `a la logique des pr´edicats . .....................83

7.5 Probl`emes.....................................84

8 Induction math´ematique 87

8.1 Induction sur les nombres naturels . . .....................87

8.2 D´efinitions inductives ..............................92

8.3 Probl`emes.....................................99

9 Autres techniques de preuve 101

9.1 Quelques lois additionnelles . . .........................101

9.2 Preuves par cas ..................................103

9.3 Preuves par implication mutuelle........................106

9.4 Preuves par contradiction............................106

9.5 Preuves par contraposition . . .........................113

9.6 Probl`emes.....................................114

10 Pr´edicats et programmation 115

10.1 Instruction d"affectation.............................115

10.2 Sp´ecification de programmes . .........................118

10.3 Plus faibles pr´econditions............................120

10.4 Axiome de l"affectation.............................121

10.5 S´equence.....................................123

10.6 Instructionskip.................................125

10.7 Instruction conditionnelle

............................125

10.8 Blocbegin-end.................................126

10.9 It´eration (boucle).................................127

10.10 Probl`emes.....................................133

11 Th´eorie des ensembles 135

11.1 Compr´ehension et appartenance........................135

11.2 Op´erations sur les ensembles . .........................141

11.3 Th´eor`emes sur les op´erations ensemblistes . . .................143

11.4 Union et intersection de familles d"ensembles .................146

11.5 Probl`emes.....................................147

TABLE DES MATI`ERESv

12 Relations et fonctions 149

12.1n-uplets et produits cart´esiens .........................149

12.2 Relations.....................................151

12.3 Fonctions.....................................161

12.4 Relations d"ordre.................................163

12.5 Bases de donn´ees relationnelles .........................164

12.6 Probl`emes.....................................167

13 Th´eorie des graphes 169

13.1 Graphes et chemins . ..............................169

13.2 Repr´esentation matricielle des graphes .....................172

13.3 Classes de graphes particuli`eres .........................176

13.4 Isomorphisme . ..................................177

13.5 Circuits Hamiltoniens ..............................177

13.6 Graphes planaires . . ..............................178

13.7 Arbres . ......................................179

13.8 Probl`emes.....................................180

14 Solution des probl`emes 181

14.1 Probl`emes du chapitre 1.............................181

14.2 Probl`emes du chapitre 2.............................187

14.3 Probl`emes du chapitre 3.............................190

14.4 Probl`emes du chapitre 4.............................200

14.5 Probl`emes du chapitre 5.............................203

14.6 Probl`emes du chapitre 6.............................211

14.7 Probl`emes du chapitre 7.............................215

14.8 Probl`emes du chapitre 8.............................219

14.9 Probl`emes du chapitre 9.............................224

14.10 Probl`emes du chapitre 10............................227

14.11 Probl`emes du chapitre 11

............................239

14.12 Probl`emes du chapitre 12............................244

14.13 Probl`emes du chapitre 13............................254

Bibliographie 261

APr´es´eance (priorit´e) des op´erateurs 263

B Liste des lois 265

viTABLE DES MATI`ERES

Chapitre 0

Introduction

Les propositions suivantes sont-elles vraies?

1.Si Superman voulait et pouvait pr´evenir le mal, il le ferait. Si Superman ne pouvait

pr´evenir le mal, il serait impuissant; s"il ne voulait pas pr´evenir le mal, il serait mal- veillant. Superman ne pr´evient pas le mal. Si Superman existe, il n"est ni impuissant, ni malveillant. Par cons´equent, Superman n"existe pas.

2.vest dans le tableaub[1..10] signifie que si la valeurvest dansb[11..20] alors elle n"est

pas dansb[11..20]. Le programme fait-il ce que les assertions pr´etendent qu"il fait? V´erifiez le programme suivant. Les variablesa,b,ietnsont enti`eres. b,i:= 1,0; i {Fonction majoranten-i} whilei2CHAPITRE 0. INTRODUCTION

Chapitre 1

Substitution textuelle et r`egle de

Leibniz

1.1 Pr´eliminaires

Syntaxe des expressions math´ematiques conventionnelles

Elles sont construites avec

-desconstantes(comme 42, 3.14), -desvariables(commea,x,y), -desop´erateurs(comme +,·,÷,=,<).

Par exemple,

13 z x+3+z 2 x+5>8÷x 2 sont des expressions. D´efinition de la syntaxe des expressions simples : -Une constante est une expression. -Une variable est une expression. -SiEest une expression, alors (E) est une expression. -Si◦est un op´erateur unaire pr´efixe etEune expression, alors◦Eest une expression, avec op´erandeE. Exemple :-peut ˆetre utilis´e comme op´erateur unaire pr´efixe, de sorte que-18 est une expression. -Si?est un op´erateur binaire infixe, et siDetEsont deux expressions, alorsD?Eest une expression. Par exemple, 8 + 14 et (-18)·(t+ 4) sont des expressions. Les parenth`eses expriment l"agr´egation : 2·(5 + 13). Priorit´e(pr´es´eance) des op´erateurs :voyez latable 1.1. 3

4CHAPITRE 1. SUBSTITUTION TEXTUELLE ET R`EGLE DE LEIBNIZ

Tab.1.1 -

Pr´es´eance (priorit´e) des op´erateurs (1) [x:=e] (substitution textuelle) (priorit´e´elev´ee) (2).(application de fonction) (3) +-¬P(op´erateurs unaires pr´efixes) (4)·/÷mod pgcd×◦ (5) +-?∩(op´erateurs binaires) (6)↓↑ (7)=<>????? (8)?? (9)?????? (10)≡?≡(priorit´e faible) Les op´erateurs binaires non associatifs sont associatifs `a gauche, sauf?, qui est associatif `a droite. Si?est un op´erateur binaire et quea?best une expression bool´eenne, alors la notationa??best une abr´eviation pour l"expression¬(a?b). L"op´erateur??alamˆeme

pr´es´eance que?. On voit des exemples de tels op´erateurs aux lignes (7, 9, 10). Vous pouvez

utiliser cette abr´eviation en tout temps et il n"est pas n´ecessaire de donner un num´ero de loi

pour la justifiersi un tel num´ero de loi n"existe pas.

A cause des conventions de pr´es´eance,

2·3+8 = (2·3) + 8.

(1.1) Exercice.Ajoutez les parenth`eses qui font qu"on n"aurait plus besoin de r`egles de priorit´e.

1.a?b?c?a∩b=a?c

2.a∩b?c

Notion d"´etat

Un´etatest une liste de variables avec leur valeur : (a,8.91),(x,10),(y,5) L"´evaluation d"une expression dans un ´etatEse fait en rempla¸cant toutes les variables deEpar leur valeur et en calculant la valeur de l"expression r´esultante : a+x·(x+y)=8.91 + 10·(10 + 5) = 158.91

1.2. SUBSTITUTION TEXTUELLE5

1.2 Substitution textuelle

(1.2) Notation.Substitution textuelle.

SoientEetRdes expressions, etxune variable.

E[x:=R]

d´enote l"expressionEavecTOUTESles occurrences dexremplac´ees par (R).

Suppression des

Expression R´esultat parenth`eses inutiles

x[x:=t+5] (t+5)t+5 (y+x)[y:=t+5] ((t+5)+x)t+5+x (x·y)[x:=t+5] ((t+5)·y)(t+5)·y (y+y)[y:= 5] ((5) + (5)) 5 + 5 (y+ 10)[x:= 5] (y+ 10)y+10

Pr´esentation que nous adopterons :

(x+ 2)[x:=t+2] =?Substitution? ((t+2)+2) =?Suppression des parenth`eses inutiles? t+2+2 Notez que si on demande simplement d"effectuer la substitution (x+ 2)[x:=t+2],

le calculdoit s"arrˆeter`a cette ´etape, sans r´eduire l"expression `a la formet+ 4. On n"utilise

pas de lois de l"arithm´etique, sauf l"associativit´e (qui permet de supprimer des parenth`eses).

(1.3) Notation.Substitution textuelle simultan´ee.

Soient

-Eune expression, -x:x 1 ,...,x n une liste de variablesDISTINCTES, -R:R 1 ,...,R n une liste d"expressions.

E[x:=R]

d´enote l"expressionEdans laquelleTOUTESles occurrences des variables de la listexont

´et´e remplac´ees simultan´ement par les expressions correspondantes de la listeR, mises entre

parenth`eses.

6CHAPITRE 1. SUBSTITUTION TEXTUELLE ET R`EGLE DE LEIBNIZ

(b+a)[a,b:=b·b,c] =?Substitution? ((c)+(b·b)) =?Suppression des parenth`eses inutiles? c+b·b (1.4) Exercice.Effectuez les substitutions suivantes, puis ´eliminez les parenth`eses super- flues.

1.(x+x·2)[x:=x·y]

2.(x+y·x)[x,y:=b+2,x+2]

(1.5) Notation.Priorit´e de la substitution textuelle : La substitution a priorit´e sur toutes les autres op´erations. (x+y)[x,y:= 2,3] = 2 + 3 x+y[x,y:= 2,3] =x+3 (1.6) Notation.Associativit´e`a gauche de la substitution : E[x:=

Q][y:=R]=?E[x:=Q]?[y:=R]

(1.7) Exercice.Effectuez les substitutions requises, puis ´eliminez les parenth`eses super- flues. (x+y·x)[x:=y+ 2][y:=y·x]

(1.8) Exercice.Consid´erez les op´erateurs suivants. La priorit´e 1 est la plus ´elev´ee et 7 la

plus faible.

Priorit´eOp´erateur

1[x:=e] (Substitution)

2??

3♥

4♦

5♣

6♠

7?†?

Effectuez les substitutions et supprimez les parenth`eses superflues. ((a?b)?b?a)[a:=b?a][b:=c?c]

1.3. R`EGLES D"INF´ERENCE7

1.3 R`egles d"inf´erence

R`egle d"inf´erence-→?A,B,C←-pr´emisses

D←-conclusion

On parle aussi d"hypoth`eses, au lieu depr´emisses. La r`egle dit que siA,B,Csont des th´eor`emes, alorsDest un th´eor`eme.

R`egle deSubstitution

(1.9) Substitution :E

E[v:=F]

Exemple :

2·a-a=a

(2·a-a=a)[a:= 5 +t]

Apr`es avoir fait la substitution, on obtient

2·a-a=a

2·(5 +t)-(5 +t)=5+t

Cet exemple est une instance de la r`egle, avec

E:2·a-a=a

v:a F:5+t

1.4 Raisonner sur l"´egalit´e

SoientXetYdes expressions.

-siXetYontlamˆeme valeur, (X=Y)=vrai; -siXetYn"ont pas la mˆeme valeur, (X=Y)=faux. On veut pouvoir raisonner au sujet de l"´egalit´eX=Ysans toujours devoir ´evaluerXet

Y.`A cette fin, nous nous dotons de lois comme

(x=y)=(y=x).

Lois de l"´egalit´e

Soientx,ydes variables etX,Ydes expressions.

8CHAPITRE 1. SUBSTITUTION TEXTUELLE ET R`EGLE DE LEIBNIZ

(1.10) R´eflexivit´e:x=x (1.11) Sym´etrie (commutativit´e) :(x=y)=(y=x) (1.12) Transitivit´e:X=Y, Y=Z X=Z Loi ´enonc´ee par Leibniz (il y a 350 ans) : Deux expressions sont ´egales si et seulement si le remplacement de l"une par l"autre dans n"importe quelle expressionEne change pas la valeur deE.

Cons´equence de cette loi :

(1.13) Leibniz : X=Y

E[z:=X]=E[z:=Y]

Exemple : la r`egle de Leibniz avec

X:b+3Y:c+5E:d+zz:z

donne b+3 =c+5 (d+z)[z:=b+3] = (d+z)[z:=c+5] c"est-`a-direb+3 =c+5 d+b+3 =d+c+5 (1.14) Exercice.Voici une instance incompl`ete de la r`egle de Leibniz (1.13). Compl´etez la partie manquante et donnez l"expressionEcorrespondante. Donnez toutes les r´eponses possibles. 7=y+1

7·x+7·y=?

(1.15) Exercice.Consid´erez les op´erateurs de l"exercice (1.8). Voici une instance incom-

pl`ete de la r`egle de Leibniz (1.13) qui utilise ces op´erateurs. Compl´etez la partie manquante

et donnez l"expressionEcorrespondante. Donnez toutes les r´eponses possibles. a?b=c?d?e ?=f?c?d?e

1.5. R`EGLE DE LEIBNIZ ET´EVALUATION DES FONCTIONS9

1.5 R`egle de Leibniz et ´evaluation des fonctions

(1.16) Notation.Application d"une fonction `a un argument. Afin de r´eduire le nombre de symboles, nous utiliserons habituellement f.xau lieu def(x) et nous ´ecrirons (par exemple) f(a+ 5) et nonf.(a+5) lorsque l"argument est entre parenth`eses.

Autre formulation de la r`egle de Leibniz :

(1.17) Leibniz : X=Y g.X=g.Y

1.6 Probl`emes

1.Effectuez les substitutions textuelles suivantes, puis supprimez les parenth`eses super-

flues : (a)(a+b·3)[b,a:=a·b,a·a] (b)((x+y)·z)[x,y:=x,y] (c)(x+x·2)[x,y:=x,z][x:=y] (d)(x+x·y+x·y·z)[x,y:=y,x][y:= 2·y]

2.La r`egle d"inf´erence de Leibniz (1.13) donne lieu `a une infinit´eder`egles d"inf´erence

particuli`eres obtenues en assignant une expression `a ses trois param`etresE,XetY.ll y a ci-dessous des cas particuliers de la r`egle de Leibniz, avec une partie manquante. Trouvez la partie manquante et donnez l"expressionEcorrespondante. Donnez toutes les r´eponses possibles. (a) x=x+2

4·x+y=?

(b) a=b+2 ?=3·(b+2)+3·b+1

3.Cet exercice porte sur la r`egle de Leibniz (1.13). On vous donne l"expressionE[z:=X]

ainsi que l"indiceX=Y. Trouvez l"expression r´esultanteE[z:=Y].

E[z:=X]X=Y

(a)(x+y)·ww=x·y (b)p∩qq=q?r

10CHAPITRE 1. SUBSTITUTION TEXTUELLE ET R`EGLE DE LEIBNIZ

4.Cet exercice porte sur la r`egle de Leibniz (1.13). Pour chacune des paires d"expressions

E[z:=X]etE[z:=Y] ci-dessous, donnez les expressionsXetYtelles queE[z:= X]=E[z:=Y]. Indiquez ensuite quelle est l"expressionE. Donnez toutes les r´eponses possibles.

E[z:=X]E[z:=Y]

(a)x·y·xy·x·x (b)p?q?(r?p)p?q?q

5.Utilisez la table de pr´es´eance suivante pour faire les substitutions demand´ees.`A l"ex-

ception de la substitution, tous les op´erateurs sont des op´erateurs binaires. La priorit´e1

est la plus ´elev´ee et 7 la plus faible.

Priorit´eOp´erateur

quotesdbs_dbs23.pdfusesText_29

[PDF] Gestion et management des achats - Decitre

[PDF] Révisions sur les acides et les bases - Nicole Cortial

[PDF] Cours 5 - Equilibres Acido-basiques

[PDF] acoustique - Maths-Sciences

[PDF] acoustique du batiment - Doc 'INSA

[PDF] Introduction ? l 'acoustique

[PDF] Gestion des entreprises et des administrations

[PDF] Manuel de Travaux Pratiques Administration Système en - inetDoc

[PDF] Chapitre 4 : ADN et information génétique Nous savons que toutes

[PDF] Flash CS3 - Adobe

[PDF] Utilisation de Flash Professional CS5 et CS55 (PDF) - Adobe

[PDF] Adressage IPv4 - inetDoc

[PDF] ADVF Titre Professionnel - CCP1 - Fichier-PDFfr

[PDF] L 'Aéronautique - BIA - acriv