Pouvez-vous me donner quelques suggestions sur un bon livre d'introduction (mais complet)
sur la logique et le calcul?
Voici quelques sujets flous auxquels je pense:
Ma réponse pourrait être en retard pour cette question, mais j'espère que cela sera utile pour d'autres personnes à la recherche d'informations similaires.
J'avais suivi un cours sur la logique mathématique à l'Université nationale de Singapour, dans lequel le professeur a utilisé ce manuel:
Une introduction concise à la logique mathématique, 3e édition, par Wolfgang Rautenberg
Personnellement, j'aime beaucoup le manuel et le cours.
Le manuel semble initialement assez difficile à lire. Cependant, une fois familiarisé avec celui-ci, il est beaucoup plus facile à suivre car le système de notation est très clair, le contenu est autonome et l'approche est en partant de la base, pas de vague hypothèse. Par exemple, ce livre développe le calcul de déduction naturelle et le calcul de Hilbert, ou prouve à partir de zéro deux théorèmes d'incomplétude de Kurt Gödel.
Je suggère l'un des livres que j'ai récemment achetés:
Je n'avais pas ("toujours pas" :-) une solide formation en logique et ce livre m'aide à mieux comprendre certains aspects "fondamentaux" de la logique et sa relation avec le calcul et la complexité. Sans aucun doute un bon livre d'introduction.
La table des matières et la préface du livre sont téléchargeables à partir de la page d'accueil de Pudlak et vous pouvez également trouver des extraits du livre sur http://books.google.com .
De l' introduction :
... Les deux premiers chapitres sont une introduction aux fondements des mathématiques et de la logique mathématique. Le matériel est expliqué de manière très informelle et une présentation plus détaillée est reportée aux chapitres suivants ... Le
chapitre 3 est consacré à la théorie des ensembles, qui est la partie la plus importante des fondements des mathématiques. Les deux thèmes principaux de ce chapitre sont: (1) les infinis supérieurs en tant que source d'axiomes puissants, et (2) les axiomes alternatifs, tels que l'axiome de la détermination ...
Les preuves d'impossibilité, sujet du chapitre 4, sont des preuves que certaines tâches sont impossibles, contrairement à l'intuition originelle. De nos jours, nous avons tendance à assimiler l'impossibilité à l'improvabilité et à la non-calculabilité, ce qui est une vision plutôt étroite. Par conséquent, il convient de rappeler que les premiers résultats d'impossibilité importants ont été obtenus dans différents contextes: géométrie et algèbre. Le résultat le plus important présenté dans ce chapitre est le théorème d'incomplétude de Kurt Godel ... Les
preuves d'impossibilité sont, de toute évidence, importantes dans les fondations. Un domaine dans lequel les problèmes les plus fondamentaux sont de prouver l'impossibilité est la théorie de la complexité de calcul, le sujet du chapitre 5. Mais il y a plus de connexions entre la complexité de calcul et les fondements ....
En fait, il existe un domaine de recherche qui étudie les liens entre la complexité informatique et la logique. Elle s'appelle «Proof Complexity» et elle est présentée au chapitre 6. Bien que nous ayons des indications que la complexité devrait jouer un rôle pertinent dans les fondations, nous n'avons aucun résultat prouvant cette connexion. ...
Chaque livre sur les fondements des mathématiques devrait mentionner les approches philosophiques de base des fondements des mathématiques. Je le fais aussi dans le chapitre 7, mais comme je ne suis pas philosophe, la partie principale du chapitre se concentre plutôt sur les résultats et les problèmes mathématiques qui sont à la frontière des mathématiques et de la philosophie ...
Il ne couvre pas la FMT et la complexité descriptive, mais il y a quelques bons livres qui se concentrent sur ces sujets (par exemple Leonid Libkin: Éléments de la théorie des modèles finis; Textes en informatique théorique. Une série EATCS; 2004 )
J'accepte ma réponse car je n'ai pas encore eu l'occasion de lire le livre proposé par Trung Ta.
J'aime le livre de Tom Stuart "Understanding computation" en ce qui concerne la modélisation du calcul. Il offre un bel aperçu progressif des modèles de calcul. Si je me souviens bien: - machines à états finis déterministes - FSM non déterministes - FSM avec une pile (déterministes et non déterministes) - Machines de Turing (avec une bande)
C'est assez interactif et pratique car il construit simultanément une implémentation simple de chaque modèle dans Ruby.
la source