Libro introductorio sobre lógica y computación

11

¿Me puede dar algunas sugerencias sobre un buen libro introductorio (pero completo)
sobre Lógica y Computación?

Algunos temas confusos que tengo en mente son:

  • Presburger artihm., PA, ZF, ZFC, HOL
  • Teoría de conjuntos, Teoría de tipos
  • Computación de modelado (máquinas de Turing) en diferentes teorías
  • Enlaces con complejidad computacional (FMT, complejidad descriptiva)
Vor
fuente

Respuestas:

7

Mi respuesta podría llegar tarde a esta pregunta, pero espero que sea útil para otras personas que buscan información similar.

Había tomado un curso sobre Lógica Matemática en la Universidad Nacional de Singapur, en el que el profesor utilizó este libro de texto:

Una introducción concisa a la lógica matemática, 3ra edición, por Wolfgang Rautenberg

Personalmente, me gustan mucho tanto el libro de texto como el curso.

El libro de texto inicialmente parece ser bastante difícil de leer. Sin embargo, una vez que se familiariza con él, es mucho más fácil de seguir, ya que el sistema de notación es muy claro, el contenido es autónomo y el enfoque es a partir de la base, sin suposición vaga. Por ejemplo, este libro desarrolla el cálculo de deducción natural y el cálculo de Hilbert, o prueba dos teoremas de incompletitud de Kurt Gödel desde cero.

Trung Ta
fuente
4

Sugiero uno de los libros que compré recientemente:

Pavel Pudlak: Fundamentos lógicos de las matemáticas y la complejidad computacional: una introducción suave; Monografías Springer en Matemáticas; 2013

No tenía ("todavía no tengo" :-) una sólida formación en lógica y este libro me está ayudando a comprender mejor algunos aspectos "fundamentales" de la lógica y su relación con la computación y la complejidad. Sin duda un buen libro introductorio.

El TOC y el prefacio del libro se pueden descargar desde la página de inicio de Pudlak y también puede encontrar algunos extractos del libro en http://books.google.com .

De la Introducción :

... Los primeros dos capítulos son una introducción a los fundamentos de las matemáticas y la lógica matemática. El material se explica de manera muy informal y la presentación más detallada se aplaza a capítulos posteriores ... El

Capítulo 3 está dedicado a la teoría de conjuntos, que es la parte más importante de los fundamentos de las matemáticas. Los dos temas principales de este capítulo son: (1) infinitos superiores como fuente de axiomas poderosos, y (2) axiomas alternativos, como el Axioma de la Determinación ...

Las pruebas de imposibilidad, el tema del Capítulo 4, son pruebas de que ciertas tareas son imposibles, contrarias a la intuición original. Hoy en día tendemos a equiparar la imposibilidad con la no demostrabilidad y la no computabilidad, que es una visión bastante limitada. Por lo tanto, vale la pena recordar que los primeros resultados importantes de imposibilidad se obtuvieron en diferentes contextos: geometría y álgebra. El resultado más importante presentado en este capítulo es el Teorema de incompletitud de Kurt Godel ...

Las pruebas de imposibilidad son, claramente, importantes en las fundaciones. Un campo en el que los problemas más básicos tratan de demostrar la imposibilidad es la teoría de la complejidad computacional, el tema del Capítulo 5. Pero hay más conexiones entre la complejidad computacional y los fundamentos ...

De hecho, hay un campo de investigación que estudia las conexiones entre la complejidad computacional y la lógica. Se llama 'Complejidad de prueba' y se presenta en el Capítulo 6. Aunque tenemos indicios de que la complejidad debería desempeñar un papel relevante en los fundamentos, no tenemos ningún resultado que pruebe esta conexión. ...

Cada libro sobre los fundamentos de las matemáticas debe mencionar los enfoques filosóficos básicos de los fundamentos de las matemáticas. También lo hago en el Capítulo 7, pero como no soy filósofo, la parte principal del capítulo se concentra más bien en los resultados matemáticos y los problemas que están en el límite de las matemáticas y la filosofía ...

No cubre la FMT y la complejidad descriptiva, pero hay algunos buenos libros que se centran en esos temas (por ejemplo, Leonid Libkin: Elementos de la teoría de modelos finitos; Textos en informática teórica. Una serie EATCS; 2004 )

Acepto mi respuesta porque todavía no tuve la oportunidad de leer el libro sugerido por Trung Ta.

Vor
fuente
¿Podría mejorar su respuesta con una breve reseña del libro de Pudlak? Ahora sabemos que no cubre FMT y la complejidad descriptiva, pero lo que es bueno de lo que hace la cubierta?
Anton Trunov
@AntonTrunov: agregué el TOC en la respuesta. Además, me gusta su estructura general: explicar conceptos a alto nivel dar más detalles en las notas al final de los capítulos explicar pruebas (no una mera lista de fórmulas) en capítulos / secciones dedicados.
Vor
2

Me gusta el libro de Tom Stuart "Comprensión de la computación" con respecto a la computación de modelado. Ofrece una buena visión general progresiva de modelos para computación. Si recuerdo correctamente: - máquinas deterministas de estado finito - FSM no determinista - FSM con una pila (determinista y no determinista) - Máquinas de Turing (con una cinta)

Es bastante interactivo y práctico, ya que construye simultáneamente una implementación simple de cada modelo en Ruby.

tvo
fuente