Lógica matematica I: lógica proposicional, intuicionista y modal Max Fernández de Castro Departamento de Filosofía Luis Miguel Villegas Silva Departamento de Matemáticas Universidad Autónoma Metropolitana Iztapalapa Annus Zur Ehre unseren Eltern und Zulässiger Ergötzung des Geistes A Doña Bertha Silva Lescale 1926-2004 Cuicatli Quicaqui Canto Triste Cuicatli quicaqui in noyol nichoca: ye nicnotla- Oye un canto en mi corazón: me pongo a llorar, me lleno de mati tiya xochitica tic cauhtehuazque tlalticpac ye dolor: nos vamos entre flores, hemos de dejar esta Tierra: ¡estamos nican titotlanehuia o tiyazque ichan. prestados unos a otros: iremos a la casa del Sol! Ma nicnocozcati nepapan xochitl ma nomac ¡Póngame yo un collar de variadas flores: en mis manos es- on mani ma nocpacxochihui. Tic cauhtehuazque tén, florezcan en mí guirnaldas. Hemos de dejar esta Tierra: ¡estamos tlalticpac ye nican zan titotlanehuia o tiyazque prestados unos a otros: iremos a la casa del Sol! ichan. Nezahualcóyotl Der Tod ist kein Unglück für den, der stirbt, sondern für den, der überlebt K. Marx Prefacio En las últimas décadas la lógica matemática ha sufrido una expansión vertiginosa, como puede constatarse por el creciente número de artículos y libros de texto recientemente consagrados a ella. Además del volumen, la variedad de temas se ha multiplicado y el lego puede tener una impresión de desconcierto ante los muchos adjetivos que califican el término: lógica clásica, de primer orden o de orden superior, modal, intuicionista, temporal, multivalente, infinitaria, etc. En efecto, si bien originada (en su versión moderna) alrededor de temas específicos de filosofía de la matemática y del lenguaje, la lógica contemporánea se ha desarrollado en estrecha relación con muy diversos campos del saber, y sus aplicaciones sobrepasan con mucho lo que al respecto hubiera podido esperarse hace apenas 80 años. Aunque no hay un acuerdo unánime sobre su definición, bajo el rubro "lógica" se hallan siempre modelos formales que intentan capturar los rasgos fundamentales de aquello que consideramos como razonamiento correcto. Por ello, no es de extrañarse que esta disciplina sea de gran utilidad en filosofía, lingüística, psicología y computación. Sin embargo, muy frecuentemente el especialista en estas materias permanece ajeno al instrumento extraordinario que la lógica matemática le ofrece, lo cual se debe a diversos a factores, y en el caso de nuestra lengua, uno de ellos es la escasez de textos que brinden una adecuada introducción a los conceptos, técnicas y resultados básicos de esta disciplina. La obra que aquí presentamos es la primera de una serie que pretende subsanar esta deficiencia; ofrece una introducción al tema que promete combinar explicaciones sencillas, para el lector que sólo requiere una primera aproximación, con el rigor, la profundidad y la extensión destinadas al estudiante más exigente, a lo que obedecen en el texto diferentes secciones claramente demarcadas que permiten realizar lecturas a distintos niveles. Tal propósito nos decidió a concentrarnos en la lógica proposicional, entre otras cosas para que el texto tuviese dimensiones razonables que faciliten su lectura y consulta. La obra comienza con la exposición del propósito que motivará los dexi xii Prefacio sarrollos ulteriores. Presenta varias definiciones de “argumento correcto”, en grados crecientes de precisión, tratando de familiarizar al lector con los conceptos básicos de nuestra disciplina, a saber, “consecuencia lógica”, “consistencia”, “validez”, para más adelante desarrollar varios métodos sintácticos para determinar o probar que un argumento es correcto. Por último demuestra que esos algoritmos o semialgoritmos cumplen con el propósito para el que fueron diseñados: producen todas y sólo las fórmulas válidas. Dos capítulos más presentan sendos desarrollos ulteriores, uno de los cuals está dedicado a la lógica modal, que es una extensión de la lógica clásica hacia las vertientes intensionales de nuestro lenguaje. El segundo, consagrado a la lógica intuicionista, presenta una desviación de la lógica clásica que pretende codificar las formas del razonamiento. Creemos que, con ellos, el lector tendrá no sólo una idea de las direcciones en las que avanza la lógica contemporánea, sino también una buena introducción a muchos de sus desarrollos recientes. El libro fue pensado originalmente para los cursos de lógica que se imparten en la Universidad Autónoma Metropolitana, pero nuestra experiencia nos indica que su utilidad no se reducirá a este ámbito, sino que será utilizado en otras instituciones de educación superior, así como por estudiantes de diversas disciplinas y por el lector independiente que desee adentrarse en algún tópico de la lógica proposicional. Como lo indica el título, éste es el primero de una serie de volúmenes destinados a los varios aspectos de la lógica matemática. El siguiente comprenderá la lógica de predicados en su versión clásica, así como sendos capítulos dedicados a sus contrapartes modal e intuicionista. El libro está diseñado de forma tal que pueda leerse de muy diversas maneras. Por un lado, hay tres niveles de profundidad para lectores con diferentes intereses; o para un mismo lector que desee realizar una primera lectura esquemática para sucesivamente profundizar en los tópicos tratados. Otra posibilidad es que el lector no desee leer todo el libro, sino que se interese por cubrir únicamente un determinado tema. En efecto, el libro está elaborado de tal suerte que algunos capítulos puedan leerse con cierta independencia del resto. El capítulo introductorio presenta de manera un tanto informal algunas de las nociones centrales de la lógica clásica. Se trata de dar al lector, en una primera aproximación, una idea de cuál es el problema central que la lógica intenta resolver, y de cuáles son algunos de los métodos empleados para tal propósito. El segundo capítulo presenta ya una definición rigurosa de consecuencia lógica para enunciados de un cierto lenguaje formal cuya sintaxis y semántica son precisamente delimitadas. Más Prefacio xiii adelante se ofrecen definiciones de conceptos relacionados y se muestra cómo todo enunciado puede ser escrito de una manera canónica que pone fácilmente al descubierto sus condiciones de verdad. Una sección ulterior expone el teorema de compacidad y prepara al lector para la introducción de métodos de prueba. El tercer capítulo expone una serie de métodos algorítmicos y semi-algorítmicos para determinar que un enunciado del lenguaje formal presentado en forma previa es o no lógicamente verdadero, o bien, para enumerar todas las fórmulas verdaderas desde un punto de vista lógico. Estos algoritmos incluyen principalmente el procedimiento de los árboles, dos sistemas axiomáticos y el método de resolución. El resto del capítulo prueba la corrección y completud de cada uno de estos métodos, es decir, demuestra que producen todas y sólo las fórmulas lógicamente verdaderas. El cuarto capítulo presenta, en su primera parte, aplicaciones de la lógica a los circuitos lógicos y eléctricos, que conforman una parte esencial en el diseño de computadoras, sistemas digitales y electrónicos. La última sección estudia en detalle los llamados diagramas binarios de decisión, que permiten efectuar operaciones aritméticas, booleanas, comprobar equivalencia de fórmulas, etc. en una computadora mediante algoritmos eficientes. El quinto capítulo es una introducción a la lógica modal e ilustra cómo la lógica clásica puede ser extendida para aplicarse a zonas intensionales de nuestro lenguaje. En él se presentan los sistemas clásicos de lógica modal proposicional, tanto sintáctica como semánticamente. Se utiliza el método de los árboles adaptado a cada uno de estos sistemas. Enseguida se ofrece una prueba de corrección y completud de una amplia clase de sistemas axiomáticos que incluye los anteriormente expuestos. El último capítulo introduce al lector en una lógica que representa una desviación de la lógica clásica, a saber, la lógica intuicionista. Inicia el capítulo exponiendo las ideas centrales que motivan esta lógica, así como la semántica que de ellas resulta. Más tarde se establece el método de los árboles para la determinación de la validez o invalidez de fórmulas desde el punto de vista intuicionista. La siguiente sección diserta sobre un método de deducción natural para esta lógica, así como algunos resultados que la vinculan con su contraparte clásica. Por último, se prueba la completud y corrección del método de los árboles antes expuesto. Todos los capítulos contienen ejercicios de diferentes grados de complejidad. En ciertos casos, se ofrecen algunas sugerencias para su resolución. Una aclaración importante debemos hacer desde ahora. Hemos buscado facilitar al máximo la lectura del texto y ello nos ha llevado a suprimir en muchos casos, cuando no hay riesgo de confusión, las diferencias entre uso y mención de expresiones. Como Prefacio xiv podrá advertirse, con mucha frecuencia empleamos un símbolo de manera autónima, es decir, como su propio nombre; y una expresión como nombre de la concatenación de los símbolos que la conforman. Como ya se mencionó, el libro está diseñado para leerse en tres niveles de dificultad crecientes. Algunos temas son más adecuados para lectores intermedios; las N secciones de esta categoría se inician con el símbolo ; además, hay temas que requieren una madurez aun mayor por parte del lector o apelan a resultados más sofisticados; éstos se agrupan en apartados que inician con M m n. El fin de estas sec- ciones se marca con los símbolos y , respectivamente. Algunos ejercicios se para significar que son complicados, pero no imposibles, simplemente señalan con requieren mayor persistencia por parte del lector. Hemos procurado que el estudioso no requiera leer cada uno de los sistemas de prueba mencionados en la obra. Así, por ejemplo, bien puede revisar sólo tablas semánticas; o tan sólo el método de Hilbert. Puede prescindir en una primera lectura de los dos últimos capítulos, pero esperamos haber generado en él el interés por los desarrollos ulteriores de la lógica clásica. También puede ocurrir que el lector pase directamente del primer capítulo al quinto y sexto, si su interés es la lógica no clásica; aunque debemos señalar que se requiere conocimiento de las nociones y métodos de los primeros capítulos en los dos capítulos finales de la obra. Toca al instructor decidir cuál es el mejor camino a seguir. Sería de enorme ayuda para los autores conocer las opiniones de colegas, lectores, estudiantes, etc. acerca de este libro, por lo que mucho agradeceríamos nos enviaran sus comentarios a la dirección de correo electrónico: A teolote.librosgmail.om Versiones preliminares de este libro han sido utilizadas en varios cursos y seminarios. Los autores agradecen los comentarios, sugerencias y correcciones de los estudiantes involucrados. En particular, queremos expresar nuestro agradecimiento a: Cecilia Hernández, Fanny Brito, Juan Carlos Aguilar, Óscar Rendón, Kinhra Aguirre, Gabriel Salazar, Marco Talavera y Luis René San Martín, por las correcciones y mejoras que nos hicieron llegar en diversas etapas del trabajo. Un especial reconocimiento a los árbitros que hicieron numerosas sugerencias y correcciones. En lo que respecta a las ilustraciones que aparecen en diversas partes del libro y no están vinculadas con las matemáticas, están relacionadas, como seguramente el lector Prefacio xv advertirá, a la vida del J. S. Bach. Es un ejercicio más averiguar de qué se trata en cada caso. Este libro fue elaborado en el marco del proyecto Conacyt "Los problemas del conocimiento y la comprensión en matemáticas" (13611289), por lo que los autores agradecemos el apoyo recibido de parte del Conacyt. Los autores. Prefacio a la primera reimpresión Para esta primera reimpresión queremos expresar nuestra gratitud a los lectores que nos han enviado correcciones. En especial a Cecilia Hernández, Kinrha Aguirre y Oscar Rendón. Además destacamos el invaluable apoyo de la División de Ciencias sociales y Humanidades, el área de Álgebra y a la Rectoría de la unidad Iztapalapa de la Universidad Autónoma Metropolitana para llevar a buen término esta reimpresión, que tan sólo incorpora correcciones menores. Contenido I Prefacio xi Introducción a la lógica proposicional I.1 Fundamentos . . . . . . . . . . . I.2 Corrección de argumentos . . . . I.3 Conceptos básicos . . . . . . . . . I.4 Otros conectivos . . . . . . . . . I.5 Ejercicios . . . . . . . . . . . . . . . . . . 1 1 4 23 26 35 . . . . . . . . . . . . . . 39 41 42 43 43 50 54 54 58 61 69 81 90 101 103 . . . . . . . . . . . . . . . . . . . . . . . . . II El lenguaje de la lógica proposicional II.1 Introducción . . . . . . . . . . . . . . . . . II.2 Lenguajes formales . . . . . . . . . . . . . II.3 El lenguaje . . . . . . . . . . . . . . . . . II.3.1 Sintaxis del lenguaje proposicional II.3.2 Semántica del cálculo proposicional II.3.3 Convenciones . . . . . . . . . . . . II.4 Argumentos válidos . . . . . . . . . . . . . II.5 Validez, satisfacibilidad y contradicción . . II.6 Consecuencia y equivalencia . . . . . . . . II.7 Formas normales . . . . . . . . . . . . . . II.8 Árboles . . . . . . . . . . . . . . . . . . . II.9 Teorías proposicionales . . . . . . . . . . . II.10 Ultraproductos . . . . . . . . . . . . . . . II.11 Ejercicios . . . . . . . . . . . . . . . . . . xvii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENIDO xviii III Pruebas formales y sistemas deductivos III.1 Pruebas formales . . . . . . . . . . . . . . . . . . . III.2 Tablas semánticas . . . . . . . . . . . . . . . . . . . III.3 Sistemas axiomáticos . . . . . . . . . . . . . . . . . III.3.1 El sistema de Gentzen . . . . . . . . . . . . III.3.2 Sistemas de Hilbert . . . . . . . . . . . . . . III.3.3 Otra prueba de la completud y correctud de H III.4 Fórmulas de Horn . . . . . . . . . . . . . . . . . . . III.5 Resolución . . . . . . . . . . . . . . . . . . . . . . III.5.1 Cláusulas . . . . . . . . . . . . . . . . . . . III.5.2 Completud de resolución . . . . . . . . . . . III.6 Árboles semánticos . . . . . . . . . . . . . . . . . . III.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 129 131 151 152 158 172 178 182 182 188 201 208 IV Aplicaciones IV.1 Circuitos eléctricos . . . . . . IV.2 Circuitos lógicos . . . . . . . IV.3 Diagramas binarios de decisión IV.3.1 La función Build . . . IV.3.2 El algoritmo Apply . . IV.3.3 El algoritmo Restrit IV.3.4 El algoritmo SatCount IV.3.5 El algoritmo Anysat . IV.3.6 El algoritmo Allsat . IV.3.7 El algoritmo Simplify IV.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 221 225 234 261 264 267 268 269 269 270 272 . . . . . . . . 287 288 290 295 300 314 324 334 341 V Lógica modal proposicional V.1 Introducción . . . . . . V.2 Sintaxis . . . . . . . . V.3 Semántica . . . . . . . V.4 Sistemas axiomáticos . V.5 Modelos canónicos . . V.6 Árboles semánticos . . V.7 Completud . . . . . . . V.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENIDO xix VI Lógica Intuicionista VI.1 Introducción . . . . . . . . . . . . VI.2 Semántica . . . . . . . . . . . . . VI.3 Árboles semánticos . . . . . . . . VI.4 Sistema de deducción natural . . . VI.5 Completud de árboles semánticos VI.6 Ejercicios . . . . . . . . . . . . . 347 348 349 352 356 371 375 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliografía 377 Índices 381 Bibliografía [Ake78] S. B. Akers, Binary decision diagrams, IEEE Trans. Comp. C-27(6)(1978), 509-516. [Ander98] H. R. Andersen, An Introduction to Binary Decision Diagrams, unpublished manuscript, 1998. [Bar77] J. Barwise, Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977. [Bor01] E. Boerger, E. Graedel, Y. Gurevich, The classical Decision Problem, Springer-Verlag, Berlin, 2001. [Bo47] G. Boole, The Mathematical Analysis of Logic, McMillan, Cambridge, 1847. [Bo54] G. Boole, An investigation of the laws of thought, Waltona and Maberley, London, 1854. [Boo95] G. Boolos, The Logic of Provability, Cambridge University Press, 1995. [Boo02] G. Boolos, J. Burguess, R. Jeffery, Computability and Logic, Fourth Ed., Cambridge Univ. Press, 2002. [Bry86] R. E. Bryant, Graph-based algorithms for boolean function manipulation, IEEE Trans. Compilers, C-35(8), 1986. [Bry92] R. E. Bryant, Symbolic boolean manipulation with ordered binary-decision diagrams, ACM Comp. Surv. 24(3), 193-318 (1992). 377 378 Bibliografía [Che95] F. B. Chellas, Modal Logic, An Introduction, Cambridge University Press, 1995. [Co04] S. B. Cooper, Computability Theory, Chapman Hall, Boca Raton, 2004. [Cori-Lascar] R. Cori, D. Lascar, Mathematical Logic. A Course with Excercises, I, Oxford University Press, 2000. [Dal04] D. Van Dalen, Logic and Structure, 4th. Ed., Springer-Verlag, Berlin, 2004. [Dev93] K. Devlin, The Joy of Sets, 2nd. Ed., Springer-Verlag, Berlin, 1993. [Ebbing93] H. Ebbinghaus, J. Flum, W. Thomas, Einführung in die mathematische Logik, 4. Auflage, Spektrum Akad. Verlag, 1993. [Eps06] R. Epstein, Classical Mathematical Logic: The Semantic Foundation of Logic, Princeton Univ. Press, 2006. [Fr79] G. Frege, Begriffsschrift, Halle, Deutschland, 1879. [Gir00] Girle, Rod, Modal Logic and Philosophy, McGill-Queen’s University Press, Canada, 2000. [Hed04] S. Hedman, A first Course in Logic, Oxford Univ. Press, 2004. [HiBe34] D. Hilbert, P. Bernays, Grundlagen der Mathematik I, Springer-Verlag, Berlin, 1934. [Hin05] P. Hinman, Fundamentals of Mathematical Logic, A. K. Peters, USA, 2005. [HuC96] G. E. Hughes, M. J. Cresswell, A New Introduction to Modal Logic, Routledge, USA, 1996. [HuRy04] M. Huth, M. Ryan, Logic in Computer Science. Modelling and Reasoning about Systems, 2nd. Ed., Cambridge University Press, UK, 2004. Bibliografía 379 [Lee59] C. Y. Lee, Representation of switching circuits by binarydecision programs, Bell System Tech. Journal 38(1959), 985999. [Mar02] D. Marker, An Introduction to Model Theory, SpringerVerlag, Berlin, 2002. [Mend04] E. Mendelson, An Introduction to Mathematical Logic, fourth Ed., Chapman & Hall, USA, 2004. [MetNer96] G. Metakides, A. Nerode, Principles of Logic and Logic Programming, North-Holland, The Netherlands, 1996. [Min00] G. Mints, A Short Introduction to Intuitionistic Logic, Kluwer Academic/Plenum Publishers, The Netherlands, 2000. [NerSho94] A. Nerode, R. Shore, Logic for Applications, Springer-Verlag, Berlin, 1994. [Pe02] C. S. Peirce, The simplest mathematics, (Peirce’s Collected Works) Harvard Univ. Press, USA, 1933. [Pra65] D. Prawitz, Natural Deduction, A proof Theoretical Study, Acta Universitatis Stockholm, Stockholm Studies Ph. 3. Almqvist & Woksell, Stockholm, 1965. [Pre92] A. Prestel, Einführung in die mathematische Logik und Modelltheorie, Vieweg, Deutschland, 1992. [Pri01] G. Priest, An Introduction to Non-Classical Logic, Cambridge University Press, UK, 2001. [Qui82] W. V. O. Quine, Methods of Logic, Harvard University Press, USA, 1982. [Rau06] W. Rautenberg, A Concise Introduction to Mathematical Logic, Springer-Verlag, Berlin, 2006. [Rub90] J. E. Rubin, Mathematical Logic: Applications and Theory, Saunders Co. Pub., USA, 1990. 380 Bibliografía [Shoen01] J. R. Shoenfield, Mathematical Logic, A. K. Peters, USA, 2001. [Sm03] P. Smith, An Introduction to Formal Logic, Cambridge University Press, UK, 2003. [ViRoMi00] L. M. Villegas Silva et al., Conjuntos y Modelos: un curso avanzado, Universidad Autónoma Metropolitana, México, 2000. Índice de símbolos (i, j, m, n), 322 Allsat, 269 AnySat, 269 Apply, 264 B, 313 Build, 261 Cn(Σ), 66 D, 308 D4, 321 D5, 321 DB, 321 E→n , 358 E∨n,m,p , 359 E∧n , 358 Fml, 291 I→n , 358 I∨n , 358 Itn , 357 K, 301 K5, 321 KB, 321 K4 , 310 MK, 261 MP, 301 MT , 332 MS , 316 Ma(Σ), 66 NDi , 356 RS , 316 Rd1 , 362 Rd2 , 362 Rd3 , 363 Rd4 , 363 Res∗ (ϕ ), 188 Restrict, 267 S ⊢R C, 186 S ⊢R ✷, 186 S5 , 319 SatCount, 268 Simpli f y, 270 T , 306 Tau, 66 Teo(A ), 97 Teo(K), 98 Teo(Γ), 95 V (γ , w), 349 VS , 316 WS , 316 A |= Σ, 64 A |= ϕ , 59 Φ ⊢H ϕ , 159 Σ ⊢ η , 300 381 382 Z2 , 113 α n , 370 ⊥, 31, 63 ✷, 186, 289, 298 ↓, 30, 110 ⋄, 289 Σ |= ψ , 64 Σ ⊢ α , 138 γ (α /π ), 292 ϕ [P1 , . . . , Pn ], 90 ϕ [P1 /ψ1 , . . . , Pn /ψn ], 90 ϕ ⇔ ψ , 63 ϕ ≡ ψ , 63 ϕ |= ψ , 61 →, 13 ↔, 14 |, 30 |= α , 299 |=c , 350 |=i , 350 |=i α , 350 ¬, 15 ⊕, 104 ⊥, 359 ⊤, 31, 63 ↑, 103 , 61 ⊢, 138 ⊢ α , 300 ⊢S α , 300 ⊢c , 350 ⊢i , 350 ∨, 12 ⊢H , 159 ⊢R , 186 Índice de símbolos ⊢S , 151 ⊢S ϕ , 151 ∧, 10 f [0/x], 248 f [1/x], 248 g(γ ), 293 gm(γ ), 293 hi(n), 246 lo(n), 246 subF (α ), 291 w |= α , 298 ✷n α , 307 (RAA), 359 A , 58 C(L ), 44 Fml, 44 Fmln , 46 gad, 239 ϕ ⇒ ψ , 54 l(ϕ ), 49 M ϕ , 59 MP, 159 NAND, 103 NOR, 110 rg(ϕ ), 47 TSC, 141, 148 Índice de conceptos correcto, 5, 6, 8, 24 correcto o válido, 4, 9 deductivos, 4 incorrección, 289 válido, 56, 68 Aritmética binaria, 229 Asignación, 58, 59 Axiomas, 95, 300 Gentzen, 152 Hilbert, 159 Alambre, 221 Algoritmo Allsat, 269 Anysat, 269 apply, 247, 249, 264 FNC, 75 FND, 75 Horn, 180 reduce, 246, 247 restrict, 267 SatCount, 268 Simplify, 270 Árbol, 81 binario, 83 completo, 373 de formación, 47 extendido, 334 semántico, 201, 373 para la lógica intuicionista, 352 para la lógica modal, 324 reglas para construir, 333 verdadero, 334 verdadero en un modelo, 371 Argumento condicional asociado al, 25 corrección del, 5, 288, 289 B-árboles, 328 Beth-demostrable con premisas, 138 Beth-refutable, 136 Bicondicional, 14, 20, 50 Cadena binaria, 83 Ciclo, 239 Circuito eléctrico, 221 lógico, 225 simple, 223 Cláusula, 182 asociada, 204 Completud, 130 Compuerta, 225 383 384 Índice de conceptos AND, 226 NAND, 226 NOR, 226 NOT, 225 OR, 226 Conclusión, 4 Condicional, 14 antecedente, 12, 20 consecuente, 12, 20 Conectivo binario, 19 Conectivos lógicos, 43 unarios ✷ y ⋄ no veritativo-funcionales, 289 Conjunción, 9, 10, 20, 23, 50 Conjunto adecuado de conectivos, 107 axiomatizable de asignaciones, 99 bien ordenado, 81 booleano, 125 completo, 88 fórmulas, 69 inconsistente de fórmulas, 24, 69 independiente, 117 K-consistente de fórmulas, 314 máximo consistente de fórmulas, 315 parcialmente ordenado, 81 regular, 125 satisfacible, 69 verificable, 69 Consecuencia directa, 300 lógica, 5, 25, 61, 130, 353 tautológica, 301 Contradicción, 23, 54 Contraejemplo de un argumento, 8 Contrapositiva, 14, 52 Conversa, 14, 52 Conyuntos, 11 Correctud, 130 dbd, 236, 240 dbdor, 242 Diagrama binario de decisión, 234, 236 ordenado, 242 Disyunción, 12, 20, 50 exclusiva, 27 ternaria exclusiva, 29 Disyuntos, 12 Dual, 341 Enunciado el grado de un, 293 el grado modal de un, 293 o proposiciones de LMP, 291 válido, 298, 332 válido en un modelo, 298 veritativo-funcionales, 27 Expresión prueba, 255 Extensión de un sistema axiomático, 307 FNC, 72 FND, 71 FNI, 255 Forma Índice de conceptos NI, 255 normal conjuntiva, 72 disyuntiva, 71 Fórmula atómica, 43 Beth-demostrable, 136 contradictoria, 24, 25, 60 de LMP, 290 falsa en un mundo, 350 Horn, 179 básica, 179 negativa, 369 primitiva, 43 proposicional, 43 refutable, 135 por tablas, 135 satisfacible, 59 válida, 59 válida en un marco, 350 valuada, 133 verdadera en un modelo, 350 verdadera en un mundo, 349 Fórmulas equivalentes, 63 lógicamente equivalentes, 31 o esquemas, 20 reglas de formación de, 290 Función booleana, 241 Build, 261 MK, 261 Gad, 239 Gráfica, 120 acíclica dirigida, 239 385 dirigida, 239 k-coloreable, 120 Grupo abeliano, 121 libre de torsión, 121 ordenable, 121 tipo finito, 121 Implicación, 50 tautológica, 54 Inferencia o argumento, 4 válida, 5 instancia de sustitución, 292 Interpolante, 93 Interruptor, 221 Inversa, 14, 52 Kripke, 296 Leibniz, 295 Lema de Shanon, 249 Lenguaje cálculo proposicional, 43 del cálculo de enunciados, 289 formal, 42 partículas del, 19 sintaxis del cálculo proposicional, 290 Letras proposicionales, 20 Ley De Morgan, 63 distributiva, 63 tercero excluido, 65 Literal, 71, 152 negativa, 71 Índice de conceptos 386 positiva, 71 Marco que corresponde a un modelo, 299 Modalidad, 311 igualdad de, 311 positiva, 311 Modelo, 59, 62 canónico, 316 D, 308 de la lógica modal proposicional, 297 i, j, m, n−convergente, 322 intuicionista o modelo i, 349 K4 , 310 modelo-i generado por r, 373 producido por r, 334 R-convergente, 323 S4 , 310 T, 306 variante de un, 334 Modus Ponens, 159, 170 Tollens, 219 Modus ponens (MP), 301 MP, 159 MT, 332 Mundo, 352 posibles, 296 terminal, 308 Necesidad, 301 Negación, 15, 20, 50 Nodo, 82 falla, 203 inferencia, 205 reducido, 134 Ocurre o aparece, 292 Operador modal, 289 veritativo-funcional, 13 Orden compatible, 243 Palabras accidentales, 8 esenciales, 8 Partícula o expresión del lenguaje, 11 veritativo-funcional, 11 Predecesor, 82 Premisas, 4 Primer silogismo, 65 Principio de los pichones, 82 Problema de las reinas, 280 de satisfacibilidad, 60 de validez, 60 Prueba, 151 formal, 129 Hilbert, 159 por tablas, 135 con premisas, 138 resolución, 186 Prueba en un sistema axiomático, 300 Rama, 82 abierta, 201 cerrada, 201 completamente desarrollada, 373 verdadera en un modelo, 334, 371 Red equivalente, 223 Índice de conceptos Reductio ad absurdum, 164 Refutación, 135 Refutación por resolución, 186 Regla asociativa, 168 B, 328 conmutativa, 168 contrapositiva, 161 correcta, 159 4, 328 D, 329, 330 de corte, 184 de deducción, 160 de doble negación, 163 de inferencia, 151, 300 de inferencia de Gentzen, 152 de inferencia de Hilbert, 159 de intercambio, 162 de reducción al absurdo (RAA), 359 de resolución, 185 de transitividad, 161 para operadores modales, 324 T, 326 Resolución, 182 Resolvente, 185 Resolver, 185 Segundo silogismo, 65 Semántica, 50 Semisumador, 230 Símbolo de constante, 42 de función, 42 de relación, 42 Simplificación de fórmulas, 54 Sintaxis, 43 387 Sistema axiomático de deducción, 300 axiomático de lógica modal, 300 B, 313 completo, 356 D, 308 de Gentzen, 152 de Hilbert, 158, 166 de Hilbert-Ackermann, 215 de lógica modal, 294 de Lukasiewicz, 217 de prueba, 130 de Rosser, 216 deductivamente equivalentes, 307 deductivo, 151 K, 301 K4 , 310 NDi , 356 normal, 294 PA, 289 S4 , 310 S5 , 319 T, 306 tipo Gentzen, 356 Subfórmula, 20, 32, 51, 291 Sucesor, 82 Sumador completo, 231, 281 Sustitución, 66 Tabla atómica, 133 contradictoria, 135 de verdad, 10, 21, 50 finita, 133 semántica, 131, 133 semántica completa, 140, 148 388 Índice de conceptos semántica con premisas, 137 semántica terminada, 148 semántica y el sistema de Gentzen, 154 terminada, 135 Tautología, 25, 31, 54, 366 Tautológicamente equivalente, 54 Teorema compacidad, 84, 90, 102, 150 completud, 146, 170 Gentzen, 158 Hilbert, 170, 178 resolución, 188, 206 tablas semánticas, 146, 150 Cook, 236 correctud, 145, 169 Gentzen, 158 Hilbert, 169, 174 resolución, 187 tablas semánticas, 145, 147 interpolación, 92 König, 82 Ramsey, 126 Teoría asignación, 97 ∆-axiomatizable, 125 de las inferencias válidas, 10 eliminación, 125 proposicional, 95 Transposición, 65 Trayectoria, 83, 140 contradictoria, 135 TSC, 141, 148 Ultraproducto, 102 Valor de verdad verdadero o falso, 297 Variable booleana, 234 proposicional, 43 El centro y los cuatro rumbos del mundo Códice Fejérváry-Mayer Este es el primer libro escrito en la antigüedad, aunque su vista está oculta al que ve y piensa. Admirable es su aparición y el relato del tiempo en el cual acabó de formarse todo en el cielo y sobre la tierra, la cuadratura y la cuadrangulación de sus signos, la medida de sus ángulos, su alineamiento y el establecimiento de las paralelas en el cielo y sobre la tierra, en los cuatro extremos, en los cuatro puntos cardinales... Este es el relato de cómo todo estaba en suspenso, todo estaba en calma y en silencio; todo estaba inmóvil, todo tranquilo, y vacía la inmensidad de los cielos. Esta es, pues, la primera palabra y el primer relato. No había aún un solo hombre, un solo animal; no había pájaros, peces, cangrejos, bosques, piedras, barrancas, hondonadas, hierbas ni sotos; sólo el cielo existía. La faz de la tierra no se manifestaba todavía; sólo el mar apacible y todo el espacio de los cielos. No había nada que formara cuerpo; nada que se asiese a otra cosa; nada que se moviera, que produjese el más leve roce, que hiciese (el menor) ruido en el cielo. Popol Vuh Z uerĆ Collegium Logicum. Da wird der GeiĆ EuĚ wohl dreĄiert, In spanisĚe Stiefeln eingesĚn§rt, Da er bedŁĚtiger so fortan HinsĚleiĚe die Gedankenbahn, Und niĚt etwa, die Kreuz und Quer, IrrliĚteliere hin und her. Dann lehret man EuĚ manĚen Tag, Da, was Ihr sonĆ auf einen SĚlag Getrieben, wie EĄen und Trinken frei, Eins! Zwei! Drei! dazu nŽtig sei. E I J. W. Goethe s gibt nur eine LandĆrae der WiĄensĚaft, und nur diejenigen haben AuĄiĚt ihren hellen Gipfel zu erreiĚen, die die Erm§dung beim Erklettern ihrer Ćeilen Pfade niĚt sĚeuen. K. Marx n niĚts zeigt siĚ der Mangel an mathematisĚer Bildung mehr als in einer §bertrieben genauen ReĚnung. Carl FriedriĚ Gau ¿Qué puede esperar el lector en el libro II? Tratará en detalle los siguientes temas: ❁ Lógica modal de predicados. ❁ Lógica Intuicionista. ❁ Lógica clásica de primer orden: pruebas formales, sistemas axiomáticos, resolución. ❁ Los teoremas de completud, correctud, Löwenheim-Skolem y compacidad de la lógica de primer orden.
© Copyright 2024