Introduction aux mathématiques discrètes

Page de titre......Page 1
Avant-propos......Page 5
1. Fonctions de l'algèbre logique......Page 7
2. Formules. Réalisation des fonctions par des formules......Page 11
3. Equivalence des formules. Propriétés des fonctions élémentaires. Principe de dualité......Page 16
4. Développement des fonctions booléennes suivant les variables. Forme canonique disjonctive......Page 20
5. Complétude et fermeture......Page 24
6. Classes fermées fondamentales. Théorème de complétude......Page 27
7. Aperçu des résultats de Post......Page 34
8. Fonctions de la logique k-valente. Formules et réalisation de fonctions par des formules......Page 36
9. Exemples de systèmes complets......Page 40
10. Reconnaissance dr la complétude. Théorème de complétude......Page 43
11. Quelques propriétés des fonctions essentielles. Critère de complétude......Page 47
12. Particularités des logiques k-valentes......Page 55
13. Fonctions déterminées......Page 63
14. Définition des fonctions déterminées par les arbres. Poids d'un arbre......Page 68
15. Fonctions déterminées bornées et procédés de définition de ces fonctions......Page 74
16. Opérations sur les f.d.b......Page 79
17. Exemples de systèmes complets......Page 89
18. Sur le lien entre les opérations S et R......Page 93
19. Machines de Turing......Page 97
20. Une méthode de construction de machines de Turing......Page 104
21. Les codes de machine et leurs conversions......Page 110
22. Fonctions calculables......Page 123
23. Opérations S, Rp et µ......Page 126
24. Fonctions calculables et opérations S, Rp, µ......Page 130
25. Formule de Kleene. Récursivité partielle des fonctions calculables. Exemples de systèmes complets......Page 140
26. Réalisation dans l'espace euclidien. Isomorphisme......Page 147
27. Estimation du nombre de graphes......Page 151
28. Réseaux et leurs propriétés......Page 154
29. Estimation du nombre de réseaux......Page 159
30. Réseaux bipolaires de combinaisons à deux objets......Page 162
31. n -réseaux......Page 176
Troisième partie. THÉORIE DU CODAGE......Page 180
32. Critère d'univocité du décodage......Page 183
33. Algorithme de reconnaissance de l'univocité du décodage......Page 190
34. Sur une propriété des codes déchiffrables......Page 194
35. Codes à redondance minimale......Page 197
36. Codes autocorrecteurs......Page 205
37. Notion de forme normale disjonctive. Minimisation des fonctions booléennes......Page 212
38. Simplification des formes normales disjonctives et des formes normales disjonctives non redondantes......Page 215
39. Position du problème dans la forme géométrique......Page 222
40. Forme normale disjonctive réduite......Page 227
41. Non-redondance du point de vue géométrique. Méthodes de construction de formes normales disjonctives non redondantes......Page 230
42. Quelques formes normales disjonctives obtenues de façon unique......Page 237
43. Notion d'algorithme local......Page 245
44. Notion de circuit d'éléments fonctionnels......Page 250
45. Problème de synthèse de circuits d'éléments fonctionnels......Page 259
46. Méthodes élémentaires de synthèse......Page 263
47. Minoration de L(n)......Page 267
48. Méthode de synthèse de circuits d'éléments fonctionnels d'ordre mininimal (méthode de Shannon)......Page 269
49. Synthèse d'un sommateur......Page 273
50. Synthèse de circuits d'éléménts fonctionnels réalisant des fonctions symétriques......Page 274
Bibliographie......Page 279
Index alphabétique......Page 281