[PDF] [PDF] Fondements de linformatique Logique, modèles, et calculs

[PDF] Généralités sur les fonctions - Maths-francefr

Soit f une fonction définie sur un intervalle I de R La courbe représentative de f ou plus simplement le graphe de f est l'ensemble des points de coordonnées (x, f 

[PDF] Analyse fonctionnelle, fonctions de lignes et équations - Numdam

L'analyse fonctionnelle, qui a pour objet l'étude de ces fonction- nelles, apparaît P LÉVY grales antérieures à l'année 19 Ï i, ou encore au tome 3 du Courts d' Analyse de E Goursat ralité très différents suivant les cas Il y a d'ailleurs deux  

[PDF] Fonctions polylogarithmes, nombres polyzêtas et - Numdam

La fonction zêta de Riemann est une vieille connaissance Ce n'est ralité, la formule précédente s'écrit Je citerai les autres contributions au cours du dé-

[PDF] LEtat moderne et ses fonctions (3e éd rev et augm - Gallica - BnF

vent étudié en détail, estencore mal connu de la géné- ralité de ceuxqui en dissertent (t) Michel Chevalier, Cours d'économie politique, tome Il, Go leçon

[PDF] Introduction à lanalyse harmonique

23 oct 2019 · Cours introductif de niveau M2, septembre–octobre 2019 3 Fonctions harmoniques sur le disque ; transformée de Hilbert 25 3 1 Égalité de la moyenne, En réalité on n'a que rarement affaire à des 20temperees pdf

[PDF] Les théorèmes de M Valiron sur les fonctions - Purdue Math

théorie générale vraiment cohérente et satisfaisante des fonctions entières, compre- nant un grand nombre de ralité dont il est susceptible : THÉORÈME D - (I) Voir par exemple E GOURSAT, Cours d'analyse, 3e édition , I9I9, Note

[PDF] Fondements de linformatique Logique, modèles, et calculs

Ce cours est un cours sur les fondements de l'informatique : il se focalise sur trois de l'école polytechnique en fonction de leurs préférences ordonnées réalité pas une règle, mais une famille de règles, une pour chaque élément a de A

[PDF] Introduction à la comptabilité - Dunod

Chapitre 1 La comptabilité : définition, fonctions et rôles 3 Chapitre 2 La d' ouvrages de cours et d'entraînement qui font référence Ces ouvrages Le travail du comptable consiste donc à traduire une réalité économique diversifiée en une

[PDF] Analyse et Équations aux Dérivées Partielles - Thomas Alazard

EDP de ce cours, Arthur Leclaire, Ayman Rimah et Rémi Tesson qui ont 3 3 Théorèmes d'inversion locale et des fonctions implicites ralité que f ˙Hs = 1

[PDF] Notes de cours de Géométrie différentielle - webusersimj-prgfr

16 sept 2016 · http://www math u-psud fr/„paulin/notescours/cours geodiff pdf (3) C Viterbo, Notes que la fonction ¯φ “ pφk`1, ,φnq : U Ñ Rn´k a une différentielle surjective en tout point ralité que M est connexe Supposons que M est 

[PDF] réflexion personnelle rapport de stage 3eme

[PDF] conclusion rapport de stage

[PDF] ce que le stage m a apporté 3eme

[PDF] réflexion critique rapport de stage

[PDF] propara montpellier rééducation

[PDF] propara avis

[PDF] centre propara montpellier 34

[PDF] mas propara montpellier

[PDF] propara montpellier piscine

[PDF] propara recrutement

[PDF] propara montpellier recrutement

[PDF] centre neurologique montpellier

[PDF] fonction exercice corrigé 3eme

[PDF] recit de science fiction

[PDF] exposé sur la science fiction

Fondements de l"informatique

Logique, modèles, et calculs

Cours INF423

de l"Ecole Polytechnique

Olivier Bournez

Version du 20 septembre 2013

2

Table des matières

1 Introduction 9

1.1 Concepts mathématiques . . . . . . . . . . . . . . . . . . . . . . . .

11

1.1.1 Ensembles, Fonctions . . . . . . . . . . . . . . . . . . . . .

11

1.1.2 Alphabets, Mots, Langages . . . . . . . . . . . . . . . . . . .

13

1.1.3 Changement d"alphabet . . . . . . . . . . . . . . . . . . . .

14

1.1.4 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

1.1.5 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

1.2 La méthode de diagonalisation . . . . . . . . . . . . . . . . . . . . .

18

1.3 Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . .

19

2 Récursivité et induction 21

2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.2 Raisonnement par récurrence surN. . . . . . . . . . . . . . . . . . .21

2.3 Définitions inductives . . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.3.1 Principe général d"une définition inductive . . . . . . . . . .

23

2.3.2 Formalisation : Premier théorème du point fixe . . . . . . . .

24

2.3.3 Différentes notations d"une définition inductive . . . . . . . .

24

2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.4.1 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . .

25

2.4.2 Arbres binaires étiquetés . . . . . . . . . . . . . . . . . . . .

26

2.4.3 Expressions arithmétiques . . . . . . . . . . . . . . . . . . .

27

2.4.4 Termes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.5 Preuves par induction . . . . . . . . . . . . . . . . . . . . . . . . . .

29

2.6 Dérivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.6.1 Écriture explicite des éléments : Second théorème du point fixe

30

2.6.2 Arbres de dérivation . . . . . . . . . . . . . . . . . . . . . .

31

2.7 Fonctions définies inductivement . . . . . . . . . . . . . . . . . . . .

33

2.8 Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . .

34

3 Calcul propositionnel 35

3.1 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

3.2 Sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.3 Tautologies, formules équivalentes . . . . . . . . . . . . . . . . . . .

38

3.4 Quelques faits élémentaires . . . . . . . . . . . . . . . . . . . . . . .

38
3

4TABLE DES MATIÈRES

3.5 Remplacements d"une formule par une autre équivalente . . . . . . .

39

3.5.1 Une remarque simple . . . . . . . . . . . . . . . . . . . . . .

40

3.5.2 Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3.5.3 Compositionnalité de l"équivalence . . . . . . . . . . . . . .

40

3.6 Système complet de connecteurs . . . . . . . . . . . . . . . . . . . .

41

3.7 Complétude fonctionnelle . . . . . . . . . . . . . . . . . . . . . . . .

41

3.8 Formes normales . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3.8.1 Formes normales conjonctives et disjonctives . . . . . . . . .

42

3.8.2 Méthodes de transformation . . . . . . . . . . . . . . . . . .

44

3.9 Théorème de compacité . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.9.1 Satisfaction d"un ensemble de formules . . . . . . . . . . . .

45

3.10 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

3.11 Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . .

47

4 Démonstrations 49

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

4.2 Démonstrations à la Frege et Hilbert . . . . . . . . . . . . . . . . . .

50

4.3 Démonstration par déduction naturelle . . . . . . . . . . . . . . . . .

53

4.3.1 Règles de la déduction naturelle . . . . . . . . . . . . . . . .

53

4.3.2 Validité et complétude . . . . . . . . . . . . . . . . . . . . .

54

4.4 Démonstrations par résolution . . . . . . . . . . . . . . . . . . . . .

54

4.5 Démonstrations par la méthode des tableaux . . . . . . . . . . . . . .

56

4.5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.5.2 Description de la méthode . . . . . . . . . . . . . . . . . . .

58

4.5.3 Terminaison de la méthode . . . . . . . . . . . . . . . . . . .

59

4.5.4 Validité et complétude . . . . . . . . . . . . . . . . . . . . .

60

4.5.5 Complétude . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

4.5.6 Une conséquence du théorème de compacité . . . . . . . . .

62

4.6 Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . .

62

5 Calcul des prédicats 63

5.1 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

5.1.1 Termes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

5.1.2 Formules atomiques . . . . . . . . . . . . . . . . . . . . . .

65

5.1.3 Formules . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

5.2 Premières propriétés et définitions . . . . . . . . . . . . . . . . . . .

66

5.2.1 Décomposition / Lecture unique . . . . . . . . . . . . . . . .

66

5.2.2 Variables libres, variables liées . . . . . . . . . . . . . . . . .

67

5.3 Sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.3.1 Interprétation des termes . . . . . . . . . . . . . . . . . . . .

69

5.3.2 Interprétations des formules atomiques . . . . . . . . . . . .

70

5.3.3 Interprétation des formules . . . . . . . . . . . . . . . . . . .

71

5.3.4 Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . .

72

5.4 Équivalence. Formes normales . . . . . . . . . . . . . . . . . . . . .

73

5.4.1 Formules équivalentes . . . . . . . . . . . . . . . . . . . . .

73

5.4.2 Forme normale prénexe . . . . . . . . . . . . . . . . . . . .

74

TABLE DES MATIÈRES5

5.5 Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . .

76

6 Modèles. Complétude. 77

6.1 Exemples de théories . . . . . . . . . . . . . . . . . . . . . . . . . .

78

6.1.1 Graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

6.1.2 Remarques simples . . . . . . . . . . . . . . . . . . . . . . .

78

6.1.3 Égalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

6.1.4 Petite parenthèse . . . . . . . . . . . . . . . . . . . . . . . .

80

6.1.5 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

6.1.6 Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

6.1.7 Arithmétique de Robinson . . . . . . . . . . . . . . . . . . .

82

6.1.8 Arithmétique de Peano . . . . . . . . . . . . . . . . . . . . .

84

6.2 Complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

6.2.1 Conséquence . . . . . . . . . . . . . . . . . . . . . . . . . .

85

6.2.2 Démonstration . . . . . . . . . . . . . . . . . . . . . . . . .

85

6.2.3 Énoncé du théorème de complétude . . . . . . . . . . . . . .

85

6.2.4 Signification de ce théorème . . . . . . . . . . . . . . . . . .

85

6.2.5 Autre formulation du théorème . . . . . . . . . . . . . . . . .

86

6.3 Preuve du théorème de complétude . . . . . . . . . . . . . . . . . . .

86

6.3.1 Un système de déduction . . . . . . . . . . . . . . . . . . . .

86

6.3.2 Théorème de finitude . . . . . . . . . . . . . . . . . . . . . .

87

6.3.3 Deux résultats techniques . . . . . . . . . . . . . . . . . . .

87

6.3.4 Validité du système de déduction . . . . . . . . . . . . . . . .

89

6.3.5 Complétude du système de déduction . . . . . . . . . . . . .

89

6.4 Compacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

6.5 Autres conséquences . . . . . . . . . . . . . . . . . . . . . . . . . .

92

6.6 Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . .

92

7 Modèles de calculs 93

7.1 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

7.1.1 Ingrédients . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

7.1.2 Description . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

7.1.3 Programmer avec des machines de Turing . . . . . . . . . . .

98

7.1.4 Techniques de programmation . . . . . . . . . . . . . . . . .

101

7.1.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . .

103

7.1.6 Variantes de la notion de machine de Turing . . . . . . . . . .

104

7.1.7 Localité de la notion de calcul . . . . . . . . . . . . . . . . .

108

7.2 Machines RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

108

7.2.1 Modèle des machines RAM . . . . . . . . . . . . . . . . . .

108

7.2.2 Simulation d"une machine RISC par une machine de Turing .

110

7.2.3 Simulation d"une machine RAM par une machine de Turing .

112

7.3 Modèles rudimentaires . . . . . . . . . . . . . . . . . . . . . . . . .

112

7.3.1 Machines àk2piles . . . . . . . . . . . . . . . . . . . . .112

7.3.2 Machines à compteurs . . . . . . . . . . . . . . . . . . . . .

114

7.4 Thèse de Church-Turing . . . . . . . . . . . . . . . . . . . . . . . .

116

7.4.1 Équivalence de tous les modèles considérés . . . . . . . . . .

116

6TABLE DES MATIÈRES

7.4.2 Thèse de Church-Turing . . . . . . . . . . . . . . . . . . . .

116

7.5 Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . .

116

8 Calculabilité 119

8.1 Machines universelles . . . . . . . . . . . . . . . . . . . . . . . . . .

119

8.1.1 Interpréteurs . . . . . . . . . . . . . . . . . . . . . . . . . .

119

8.1.2 Codage d"une machine de Turing . . . . . . . . . . . . . . .

120

8.1.3 Coder des paires, des triplets, etc... . . . . . . . . . . . . . .

121

8.1.4 Existence d"une machine de Turing universelle . . . . . . . .

122

8.1.5 Premières conséquences . . . . . . . . . . . . . . . . . . . .

123

8.2 Langages et problèmes décidables . . . . . . . . . . . . . . . . . . .

123

8.2.1 Problèmes de décision . . . . . . . . . . . . . . . . . . . . .

123

8.2.2 Problèmes versus Langages . . . . . . . . . . . . . . . . . .

124

8.2.3 Langages décidables . . . . . . . . . . . . . . . . . . . . . .

125

8.3 Indécidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

125

8.3.1 Premières considérations . . . . . . . . . . . . . . . . . . . .

125

8.3.2 Est-ce grave? . . . . . . . . . . . . . . . . . . . . . . . . . .

126

8.3.3 Un premier problème indécidable . . . . . . . . . . . . . . .

126

8.3.4 Problèmes semi-décidables . . . . . . . . . . . . . . . . . . .

127

8.3.5 Un problème qui n"est pas semi-décidable . . . . . . . . . . .

127

8.3.6 Sur la terminologie utilisée . . . . . . . . . . . . . . . . . . .

129

8.3.7 Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . .

130

8.4 Autres problèmes indécidables . . . . . . . . . . . . . . . . . . . . .

131

8.4.1 Réductions . . . . . . . . . . . . . . . . . . . . . . . . . . .

131

8.4.2 Quelques autres problèmes indécidables . . . . . . . . . . . .

133

8.4.3 Théorème de Rice . . . . . . . . . . . . . . . . . . . . . . .

134
quotesdbs_dbs16.pdfusesText_22