LÓGICA MATEMÁTICA

APUNTES

Ingeniería en Informática

ESCET

Alessandra Gallinari

2006�2007

i

PrólogoEl contenido de esta publicación es un guión de la asignatura de Lógica

Matemática para la titulación de Ingeniería en Informática de la Escuela Su-perior de Ciencias Experimentales y Tecnología (ESCET) de la UniversidadRey Juan Carlos.

Los principales objetivos de la asignatura son:

• Introducir herramientas y conceptos básicos de la Lógica Matemáticay sus aplicaciones.

• Ayudar al alumno a aprender a razonar y formalizar correctamente.

• Junto con la asignatura Lógica Informática del próximo cuatrimestre,dar una formación global acerca de los procedimientos formales y algo-rítmicos de razonamiento automático y resolución formal de problemas.

Con estas notas de clase se intenta presentar de forma organizada el mate-rial que se expondrá en las clases teóricas. Por la naturaleza de estos apuntes,la exposición no es completa y es fundamental que el alumno consulte tam-bién los libros recomendados en la bibliografía relativa a la asignatura.

Las principales referencias bibliográ�cas empleadas en estos apuntes son[A], [HLR], [MH], [R] y las notas de clase de los profesores Ana Pradera yLuis Solá.

La primera parte de la publicación trata la lógica proposicional y la se-gunda la lógica de predicados.

Las dos partes tienen la misma estructura y están divididas en cincocapítulos. Los primero tres introducen la sintaxis, la semántica y la teoríade la demostración. Los últimos dos presentan unas aplicaciones y proponenunos ejercicios de repaso, que son exámenes propuestos en años académicosanteriores. Además, cada capítulo contiene un apartado de ejercicios.

Estas notas incluyen también dos capítulo preliminares. El primero es unabreve introducción histórica a la lógica y a su relaciones con la Matemáticasy la Informática, el segundo es un repaso de la teoría de conjuntos.

El apéndice A contiene las soluciones de algunos de los exámenes �nalesde años anteriores y el apéndice B el sistema axiomático de Kleene.

ii

AgradecimientosQuiero agradecer al profesor Roberto Muñoz por su indispensable parti-

cipación en la corrección de estas notas.Gracias también al profesor Ariel Sánchez por su sugerencias y a los

alumnos que han señalado erratas y errores en versiones previas.

Índice General

1 Introducción 11.1 El lenguaje de la lógica . . . . . . . . . . . . . . . . . . . . . . 11.2 Resumen de la historia de la lógica . . . . . . . . . . . . . . . 5

1.2.1 Lógica y �losofía . . . . . . . . . . . . . . . . . . . . . 61.2.2 Lógica y matemáticas . . . . . . . . . . . . . . . . . . . 61.2.3 Lógica e informática . . . . . . . . . . . . . . . . . . . 7

1.3 Consejos prácticos para el estudio de la asignatura . . . . . . . 8

2 Algunas nociones de teoría de conjuntos, relaciones y funcio-nes 112.1 Nociones de teoría de conjuntos . . . . . . . . . . . . . . . . . 12

2.1.1 Inclusión e igualdad de conjuntos . . . . . . . . . . . . 132.1.2 Operaciones con conjuntos . . . . . . . . . . . . . . . . 142.1.3 Partes de un conjunto y propiedades de las operaciones

con conjuntos . . . . . . . . . . . . . . . . . . . . . . . 152.1.4 Cardinal de un conjunto . . . . . . . . . . . . . . . . . 16

2.2 Relaciones binarias . . . . . . . . . . . . . . . . . . . . . . . . 172.2.1 Relaciones de equivalencia . . . . . . . . . . . . . . . . 18

2.3 Relaciones n−arias . . . . . . . . . . . . . . . . . . . . . . . . 192.4 Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

I Lógica de proposiciones 253 Sintaxis de la lógica proposicional 27

3.1 Alfabeto del lenguaje formal de la lógica proposicional . . . . 28

iii

iv

3.2 De�nición recursiva de las expresiones bien construidas: fór-mulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.2.1 El principio de inducción estructural para fórmulas pro-

posicionales . . . . . . . . . . . . . . . . . . . . . . . . 313.3 Representación de las fórmulas bien construidas . . . . . . . . 33

3.3.1 Fórmulas en forma usual y abreviada . . . . . . . . . . 333.3.2 Fórmulas en forma de árbol estructural . . . . . . . . . 353.3.3 El principio de recursión estructural para fórmulas pro-

posicionales . . . . . . . . . . . . . . . . . . . . . . . . 383.4 Formalización del lenguaje natural . . . . . . . . . . . . . . . 393.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4 Semántica de la lógica proposicional.Teoría interpretativa 454.1 Valoraciones de un lenguaje formal . . . . . . . . . . . . . . . 454.2 Evaluación semántica de fórmulas . . . . . . . . . . . . . . . . 46

4.2.1 Tablas de verdad . . . . . . . . . . . . . . . . . . . . . 484.3 Modelos y contraejemplos de una fórmula bien construida.

Tautologías, contingencias y contradicciones . . . . . . . . . . 514.4 Evaluación semántica de deducciones. Consecuencia lógica . . 544.5 Equivalencia de fórmulas . . . . . . . . . . . . . . . . . . . . . 554.6 Métodos de refutación. Tableaux . . . . . . . . . . . . . . . . 57

4.6.1 Refutación . . . . . . . . . . . . . . . . . . . . . . . . . 574.6.2 De�nición de los tableaux . . . . . . . . . . . . . . . . 594.6.3 Aplicaciones de los tableaux . . . . . . . . . . . . . . . 67

4.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5 Teoría de la demostración 775.1 De�nición de sistema formal axiomático . . . . . . . . . . . . 78

5.1.1 Subdeducciones y notación de Fitting . . . . . . . . . . 825.2 El sistema de deducción natural de Gentzen . . . . . . . . . . 83

5.2.1 De�nición del sistema de deducción natural de Gentzen 845.2.2 Reglas derivadas del sistema de Gentzen . . . . . . . . 90

5.3 Tableaux sintácticos . . . . . . . . . . . . . . . . . . . . . . . 1045.4 Completitud, corrección y decidibilidad . . . . . . . . . . . . . 1055.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

v

II Lógica de predicados de primer orden 1096 Sintaxis de la lógica de primer orden 111

6.1 Alfabeto del lenguaje formal de la lógica de predicados . . . . 1126.2 De�nición recursiva de las expresiones bien construidas: tér-

minos y fórmulas . . . . . . . . . . . . . . . . . . . . . . . . . 1176.2.1 Variables libres y variables ligadas . . . . . . . . . . . . 1206.2.2 El principio de inducción estructural para expresiones

bien construidas . . . . . . . . . . . . . . . . . . . . . . 1216.3 Representación de las expresiones bien construidas . . . . . . . 122

6.3.1 Fórmulas en forma abreviada . . . . . . . . . . . . . . 1226.3.2 Principio de unicidad de estructura para expresiones

bien construidas . . . . . . . . . . . . . . . . . . . . . . 1236.3.3 Términos y fórmulas en forma de árbol estructural . . 1246.3.4 El principio de recursión estructural para expresiones

bien construidas . . . . . . . . . . . . . . . . . . . . . . 1256.4 Formalización del lenguaje natural . . . . . . . . . . . . . . . 1296.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

7 Semántica de la lógica de primer orden. Teoría interpretati-va 1417.1 Interpretaciones en lógica de primer orden . . . . . . . . . . . 1427.2 Interpretación semántica de términos y fórmulas . . . . . . . . 1457.3 Validez semántica de fórmulas: modelos . . . . . . . . . . . . . 1497.4 Evaluación semántica de deducciones . . . . . . . . . . . . . . 1517.5 Equivalencia de fórmulas . . . . . . . . . . . . . . . . . . . . . 153

7.5.1 Sustitución de una variable por un término . . . . . . . 1537.5.2 Equivalencia de fórmulas . . . . . . . . . . . . . . . . . 1557.5.3 Equivalencia lógica y reemplazamiento . . . . . . . . . 157

7.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

8 Teoría de la demostración 1638.1 De�nición del sistema de deducción natural de Gentzen . . . . 164

8.1.1 Reglas derivadas del sistema de deducción natural . . . 1678.2 Corrección, completitud y decidibilidad . . . . . . . . . . . . . 1708.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

vi

Índice de Figuras

1.1 http : //personal5.iddeo.es/ztt/pra/alfabeto_griego.htm . . 10

2.1 Grá�ca de A×B. . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Grá�ca de R. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1 Árbol sintáctico de ((p ∧ (p → r)) ∨ (q ↔ t)). . . . . . . . . . . 37

4.1 Árbol estructural de ϕ = ((p ∧ (p → r)) ∨ (q ↔ t)) . . . . . . 50

6.1 Expresiones bien construidas . . . . . . . . . . . . . . . . . . . 1206.2 Árbol sintáctico del término f(g(x, h(a, y)), i(x, l(y))). . . . . 1256.3 Árbol sintáctico de ϕ. . . . . . . . . . . . . . . . . . . . . . . 126

vii

viii

Índice de Tablas

3.1 Los conectivos de la lógica proposicional . . . . . . . . . . . . 293.2 Tabla de formalización en la lógica proposicional . . . . . . . . 41

4.1 Valores de verdad de los conectivos . . . . . . . . . . . . . . . 494.2 Tabla de verdad de ϕ = (p ∧ (p → r)) ∨ (q ↔ t). . . . . . . . 514.3 Tabla de algunas implicaciones lógicas . . . . . . . . . . . . . 554.4 Tabla de algunas equivalencias lógicas . . . . . . . . . . . . . . 564.5 Fórmulas reducibles . . . . . . . . . . . . . . . . . . . . . . . . 614.6 Esquema de reducción de fórmulas . . . . . . . . . . . . . . . 62

7.1 Valores de verdad de los conectivos . . . . . . . . . . . . . . . 1477.2 Tabla de algunas implicaciones lógicas . . . . . . . . . . . . . 1537.3 Equivalencias relativas a conectivos lógicos . . . . . . . . . . . 1567.4 Equivalencias relativas a cuanti�cadores . . . . . . . . . . . . 156

ix

Capítulo 1

Introducción

La lógica formal es la ciencia que estudia las leyes de inferencia en losrazonamientos. Por medio de la formalización del lenguaje y de sus reglasbásicas, proporciona las herramientas necesarias para poder tratar e intentarresolver rigurosamente problemas que tienen sus origines y aplicaciones entodas las áreas de las ciencias.

En particular, los alumnos de la Ingeniería en Informática podrán aplicarsus conocimientos de lógica al estudio del Álgebra, del Cálculo, de la Ma-temática Discreta, de la Electrónica Digital, de la Teoría de Autómatas yLenguajes Formales, de la Programación, de las Bases de Datos, etc.

El contenido de este primer capítulo es una breve introducción a los con-ceptos generales que se desarrollarán en esta publicación.

1.1 El lenguaje de la lógicaEl lenguaje natural que utilizamos en la comunicación humana permite unalto grado de �exibilidad. Ese lenguaje está caracterizado por su gramática,que nos permite determinar si una cierta frase, una combinación de palabras,es válida.

Por ejemplo, en el idioma español la frase �La mesa habla suavemente�es una frase válida, ya que está compuesta por un artículo (la), seguido porun sujeto (mesa) y un predicado (habla suavemente), que consiste a su vezde un verbo (habla) y de un adverbio (suavemente). Es la sintaxis de unleguaje, las reglas de formación de frases correctas, que nos permite a�rmar

1

2

si una cierta combinación de palabras es válida. Por tanto, la sintaxis no seocupa del sentido de las frase, sólo determina su validez.

Por el otro lado, la semántica de un lenguaje trata el estudio de los sen-tidos de las frases sintácticamente válidas. Así, la frase del ejemplo anteriores sintácticamente correcta, pero falta de sentido semántico.

La �exibilidad de los lenguajes naturales se basa en la complejidad desus gramáticas. Es muy complicado, si no imposible, dar una representacióncompleta de las reglas sintácticas de los lenguajes hablados.

Por esa razón, los lenguajes naturales presentan unas limitaciones: siqueremos poder formular sólo a�rmaciones que se puedan de�nir correctas(sintácticamente) o verdaderas (semánticamente) sin ningún grado de ambi-güedad, tendremos que de�nir un lenguaje más preciso que se suele denomi-nar lenguaje formal.

Sin un lenguaje formal sería imposible estudiar las matemáticas, progra-mar un ordenador y, en general, desarrollar razonamientos cientí�camenteirrefutables.

El siguiente ejemplo ilustra como en el lenguaje natural, en este caso elespañol, existen oraciones para la cuales ni siquiera tiene sentido preguntarsesi son verdaderas o falsas.

Ejemplo 1.1.1 Las frases �¾Cómo te llamas?� y �Por favor, dame tu libro�son dos ejemplos de oraciones a las cuales no podemos asociar un valor deverdad.

Por estas razones y por la necesidad de realizar cálculos exactos, el len-guaje formal de la lógica se construye a partir de unos elementos básicos(atómicos) llamados proposiciones, que son oraciones declarativas (apofán-ticas) simples, a las cuales se pueden asociar valores de verdad sin ningunaambigüedad.

Entonces las frases �¾Cómo te llamas?� y �Por favor, dame tu libro� noson proposiciones, sin embargo las frases �Hoy llueve� o �Si estudio mucho,apruebo la asignatura� lo son.

De�nimos metalenguaje al lenguaje, en nuestro caso el español, quevamos a usar para de�nir un lenguaje formal.

Por ejemplo, en la frase �√

2 es el número real positivo tal que su cua-drado es igual a 2� se usa el metalenguaje español para de�nir el símbolomatemático

√2.

3

Estructura del lenguaje formalYa comentamos que el interés principal de la lógica es el estudio de la validezdel razonamiento. Las de�niciones básicas de razonamiento y validez son lassiguientes:

Razonamiento (deducción, inferencia, argumento): es la obtenciónde un nuevo conocimiento (conclusión) a partir de una serie de conocimientos(premisas).

Validez formal de un razonamiento: un razonamiento es formalmen-te válido si la conclusión es necesariamente verdadera, siendo las premisasverdaderas.

Ejemplo 1.1.2 Razonamiento válido:Premisa 1: Si estudio todo el temario, entonces apruebo la asignatura.Premisa 2: No he aprobado la asignatura.Conclusión: No he estudiado todo el temario.Razonamiento no válido:Premisa 1: Si estudio todo el temario, entonces apruebo la asignatura.Premisa 2: No he estudiado todo el temario.Conclusión: No apruebo la asignatura.

En las matemáticas es necesario aprender a distinguir entre razonamientosque son matemáticamente correctos (las demostraciones) y razonamientosque no lo son. Además, para poder resolver problemas concretos es necesariodesarrollar la habilidad de construir razonamientos matemáticos originales.

La lógica proporciona las herramientas necesaria para el razonamientomatemático, pero también para muchas otras aplicaciones.

En estos apuntes veremos como aplicar la lógica al diseño de circuitos deordenador y a la veri�cación de programas.

Resumiendo, la estructura de todo lenguaje formal viene de�nida por susintaxis, semántica y sistemas de demostración:

Sintaxis (reglas de formación, gramática): es la de�nición axiomáticade los elementos básicos del lenguaje y de las reglas que permiten obtenernuevas expresiones correctas a partir de aquellos. Las expresiones admitidaspor el lenguaje se denominan fórmulas.

Semántica (relación entre el lenguaje y su signi�cado): es la de�nición deun conjunto de signi�cados (generalmente verdadero o falso) que se puedan

4

asociar a una fórmula. Permite de�nir la validez de una fórmula o de unrazonamiento.

Sistemas de demostración: son sistemas formales que permiten ave-riguar cuándo una fórmula o un razonamiento son válidos. En el contextode la sintaxis se denominan teoría de la demostración. En el caso de lasemántica se denominan teoría interpretativa.

Niveles de la lógica formalLógica proposicional (lógica de proposiciones, LP): en la lógica proposicio-nal se estudian las fórmulas proposicionales construidas a partir de fórmulasatómicas (proposiciones declarativas simples) y conectivos lógicos (y, o, im-plica, etc.).

Ejemplos 1.1.3 1) Formalización de frases:Estudio todo el temario (e);No estudio todo el temario(¬(e));Apruebo la asignatura (a);Estudio todo el temario y apruebo la asignatura (e ∧ a);Si estudio todo el temario, entonces apruebo la asignatura (e −→ a).2) Formalización de razonamientos:Razonamiento válido:Premisa 1: Si estudio todo el temario, entonces apruebo la asignatura(e −→ a).Premisa 2: No he aprobado la asignatura (¬(a))Conclusión: No he estudiado todo el temario (¬(e))Razonamiento no válido:Premisa 1: Si estudio todo el temario, entonces apruebo la asignatura(e −→ a).Premisa 2: No he estudiado todo el temario (¬(e))Conclusión: No apruebo la asignatura (¬(a))

Lógica de predicados de primer orden, (LPO): la lógica de primer or-den es una generalización de la lógica de proposiciones. Distingue entre losobjetos del discursos y sus propiedades o posibles relaciones entre ellos. Ade-más, introduciendo nuevos elementos como los cuanti�cadores existenciales

5

y universales ( ∃ : existe un, ∀ : para todo), permite estudiar la estructurainterna de los enunciados.

Ejemplos 1.1.4 1) Formalización de una frase:�El cuadrado de todo número real es no negativo.�Sean R el conjunto de los números reales y P (x) : x es un número no

negativo. La formalización de nuestra frase es:

(∀x(P (x2)).

2) Formalización de un razonamiento (válido):Sean D el conjunto de los seres, P (x) : x es una persona, M(x) : x es

mortal y s el símbolo constante �Socrates.�Entonces podemos formalizar el siguiente razonamiento:Premisa 1: Todas las personas son mortales (∀x(P (x) −→ M(x)))Premisa 2: Sócrates es una persona (P (s))Conclusión: Sócrates es mortal (M(s))

Lógicas de orden superior: son extensiones de la lógica proposicional yde predicados de primer orden que amplían el uso de los cuanti�cadores alas propiedades y a las relaciones entre los objetos. Notar que en la lógica deprimer orden los cuanti�cadores se re�eren sólo a los objetos.

En esta publicación se tratará exclusivamente el estudio de la lógica pro-posicional y de predicados de primer orden.

1.2 Resumen de la historia de la lógicaLa de�nición de lógica como ciencia formal en la cultura occidental es el re-sultado de un largo desarrollo histórico que empieza con las obras de algunos�lósofos griegos y llega hasta la actualidad.

Históricamente las áreas de aplicación más importantes de la lógica sonla �losofía, las matemáticas y la informática.

A continuación se presenta un resumen muy reducido de los principalespasos que han llevado a la formulación de la lógica formal. El lector interesadopodrá encontrar un tratamiento más extensivo en la referencia [UNED1] ysu bibliografía.

6

1.2.1 Lógica y �losofíaEn el siglo cuarto antes de nuestra era Aristóteles fue el primero en tratarde formalizar el razonamiento humano para poder discernir en la discusiones�losó�cas. Aristóteles se puede considerar el fundador de la denominadalógica clásica.

Durante la Edad Media el proceso de sistematización de la lógica fuedesarrollado por los �lósofos árabes y los escolásticos.

En el siglo XIII Santo Tomás de Aquino empleó la lógica en el contextode las discusiones teológicas.

Fue Leibniz, en el siglo XVII, el primero a formular la lógica como basedel razonamiento matemático, pero sus estudios fueron abandonados hasta elsiglo XIX, cuando �nalmente se fundó la lógica matemática como ciencia.

1.2.2 Lógica y matemáticasA mediados del siglo XIX, en el 1854, el inglés George Boole publicó ellibro The Laws of Thought (Las leyes del pensamiento). In�uenciado por lasteorías de los matemáticos De Morgan y Hamilton, Boole de�nió la lógicacomo sistema formal dirigido no sólo al estudio del lenguaje natural. Su obraproporciona un modelo algebraico de la lógica de proposiciones.

En el 1879 el alemán Gottob Frege publicó el libro Grundgesetze derAruthmetik: Begri�sschriftlich abgeleitet (Fundamentos de Aritmética: Con-ceptualmente derivada), en el cuál se formaliza la lógica de predicados.

A principios del siglo XX Bertrand Russell y Whitehead, inspiradospor el trabajo del matemático italiano Giuseppe Peano, publicaron los tresvolúmenes de Principia Mathematica y Hilbert, en 1920, propuse el proble-ma de la axiomatización de las matemáticas. En 1930 Gödel demuestróel famoso teorema de incompletitud del enfoque axiomático, que contestanegativamente al problema de Hilbert.

El resultado de todas estas obras fue la base teórica de la teoría axiomáticay semántica.

Toda teoría matemática se construye a partir de unos axiomas, quede�nen las propiedades básicas de los objetos de la teoría que se consideranverdaderas y, sin embargo, no se demuestran.

La geometría euclídea y la construcción de los números reales son dosejemplos de este tipo de teorías axiomáticas.

7

El modelo matemático conocido como Álgebra de Boole es otro ejemplomuy importante en informática usado para el diseño de circuitos lógicos ylas búsquedas booleanas en grandes colecciones de datos (indices de páginasWeb, datos genéticos, etc.).

Los axiomas de toda teoría matemática tienen que ser:1) compatibles: a partir de ellos no tiene que ser posible deducir una

contradicción,2) independientes: ningún axioma se debe poder deducir a partir del

resto de ellos (habría redundancia de axiomas),3) su�cientes: a partir de ellos tiene que ser posible deducir todas las

propiedades que necesitamos satisfagan los objetos de nuestra teoría.

1.2.3 Lógica e informáticaUna nueva época para la lógica comienza en las décadas de 1950 y 1960a causa de la aparición de los ordenadores. Surgió entonces la necesidadde determinar si fuese posible especi�car formalmente programas y de�nirsistemas de demostración automática de teoremas. Estos tipo de problemasson los principales objetos de estudio de la lógica informática.

El nacimiento de la inteligencia arti�cial y del primer lenguaje declarativo(LISP) se puede �jar en el 1959, con el trabajo de Mc Carthy.

A lo largo de los años sesenta se mejoran los primeros sistemas de demos-tración automática y en el 1965 aparece la la regla universal de resolucióncon uni�cación de Robinson.

En los años setenta se desarrolló la programación lógica como herramientade resolución de problemas. En 1972 Colmerauer creó el primer lenguajede programación lógica: Prolog.

A partir de los años ochenta se empiezan a utilizar nuevas lógicas noclásicas, como, por ejemplo, lógicas que permiten dar una interpretaciónprobabilista de la incertidumbre.

Los métodos deductivos de la lógica matemática están a la base de lademostración automática de teoremas. Se trata de buscar los sistemas dedemostración más e�cientes para su implementación en un ordenador.

De�nida la semántica de un lenguaje de programación, se pueden usar losmétodos de demostración de la lógica matemática para veri�car (automáti-camente) la corrección de programas y sus propiedades.

8

La programación lógica está a la base de la inteligencia arti�cial ypermite deducir nuevos conocimientos a partir de una base de conocimientos(los axiomas) y una serie de deducciones automáticas.

Por tanto, algunas de las áreas de aplicación de la lógica en informáticason:

• La minería de datos.

• La description de la semántica de los lenguajes de programación y laveri�cación de programas.

• La demostración automática de teoremas.

• La programación lógica y los sistemas basados en el conocimiento enla inteligencia arti�cial.

1.3 Consejos prácticos para el estudio de la asig-natura

Cierra este capítulo de introducción una lista de consejos para los alumnos,que tiene la intención de facilitar el estudio de la lógica matemática.

El principal objetivo del estudio de la lógica es el aprendizaje de las técni-cas de demostración formales y su aplicaciones a la resolución de problemas.

Por eso es indispensable que el alumno domine el lenguaje formal y lastécnicas de deducción. Sin estos conocimientos, es imposible desarrollar laactividad creativa necesaria para resolver nuevos problemas, como los queserán propuestos a lo largo de la asignatura.

En general, para aprender un lenguaje es necesario conocer su sintaxisy semántica. Además, sólo con mucha práctica se puede llegar a hablar yrazonar correctamente usando ese lenguaje.

Lista de consejos:

• Bibliografía: tener unos buenos libros de texto facilita enormementeel estudio de cualquier materia. Esta publicación de apuntes de la asig-natura es un guión para las clases, no pretende sustituir la bibliografíarecomendada.

9

• Método de estudio: las asignaturas de matemáticas requieren unestudio llevado al día. Los temas del programa están desarrollados deforma tal que el aprendizaje sea progresivo y, por tanto, no es posibleentender un nuevo tema si se tienen dudas importantes sobre el anterior.Para aclarar dudas es conveniente:- volver a estudiar el tema que presenta di�cultades consultando dis-tintos textos e intentar resolver los problemas propuestos,- preguntar las dudas al profesor en clase o durante sus horas detutoría,- trabar en grupo con otros compañeros.

• Tiempo de estudio: en media, el estudio independiente del alumnotendría que ser de una hora y media para cada hora de clase teórica.Este tiempo incluye las actividades dedicadas a la comprensión de losejemplos presentados y a la resolución de los ejercicios propuestos.

• Clases prácticas: durante la clases prácticas el alumnos puede ha-cer ejercicios individualmente o en grupo. En esto tipo de clases losalumnos pueden veri�car si su nivel de comprensión de la materia esel adecuado y tienen la oportunidad de corregir errores de aprendiza-je. En las clases prácticas es conveniente aprovechar la presencia y ladisponibilidad del profesor para aclarar posibles dudas.

• Exámenes parciales: los exámenes parciales también sirven para queel alumno pueda veri�car su nivel de conocimiento de la materia. Si esnecesario, permiten mejorar su preparación a tiempo para el examen�nal.

La tabla 1.1 contiene los símbolos del alfabeto griego. En estos apun-tes, siguiendo la notación tradicional, se usarán varios de ellos. Con muchafrecuencia se emplearán los símbolos:

ϕ= � minúscula,Φ= � mayúscula,ψ= psi,χ= ji.

10

Figura 1.1: http : //personal5.iddeo.es/ztt/pra/alfabeto_griego.htm

Capítulo 2

Algunas nociones de teoría deconjuntos, relaciones y funciones

(Referencias: R. Criado, A. Burjosa, C. Vegas, R. Banerjee, Fundamentosmatemáticos I, Ed. Centro de estudios Ramón Acreces. Madrid, 1998 yP.H. Halmos, Naive Set Theory, Springer-Verlas New York, Heidelberg, Ber-lin, 1987.)

Este capítulo es un repaso de algunas nociones de teoría de conjuntos yde las de�niciones básicas de relaciones y funciones.

En esta exposición presentaremos sólo aquellos conceptos indispensablespara el estudio de la asignatura de Lógica Matemática. Los alumnos amplia-rán sus conocimientos en asignaturas paralelas, que proporcionan un trata-miento más amplio y detallado de los temas aquí considerados.

La lógica y la teoría de conjuntos están estrechamente relacionadas. Dehecho en un principio se pensó que toda propiedad P (x) (todo predicado enel lenguaje de la lógica de primer orden) llevaba asociado un �conjunto�,

{x : P (x)}.

El conjunto obtenido estaría formado por los elementos a del universo dediscurso U que satisfacen la propiedad P (x), es decir, tales que se puedaa�rmar que P (x) es verdadera si x = a.

Así, por ejemplo, sea nuestro universo de discurso �los seres humanos� ysea P (x) la propiedad de un genérico ser humano x de ser alto al menos1,70 metros. Dado un particular ser humano a, es posible determinar si amide al menos 1,70 metros, es decir, si a pertenece al conjunto {x : P (x)}.

11

12

Más concretamente, inicialmente se aceptaba la idea que toda propiedadP (x) divide un universo de discurso en dos partes: la formada por los objetosa que la satisfacen, a ∈ {x : P (x)}, y la formada por los objetos a que nola satisfacen, a /∈ {x : P (x)} .

En 1903 Bertrand Russell propuso el siguiente ejemplo de �conjunto� (se-gún la de�nición de conjunto de su época)

A = {x : x /∈ x},

y preguntó si A ∈ A.De la de�nición de A se sigue que A ∈ A implica que A /∈ A y, además,

que A /∈ A implica que A ∈ A.Por tanto se obtiene la contradicción: A ∈ A si y sólo si A /∈ A.

El ejemplo de Russell muestra que no toda propiedad determina un con-junto, hace falta restringir la clase de propiedades que de�nen conjuntos.

La primera de las restricciones es el axioma de especi�cación: una pro-piedad por sí sola no determina un conjunto, sino que selecciona elementosde un conjunto dado al que es necesario referirse.

Para no incurrir en contradicción con el axioma de especi�cación, es nece-sario asumir la no existencia del �conjunto universal U,� el conjunto de todoslos conjuntos. Si U fuera un conjunto, también A = {x ∈ U : x /∈ x} tendríaque ser un conjunto.

En respuesta a la paradoja de Russell, se propusieron varias formulacionesaxiomáticas de la teoría de conjuntos.

En nuestra exposición, utilizaremos reglas de construcción de conjuntosformuladas en términos de la lógica de predicados, a partir de los conceptosprimitivos de conjunto y pertenencia (Zermelo-Fraenkel,1922).

2.1 Nociones de teoría de conjuntosLos conceptos de conjunto y de pertenencia de un elemento a un conjuntoson conceptos primitivos, es decir, no se de�nen.

Diremos que un conjunto A es una colección (familia, clase), �nita oin�nita, de objetos de un universo U tal que para todo objeto x se puedadeterminar si x pertenece a A. Los objetos de un conjunto serán sus ele-mentos. Si x pertenece al conjunto A, se escribirá x ∈ A. Si x no pertenecea A, se escribirá x /∈ A.

13

Ejemplos 2.1.1N := {1, 2, · · · } es el conjunto de los números naturales,Z := {· · · ,−2,−1, 0, 1, 2, · · · } es el conjunto de los números enteros,F := {p

q: p, q ∈ Z y q 6= 0} es el conjunto de las fracciones de

números enteros,A := {x ∈ R : x2 = 1} = {−1, 1} es el conjunto solución de la ecuaciónx2 − 1 = 0.

Notación: los símbolos Q, R y C denotarán, respectivamente, el con-junto de los números racionales, reales y complejos.

2.1.1 Inclusión e igualdad de conjuntosSi todo elemento x de un conjunto A es también elemento de un conjunto B,se dirá que A está contenido en B o que A es un subconjunto de B (y seescribirá A ⊆ B ó B ⊇ A).

Si A es un subconjunto de B y existe un elemento de B que no pertenecea A, entonces A es un subconjunto propio de B : A B ó A ⊂ B.

Dos conjuntos A y B son iguales si contienen los mismos elementos. Porejemplo, los conjuntos A = {−2, 1, 0,−7} y B = {−7, 1, 0,−2} son iguales.

Nota importante: para demostrar que dos conjuntos A y B son iguales,es necesario veri�car las dos siguientes condiciones:

1)A ⊆ B (2.1)2)B ⊆ A (2.2)

Ejemplos 2.1.2 1) Sean A = {x ∈ R : x2 + x− 2 = 0} y B = {−2, 1}.Los elementos de A son las soluciones de la ecuación x2 +x−2 = 0, es decir,son los números x1 = 1 y x2 = −2. Ya que x1 ∈ B y x2 ∈ B, A ⊆ B. Ahoraestá claro que también B ⊆ A. Por tanto, A = B.

2) Sean A = {a, b, c, d} y B = {c, a, d, b}, entonces A = B.

El conjunto vacío ∅ es el conjunto que no tiene elementos.Nota: el conjunto ∅ no es igual al conjunto A = {∅}, pués A tiene un

elemento, el conjunto vacío.Ejemplo 2.1.3 Sea A = {x ∈ R : x2 = −1}. Entonces A = ∅.Proposición 2.1.4 Sea A un conjunto cualquiera. Entonces ∅ ⊆ A.

14

2.1.2 Operaciones con conjuntosSi A y B son dos conjuntos, es posible construir nuevos conjuntos por mediode las siguientes operaciones:

• la unión de A y B es el conjunto A ∪ B de todos los elementos de Ao de B, es decir

A ∪B = {x : x ∈ A ó x ∈ B},

• la intersección de A y B es el conjunto A∩B de todos los elementosque pertenecen tanto a A como a B, es decir

A ∩B = {x : (x ∈ A) y (x ∈ B)}.

Si A y B no tienen elementos en común, entonces A ∩B = ∅ y se diráque A y B son disjuntos,

• el complemento (relativo) de B respecto de A es el conjunto A\Bde todos los elementos de A que no pertenecen a B, es decir

A\B = {x : (x ∈ A) y (x /∈ B)}.

• el producto cartesiano de dos conjuntos no vacíos A y B es el con-junto de todos pares ordenados (a, b) con a ∈ A y b ∈ B, es decir

A×B = {(a, b) : (a ∈ A) y (b ∈ B)}.

Para representar grá�camente un producto cartesiano A×B de dos conjuntos,se puede utilizar un sistema de ejes. Los elementos de A se representan pormedio de puntos del eje de las abscisas y los elementos de B por medio depuntos del eje de las ordenadas. Entonces los elementos de A×B son todoslos puntos de �coordenadas� (a, b).Por ejemplo, sean A = {x, y, z} y B = {a, b}. La �gura (2.1) es una repre-sentación grá�ca (obtenida con el sistema Maple sustituyendo las letras pornúmeros: x = 1, y = 2, z = 3, a = 1, b = 2) de A×B.

15

0

1

2

3

4

y

1 2 3 4x

Figura 2.1: Grá�ca de A×B.

2.1.3 Partes de un conjunto y propiedades de las ope-raciones con conjuntos

Si A es un conjunto, se llama conjunto de las partes de A, P (A), al nuevoconjunto cuyos elementos son exactamente los subconjuntos de A.

Nota: Para todo conjunto A, P (A) es siempre no vacío, ya que ∅ ∈ P (A).

Ejemplo 2.1.5 Sea A = {a, b, c}. Entonces

P (A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Sean A, B y C tres conjuntos. Las principales propiedades de las opera-ciones con conjuntos son las siguientes:

1) idempotencia de la unión y de la intersección:

A ∪ A = A (2.3)A ∩ A = A (2.4)

2) conmutatividad de la unión y de la intersección:

A ∪B = B ∪ A (2.5)A ∩B = B ∩ A (2.6)

3) asociatividad de la unión y de la intersección:

A ∪ (B ∪ C) = (A ∪B) ∪ C (2.7)A ∩ (B ∩ C) = (A ∩B) ∩ C (2.8)

16

4) distributividad de la unión respecto de la intersección y de la inter-sección respecto de la unión:

A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) (2.9)A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C) (2.10)

5)

A ∪ ∅ = A (2.11)A ∩ ∅ = ∅ (2.12)

6) Leyes de De Morgan (para conjuntos):

C\(A ∪B) = (C\A) ∩ (C\B) (2.13)C\(A ∩B) = (C\A) ∪ (C\B) (2.14)

7)

(A\B) ∪B = A ∪B (2.15)(A\B) ∩B = ∅ (2.16)

A\(A\B) = A ∩B (2.17)

2.1.4 Cardinal de un conjuntoEl cardinal de un conjunto �nito A, Card(A), es el número de elementos deA. Si A es un conjunto in�nito se escribirá Card(A) = ∞.

Sean A y B dos conjuntos �nitos cualesquiera, entonces

Card(A ∪B) = Card(A) + Card(B)− Card(A ∩B) ≤ (2.18)≤ Card(A) + Card(B)

Si A ∩B = ∅, Card(A ∪B) = Card(A) + Card(B).

Observación: Se puede comprobar que si A es un conjunto �nito conCard(A) = n, entonces Card(P (A)) = 2n.

Ejemplos 2.1.6 1) Card(N) = ∞2) Sean A = {−2, 0, 3, 17} y B = {−7, 0, 5, 17, 18}. Entonces, A ∪ B =

{−7,−2, 0, 3, 5, 17, 18} y A ∩B = {0, 17}. Se sigue que

7 = Card(A ∪B) = Card(A) + Card(B)− Card(A ∩B) = 4 + 5− 2.

17

2.2 Relaciones binariasSean A y B dos conjuntos no vacíos.

De�nición 2.2.1 Una relación binaria entre A y B es un subconjuntoR del producto cartesiano A × B. Si (a, b) ∈ R se dirá que a y b estánrelacionados y se escribirá aRb.

Ejemplo 2.2.2 Sean A = {a, b, c}, B = {d, e} y R = {(a, d), (b, e), (c, d), (c, e)}.Entonces aRd, bRe, cRd y cRe. (Ver �gura (2.2))

0

1

2

3

4

y

1 2 3 4x

Figura 2.2: Grá�ca de R.

Si R ⊆ A×A (es decir, si A = B), se dirá que R es una relación binariaen A.

En las siguientes de�niciones vamos a emplear el cuanti�cador universal ∀y el símbolo de implicación → de la lógica de predicados, que estudiaremos endetalle. La notación ∀x ∈ A quiere interpretarse como �para todo elementox del conjunto A �.

Una relación R en un conjunto no vacío A puede ser:

• R1) re�exiva: ∀x ∈ A xRx

• R2) simétrica: ∀x, y ∈ A xRy → yRx

• R3) antisimétrica: ∀x, y ∈ A (xRy y yRx) → x = y

• R4) transitiva: ∀x, y, z ∈ A (xRy y yRz) → xRz

Para estudiar las propiedades de una relación binaria sobre un conjuntoA es conveniente representar grá�camente la relación (ver ejercicio (2.5.6)).

18

Observación 2.2.3 Las únicas relaciones binarias en un conjunto no vacíoA que sean al mismo tiempo simétricas y antisimétricas son tales que R ⊆{(x, y) : x = y}.

Ejemplos 2.2.4 1) Sea A el conjunto de las personas y R = {(a, b) ∈ A×A :a es el padre de b}. Esta relación no tiene ninguna de las propiedades R1, R2y R4.

2) En el conjunto de las partes P (A) de un conjunto A, la relación deinclusión R = {(B, C) ∈ P (A) × P (A) : B ⊆ C} es re�exiva, antisimétricay transitiva.

3) En el conjunto Z de los números enteros, la relación R = {(n,m) ∈Z× Z : n−m es par} es re�exiva, simétrica y transitiva.

4) En el conjunto de las rectas del plano real, la relación �r es ortogonala s� no es re�exiva, es simétrica y no es transitiva.

De�nición 2.2.5 Si R ⊆ A×B es una relación binaria, se denomina

• dominio de R al conjunto

dom(R) = {x ∈ A : ∃y ∈ B tal que (x, y) ∈ R} ⊆ A

• imagen directa (o rango) de R al conjunto

Im(R) = {y ∈ B : ∃x ∈ A tal que (x, y) ∈ R} ⊆ B

• imagen inversa (o recíproca) de un subconjunto C de B al conjunto

R−1(C) = {x ∈ A : ∃y ∈ C tal que (x, y) ∈ R} ⊆ A

• codominio de R al conjunto B.

2.2.1 Relaciones de equivalenciaDe�nición 2.2.6 Una relación binaria R en un conjunto no vacío A sedenomina relación de equivalencia si es re�exiva, simétrica y transitiva.Si R es una relación de equivalencia en A y a, b ∈ A son tales que aRb, seescribirá a ∼ b.

19

Si a ∈ A y ∼ es una relación de equivalencia en A, se puede de�nir unsubconjunto C(a) de A denominado clase de equivalencia de a :

C(a) = {x ∈ A : x ∼ a}. (2.19)

Notar que C(a) no es vacío ya que toda relación de equivalencia es re�exiva.Sea b otro elemento de A. Puede ocurrir sólo una de las siguientes situa-

ciones:

si a ∼ b, entonces C(a) = C(b), (2.20)si a � b, entonces C(a) ∩ C(b) = ∅. (2.21)

Por tanto, si consideramos el conjunto de las distintas clases de equivalencias,este conjunto representa una partición de todo A entre subconjuntos disjuntosy se denomina conjunto cociente.

Ejemplos 2.2.7 1) La relación R = {(n,m) ∈ Z × Z : n − m es par}, esuna relación de equivalencia y Z = C(0)∪C(1). C(0) es el conjunto de todoslos enteros pares y C(1) de los enteros impares.

2) En el conjunto de las rectas del plano real, la relación �r es paralela as� es una relación de equivalencia. Para toda recta r, C(r) representa a ladirección determinada por r.

3)Números racionalesEn el conjunto F de las fracciones F := {p/q : p, q ∈ Z y q 6= 0}, paratodo par de fracciones r1 = p1

q1y r2 = p2

q2, se de�ne la relación de equivalencia

R como r1 ∼ r2 ↔ p1q2 = p2q1. El conjunto de las clases de equivalencia esel conjunto Q de los números racionales.

Observación 2.2.8 Otra importante clase de relaciones binarias sobre unconjunto es la clase de la relaciones de orden, que no necesitaremos conocerpara el estudio de la lógica matemática. Además, el alumno tendrá ocasiónde estudiar las relaciones de orden en la asignatura paralela de MatemáticaDiscreta y Álgebra. Por estas razones, omitimos su estudio en estos apuntes.

2.3 Relaciones n−ariasSean A1, A2, . . . , An conjuntos no vacíos.

20

De�nición 2.3.1 Una relación de aridad n o n−aria es un subconjuntoR del producto cartesiano A1×A2× · · · ×An. Si (a1, a2, . . . , an) ∈ R se diráque (a1, a2, . . . , an) están relacionados.

Ejemplo 2.3.2 Sean A1 = {a, b, c}, A2 = {d, e} y A3 = {1, 2}. R ={(a, d, 1), (b, e, 1), (c, d, 2), (c, e, 2)} es una relación ternaria sobre A1 × A2 ×A3.

2.4 FuncionesUna función (o aplicación) (n + 1)−aria, f : A1 × A2 × · · · × An −→ B, deun conjunto no vacío A = A1 × A2 × · · · × An a un conjunto no vacío B sepuede de�nir como �una regla de correspondencia que asigna a cada elemento(a1, a2, . . . , an) ∈ A un único elemento b = f(a1, a2, . . . , an) ∈ B.� Esta de�-nición es muy intuitiva, pero no explica el término �regla de correspondencia�con su�ciente claridad.

La siguiente de�nición es más general e identi�ca el concepto de funcióncon una clase particular de relaciones binarias.

De�nición 2.4.1 Sean A1, A2, . . . , An y B conjuntos no vacíos. Una fun-ción (o aplicación) (n + 1)−aria f : A1 × A2 × · · · × An −→ B es unarelación (n + 1)−aria f ⊆ A1 × A2 × · · · × An ×B tal que

f1) dom(f) = A1 × A2 × · · · × An,f2) si (a1, a2, . . . , an) ∈ dom(f) existe un único f(a1, a2, . . . , an) ∈ Btal que (a1, a2, . . . , an, f(a1, a2, . . . , an)) ∈ f.

Entonces una función f : A1 × A2 × · · · × An −→ B es una relación entreA1 × A2 × · · · × An y B tal que a cada elemento de (a1, a2, . . . , an) ∈ A1 ×A2× · · · ×An corresponde un único elemento f(a1, a2, . . . , an) del codominioB. Si (a1, a2, . . . , an, f(a1, a2, . . . , an)) ∈ f, se dirá que f(a1, a2, . . . , an) es laimagen de (a1, a2, . . . , an) por la función f o el valor de f en (a1, a2, . . . , an).

Si el dominio de una función está compuesto de un sólo conjunto A,entonces la función es binaria.

Test de la recta vertical: Una relación R ⊆ A×B es una función si ysólo si

1) dom(R) = A y2) su grá�ca corta a cada �recta vertical� en un punto a lo más.

21

Ejemplos 2.4.2 1) La relación binaria de�nida en el ejemplo (2.2.2) no esuna función.

2) La función f : R −→ R de�nida por ∀x ∈ R, f(x) = x, es tal quedom(f) = R y Im(f) = R.

3) La función f : R −→ R de�nida por ∀x ∈ R, f(x) = x2, es talque dom(f) = R e Im(f) = R+ ∪ {0}(= [0,∞)). En este caso, f−1([0, 2]) =[−√2,

√2] y f−1((−2, 0]) = {0}.

4) La función f(x) =√

x está de�nida sólo para números reales no ne-gativos, entonces dom(f) = Im(f) = [0,∞).

5) El dominio de la función f(x) = x+2x2−1

es R\{−1, 1}.

De�nición 2.4.3 Dos funciones f, g ⊆ A×B son iguales si y sólo si:a) dom(f) = dom(g)b) ∀x ∈ dom(f), f(x) = g(x).

Ejemplo 2.4.4 Las funciones f(x) = x2, ∀x ∈ R y g(x) = x2, ∀x > 0 noson iguales, ya que dom(f) 6= dom(g).

De�nición 2.4.5 Sean f : A −→ B y g : B −→ C dos funciones. Lafunción composición (o compuesta) de f y g es la función g◦f : A −→ Cde�nida por ∀a ∈ A, (g ◦ f)(a) = g(f(a)). Entonces

g ◦ f = {(a, g(f(a))) : a ∈ A} ⊆ A× C.

Ejemplos 2.4.6 a) Siendo R+ el conjunto de los números reales positivos,sea f : R −→ R+ ∪ {0} la función f(x) = x2 + 1 y sea g : R+ ∪ {0} −→R+ ∪ {0} la función g(x) =

√x.

Entonces, la función g ◦ f : R −→ R+ ∪ {0} es la función (g ◦ f)(x) =g(f(x)) =

√x2 + 1.

b) Sean D el conjunto de las personas, M el subconjunto de las madresy A el subconjunto de las abuelas.

De�nimos las funciones f : D −→ M y g : M −→ A que asocian a todapersona y a toda madre, respectivemente, su propia madre.

En este caso la función g ◦ f : D −→ A resulta ser la función que asociaa toda persona su abuela materna.

22

2.5 EjerciciosEjercicio 2.5.1 Sean A = {−1, 0, 3, 7} y B = {−3,−1, 0, 3, 5, 7, 8}. Deter-minar A ∪B, A ∩B y A\B.

Ejercicio 2.5.2 Sean A = {−1, 0, 3, 7} y B = {−1, 1}. Determinar y repre-sentar grá�camente el conjunto A×B.

Ejercicio 2.5.3 Demostrar las propiedades

(A\B) ∪B = A ∪B (2.22)(A\B) ∩B = ∅ (2.23)

A\(A\B) = A ∩B (2.24)

Ejercicio 2.5.4 Sean A = {a, b, c}, R = {(a, a), (b, a), (c, b), (c, c)}. Enton-ces aRa, bRa, cRb y cRc. Representar grá�camente la relación R.

Ejercicio 2.5.5 En base a la siguiente Tabla 1, describir las relaciones enel conjunto A = {Andrea, Beatriz, Carlos, Davide, Edward } :

1) xR1y ↔ x e y viven en el mismo país.2) xR2y ↔ x e y tienen el mismo número de teléfono o la misma edad.3) xR3y ↔ x e y tienen la misma altura y son europeos.

Tabla 1 Edad Tel. País Altura OcupaciónAndrea 21 43-6950-555-0001 Alemania 1,75 InformáticaBeatriz 18 34-91-555-0000 España 1,68 EstudianteCarlos 37 34-91-555-0000 España 1,75 ProfesorDavide 18 39-06-555-0002 Italia 1,65 EstudianteEdward 21 1-215-555-0003 EEUU 1,68 Profesor

Ejercicio 2.5.6 Interpretar grá�camente las propiedades re�exiva, simétri-ca, antisimétrica y transitiva.

Ejercicio 2.5.7 Determinar dominio e imagen de las relaciones de�nidasen los ejemplos (2.2.2) y (2.2.4).

Ejercicio 2.5.8 Utilizando la Tabla 1 del ejercicio (2.5.5), de�nir una rela-ción de equivalencia en A y determinar las relativas clases de equivalencia.

23

Ejercicio 2.5.9 Determinar cuáles de las siguientes relaciones binarias sonfunciones:

a) Sobre el conjunto de las personas, la relación que asocia a cada personasu madre.

b) Sobre el conjunto de las personas que tienen hermanos, la relación queasocia a cada persona su hermano.

c) Sean A el conjunto de los alumnos matriculados en nuestra asignaturael año pasado y B el conjunto de las notas

{NP, SS,AP,NT, SB,MH}.

En A×B de�nimos la relación que asocia a cada alumno su nota �nal.d) Con la notación del apartado c), en B × A de�nimos la relación que

asocia a cada nota los alumnos que han sacado esa nota en la asignatura.

Ejercicio 2.5.10 a) Sean f, g : R −→ R las funciones f(x) =√

x2 + 1 yg(x) = x+1. Veri�car que g◦f 6= f◦g. (Entonces la composición de funcionesno es conmutativa.)

b) Demostrar que si f : A −→ B es una función, entonces f = IdB ◦ f =f ◦ IdA.

c) Descomponer la función f(x) =√

3 + ( 12+sen(x)

)2 en una composiciónde funciones más simples.

24

Parte I

Lógica de proposiciones

25

Capítulo 3

Sintaxis de la lógica proposicional

Como ya comentamos en el capítulo de introducción, la sintaxis es la de�-nición axiomática de los elementos básicos del lenguaje y de las reglas quepermiten obtener nuevas expresiones correctas a partir de aquellos, las fór-mulas.

Recordamos que se puede �jar el origen de la lógica matemática (y de lalógica proposicional) al �nal del siglo XIX, coincidiendo con la aparición delas obras de G. Boole (1815-1864) y de G. Frege (1848-1925).

El objetivo de este capítulo es el estudio de la sintaxis de la lógica propo-sicional que nos permite analizar las fórmulas proposicionales construidas apartir de fórmulas atómicas (proposiciones declarativas simples) y conectivoslógicos.

De�niciones generales:• Un alfabeto A es un conjunto de símbolos.

• Una palabra sobre el alfabeto A es una secuencia �nita de símbolosde A. Al conjunto de todas las posibles palabras se le suele denotarcomo A∗.

• Un lenguaje sobre el alfabeto A es un cualquier subconjunto de A∗.

• Las reglas de formación son las reglas que permiten obtener nuevasexpresiones de un lenguaje a partir de expresiones básicas.

A continuación vamos a de�nir el lenguaje de la lógica de proposicionespor medio de su alfabeto y sus reglas de formación.

27

28

3.1 Alfabeto del lenguaje formal de la lógicaproposicional

Los elementos básicos del alfabeto del la lógica proposicional son:

• Las proposiciones atómicas (enunciados simples o variablesproposicionales): son proposiciones (oraciones declarativas a las cua-les se pueden asociar valores de verdad) que no pueden descomponerseen otras proposiciones más simples.Para representar las proposiciones atómicas se suelen usar los símbo-los p, q, r, s, t, . . . El conjunto de estos símbolos se suele denominarsignatura.

Ejemplos 3.1.1 Los siguientes son ejemplos de proposiciones simples:p = la raíz cuadrada de 2 es irracional,q = hoy me siento feliz,t = los gatos son felinos.

• Los conectivos lógicos:

1. constantes (de aridad 0): > (verdadero) y ⊥ (falso)

2. conectivos unarios: ¬ (negación)

Ejemplo 3.1.2 Siendo q = hoy me siento feliz, aplicando la ne-gación se obtiene ¬(q) = hoy no me siento feliz.

3. conectivos binarios:∧ (y: la conjunción),∨ (ó: la disyunción),→ (la implicación o condicional),↔ (la doble implicación o coimplicación).

NOTACIÓN: El símbolo ◦ se usará para representar un conec-tivo binario cualquiera.

29

Conectiva lingüística Conectivo lógico Símbolo Fórmulaverdadero Constante de aridad 0 > >

falso Constante de aridad 0 ⊥ ⊥no p Negación (unario) ¬ ¬(p)p y q Conjunción (binario) ∧ (p ∧ q)p ó q Disyunción (binario) ∨ (p ∨ q)

si p entonces q Implicación (binario) → (p → q)(p ↔ q)

p si y sólo si q Coimplicación (binario) ↔ o(p → q) ∧ (q → p)

Tabla 3.1: Los conectivos de la lógica proposicional

Ejemplos 3.1.3 1) La frase �Hoy llueve, sin embargo no hacefrío� se escribe como (p ∧ ¬(q)), donde p = hoy llueve y q = hacefrío.2) La frase �Los lápices de mi hermana son rojos o negros� seescribe como (p ∨ q), donde p = los lápices de mi hermana sonrojos y q = los lápices de mi hermana son negros.3) El comando �IF p THEN q� se escribe como (p → q).

4) La frase �La luna es de papel si y sólo si Carlos lee muchoslibros� se escribe como (p ↔ q), donde p = la luna es de papel yq = Carlos lee muchos libros.

• Los símbolos de puntuación (o símbolos auxiliares): paréntesisabiertos y cerrados, comas.

Ejemplos 3.1.4 1) La frase �Si n es un número primo y mayor que2, entonces n es impar� se escribe como ((p ∧ q) → r), donde p = n esprimo, q = n es mayor que 2 y r = n es impar.

2) El comando �IF p THEN q ELSE r� en lógica de proposiciones seescribe como ((p → q) ∨ r).

30

3.2 De�nición recursiva de las expresiones bienconstruidas: fórmulas

Los elementos básicos de un lenguaje permiten de�nir cadenas �nitas desímbolos arbitrarias (palabras). Así, por ejemplo, la palabra ()¬p∧∨)q →)se puede formar a partir del alfabeto de la lógica de proposiciones. De todaslas posibles palabras, nos interesa de�nir aquellas que se obtienen a partir delalfabeto dado sólo por medio de la reglas de formación de nuestro lenguaje.

En matemáticas y en la ciencia de la computación a menudo se usande�niciones recursivas de conjuntos o funciones.

Por ejemplo, para de�nir el conjunto N = {1, 2, 3, 4, . . . } de los númerosnaturales se puede dar un símbolo inicial 1 y unas reglas de formación, quenos permite hallar el resto de los elementos del conjunto. En nuestro caso,la de�nición recursiva de los números naturales está dad por los axiomas dePeano (siglo XIX).Axiomas de Peano:

• En N hay un elemento distinguido que denominamos 1.

• Para cada n ∈ N se de�ne de manera única el siguiente de n. Elsiguiente de n se denota s(n) = n + 1 y es un elemento de N para cadan ∈ N.

• No existe ningún número natural n tal que s(n) = 1.

• Si s(n) = s(m) entonces n = m.

• Principio de inducción: si un conjunto de números naturales con-tiene al 1 y a los sucesores de cada uno de sus elementos, entoncescontiene a todos los números naturales.

Otro ejemplo muy conocido es la de�nición recursiva de la sucesión {fn}n∈Nde Fibonacci (hacia 1175−1250), que fue de�nida para estudiar la reproduc-ción de los conejos. Sus primeros dos términos son f1 = 1 y f2 = 1. Si n ≥ 3,entonces el valor fn se deduce de los valores fn−1 y fn−2 según la fórmulafn = fn−1 + fn−2. Se sigue que {fn} = {1, 1, 2, 3, 5, 8, 13, · · · }.

Volviendo a la lógica proposicional, para de�nir las expresiones sintácti-camente correctas también se usa una construcción de tipo recursivo, que esla siguiente:

31

De�nición 3.2.1 Una fórmula proposicional (fórmula bien construi-da, fbc) es una palabra sobre el alfabeto de la lógica proposicional que puedeconstruirse en un número �nito de pasos mediante las reglas de formaciónque vamos a de�nir a continuación.

De�nición recursiva de las expresiones bien construidas:

1. (At): Los símbolos > y ⊥ y toda proposición atómica son una fórmula.

2. (¬): Si ϕ es una fórmula entonces ¬(ϕ) es una fórmula.

3. (◦): Si ϕ y ψ son dos fórmulas entonces (ϕ ◦ ψ) es una fórmula.

4. Si una palabra no se obtiene mediante las tres reglas anteriores entoncesno es una fórmula.

NOTACIÓN: Para representar las fórmulas se suelen usar las letras delalfabeto griego ϕ, ψ, χ, . . .

De�nición 3.2.2 Dadas dos fórmulas ϕ y ψ, se dice que ψ es una sub-fórmula de ϕ si ψ consiste de símbolos consecutivos de ϕ. En particular,cada fórmula es una subfórmula de sí misma.

Ejemplo 3.2.3 La palabra ((p∧q) → r), del ejemplo (3.1.4) es una fórmulabien construida ya que:

1. p, q, r, son fórmulas atómicas (aplicando (At)),2. (p ∧ q) es una fórmula proposicional (aplicando (◦)),3. ((p ∧ q) → r) es una fórmula proposicional (aplicando (◦)).Además, (p ∧ q) y r son subfórmulas de ((p ∧ q) → r).

3.2.1 El principio de inducción estructural para fórmu-las proposicionales

Para poder estudiar las propiedades de las fórmulas proposicionales una delas técnicas más adecuadas es el principio de inducción estructural para fór-mulas proposicionales, que es una versión generalizada del razonamiento deinducción de�nido a partir de los axiomas de Peano de los números naturales.

Antes de enunciar el principio de inducción estructural, recordamos lade�nición de razonamiento por inducción:

32

Razonamiento por inducciónSea P (n) una propiedad para números naturales. Supongamos que se

pueda probar que:

1. Base de inducción: se veri�ca P (1),

2. Paso de inducción: si se veri�ca P (n) (hipótesis de inducción),entonces se veri�ca P (n + 1).

Bajo las hipótesis anteriores, se sigue que se veri�ca P (n) para todo númeronatural n.

La demostración de la validez del razonamiento de inducción se obtieneaplicando el principio de inducción al conjunto A = {n ∈ N : P (n) se veri�ca}.

Ejemplo 3.2.4 Vamos a demostrar por inducción que para todo n ∈ N,

2n ≤ (n + 1)!

Base de inducción: P (1) es verdadera, siendo (2 ≤ 2).Paso de inducción: si 2n ≤ (n + 1)! (si se veri�ca P (n)), entonces

2n+1 = 2 2n ≤ 2 (n + 1)! ≤ (n + 2) (n + 1)! = (n + 2)!.

Por tanto, 2n ≤ (n + 1)! se veri�ca para todo número natural n.

El principio de inducción estructural generaliza el método de demostra-ción por inducción. Ese método de demostración se emplea para veri�carpropiedades de conjuntos generados inductivamente (recursivamente), cuyoselementos se obtienen como resultado de aplicar un número �nito de reglasde formación.

Sus aplicaciones son numerosas y en informática se utiliza, por ejemplo,para la veri�cación de programas (ver por ejemplo el capítulo 9 de [C]).Principio de inducción estructural para fórmulas proposicionales

Sea P una cierta propiedad tal que:

1. Base de inducción (At): Los símbolos > y ⊥ y toda proposiciónatómica cumplen la propiedad P.

33

2. Pasos de inducción:

• (¬): Si ϕ es una fórmula que cumple la propiedad P (hipótesisde inducción), entonces ¬(ϕ) cumple la propiedad P.

• (◦): Si ϕ y ψ son dos fórmulas que cumplen la propiedad P(hipótesis de inducción), entonces (ϕ◦ψ) cumple la propiedad P.

Entonces, el principio de inducción estructural para fórmulas pro-posicionales a�rma que, si se veri�can las condiciones anteriores, se puedeconcluir que toda fórmula bien construida cumple la propiedad P.

Ejemplo 3.2.5 [HLR] Usando el principio de inducción estructural podemosprobar que toda fórmula ϕ contiene el mismo número de paréntesis abiertosy cerrados:

Base de inducción (At): Los símbolos > y ⊥ y toda proposiciónatómica contienen 0 paréntesis abiertos y 0 paréntesis cerrados.

Pasos de inducción:(¬): Si ϕ es una fórmula que contiene n paréntesis abiertos y n parén-

tesis cerrados, entonces ¬(ϕ) contiene n + 1 paréntesis abiertos y n + 1paréntesis cerrados.

(◦): Si ϕ y ψ son dos fórmulas que contienen nϕ y nψ paréntesisabiertos y nϕ y nψ paréntesis cerrados respectivamente, entonces (ϕ ◦ ψ)contiene nϕ + nψ + 1 paréntesis abiertos y nϕ + nψ + 1 paréntesis cerrados.Se sigue que, por el principio de inducción estructural, toda fórmula ϕ con-tiene el mismo número de paréntesis abiertos y cerrados.

3.3 Representación de las fórmulas bien cons-truidas

En este apartado vamos a ilustrar las maneras más usadas para representarlas fórmulas de la lógica proposicional.

3.3.1 Fórmulas en forma usual y abreviadaForma usual

Siguiendo las reglas de formación de las fórmulas proposicionales obtene-mos ejemplos de expresiones bien construidas como las siguientes:

34

1. ((p ∧ (p → r)) ∨ (q ↔ t)),

2. (p ∧ (¬(¬((q → r) → (p ∨ (¬(r))))))),

3. (p → (q → r)).

Se puede notar que se usan paréntesis para evitar ambigüedad en la for-malización. Sin embargo este uso se puede relajar obteniendo expresionesque no son fórmulas bien construidas, pero vienen empleadas como tales porrazones de convenios.Forma abreviada

Para reducir una fórmula bien construida a su forma abreviada pode-mos seguir los siguientes pasos:a) Se puede omitir el par de paréntesis externo.

Así, por ejemplo, las anteriores fórmulas 1., 2. y 3. se escribirían como:1.1. (p ∧ (p → r)) ∨ (q ↔ t),2.1. p ∧ (¬(¬((q → r) → (p ∨ (¬(r)))))),3.1. p → (q → r).

b) Se introducen las siguientes reglas de precedencia entre conectivos quede�nen las prioridades que tenemos que respectar a la hora de aplicarlos:

Nivel 1: ¬,Nivel 2: ∨ y ∧,Nivel 3: → y ↔ .

Así, por ejemplo, las anteriores fórmulas 1.1, 2.1. y 3.1 se escribiríancomo:

1.2. (p ∧ (p → r)) ∨ (q ↔ t),2.2. p ∧ ¬¬((q → r) → p ∨ ¬r),3.2. p → (q → r).

c) Se admite el convenio de asociatividad: los conectivos ∨∧, → y ↔se asocian por la derecha:

p ∧ q ∧ r es p ∧ (q ∧ r)

p ∨ q ∨ r es p ∨ (q ∨ r)

35

p → q → r es p → (q → r).

Así, por ejemplo, las anteriores fórmulas 1.2, 2.2. y 3.2 se escribiríancomo:

1.3. (p ∧ (p → r)) ∨ (q ↔ t),2.3. p ∧ ¬¬((q → r) → p ∨ ¬r),3.3. p → q → r.

3.3.2 Fórmulas en forma de árbol estructuralEl siguiente principio de unicidad de estructura para fórmulas pro-posicionales a�rma que cada fórmula admite un análisis sintáctico único,es decir, existe una única manera de derivar una fórmula usando las reglasde formación dadas.

Principio de unicidad de estructura para fórmulas proposicionalesToda fórmula proposicional ϕ pertenece a una y sólo una de las siguientes

categorías:

1. (At): ϕ es atómica,

2. (¬): ϕ es ¬(ϕ1) para cierta fórmula ϕ1,

3. (◦): ϕ es (ϕ1 ◦ ϕ2) para cierto conectivo ◦ y ciertas fórmulas ϕ1 yϕ2 .

Además, en todos los casos la fórmulas ϕ1 y ϕ2 están unívocamente deter-minadas.

Una primera consecuencia del principio de unicidad de estructura es laposibilidad de representar fórmulas proposicionales por medio de árboles.Este tipo de representación nos permite facilitar el análisis de la estructurasintáctica de toda fórmula, ya que nos permite recorrer al revés los pasos desu construcción.

El alumno estudiará el concepto de árbol en detalle en él contexto de lateoría de grafos en la asignatura de Matemática Discreta y Álgebra. Aquíqueremos simplemente introducir, por medio de ejemplos, árboles con raízpara realizar diagramas grá�cos asociados a fórmulas proposicionales.

36

Repaso de alguna de�niciones y propiedades básicas sobre árboles[CM]:

De�nición 3.3.1 Un grafo simple G es un par G = (V, E) formado porun conjunto �nito de vértices V y un conjunto E de pares no ordenados devértices distintos, es decir,

E ⊂ {{u, v} |u, v ∈ V ∧ u 6= v}.A los elementos de E se les denomina aristas (no dirigidas o no orien-tadas).

De�nición 3.3.2 El grado de un vértice en un grafo simple es el númerode aristas incidentes con él.

De�nición 3.3.3 Un camino de longitud n entre los vértices a y b de ungrafo no dirigido es una sucesión �nita (e0, ..., en−1) de aristas del grafo

e0 = {v0, v1}, e1 = {v1, v2}, ..., en−1 = {vn−1, vn}de manera que v0 = a, vn = b y cada arista sucesiva empieza donde terminóla anterior. Si el grafo es simple, el camino (e0, ..., en−1) queda perfectamentedeterminado por la sucesión de vértices

(a, v1, v2, ..., vn−1, b).

Diremos que el camino anterior pasa por (o atraviesa) los vértices a,v1, v2, ..., vn−1, b.

Se dice que un camino es un circuito si es cerrado, esto es, empieza ytermina en el mismo vértice, es decir, si a = b.

Se dice que un camino es simple si no contiene a la misma arista másde una vez.

Un circuito que no pasa dos veces por el mismo vértice (salvo el inicialpor el que pasa dos veces) se llama ciclo.

De�nición 3.3.4 Un árbol es un grafo no dirigido, conexo y sin circuitossimples.

Proposición 3.3.5 Sea G = (V, E) un grafo simple. G es un árbol si ysolamente si para cada par de vértices u, v ∈ V existe un único camino simpleque une u con v.

37

De�nición 3.3.6 Un árbol con raíz es un par (T, r) donde T es un árboly r un vértice distinguido de T llamado raíz al que se suele colocar en larepresentación grá�ca en la parte superior.

De�nición 3.3.7 Dado un árbol con raíz (G, r) se denominan hojas a losvértices de G distintos de r que tienen grado 1.

A los vértices distintos de la raíz que no son hojas de un árbol con raízse les denomina vértices internos.

Los árboles con raíz llevan asociada una terminología de origen botánicoy genealógico: dado un árbol con raíz T, si v es un vértice de T distinto dela raíz, el padre de v es el único vértice u de T tal que hay una arista deu a v. Si u es el padre de v, también diremos que v es un hijo de u. Losantecesores de un vértice son los vértices que nos encontramos en el únicocamino que une dicho vértice con la raíz. Los descendientes de un vérticev son todos aquellos vértices de los que v es antecesor.

Es fácil darse cuenta de que las hojas de un árbol dirigido son los vérticesque no tienen descendientes.

p

p

r

→

∧

∨

↔

q t

¡¡

¡¡

¡¡

¡¡

@@

@@

@@

@@³³³³³³³³³³³HHHHHHHH

@@

@@

¡¡

¡¡

Figura 3.1: Árbol sintáctico de ((p ∧ (p → r)) ∨ (q ↔ t)).

Vamos entonces a usar árboles con raíz para representar la estructurasintáctica de las fórmulas proposicionales como en el siguiente ejemplo.

Ejemplo 3.3.8 Sea ϕ la fórmula proposicional

((p ∧ (p → r)) ∨ (q ↔ t)).

38

Para representar la estructura sintáctica de ϕ, podemos dibujar el árbolcon raíz de la �gura (3.1).

Las hojas del árbol obtenido representan las fórmulas atómicas a partir delas cuales se ha generado ϕ. El árbol se lee de abajo hacía arriba y en cadanodo interior y en la raíz aparecen los conectivos empleados en la formaciónde nuestra fórmula.

3.3.3 El principio de recursión estructural para fórmu-las proposicionales

Una segunda consecuencia del principio de unicidad de estructura es el prin-cipio de recursión estructural para fórmulas proposicionales que nospermite de�nir funciones

f : L −→ A

cuyo dominio sea el conjunto L de todas las fórmulas proposicionales y cuyocodominio sea un conjunto dado A.

El principio de recursión estructural para fórmulas proposicionalesconsiste en la siguiente de�nición recursiva de la función f : L −→ A :

1. Base (At): Si ϕ es atómica, f( ϕ ) se de�ne explícitamente, es unelemento de A,

2. Pasos recursivos:

• (¬): f(¬(ϕ)) es un valor que depende de ¬ y de f(ϕ1),

• (◦): f(ϕ1 ◦ ϕ2) para cierto conectivo ◦ y ciertas fórmulas ϕ1 yϕ2 es un valor que depende de ◦, f(ϕ1) y f(ϕ2).

Estas de�niciones determinan la función f sobre todo L.

Ejemplo 3.3.9 (HLR) Se puede de�nir recursivamente la función

f : L −→ N ∪ {0}

que a cada fórmula ϕ ∈ L asocia el número (entero no negativo) de conec-tivos binarios en la estructura sintáctica de ϕ :

39

1. Base (At): Si ϕ es atómica, f( ϕ ) = 0

2. Pasos recursivos:(¬): f(¬(ϕ)) = f( ϕ )

(◦): f(ϕ1 ◦ ϕ2) = f(ϕ1) + f(ϕ2) + 1, para cierto conectivo ◦ y ciertasfórmulas ϕ1 y ϕ2.

Estas de�niciones determinan la función f sobre todo L.

3.4 Formalización del lenguaje naturalEn esta sección se presentan algunos ejemplos de formalización del lenguajenatural. La formalización es una herramienta básica y el alumno tendráocasión de practicarla a lo largo de todo el estudio de la lógica proposicionaly de predicados.

La tabla (3.2) ([C]) contiene algunos ejemplos de formalización de frasesimples. A partir de la formalización de estos ejemplos podemos formalizarfrases y razonamiemtos más complejos.

Para formalizar un razonamiento con premisas p1, p2, . . . , pn y conclusiónq usaremos cualquiera de las dos formas:

p1

p2...pn

q

o p1 ∧ p2 ∧ · · · ∧ pn → q.

Observación 3.4.1 Una manera sencilla de veri�car la validez de la forma-lización de una frase del lenguaje natural es de volver a traducir al lenguajenatural la formalización obtenida.

Así, por ejemplo, consideremos la frase �No voy a la playa a menos quehaga mucho calor.�

Siendo p = voy a la playa y q = hace mucho calor, la formalización(p → q) es correcta y la formalización (q → p) no es correcta. En efecto,la primera se lee como �Voy a la playa sólo si hace mucho calor� y la se-gunda como �Si hace mucho calor, entonces voy a la playa.� En la segundaformalización se ha intercambiado la condición necesaria (la conclusión) conla su�ciente (la premisa).

40

Ejemplos 3.4.2 1) El enunciado �Si una función f es derivable en el inter-valo [a, b], entonces f es continua en [a, b], � se puede formalizar de�niendolas fórmulas atómicas p = la función f es derivable en [a, b] y q = lafunción f es continua en [a, b] y aplicando el conectivo de implicación. Seobtiene (p → q) y, en forma abreviada, p → q.

2) La frase �Si salto por la ventana, o me hago daño o empiezo a volar�se puede formalizar por medio de las proposiciones atómicas p = salto porla ventana, q = me hago daño, r = empiezo a volar y los conectivos deimplicación y de disyunción. Se obtiene (p → (q∨r)) y, en forma abreviada,p → (q ∨ r).

3) La frase �Si salto por la ventana me podría hacer daño, sin embargoempiezo a volar� se puede formalizar por medio de las proposiciones atómicasp = salto por la ventana, q = me podría hacer daño, r = empiezo a volary los conectivos de implicación y de conjunción. Se obtiene (( p → q)∧ r) y,en forma abreviada, ( p → q) ∧ r.

4) El enunciado �Condición necesaria y su�ciente para que un númeroentero n sea par es que n sea divisible por 3� se puede formalizar por mediode las proposiciones atómicas p = n es un número entero, q = n es par,r = n es divisible por 3 y los conectivos de conjunción y doble implicación.Se obtiene ((p ∧ q) ↔ r) y, en forma abreviada, p ∧ q ↔ r.

5) Consideremos el razonamiento �Me gusta el helado de fresa, pero tam-bién el de limon. Si hay sólo helado de chocolate lo comeré, a pesar de queno me guste. Por tanto, no comeré helado de fresa.� Para formalizar elrazonamiento dado, de�nimos las proposiciones atómicas p = me gusta elhelado de fresa, q = me gusta el helado de limon, r = hay sólo helado dechocolate, s = comeré helado de chocolate, t = me gusta el helado de cho-colate, u = comeré helado de fresa. La formalización se puede escribir, enforma abreviada, como:

p ∧ q(r → s) ∧ ¬t

¬u

o como:

p ∧ q ∧ (r → s) ∧ ¬t → ¬u

41

Expresiones en el lenguaje natural Formalizaciónno p

es falso que p ¬pno es cierto p

p y qp pero q

p sin embargo q p ∧ qp no obstante qp a pesar de q

o p o q o ambas cosasal menos p o q p ∨ q

como mínimo p o qsi p entonces q

p sólo si qq si p

q es necesario para p p → qp es su�ciente para qno p a menos que q

no p o qp si y sólo si q p ↔ q

p es necesario y su�ciente para q oq es necesario y su�ciente para q (p → q) ∧ (q → p)

Tabla 3.2: Tabla de formalización en la lógica proposicional

42

3.5 EjerciciosEjercicio 3.5.1 Determina cuáles de las siguientes frases son proposiciones:

a) ¾Puedes ir a la cafetería?b) Por favor, sea educado.c) El jardín es muy grande.d) ½La organización del evento es un desastre!e) ½Échame una mano!

Ejercicio 3.5.2 Identi�ca cuáles de las siguientes palabras no son fórmulasproposicionales o fórmulas proposicionales abreviadas:

a) ( p → q) ∧ r) ∨ (s ∧ t),b) (¬(¬(¬(p ∧ (q → ¬(r))))),c) ¬(p),d) p¬ ∧ q,e) ¬p ∨ q ∨ s.

Ejercicio 3.5.3 Escribe en forma abreviada las siguientes fórmulas propo-sicionales:

a) ((( p → q) ∧ r) ∨ (s ∧ t)),b) ((p → (q ∨ r)) ∧ (((s → t) ∧ r) → q)),c) ((¬(p ∧ q) ↔ r) ∨ s),d) (¬((¬(p) → q) ∨ r)),e) (¬(p ∨ q) ↔ (¬(p) ∧ ¬(q))).

Ejercicio 3.5.4 Escribe en forma no abreviada las siguientes fórmulas pro-posicionales:

a) ¬r → q ∨ t ∨ s,b) p ∧ q ∧ r → s → t,c) (p ∧ q) ∨ (r ↔ s) → p,d) ¬(¬p → q ∨ r),e) p ∧ (q ∨ r) → s ∨ t.

Ejercicio 3.5.5 Representa en forma de árbol estructural las siguientes fór-mulas:

a) ((p ∨ q) → r),b) ((p → q) → ((r → p) → (r → q))),c) (¬(p ∨ q) ↔ (¬(p) ∧ ¬(q))),

43

d) ((¬(¬(¬(p) ∨ r) ∨ q)) → (¬(p ∧ q) ∨ r)),e) (((p ∨ r) → (p ∨ ¬(r))) ↔ (r → p)),f) (p → (s → p)).

Ejercicio 3.5.6 La profundidad de una fórmula proposicional ϕ es la lon-gitud máxima de los caminos simples con vértice inicial la raíz del árbol sin-táctico de ϕ.

Usando el principio de recursión estructural, de�ne recursivamente la fun-ción fp que asigna a cada fórmula ϕ su profundidad.Sugerencia: usa la función que calcula el máximo entre dos números ente-ros.

Ejercicio 3.5.7 (HLR) a) Usando el principio de recursión estructural, de-�ne recursivamente la función fn que asocia a cada fórmula ϕ el número(entero no negativo) de conectivos, sin contar los conectivos de aridad 0, queaparecen en la estructura sintáctica de ϕ.

b) Demuestra por inducción estructural que para toda fórmula ϕ se veri-�ca que

fp(ϕ) ≤ fn(ϕ),

donde la función fp es la función profundidad del ejercicio anterior.

En los siguientes ejercicios se pide formalizar los razonamientos dados. Encada caso, determinar las condiciones necesarias y las condiciones su�cientesdel razonamiento y volver a traducir al lenguaje natural la formalizaciónobtenida:

Ejercicio 3.5.8 Voy al bar siempre que me apetezca y tenga tiempo libre.

Ejercicio 3.5.9 No voy a correr a menos que tu vengas conmigo.

Ejercicio 3.5.10 Un número entero es primo sólo si no tiene divisores notriviales.

Ejercicio 3.5.11 Todos los alumnos estudian mucho y están alegres. Si losalumnos están alegres, entonces sacan buenas notas. Por tanto, los alumnosestudian mucho sólo si están alegres.

44

Ejercicio 3.5.12 Ningún número es hermano de un perro o ningún gato esprimo de un número. Si un perro es primo de un gato, entonces es hermanode un número. Por tanto, ningún gato es primo de un número.

Ejercicio 3.5.13 [C] Si llueve las calles estarán vacías. Si las calles estánvacías, el comercio obtiene perdidas. Los músicos no podrían sobrevivir silos comerciantes no les contratasen para componer canciones para publicidad.Los comerciantes invierten en canciones publicitarias cuando tienen perdidas.Por tanto, si llueve, los músicos pueden sobrevivir.

Capítulo 4

Semántica de la lógicaproposicional.Teoría interpretativa

En este capítulo vamos a estudiar la semántica y sus sistemas de demostraciónen la lógica proposicional. A continuación recordamos sus de�niciones:

La semántica es la de�nición de un conjunto de signi�cados (generalmen-te verdadero o falso) que se puedan asociar a una fórmula. Permite de�nirla validez de una fórmula o de un razonamiento.

Los sistemas de demostración son sistemas formales que permitenaveriguar cuándo una fórmula o un razonamiento son válidos. En el contextode la semántica se denominan teoría interpretativa.

Los sistemas de demostración se suelen dividir en dos clases: sistemasdirectos y sistemas indirectos (o por refutación). Los primeros aplicanuna cadena �nita de reglas de inferencia hasta llegar a la fórmula que sequiere demostrar. Los segundos aplican la técnica de reducción al absurdo.

Como sistema de demostración directo estudiaremos las tablas de verdady como sistema indirecto el método de los tableaux.

4.1 Valoraciones de un lenguaje formalRecordamos que el conjunto Σ de los símbolos p, q, r, s, t, . . . que represen-tan las proposiciones atómicas de una fórmula se suele denominar signatura:

Σ = {p, q, r, s, t, . . . }.

45

46

De�nición 4.1.1 Sea L el lenguaje de la lógica proposicional. Una valora-ción del lenguaje L es cualquier función

v : Σ −→ {0, 1}de la signatura Σ al conjunto de dos elementos {0, 1}. El símbolo 0 representael valor �falsedad� y el símbolo 1 el valor �verdad�.

Ejemplo 4.1.2 Si Σ = {p, q}, podemos representar las cuatro posibles valo-raciones de Σ :

Σ → {0, 1}p → 0q → 0

Σ → {0, 1}p → 0q → 1

Σ → {0, 1}p → 1q → 0

Σ → {0, 1}p → 1q → 1

por medio de las �las de la tabla a). De forma similar, si Σ = {p, q, r},podemos representar las ocho posibles valoraciones de Σ por medio de las�las de la tabla b).

a)

p q0 00 11 01 1

b)

p q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

Observación 4.1.3 Usando una demostración por inducción se puede veri-�car que si Σ contiene n elementos, entonces hay 2n posibles valoracionesde Σ.

4.2 Evaluación semántica de fórmulasDada una valoración v : Σ −→ {0, 1} nos interesa extender su de�nicióna todas las fórmulas proposicionales de�nidas a partir de las proposicionesatómicas de Σ. Esto no permitirá establecer los valores de verdad (veri-tativos) de esas fórmulas. Como es de esperar, la de�nición de la extensiónde una valoración tiene carácter recursivo.

47

Nota: En lo que se sigue usaremos la forma abreviada para las fórmulasproposicionales.

Como primer paso tenemos que de�nir, para toda valoración v : Σ −→{0, 1}, los valores que toman los conectivos lógicos.

Valores de verdad de los conectivos lógicos

(¬): Los valores de verdad del conectivo lógico negación, v¬p , residen en quela fórmula ¬p es verdadera si y sólo si p es falsa y, recíprocamente,que ¬p es falsa si y sólo si p es verdadera. Los valores de verdad v¬p

correspondientes al conectivo ¬ se representan en la tercera columnade la tabla (4.1).

Ejemplo 4.2.1 Sea p = Luis tiene 18 años. Entonces ¬p = Luis notiene 18 años es verdadera si es falso que Luis tiene 18 años y es falsasi Luis los tiene.

(∧): La fórmula p∧ q ( p y q ) es verdadera si y sólo si p y q son verdaderassimultáneamente. Los valores de verdad vp∧q correspondientes a esteconectivo se representan en la cuarta columna de la tabla (4.1).

Ejemplo 4.2.2 Sean p = Luis tiene 18 años y q = Maria es española.Entonces p∧ q = Luis tiene 18 años y Maria es española es verdaderasólo si es verdadero que Luis tiene 18 y es también verdadero que Mariaes española.

(∨): La fórmula p∨q ( p ó q ), es verdadera si y sólo si p es verdadera o q esverdadera o ambas p y q son verdaderas. Los valores de verdad vp∨q

correspondientes a este conectivo se representan en la quinta columnade la tabla (4.1).

Ejemplo 4.2.3 Sean p = Luis tiene 18 años y q = Maria es española.Entonces p∨ q = Luis tiene 18 años ó Maria es española es falsa sólosi es falso que Luis tiene 18 y es también falso que Maria es española.

(→): Para establecer el signi�cado de la fórmula p → q ( p implica q ), debe-mos tener presente que en lenguaje natural este enunciado encierra una

48

relación de causalidad, que no siempre aparece al utilizar este conectivoen el ámbito formal.En el lenguaje matemático, p implica q quiere decir que si p es ver-dadera, necesariamente q es verdadera, o lo que es lo mismo, que esimposible que q sea falsa si p es verdadera. Por tanto el único casoen el cual p → q puede ser falsa es si p es verdadera y q es falsa.Las fórmulas atómicas p y q son, respectivamente, el antecedente opremisa y el consecuente o conclusión de la fórmula p → q.

La fórmula q → p se denomina sentencia recíproca de la sentenciap → q, y la sentencia ¬q → ¬p sentencia contrarrecíproca de lasentencia p → q.

Los valores de verdad vp→q correspondientes al conectivo p → q serepresentan en la sexta columna de la tabla (4.1).

Ejemplo 4.2.4 Sean p = Luis tiene 18 años y q = Maria es española.Entonces p → q es falsa sólo si es verdadero que Luis tiene 18 y esfalso que Maria es española.

(↔): La fórmula p ↔ q ( p si y sólo si q ) es verdadera cuando p y q tienenel mismo valor de verdad. Los valores de verdad vp↔q correspondientesal conectivo p ↔ q se representan en la última columna de la tabla(4.1).

Ejemplo 4.2.5 Sean p = Luis tiene 18 años y q = Maria es española.Entonces p ↔ q es falsa si es verdadero que Luis tiene 18 y es falsoque Maria es española o si es falso que Luis tiene 18 y es verdaderoque Maria es española.

4.2.1 Tablas de verdadDe�nidos los valores de verdad de los conectivos de la lógica proposicional,el principio de inducción estructural nos permite extender una valoración atodas las fórmulas proposicionales.

De�nición 4.2.6 Dada una valoración v : Σ −→ {0, 1}, se asocia a cadafórmula proposicional ϕ un valor de verdad (ϕ)v ∈ {0, 1} de la siguienteforma:

49

p q v¬p vp∧q vp∨q vp→q vp↔q

0 0 1 0 0 1 10 1 1 0 1 1 01 0 0 0 1 0 01 1 0 1 1 1 1

Tabla 4.1: Valores de verdad de los conectivos

De�nición recursiva de una valoración

(At): (>)v = 1, (⊥)v = 0 y(p)v = v(p) para toda proposición atómica p.

(¬): Si ϕ es una fórmula entonces (¬(ϕ))v = v¬(ϕ).

(◦): Si ϕ y ψ son dos fórmulas entonces (ϕ ◦ ψ)v = vϕ◦ψ(ϕ ◦ ψ).

Construcción de una tabla de verdadLa tabla de verdad de una fórmula proposicional ϕ es una forma de

representar todos los posibles valores de verdad que ϕ puede tomar entodas las posibles valoraciones de las proposiciones atómicas de su signatu-ra.

La construcción de la tabla de verdad de una fórmula ϕ está basada enla de�nición recursiva de la valoración de ϕ. Por tanto, necesitamos seguirvarios pasos para completarla:

Paso 1: Tenemos que identi�car las proposiciones atómicas y los pasos que sehan seguido para construir ϕ. Para eso podemos usar el árbol estruc-tural ed ϕ.

Ejemplo 4.2.7 Volvamos a considerar la fórmula

ϕ = ((p ∧ (p → r)) ∨ (q ↔ t))

y la �gura (4.1).La proposiciones atómicas son p, q, r y t y la construcción de ϕ seobtiene leyendo su árbol de abajo hacía arriba.

50

p

p

r

→

∧

∨

↔

q t

¡¡

¡¡

¡¡

¡¡

@@

@@

@@

@@³³³³³³³³³³³HHHHHHHH

@@

@@

¡¡

¡¡

Figura 4.1: Árbol estructural de ϕ = ((p ∧ (p → r)) ∨ (q ↔ t))

Paso 2: Siguiendo el orden de construcción de ϕ se escribe la primera �la desu tabla de verdad.

Para nuestro ejemplo se obtiene:

p q r t p → r p ∧ (p → r) q ↔ t (p ∧ (p → r)) ∨ (q ↔ t)

Paso 3: Se rellenan las columnas que se corresponden a las proposiciones ató-micas con todas sus posibles valoraciones.

Para nuestro ejemplo serían las primeras cuatro columnas de la tabla(4.2), que contiene 24 + 1 = 17 �las.

Paso 4: Se rellenan todas las columnas siguiendo las valoraciones de los conec-tivos lógicos de la tabla (4.1) y, en cada �la, las valoraciones de lasproposiciones atómicas.

Para nuestro ejemplo se obtiene la tabla de verdad (4.2).

51

p q r t p → r p ∧ (p → r) q ↔ t (p ∧ (p → r)) ∨ (q ↔ t)0 0 0 0 1 0 1 10 0 0 1 1 0 0 00 0 1 0 1 0 1 10 0 1 1 1 0 0 00 1 0 0 1 0 0 00 1 0 1 1 0 1 10 1 1 0 1 0 0 00 1 1 1 1 0 1 11 0 0 0 0 0 1 11 0 0 1 0 0 0 01 0 1 0 1 1 1 11 0 1 1 1 1 0 11 1 0 0 0 0 0 01 1 0 1 0 0 1 11 1 1 0 1 1 0 11 1 1 1 1 1 1 1

Tabla 4.2: Tabla de verdad de ϕ = (p ∧ (p → r)) ∨ (q ↔ t).

4.3 Modelos y contraejemplos de una fórmu-la bien construida. Tautologías, contingen-cias y contradicciones

La posibilidad de valorar fórmulas proposicionales nos permite de�nir lassiguientes nociones fundamentales.

De�nición 4.3.1 Se dice que una fórmula ϕ es satisfacible bajo unavaloración v (o que v es un modelo de ϕ ) cuando se veri�ca que

(ϕ)v = 1.

Si ϕ es satisfacible bajo v se emplea la notación v |= ϕ.

52

Ejemplo 4.3.2 En la tabla de verdad de la tabla (4.2), las valoraciones

Σ → {0, 1}p → 0q → 0r → 0s → 0

y

Σ → {0, 1}p → 0q → 0r → 1s → 0

son dos de los diez posibles modelos de la fórmula ϕ = (p∧(p → r))∨(q ↔ t).

De�nición 4.3.3 Se dice que una valoración v es un contraejemplo deuna fórmula ϕ cuando se veri�ca que (ϕ)v = 0.

Ejemplo 4.3.4 En la tabla de verdad de la tabla (4.2), las valoraciones

Σ → {0, 1}p → 0q → 0r → 0s → 1

y

Σ → {0, 1}p → 0q → 0r → 1s → 1

son dos de los seis posibles contraejemplos de la fórmula ϕ = (p ∧ (p →r)) ∨ (q ↔ t).

De�nición 4.3.5 Se dice que una fórmula ϕ es satisfacible cuando essatisfacible bajo alguna valoración v. En caso contrario se dice que es insa-tisfacible.

Ejemplo 4.3.6 La fórmula ϕ = p∧¬p es insatisfacible, ya que p y ¬p nopueden ser verdaderos a la vez.

Observación 4.3.7 Las de�niciones anteriores se pueden extender a unconjunto de fórmulas Φ = {ϕ1, ϕ2, . . . , ϕn} pidiendo que la satisfacibilidadde Φ sea la satisfacibilidad simultánea de todas las fórmulas que lo de�nen.

Entonces,1) Φ es satisfacible si y sólo si ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn es satisfacible.2) Φ es insatisfacible si y sólo si ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn es insatisfacible.

Ejemplo 4.3.8 Sea v(p) = 0, v(q) = 1, v(r) = 1 una valoración del con-junto {p, q, r}.

Entonces v es un modelo del conjunto de dos fórmulas Φ1 = {(p →q)∧ r, q ∧ r} y es un contraejemplo del conjunto Φ2 = {p∧ (q → r), q ∧ r}.

53

De�nición 4.3.9 Sea ϕ una fórmula proposicional construida a partir deun conjunto Σ = {p1, p2, p3, . . . } de proposiciones atómicas.

1. Se dice que la fórmula ϕ es lógicamente válida o una tautologíacuando es verdadera bajo cualquier valoración, es decir, si v |= ϕ paratoda valoración v de Σ.

2. Se dice que ϕ es una contradicción cuando es falsa bajo cualquiervaloración, es decir, si toda valoración v de Σ es un contraejemplo deϕ. Por tanto una contradicción es una fórmula insatisfacible.

3. Se dice que ϕ es una contingencia cuando entre las valoraciones deΣ existen al menos un modelo y al menos un contraejemplo de ϕ.

Ejemplos 4.3.10 1) Por de�nición,

> es una tautología y⊥ es una contraddicción.

2) Para toda fórmula ϕ,

ϕ ∨ ¬ϕ es una tautología (ley del tercio excluso) yϕ ∧ ¬ϕ es una contradicción.

3) Usando una tabla de verdad se puede veri�car que vale la ley conmu-tativa para el conectivo ∧, es decir, que

p ∧ q ↔ q ∧ p

es una fórmula lógicamente válida.

p q p ∧ q q ∧ p p ∧ q ↔ q ∧ p0 0 0 0 10 1 0 0 11 0 0 0 11 1 1 1 1

4) La tabla de verdad (4.2) de ϕ = (p ∧ (p → r)) ∨ (q ↔ t) nos indicaque ϕ es una contingencia.

54

4.4 Evaluación semántica de deducciones. Con-secuencia lógica

Otro concepto fundamental que vamos a de�nir es el concepto de consecuen-cia lógica.

De�nición 4.4.1 Se dice que una fórmula ϕ es consecuencia lógica deun conjunto �nito de fórmulas Φ = {ϕ1, ϕ2, . . . ϕn} si todo modelo v delconjunto Φ es un modelo de la fórmula ϕ, es decir, si

v |= Φ implica que v |= ϕ.

Si ϕ es consecuencia lógica de Φ también se dice que Φ implica lógi-camente a ϕ y se escribe

Φ |= ϕ.

Ejemplo 4.4.2 La tabla (4.3) contiene algunos importantes ejemplos de im-plicaciones lógicas (ver ejercicio (4.7.4)).

De�nición 4.4.3 Sean Φ = {ϕ1, ϕ2, . . . ϕn} un conjunto �nito de fórmulasproposicionales y ϕ una fórmula. Se de�ne deducción o razonamiento ala fórmula

((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) → ϕ).

Para distinguir las premisas del conjunto Φ de la conclusión ϕ, un ra-zonamiento se puede representar de la siguiente manera:

ϕ1...

ϕn

ϕ

Observación 4.4.4 Decir que ((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) → ϕ) es una tautologíasigni�ca que es imposible que las fórmulas de Φ tengan todas el valor deverdad 1 y ϕ tenga valor 0. Por tanto ((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) → ϕ) es unatautología si y sólo si Φ implica lógicamente a ϕ.

Por el otro lado, una fórmula ϕ es siempre consecuencia lógica de uncualquier conjunto de fórmulas Φ insatisfacible.

55

¬¬p |= p, Ley de la doble negación(p ∧ q) |= p Leyes de simpli�caciónp |= (p ∨ q)(p → q) |= (¬q → ¬p) Ley de contraposición((p → q) ∧ (q → r)) |= (p → r) Ley transitiva de →((p ∧ q) → r) |= (p → (q → r)) Ley de exportación(p ∧ (p → q)) |= q Modus ponens((p → q) ∧ ¬q) |= ¬p Modus tolens

Tabla 4.3: Tabla de algunas implicaciones lógicas

De�nición 4.4.5 Se dice que el razonamiento anterior es correcto o lógi-camente válido si

(ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) |= ϕ,

es decir, si el conjunto Φ de las premisas o hipótesis del razonamientoimplica lógicamente a la conclusión o tesis ϕ.

Observación 4.4.6 Observar que, según la de�nición anterior, un razona-miento

((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) → ϕ)

es correcto si y sólo si es una tautología.

Ejemplos 4.4.7 1) El razonamiento (Modus ponens)pp → qq

es válido ya que p ∧ (p → q) → q es una tautología.2) Todas las implicaciones de la tabla (4.3) son razonamientos correctos.

4.5 Equivalencia de fórmulasEn este apartado vamos a estudiar el concepto de equivalencia lógica entrefórmulas. Veremos que la equivalencia de fórmulas es una relación binaria deequivalencia en el sentido de las de�niciones del capítulo (2). Por tanto, dosfórmulas equivalente pertenecen a una misma clase de equivalencia.

56

De�nición 4.5.1 Sean ϕ y ψ dos fórmulas proposicionales. Se dice que ϕequivale lógicamente a ψ si la fórmula proposicional (ϕ ↔ ψ) es unatautología. Si ϕ y ψ son equivalentes se escribe ϕ ≡ ψ.

Observación 4.5.2 Se sigue de la de�nición que si ϕ y ψ son dos fórmulasequivalentes, entonces tienen los mismos valores de verdad bajo unacualquier valoración.

ϕ ∧ > ≡ ϕ ϕ ∧ ⊥ ≡ ⊥ Leyes de Identidadϕ ∨ > ≡ > ϕ ∨ ⊥ ≡ ϕϕ ∧ ¬ϕ ≡ ⊥ No contradicciónϕ ∨ ¬ϕ ≡ > Tercio exclusoϕ ∧ ϕ ≡ ϕ ϕ ∨ ϕ ≡ ϕ Idempotenciaϕ1 ∧ (ϕ1 ∨ ϕ2) ≡ ϕ1 ϕ1 ∨ (ϕ1 ∧ ϕ2) ≡ ϕ1 Absorciónϕ1 ∧ ϕ2 ≡ ϕ2 ∧ ϕ1 ϕ1 ∨ ϕ2 ≡ ϕ2 ∨ ϕ1 Conmutatividad(ϕ1 ↔ ϕ2) ≡ (ϕ2 ↔ ϕ1)(ϕ1 ∧ ϕ2) ∧ ϕ3 ≡ ϕ1 ∧ (ϕ2 ∧ ϕ3) Asociatividad(ϕ1 ∨ ϕ2) ∨ ϕ3 ≡ ϕ1 ∨ (ϕ2 ∨ ϕ3)ϕ1 ∧ (ϕ2 ∨ ϕ3) ≡ (ϕ1 ∧ ϕ2) ∨ (ϕ1 ∧ ϕ3) Distributividadϕ1 ∨ (ϕ2 ∧ ϕ3) ≡ (ϕ1 ∨ ϕ2) ∧ (ϕ1 ∨ ϕ3)ϕ1 → (ϕ2 ∧ ϕ3) ≡ (ϕ1 → ϕ2) ∧ (ϕ1 → ϕ3)ϕ1 → (ϕ2 ∨ ϕ3) ≡ (ϕ1 → ϕ2) ∨ (ϕ1 → ϕ3)ϕ1 ↔ (ϕ2 ∧ ϕ3) ≡ (ϕ1 ↔ ϕ2) ∧ (ϕ1 ↔ ϕ3)ϕ1 ↔ (ϕ2 ∨ ϕ3) ≡ (ϕ1 ↔ ϕ2) ∨ (ϕ1 ↔ ϕ3)¬(¬ϕ) ≡ ϕ Doble negación(ϕ1 → ϕ2) ≡ (¬ϕ2 → ¬ϕ1) Ley de contraposición¬(ϕ1 ∧ ϕ2) ≡ ¬ϕ1 ∨ ¬ϕ2 Leyes de De Morgan¬(ϕ1 ∨ ϕ2) ≡ ¬ϕ1 ∧ ¬ϕ2

Tabla 4.4: Tabla de algunas equivalencias lógicas

Ejemplo 4.5.3 Vamos a veri�car la siguiente importante equivalencia lógi-ca, llamada interde�nición:

(p → q) ≡ (¬p ∨ q).

57

El único caso en el cual (p → q) es falsa es cuando p es verdadera y q esfalsa.El único caso en el cual (¬p ∨ q) es falsa es si ¬p es falsa y q es falsa.Esto es, el caso p verdadera y q falsa.Ya que las dos fórmulas toman los mismos valores de verdad bajo una cual-quier valoración, se sigue la equivalencia lógica de las dos fórmulas.

Observación 4.5.4 Recordamos que una relación binaria R sobre un con-junto no vacío A se dice de equivalencia si es:

Re�exiva: para todo elemento a del conjunto A, R(a, a) es verdadera,Simétrica: para todo par a y b de elementos de A,R(a, b) → R(b, a) es verdadera.Transitiva: para toda terna a, b y c de elementos de A,(R(a, b) ∧R(b, c)) → R(a, c) es verdadera.En el ejercicio (4.7.8) se pide demostrar que en el conjunto L de las

fórmulas bien construidas, la relación

ϕ ≡ ψ si y sólo si (ϕ ↔ ψ es una tautología)es una relación de equivalencia.

Ejemplo 4.5.5 La tabla (4.4) contiene una lista de las equivalencias lógicasmás utilizadas (ver ejercicio (4.7.9)).

4.6 Métodos de refutación. Tableaux4.6.1 RefutaciónLos métodos de demostración por refutación pertenecen a los sistemas dedemostración indirectos que, como ya comentamos, son más modernos quelos métodos de demostración axiomáticos y más adecuados para su automa-tización. Estos métodos nos proporcionan así una nueva forma de veri�carla validez de fórmulas y de razonamientos.

Un ejemplo de sistema de demostración por refutación es la teoría de lostableaux, que vamos a estudiar en las siguientes secciones.

El alumno estudiará el método de demostración por refutación llamadoresolución proposicional en la asignatura de Lógica Informática.

58

Vamos ahora a ver cómo se pueden emplear métodos indirectos para ve-ri�car la validez de una fórmula o de un razonamiento.

Procedimiento por reducción al absurdo de demostración de la va-lidez de una fórmula ϕ.

Si la existencia de un modelo de ¬ϕ implica una contradicción, entoncespodemos refutar ¬ϕ (¬ϕ es una contradicción) y a�rmar la validez de ϕ(ϕ es una tautología).

Ejemplo 4.6.1 Si queremos demostrar que la fórmula

ϕ : ¬(p ∧ (p ∨ q)) ∨ p

es una tautología, podemos usar una razonamiento por reducción al absurdo.Se trata de suponer que exista un modelo para ¬ϕ. Tal modelo es un con-traejemplo para ϕ y, por tanto, tiene que ser tal que ¬(p∧ (p∨ q)) y p seanfalsas. Pero p ∧ (p ∨ q) verdadera implica que p es verdadera. Así que ptendría que ser verdadera y falsa al mismo tiempo y esto es imposible.

Procedimiento por reducción al absurdo de demostración de la va-lidez de un razonamiento.

El siguiente teorema a�rma que Φ → ϕ es una tautología (una implica-ción lógica) si y sólo si no pueden ser simultáneamente verdaderas todas suspremisas y la negación de su conclusión:

Teorema 4.6.2 [HLR] Sean Φ = {ϕ1, ϕ2, . . . ϕn} un conjunto �nito de fór-mulas proposicionales y ϕ una fórmula. Entonces las siguientes son equiva-lentes:

• ((ϕ1 ∧ϕ2 ∧ · · · ∧ϕn) → ϕ) es una fórmula válida (una tautología, unrazonamiento válido).

• ((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) ∧ ¬(ϕ)) es una contradicción (Reducción alabsurdo).

59

Observación 4.6.3 Se puede notar que, por interde�nición, la fórmula

((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) → ϕ)

es equivalente a la fórmula

(¬(ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) ∨ ϕ).

Por tanto, su negación es equivalente a la fórmula

((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) ∧ ¬(ϕ)).

Ejemplo 4.6.4 Para veri�car que

p |= (q → p),

hace falta demostrar que la fórmula

(p → (q → p))

es una tautología.Aplicando el teorema (4.6.2) (el método de refutación), es su�ciente ve-

ri�car que la fórmulap ∧ ¬(q → p)

es insatisfacible (es una contradicción).Para toda valoración tal que ¬(q → p) es falsa, p∧¬(q → p) es falsa. Si

una valoración es tal que ¬(q → p) es verdadera, entonces (q → p) es falsa,es decir, tiene que ser q verdadera y p falsa. También en este caso nuestrafórmula p ∧ ¬(q → p) resultaría ser falsa. Se sigue que p ∧ ¬(q → p) noadmite ningún modelo y, por tanto, es insatisfacible.

4.6.2 De�nición de los tableauxComo veremos, los tableaux son métodos de naturaleza sintáctica, pero sesuelen presentar también por medio de una de�nición semántica.

Los tableaux semánticos se basan sobre el teorema (4.6.2) y son unprocedimiento sistemático para veri�car si una fórmula es insatisfacible.

60

Dada una implicación ϕ → ψ, su negación ϕ ∧ ¬ψ es insatisfacible si ysólo si ϕ → ψ es una implicación lógica.

Más en general, si una fórmula es insatisfacible, su negación es una tauto-logía y, por tanto, un tableau permite averiguar si una fórmula es lógicamenteválida.

Además, en muchos casos los tableaux son más e�cientes que las tablas deverdad (donde para n proposiciones atómicas tenemos 2n posibles valoracio-nes), proporcionan una teoría para programar herramientas de demostraciónautomática y tienen una extensión natural a la lógica de predicados, queestudiaremos en la segunda parte de estos apuntes.

Otra aplicaciones de la teoría de los tableaux semánticos son la clasi�ca-ción de fórmulas proposicionales (en satisfacibles, insatisfacibles, tautologíaso contingencias) y la obtención de sus formas normales conjuntivas o disyun-tivas.

Durante el estudio de los tableaux semánticos descubriremos que la ver-dadera naturaleza de las reglas que los de�nen es sintáctica y que, por tanto,la presentación semántica (y no sintáctica) de la teoría de los tableaux tienesu justi�cación en su mayor simplicidad y claridad.

La principales referencias utilizadas para la siguiente descripción de lateoría de tableaux son [HLR] y [MH].

Formas conjuntivas y disyuntivasAntes de poder de�nir la teoría de los tableaux semánticos, necesitamos pro-fundizar en el análisis semánticos de las fórmulas proposicionales.

En el ejercicio (4.7.11) se pide demostrar que toda fórmula proposicionales equivalente a otra donde intervienen sólo los conectivos ¬, ∧ y ∨.

Esta propiedad se suele expresar diciendo que el conjunto {¬,∧,∨} es unconjunto completo o adecuado de conectivos para la lógica proposicional.

El anterior resultado justi�ca las siguientes de�niciones, que nos permitenclasi�car más fácilmente las fórmulas proposicionales:

De�nición 4.6.5 (Fórmulas conjuntivas y disyuntivas)Si una fórmula proposicional α es equivalente a una conjunción de otras

dos fórmulas más sencillas, α ≡ α1 ∧ α2, diremos que es una fórmulaconjuntiva (de la categoría α).

61

Si una fórmula proposicional β es equivalente a una disyunción de otrasdos fórmulas más sencillas, β ≡ β1 ∨ β2, diremos que es una fórmula dis-yuntiva (de la categoría β).

Si una fórmula proposicional σ es del tipo ¬>, ¬⊥ o ¬¬ϕ diremos quees simpli�cable (de la categoría σ) y su forma simpli�cada es σ1, que esigual a ⊥, > o ϕ, respectivamente.

Las fórmulas conjuntivas, disyuntivas y simpli�cables se llaman fórmulasreducibles.

Usando las equivalencias lógicas estudiadas, podemos recoger en la tabla(4.5) todas las posibles fórmulas conjuntivas, disyuntivas y simpli�cables.

Fórmulas conjuntivas Fórmulas disyuntivasα α1 α2 β β1 β2

ϕ ∧ ψ ϕ ψ ϕ ∨ ψ ϕ ψ¬(ϕ ∨ ψ) ¬ϕ ¬ψ ¬(ϕ ∧ ψ) ¬ϕ ¬ψ¬(ϕ → ψ) ϕ ¬ψ ϕ → ψ ¬ϕ ψ

ϕ ↔ ψ ϕ → ψ ψ → ϕ ¬(ϕ ↔ ψ) ¬(ϕ → ψ) ¬(ψ → ϕ)

Fórmulas simpli�cablesσ σ1

¬> ⊥¬⊥ >¬¬ϕ ϕ

Tabla 4.5: Fórmulas reducibles

Usando árboles con raíz, podemos ahora representar las fórmulas reduci-bles de la tabla (4.5) por medio del esquema de la tabla (4.6).

Observación 4.6.6 El hecho de que toda fórmula proposicional es equiva-lente a otra donde intervienen sólo los conectivos ¬, ∧ y ∨ implica que todafórmula proposicional es equivalente a una fórmula conjuntiva, auna fórmula disyuntiva o es simpli�cable.

Ejemplo 4.6.7 Seaϕ → (ψ ↔ χ)

62

α • β • σ •| �� |

α1• β1• •β2 σ1•|

α2•

Tabla 4.6: Esquema de reducción de fórmulas

la fórmula proposicional que se quiere reducir. La regla de interde�nición nospermite reescribir nuestra fórmula de forma equivalente como una fórmuladisyuntiva

β ≡ ¬ϕ ∨ (ψ ↔ χ),

dondeβ1 : ¬ϕ y β2 : (ψ ↔ χ).

Tableaux semánticosDado un conjunto �nito de fórmulas proposicionales Φ, queremos asociara este conjunto un árbol con raíz que nos permita determinar fácilmentepropiedades semánticas del conjunto Φ. Este árbol será el tableau asociadoa Φ.

En el capítulo (3) introducimos el concepto de árbol con raíz y sus pro-piedades básicas. En este capítulo necesitamos ampliar un poco más la ter-minología ya introducida.

De�nición 4.6.8 1) Una rama de un árbol con raíz es un cualquier caminosimple que no pueda prolongarse a otro más largo.

2) Un árbol con raíz es binario si todos sus vértices no tienen más quedos hijos.

3) Un árbol de fórmulas T es cualquier árbol con raíz binario quetenga asociada a cada uno de sus vértices una fórmula proposicional (cadauno de sus vértice está etiquetado por una fórmula proposicional).

4) Una rama θ de un árbol de fórmulas T se dice cerrada si ⊥ apareceen θ, o si ambas fórmulas ϕ y ¬ϕ aparecen en θ.

5) Una rama θ de un árbol de fórmulas T se dice abierta si no escerrada.

63

Antes de de�nir formalmente el método de los tableaux, vamos a ver unejemplo de como se construye un tableau asociado a un razonamiento.

Ejemplo 4.6.9 (Ejemplo de construcción de un tableau asociado a un razo-namiento)

Consideramos el razonamiento:1) Si quiero comer fruta y hay una frutería cerca, entonces soy feliz.2) No soy feliz.3) Quiero comer fruta.Por tanto,4) No hay una frutería cerca.Sean p = quiero comer fruta, q = hay una frutería cerca y r = soy feliz.El razonamiento anterior será válido si

{p ∧ q → r,¬r, p} |= ¬q.

Ya que los tableaux usan el método de refutación, podemos a�rmar lavalidez del razonamiento anterior si demostramos que el conjunto de fórmulas

Φ = {p ∧ q → r,¬r, p,¬¬q}es insatisfacible.

Por eso, empezamos a construir un árbol de fórmulas T0 con la regla deinicialización que consiste en dibujar un primer árbol con una única ramacuyos vértices están etiquetados por las fórmulas de nuestro conjunto Φ. T0

es nuestro tableau inicial:

T0

• p ∧ q → r|• ¬r|• p|• ¬¬q

Ahora intentamos simpli�car las fórmulas anteriores usando el esquemade la tabla (4.6) y obtenemos un nuevo tableaux T1, que es una extensión delanterior. En T1, marcamos con el símbolo X las fórmulas que hemos reducidoy cerramos con el símbolo ] aquellas ramas que contienen un conjunto defórmulas insatisfacible:

64

T1

• p ∧ q → r X|• ¬r|• p|• ¬¬q��

¬(p ∨ q) • • r]

Hemos cerrado la rama derecha de T1 que contiene las fórmulas ¬r y r,ya que esto quiere decir que el conjunto de fórmulas {¬r, p,¬¬q, r} (todaslas que aparecen en esta rama, eliminando las que llevan el símbolo X) esinsatisfacible.

Ahora, usando su rama izquierda, podemos extender T1 a un nuevo árbolT2 :

T2

• p ∧ q → r X|• ¬r|• p|• ¬¬q��

¬(p ∨ q) X • • r| ]

¬p •|

¬q •]

Las dos ramas de este último árbol están cerradas ya que cada una deellas contiene una contradicción, la primera contiene el conjunto {p,¬p} yla segunda el conjunto {¬r, r}.

Por tanto el conjunto Φ es insatisfacible y nuestro razonamiento es vá-lido.

65

Podemos observar que el cálculo de la tabla de verdad para este ejem-plo requiere considerar 8 posibles valoraciones, mientras el tableau estudiadotiene 2 ramas.

Vamos entonces a de�nir los tableaux semánticos. Como veremos, estade�nición será, una vez más, una de�nición recursiva.

De�nición 4.6.10 Sea

Φ = {ϕ1, ϕ2, . . . , ϕn}

un conjunto �nito de fórmulas proposicionales.Un tableau T asociado al conjunto Φ es cualquier árbol de fórmulas

que pueda construirse en un número �nito de pasos mediante las reglas deformación que se de�nen a continuación.

Reglas de formación de un tableau:

• Regla de inicialización (Rini): el tableau inicial es un árbol defórmulas T0 con una única rama cuyos vértices están etiquetados porlas fórmulas del conjunto Φ.

• Regla de reducción (Rα): si una rama abierta θ de T incluye unvértice etiquetado por una fórmula conjuntiva α ≡ α1 ∧ α2, podemosextender T a un nuevo tableau T ′ (una extensión directa de T )prolongando θ de forma lineal, con dos nuevos vértices α1 y α2. Seañade a la fórmula conjuntiva el símbolo X.

Esta regla no se aplica si la rama abierta θ ya contiene α1 y α2.

• Regla de reducción (Rβ): si una rama abierta θ de T incluye unvértice etiquetado por una fórmula disyuntiva β ≡ β1 ∨ β2, podemosextender T a un nuevo tableau T ′ (una extensión directa de T )bifurcando θ con dos nuevos vértices β1 y β2, que sean hijos del vérticeβ. Se añade a la fórmula disyuntiva el símbolo X.

Esta regla no se aplica si la rama abierta θ ya contiene β1 y β2.Si θ contiene sólo una de las dos componentes, se puede suprimir labifurcación.

66

• Regla de reducción (Rσ): si una rama abierta θ de T incluye unvértice etiquetado por una fórmula simpli�cable σ ≡ σ1, podemosextender T a un nuevo tableau T ′ (una extensión directa de T )prolongando θ de forma lineal, con un nuevos vértice σ1. Se añade ala fórmula simpli�cable el símbolo X.

Esta regla no se aplica si la rama abierta θ ya contiene σ1.

• Regla de cierre (Rc): si una rama abierta θ, contiene ⊥ o ambasfórmulas ϕ y ¬ϕ aparecen en θ se cierra usando el símbolo ].

Las siguientes de�niciones permiten saber cuando no es posible extenderulteriormente un tableau.

De�nición 4.6.11 • Una rama θ, de tableau T está completa (ó sa-turada) si y sólo si se cumplen las tres siguientes condiciones:1) Si α ≡ α1 ∧ α2, pertenece a θ, entonces α1 y α2, pertenecen a θ.

2) Si β ≡ β1 ∨ β2, pertenece a θ, entonces β1 ó β2, pertenece a θ.

3) Si σ ≡ σ1, pertenece a θ, entonces σ1 pertenece a θ.

• Un tableau está cerrado si todas sus ramas lo están.

• Un tableau está acabado si todas sus ramas están cerradas o completas.

Observación 4.6.12 Dado un conjunto de fórmulas, el tableau asociado aesto conjunto no queda únicamente de�nido. Para intentar minimizar lacomplejidad del tableau que se obtiene, en general es conveniente reducirprimero fórmulas de tipo σ y α, o fórmulas que permitan cerrar ramas.Entre las restantes fórmulas, conviene reducir las más sencillas antes que lasmás complejas.

Las siguientes de�niciones y teoremas permiten interpretar un tableauacabado.

Si una rama θ de un tableau es completa y abierta, el conjunto de lasfórmulas que son sus etiquetas se dice conjunto de Hintikka. Es posibledemostrar (ver [HLR]) que todo conjunto de Hintikka es satisfacible.

67

De�nición 4.6.13 • Una rama θ de un tableau es satisfacible si ysólo si existe una valoración que satisface las fórmulas de θ.

• Un tableau T es satisfacible si y sólo si existe una valoración quesatisface las fórmulas de alguna de sus ramas.

Lema 4.6.14 (Lema de reducción) Si un tableau T ′ es extensión de unun tableau T, toda valoración que satisface T satisface también T ′.

Teorema 4.6.15 (Su�ciencia y adecuación) Un conjunto de fórmulasproposicionales Φ es insatisfacible si y sólo si se le puede asociar un tableauxcerrado TΦ.

Observación 4.6.16 Modi�cando la regla de iniciación y admitiendo la adi-ción de hipótesis, es posible de�nir el concepto de tableau asociado a un con-junto in�nito de fórmulas proposicionales. Su de�nición proporciona árbolescon un número �nito de vértices, ya que usan sólo un número �nito de lasfórmulas iniciales. Las consecuencia teóricas de la de�nición de tableaux pa-ra conjuntos in�nitos de fórmulas son profundas y están relacionadas con laspropiedades de corrección y completitud de los sistemas de demostración, quetrataremos brevemente.

4.6.3 Aplicaciones de los tableaux

Tableaux y razonamientosSea Φ → ϕ un razonamiento.

El teorema (4.6.15) asegura que el tableaux asociado a Φ∧¬ϕ es cerradosi y sólo si el razonamiento es válido.

Por el otro lado, si el tableaux asociado no es cerrado, contendrá unarama abierta θ que nos permite hallar un contraejemplo a la validez delrazonamiento (toda valoración que satisface θ es un contraejemplo).

Ejemplo 4.6.17 Consideremos el siguiente razonamiento:

p → (q ↔ ¬r)(q ∨ ¬r) → ¬p

(q ∧ r) ∨ pp ∧ q ∧ ¬r

68

Para veri�car su validez usando tableaux, tendremos que refutar la fór-mula que se obtiene como conjunción de todas las premisas con la negaciónde la conclusión.

Podemos simpli�car la construcción del tableaux asociado escribiendo to-das las fórmulas en forma conjuntivas o disyuntiva.

Usando equivalencias semánticas, obtenemos:

(¬p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ r ∨ q)(¬q ∧ r) ∨ ¬p

(q ∧ r) ∨ pp ∧ q ∧ ¬r

El tableau completo asociado es:

• (¬p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ r ∨ q)|• (¬q ∧ r) ∨ ¬p|• (q ∧ r) ∨ p|• ¬p ∨ ¬q ∨ r|• ¬p ∨ ¬q ∨ ¬r|• ¬p ∨ r ∨ q

��� �

• ¬q ∧ r ¬p •| ��• ¬q q ∧ r • • p| | ]• r q •

�� |q ∧ r • • p r •

|q •]

El tableaux completo obtenido tiene dos ramas cerradas y dos abierta. Estas

69

últimas nos proporcionan dos contraejemplos del razonamiento:

p : 1, r : 1, q : 0 y p : 0, r : 1, q : 1.

Tableaux y clasi�cación de fórmulas

Sea T (ϕ) el tableaux asociado a una fórmula ϕ.

• Si T (ϕ) es cerrado, ϕ es una contradicción (es insatisfacible).

• Si T (ϕ) tiene al menos una rama abierta, ϕ es satisfacible y tenemosque construir el tableaux T (¬ϕ) asociado a ¬ϕ :

� si T (¬ϕ) es cerrado, ϕ es una tautología,� si T (¬ϕ) tiene al menos una rama abierta, ϕ es una contingencia.

Ejemplo 4.6.18 Sea ϕ : p → (p ∧ q) la fórmula que se quiere clasi�car.ϕ es equivalente a las forma disyuntiva ¬p∨ (p∧ q) y el tableaux T (ϕ)

es• ¬p ∨ (p ∧ q)

T (ϕ) ��� �

¬p • • p ∧ q|• p|• q

Ya que hay dos ramas abiertas, ϕ es satisfacible (un modelo es, por ejemplo,q : 1, p : 1).

Ahora, ¬ϕ : ¬(¬p ∨ (p ∧ q))) es equivalente a las forma conjuntiva p ∧

70

(¬p ∨ ¬q) el tableaux T (¬ϕ) es

• p ∧ (¬p ∨ ¬q)T (¬ϕ) |

• p|• ¬p ∨ ¬q��

� �¬p • •¬q

]

Hay una rama abierta y, por tanto, ϕ es una contingencia (la valoraciónq : 0, p : 1 es un contraejemplo de ϕ).

Tableaux y formas normales disyuntivas y conjuntivasVamos ahora a ver como la teoría de los tableaux semánticos se puede aplicarpara hallar la forma normal disyuntiva y conjuntiva de una fórmula proposi-cional.

Representar un fórmula ϕ por medio de su formas normales disyuntivay conjuntiva permite aplicar nuevos métodos de refutación como el métodode resolución, que se estudiará en el contexto de la lógica de primer orden enla asignatura de Lógica Informática.

Siendo sus formas normales una nueva manera de expresar una fórmulapor medio de los conectivos del conjunto {¬,∧,∨}, no es sorprendente que,también en este caso, la teoría de los tableaux sea una herramienta de cálculoefectiva.

De�nición 4.6.19 (Formas normales disyuntivas y conjuntivas)

1. Un literal es cualquier fórmula de la forma p (literal positivo) o ¬p(literal negativo), donde p es una proposición atómica.

2. Una cláusula disyuntiva es cualquier disyunción de literales.

3. Una cláusula conjuntiva es cualquier conjunción de literales.

71

4. Una fórmula está en forma normal disyuntiva (FND) si es unadisyunción de cláusulas conjuntivas.

5. Una fórmula está en forma normal conjuntiva (FNC) si es unaconjunción de cláusulas disyuntivas.

Convenios:

• Un literal se puede considerar como una disyunción o una conjunción.

• ⊥ representa una disyunción, una cláusula disyuntiva o una FND vacía(siempre falsa).

• > representa una conjunción, una cláusula conjuntiva o una FNC vacía(siempre verdadera).

Teorema 4.6.20 ([HLR]) Sea ϕ una fórmula. A partir de las proposicionesatómicas de ϕ, se pueden siempre construir una forma normal disyuntiva,FND(ϕ), y una forma normal conjuntiva, FNC(ϕ), tales que

ϕ ≡ FND(ϕ) y ϕ ≡ FNC(ϕ).

Además, por las leyes de De Morgan y de la doble negación,

FNC(ϕ) ≡ ¬FND(¬ϕ).

Cálculo de las formas normales disyuntiva y conjuntiva mediantetableauxDado un tableau acabado T (ϕ), sean θ1, θ2, . . . , θn sus ramas abiertas.

Para todo i ∈ {1, 2, . . . , n}, sea Φi las fórmula obtenida como conjunciónde los literales de la rama θi.

Por el lema de reducción (4.6.14) se obtiene que

FND(ϕ) = Φ1 ∨ Φ2 ∨ Φ3 ∨ · · · ∨ Φn.

72

Observación 4.6.21 Las ramas cerradas de T (ϕ) contribuyen a FND(ϕ)por una disyunción con ⊥ y se pueden ignorar.

Si T (ϕ) está acabado, para determinar FND(ϕ) es su�ciente considerarsólo los literales que aparezcan en sus ramas abiertas, ya que todas las demásfórmulas ya han sido reducidas.

Aplicando las anteriores consideraciones y la equivalencia FNC(ϕ) ≡¬FND(¬ϕ), vamos a ver como T (ϕ) y T (¬ϕ) permiten calcular FND(ϕ)y FNC(ϕ).

Ejemplo 4.6.22 Sea ϕ : p → (p ∧ q) la fórmula clasi�cada en el ejemplo(4.6.18).

Ya comentamos que, usando equivalencias lógicas, se obtiene que

ϕ ≡ ¬p ∨ (p ∧ q) = FND(ϕ).

Mirando al tableaux acabado T (ϕ),

• ¬p ∨ (p ∧ q)T (ϕ) ��

� �¬p • • p ∧ q

|• p|• q

observamos que hay dos ramas abiertas con Φ1 = ¬p y Φ2 = p ∧ q. Portanto, en este caso,

FND(ϕ) = Φ1 ∨ Φ2.

También usamos equivalencias lógicas para a�rmar que

¬ϕ ≡ p ∧ (¬p ∨ ¬q) = ϕ.

73

Mirando al tableaux acabado T (¬ϕ),

• p ∧ (¬p ∨ ¬q)T (¬ϕ) |

• p|• ¬p ∨ ¬q��

� �¬p • •¬q

]

observamos que hay una sola rama abierta con Φ2 = p ∧ ¬q.Si no ignoramos la rama cerrada,

FND(¬ϕ) = (p ∧ ¬p) ∨ (p ∧ ¬q)

yFNC(ϕ) = ¬FND(¬ϕ) = ¬((p ∧ ¬p) ∨ (p ∧ ¬q)) ≡≡ ¬(p ∧ ¬p) ∧ ¬(p ∧ ¬q) ≡ (¬p ∨ p) ∧ (¬p ∨ q).

74

4.7 EjerciciosEjercicio 4.7.1 ¾Cuáles de las fórmulas del ejercicio (3.5.5) del capítulo 3son tautologías? ¾Cuáles son contradicciones?

Para aquellas que sean contingencias, calcula sus modelos y sus contrae-jemplos.

Ejercicio 4.7.2 Prueba que las siguientes fórmulas son tautologías:

ϕ ∨ ¬ϕ, ¬(ϕ ∧ ¬ϕ),(ϕ ∧ ψ) ↔ (ψ ∧ ϕ), (ϕ ∨ ψ) ↔ (ψ ∨ ϕ),ϕ ∧ (ψ ∧ χ) ↔ (ϕ ∧ ψ) ∧ χ, ϕ ∨ (ψ ∨ χ) ↔ (ϕ ∨ ψ) ∨ χϕ ∧ (ψ ∨ χ) ↔ (ϕ ∧ ψ) ∨ (ϕ ∧ χ), ϕ ∨ (ψ ∧ χ) ↔ (ϕ ∨ ψ) ∧ (ϕ ∨ χ),(ϕ ∨ ¬ϕ) ∧ ψ ↔ ψ, (ϕ ∨ ¬ϕ) ∨ ψ ↔ (ϕ ∨ ¬ϕ),(ϕ ∧ ¬ϕ) ∨ ψ ↔ ψ, (ϕ ∧ ¬ϕ) ∧ ψ ↔ (ϕ ∧ ¬ϕ),¬(ϕ ∨ ψ) ↔ ¬ϕ ∧ ¬ψ, ¬(ϕ ∧ ψ) ↔ ¬ϕ ∨ ¬ψ.

Ejercicio 4.7.3 Sea ϕ una fórmula proposicional. Determina cuáles de lassiguientes a�rmaciones son verdaderas y justi�ca tus respuestas.

a) Si ϕ es insatisfacible, ¬(ϕ ) es una tautología.b) Si ϕ es una tautología, ¬(ϕ ) es insatisfacible.c) Si ϕ es una contingencia, ¬(ϕ ) es una contingencia.d) Si ϕ es satisfacible, ¬(ϕ ) es satisfacible.e) Si ϕ es satisfacible, ¬(ϕ ) no es una tautología.

Ejercicio 4.7.4 Veri�ca las implicaciones lógicas de la tabla (4.3).

Ejercicio 4.7.5 ¾Son validas las siguientes deducciones?

p → ¬rq → r¬(p ∧ q)

,

(q ∨ ¬s) → r¬q → rp → ¬sr → sp → r

,

p → ((q → r) → s)(q → r) → (p → s)

,(q → r) → (p → s)p → ((q → r) → s)

,

p → qq → rs ∨ pr ∨ t

.

75

Ejercicio 4.7.6 Peláez, Quesada y Rodríguez son tres políticos acusados decorrupción. En el juicio ellos declaran:

Peláez: �Quesada es culpable y Rodríguez es inocente.�

Quesada: �Peláez es culpable sólo si Rodríguez es también culpable.�

Rodríguez: �Yo soy inocente, pero al menos uno de los otros es cul-pable.�

Si todos son inocentes, ¾quién ha mentido?Si todos dicen la verdad, ¾quién es inocente?Si los inocentes dicen la verdad y los culpables mienten, ¾quién es inocen-

te?

Ejercicio 4.7.7 Determina si la deducciones de los ejercicios (3.5.11), (3.5.12)y (3.5.13) del capítulo 3 son válidas.

Ejercicio 4.7.8 (La equivalencia de fórmulas es una relación de equivalen-cia) Demuestra que en el conjunto L de las fórmulas bien construidas, larelación

ϕ ≡ ψ si y sólo si (ϕ ↔ ψ es una tautología)es una relación de equivalencia.

Ejercicio 4.7.9 Veri�ca las equivalencias lógicas de la tabla (4.4).

Ejercicio 4.7.10 Elegir de las a�rmaciones siguientes aquella que sea equi-valente a �No es cierto que sea su�ciente trabajar para ser feliz.�

1. No trabajar es su�ciente para no ser feliz.

2. Para ser feliz es necesario trabajar.

3. No es posible trabajar y no ser feliz al mismo tiempo.

4. Se puede trabajar y no ser feliz.

5. Se trabaja o no se es feliz.

76

Ejercicio 4.7.11 Dadas las fórmulas

p → q, (q ∨ ¬s) → r, p ↔ q, (p ∨ r) → (p ∧ ¬r), (r → p) → (r → q),

encuentra otras equivalentes en las que se usen sólo los conectivos ¬,∧,∨.Deduce que toda fórmula bien construida es equivalente a otra donde inter-vienen sólo los conectivos ¬,∧,∨.

Ejercicio 4.7.12 Encuentra una fórmula equivalente a p ∨ q en la que sólointervengan los conectivos ∧,¬. Deduce que toda fórmula bien construida esequivalente a otra donde intervienen sólo los conectivos ¬,∧.

Ejercicio 4.7.13 Estudia, mediante tableaux, la validez de los argumentos:{(p ∨ ¬q) → r, ¬p → t, s → ¬q, r → q} |= s → t

{t → (s → p), p → ¬p, (r → t) ∧ (q → s)} |= r → ¬q

{s ∨ t, q → p, t → ¬p, ¬s} |= ¬q

Ejercicio 4.7.14 Formaliza el siguiente razonamiento y estudia su validezusando tableaux.

Si el barco entra en el puerto, habrá una gran �esta. El barco entra en elpuerto sólo si necesita repostar combustible. El barco no necesita combustiblea menos que venga de muy lejos. Es imposible que no necesite combustiblesi la comida ya se les ha terminado. Sabemos que, o bien se le ha terminadola comida, o bien necesita combustible. Por tanto: habrá una gran �esta.

Ejercicio 4.7.15 Usando tableaux, clasi�ca las fórmulas:

1. ¬s ∨ ¬p → (t → (p ∨ ¬s))

2. (p → q) → (q → p)

3. (t → (p ∧ s)) ∧ (¬s → p ∧ ¬t)

4. (¬(¬(¬p ∨ r) ∨ q)) → (¬(p ∧ q) ∨ r)

Ejercicio 4.7.16 Con el método de los tableaux, escribe las fórmulas delejercicio anterior en su formas normal disyuntiva y conjuntiva.

Capítulo 5

Teoría de la demostración

En el capítulo anterior estudiamos el método indirecto de refutación (y los ta-bleaux semánticos) y el método directo de la tablas de verdad como métodossemánticos para veri�car la validez de fórmulas y deducciones. Sin embargo,si el número de proposiciones atómicas es elevado las tablas de verdad no sonun método e�ciente (para un signatura con n fórmulas atómicas, tenemosque construir una tablas de 2n �las).

La teoría de la demostración o teoría de pruebas nos proporcionamétodos alternativos a las tablas de verdad para averiguar

• la validez de una fórmula proposicional: si ϕ es una fórmulaválida se dice que es demostrable y se escribe ` ϕ.

• si una fórmula ϕ es consecuencia lógica de un conjunto depremisas Φ : si ϕ es consecuencia lógica de Φ se dice que ϕ esdeducible en el sistema a partir de Φ y se escribe Φ ` ϕ.

El objetivo principal de cualquier teoría de pruebas es demostrar la va-lidez de fórmulas, independientemente del contexto particular que se esténconsiderando: la demostración de la validez de una fórmula o de una deduc-ción en un sistema de demostración no se desarrolla teniendo en cuenta todaslas posibles valoraciones, se obtiene utilizando una secuencia �nita de pasosy, en cada uno de ellos, se aplican las reglas de inferencia del sistema.

Ya comentamos que los sistemas de demostración se suelen dividir endos clases: sistemas directos y sistemas indirectos (o por refutación).Los primeros aplican una cadena �nita de reglas de inferencia hasta llegar

77

78

a la fórmula que se quiere demostrar. Los segundos aplican la técnica dereducción al absurdo.

Siendo sistemas clásicos, los sistemas de demostración directos tieneninterés histórico y además son los más naturales ya que son los más cercanosa la forma de razonamiento habitual.

Los sistemas directos son adaptables a lógicas no clásicas, pero son dedifícil automatización.

Lo sistemas de demostración indirectos son más modernos y adecuadospara su automatización, pero no son aplicables a lógicas distintas de laslógicas clásicas.

En este capítulo estudiaremos un particular sistema de demostración axio-mático, el sistema de deducción natural de Gentzen.

El método de los tableaux semánticos que estudiamos en la teoría inter-pretativa tiene, en realidad, una estructura completamente sintáctica y, portanto, se puede considerar un ejemplo de sistemas de demostración axiomá-tico indirecto.

Como veremos, es posible demostrar que estos sistemas axiomáticos sonequivalentes a la teoría interpretativa. Es decir, se puede veri�car que unafórmula proposicional es una tautología en la teoría interpretativa si y sólo sies una fórmula válida en la teoría de la demostración que vamos a estudiar.

5.1 De�nición de sistema formal axiomáticoDe�nición 5.1.1 Un sistema de demostración formal S o sistema depruebas se de�ne matemáticamente mediante los siguientes cuatro elemen-tos:

A es el alfabeto del sistema: el conjunto de símbolos que se pueden uti-lizar,

F es el conjunto de reglas de sintaxis: las reglas que permiten de�nirlas fórmulas bien construidas,

X es el conjunto de axiomas: fórmulas válidas por de�nición,

R es el conjunto de reglas de inferencias: reglas de transformación quepermiten �inferir� una fórmula, la conclusión, a partir de un conjuntode fórmulas, las condiciones o premisas.

79

Un sistema de demostración S se puede representar en forma compacta como

S = (A,F, X, R).

De�nición 5.1.2 (De�nición recursiva de teorema) Un teorema es unafórmula válida (demostrable) y tiene la siguiente de�nición recursiva:una fórmula bien construida ϕ es un teorema si es un axioma o si se obtienecomo conclusión de la aplicación de un conjunto de reglas de inferencias aotros teoremas.

Si ϕ es un teorema (es válida), se escribe ` ϕ.

Ejemplo 5.1.3 En el contexto de las implicaciones lógicas (semánticas), es-tudiamos la validez de la ley de contraposición de la tabla (4.3):

(p → q) |= (¬q → ¬p).

Dicimos también que la fórmula

(p → q) → (¬q → ¬p)

es una tautología.Si somos capaces de demostrar que la ley de contraposición es válida en elsistema axiomático que estamos usando, podemos escribir la misma ley decontraposición en forma de teorema, usando la notación:

` (p → q) → (¬q → ¬p).

Sólo como caso particular, consideremos las dos proposiciones p=�comodemasiado� y q=�me duele el estómago.�

La teoría interpretativa, en este caso, nos dice que la proposición �si nome duele el estómago entonces no he comido demasiado,� (¬q → ¬p), esconsecuencia lógica (vimos que en realidad es equivalente) de la proposición�si como demasiado me duele el estómago,� (p → q).

En una teoría de pruebas la validez de la ley de contraposición se expresa-ría, en nuestro ejemplo particular, como la validez de la fórmula bien cons-truida �si como demasiado me duele el estómago implica que si no me dueleel estómago entonces no he comido demasiado,� ` (p → q) → (¬q → ¬p).

De�nición 5.1.4 Una deducción o razonamiento consiste de un con-junto de fórmulas Φ = {ϕ1, ϕ2, . . . ϕn}, llamadas las premisas, y de unafórmula ϕ, llamada la conclusión de la deducción.

80

Ejemplo 5.1.5 Escrita como deducción, la ley de contraposición tiene unasola premisa Φ = {(p → q)} y conclusión (¬q → ¬p).

Las nociones de demostración de un teorema y de una deducción estánestablecidas por las siguientes de�niciones:

De�nición 5.1.6 (Demostración de fórmulas (de teoremas)) Una de-mostración de un teorema ` ϕ es una sucesión �nita de fórmulas

{ϕ1, ϕ2, . . . , ϕn, ϕn+1 = ϕ}tal que:

1. Cada fórmula de la sucesión es

• un axioma, un teorema ya demostrado o• un teorema obtenido a partir de las fórmulas anteriores de la su-cesión aplicando un conjunto de reglas de inferencias.

2. El último elemento de la sucesión es la fórmula ϕ.

Si {ϕ1, ϕ2, . . . , ϕn, ϕn+1 = ϕ} es una demostración de un teorema, se diceque ϕ es válida (demostrable) y se escribe ` ϕ .

De�nición 5.1.7 (Demostración de deducciones) Sean Φ = {ϕ1, ϕ2, . . . ϕn}un conjunto �nito de fórmulas proposicionales y ϕ una fórmula.

Una demostración de una deducción con conjunto de premisas Φ y con-clusión ϕ es una sucesión �nita de fórmulas

{ϕ1, ϕ2, . . . ϕn, ϕn+1, . . . , ϕn+m−1, ϕn+m = ϕ}tal que:

1. Cada fórmula de la sucesión es

• una premisa (un elemento de Φ = {ϕ1, ϕ2, . . . , ϕn}) o• un axioma, un teorema ya demostrado o• un teorema obtenido a partir de las fórmulas anteriores en la su-cesión aplicando un conjunto de reglas de inferencias.

2. El último elemento de la sucesión es la fórmula ϕ.

81

Si {ϕ1, ϕ2, . . . ϕn, ϕn+1, . . . ϕn+m−1, ϕn+m = ϕ} es una demostración de unadeducción, se dice que la conclusión ϕ es consecuencia lógica (deduci-ble) del conjunto de las premisas Φ y se escribe Φ ` ϕ.

Observación 5.1.8 Podemos observar que la demostración de un teoremaes la demostración de una deducción cuyo conjunto de premisas es vacío.

El siguiente teorema es un resultado fundamental ya que permite de�niruna relación entre demostraciones de teoremas y demostraciones de deduc-ciones. No presentamos aquí su demostración (ver, por ejemplo, el párrafo2.3 de [C] o el párrafo 3.1.1 de [A]).

Teorema 5.1.9 (Teorema de la deducción) Sean {ϕ1, ϕ2, . . . ϕn} unconjunto de fórmulas y ϕ una fórmula. Entonces

{ϕ1, ϕ2, . . . ϕn} ` ϕ si y sólo si {ϕ1, ϕ2, . . . ϕn−1} ` (ϕn → ϕ).

El siguiente corolario del teorema de la deducción establece la relaciónbuscada entre demostraciones de deducciones y de teoremas.

Corolario 5.1.10 Dada una demostración de una deducción, es siempre po-sible encontrar una fórmula válida que la represente.

Demostración [C]: Si {ϕ1, ϕ2, . . . ϕn} ` ϕ es la demostración de una de-ducción, se aplica el teorema de la deducción sucesivamente hasta que elconjunto de premisas sea vacío. Se obtiene así la siguiente cadena de fórmu-las que tiene como último elemento un teorema:

{ϕ1, ϕ2, . . . ϕn} ` ϕ{ϕ1, ϕ2, . . . ϕn−1} ` ϕn → ϕ{ϕ1, ϕ2, . . . ϕn−2} ` ϕn−1 → (ϕn → ϕ)...` ϕ1 → (ϕ2 → (· · · → (ϕn → ϕ) . . . ).

82

Ejemplo 5.1.11 El teorema de la deducción implica que, en un sistema depruebas, demostrar la validez de la ley de contraposición

` (p → q) → (¬q → ¬p)

es equivalente a demostrar la deducción

{p → q} ` ¬q → ¬p

o, también, la deducción

{p → q,¬q} ` ¬p.

En el caso de nuestro ejemplo particular con p= �como demasiado� yq= �me duele el estómago�, la última deducción se lee �si como demasiadome duele el estómago y si no me duele el estómago, entonces no he comidodemasiado.�

5.1.1 Subdeducciones y notación de FittingAntes de de�nir formalmente el sistema de deducción natural de Gentzen,necesitamos extender la de�nición de demostración de deducción dada, la(5.1.7), para poder admitir la introducción de subdeducciones. Informal-mente se puede decir que, en el proceso de demostración de una deducción(la demostración madre), una subdeducción es la derivación de una conclu-sión ψ a partir de una premisa auxiliar (o hipótesis) ϕ. Después de obtenerla conclusión buscada en la subdeducción, se remueve la subdeducción de lademostración madre y se sustituye por el resultado ϕ ` ψ.

Para representar subdeducciónes usaremos la notación de Fitting [F]. Es-ta notación emplea rectángulos, llamados cajas. La primera �la de una cajaestá ocupada por la premisa auxiliar ϕ, mientras en la última �la se encuen-tra la conclusión ψ.

El siguiente es un ejemplo de un esquema de una deducción que contienea una subdeducción:

83

1) ϕ1 (Premisa)2) ϕ2 (Premisa)3) ` ϕ3 (R1(1): regla R1 aplicada a ϕ1)

4) ψ1 (Premisa auxiliar)5) ` ψ2 (R2(2,1): regla R2 aplicada a ϕ2 y ψ1)6) ` ψ3 (R3(5): regla R3 aplicada a ψ2)

7) ` ϕ4 (R4(4,6): regla R4 aplicada a la subdeducción)

La notación usada en el último paso de la demostración madre, R4(4, 6),quiere decir que la regla R4 se aplica a toda la subdeducción. Se citan sólola premisa auxiliar y la conclusión de ella.

Pronto veremos algunos ejemplos, pero hay que notar que una subdeduc-ción puede contener a su vez una subdeducción. Por tanto, en la representa-ción de Fitting pueden aparecer varios rectángulos encajados.

5.2 El sistema de deducción natural de Gent-zen

El sistema de demostración natural de Gerald Gentzen (1934) es el sistemaque mejor modela el razonamiento informal o intuitivo.

Este sistema se basa en deducciones y tiene ocho reglas de inferencia yningún axioma. Las reglas de inferencia son dos para cada conectivo lógicodel alfabeto (una de introducción y otra de eliminación).

El uso exclusivo de deducciones presupone razonamientos que siempredependen de unas premisas iniciales, no necesariamente válidas. Se podríadecir que el sistema de Gentzen simula el razonamiento coherente más queel razonamiento válido.

84

5.2.1 De�nición del sistema de deducción natural deGentzen

De�nición 5.2.1 El sistema de deducción natural de Gentzen es el sistemade demostración axiomático

G = (A,F,X,R),

donde

A : el alfabeto está compuesto por

� los símbolos p, q, r, s, t, . . . de proposiciones atómicas,� los símbolos de conectivos ¬,∧,∨,→,

� los símbolos de paréntesis ( , ) .

F : el conjunto de las fórmulas bien construidas (fbc) se de�ne recursiva-mente como

At : toda proposición atómica es una fbc,¬ : Si ϕ es una fbc entonces ¬ϕ es una fbc,◦ : si ϕ y ψ son dos fbc, entonces

ϕ ∧ ψ, ϕ ∨ ψ, ϕ → ψ, ψ → ϕ

son fbc.

Toda fbc se obtiene mediante las tres reglas anteriores.

NOTA: En lo que se sigue usaremos también el conectivo de coim-plicación entre dos fórmulas, ϕ ↔ ψ. Este conectivo se entenderácomo una forma abreviada de representar la fórmula bien construida(ϕ → ψ) ∧ (ψ → ϕ).

X : el conjunto de los axiomas es vacío.

R : el conjunto R de las reglas de inferencia está compuesto por las reglasde introducción y de eliminación que se describen a continuación.

85

Reglas del sistema de Gentzen:

(I ∧): Regla de introducción de la conjunción

{ϕ, ψ} ` ϕ ∧ ψ

De dos fórmulas se deduce su conjunción.

(E ∧): Regla de eliminación de la conjunción

ϕ ∧ ψ ` ϕ (eliminación derecha)ϕ ∧ ψ ` ψ (eliminación izquierda)

De una conjunción de dos fórmulas se deducen las dos fórmulas.

Ejemplo 5.2.2 [UNED1] Usando sólo las dos reglas anteriores pode-mos demostrar que

p ∧ (q ∧ r) ` p ∧ r.

1) ϕ1 : p ∧ (q ∧ r) (Premisa)2) ` ϕ2 : ` p (E ∧(1))3) ` ϕ3 : ` q ∧ r (E ∧(1))4) ` ϕ4 : ` r (E ∧(3))5) ` ϕ5 : ` p ∧ r (I ∧(2,4))

(I ∨): Regla de introducción de la disyunción

ϕ ` (ϕ ∨ ψ) (introducción derecha)ψ ` (ϕ ∨ ψ) (introducción izquierda)

La disyunción de dos fórmulas se puede deducir de cada una de ellas.

(E ∨): Regla de eliminación de la disyunciónNOTA: la regla de eliminación de la disyunción NO es

ϕ ∨ ψ ` ϕϕ ∨ ψ ` ψ,

86

ya que de la validez de una disyunción de dos fórmulas no se puedededucir la validez de las dos fórmulas. Sólo sabemos que al menos unade las dos es válida, sin saber cuál es.

La regla de eliminación de la disyunción es

(E ∨) : {ϕ ∨ ψ, ϕ → χ, ψ → χ} ` χ.

Esta regla se usa en el método de demostración por casos, que seaplica cuando se quiere demostrar una deducción del tipo ϕ ∨ ψ ` χ :

1) se introducen las premisas auxiliares ϕ y ψ,

2) usando las dos premisas auxiliares se intentan demostrar dos subde-ducciones independientes con igual conclusión χ, es decir, las subde-ducciones

ϕ ` χ y ψ ` χ,

3) si se ha completado el paso anterior, se usan las subdeduccionesobtenidas en la deducción madre y se obtiene que

{ϕ ∨ ψ, ϕ → χ, ψ → χ} ` χ.

Con la notación de Fitting (E ∨) se representa como:

ϕ ∨ ψ (Premisa)

ϕ (Premisa auxiliar)......` χ

ψ (Premisa auxiliar)......` χ

` χ

87

Ejemplo 5.2.3 [UNED1] Si queremos demostrar la propiedad distri-butiva de la conjunción

p ∧ (q ∨ r) ` (p ∧ q) ∨ (p ∧ r)

podemos usar el siguiente esquema:1) p ∧ (q ∨ r) (Premisa)2) ` p (E ∧(1))3) ` q ∨ r (E ∧(1))

4) q (Premisa auxiliar)5) ` p ∧ q (I ∧(2, 4))6) ` (p ∧ q) ∨ (p ∧ r) (I ∨(5))

r (Premisa auxiliar)` p ∧ r (I ∧(2, 4))` (p ∧ q) ∨ (p ∧ r) (I ∨(5))

7) ` (p ∧ q) ∨ (p ∧ r) (E ∨(3, (4, 5)))

(I ¬): Regla de introducción de la negación

(I¬) : {ϕ → ψ, ϕ → ¬ψ} ` ¬ϕ.

Esta regla se usa en demostraciones por reducción al absurdo dela validez de una fórmula ¬ϕ :

1) Tomamos como premisa auxiliar la fórmula ϕ,

2) Si de esta premisa auxiliar podemos deducir la validez de una con-tradicción ψ ∧ ¬ψ, entonces podemos a�rmar la validez de ¬ϕ.

Con la notación de Fitting (I ¬) se representa como:

ϕ (Premisa auxiliar)......` ψ ∧ ¬ψ

` ¬ϕ

88

Usaremos esta regla en el ejemplos (5.2.4)

(E ¬): Regla de eliminación de la doble negación

(E¬) : ¬¬ϕ ` ϕ.

(I →): Regla de introducción de la implicaciónPara de�nir esta regla1) se toma una premisa auxiliar ϕ,

2) si se demuestra que de ϕ se deduce una fórmula ψ, entonces se hademostrado la validez de ϕ → ψ.

Con la notación de Fitting (I →) se representa como:

ϕ (Premisa auxiliar)......` ψ

` ϕ → ψ

Esta última regla es una versión del teorema de la deducción (5.1.9).Usaremos esta regla en el ejemplos (5.2.4)

(E →): Regla de eliminación de la implicación (también Modus Ponens):

(E →) : {ϕ, ϕ → ψ} ` ψ.

Usaremos esta regla en el ejemplos (5.2.4)El sistema de Gentzen está ahora completamente de�nido.

89

Ejemplos 5.2.4 1) Si queremos demostrar la contraposición

{ϕ → ψ,¬ψ} ` ¬ϕ,

podemos escribir el siguiente esquema:

1) ϕ → ψ (Premisa)2) ¬ψ (Premisa)

3) ¬¬ϕ (Premisa auxiliar)4) ` ϕ (E ¬(3))5) ` ψ (E →(3,1))6) ` ψ ∧ ¬ψ (I ∧(4,2))

7) ` ¬ϕ (I ¬(3,5))

2) La validez de la fórmula

ϕ ` ψ → ϕ

se puede demostrar en el sistema de deducción natural usando la intro-ducción de la implicación, según el esquema:

1) ϕ (Premisa)

2) ψ (Premisa auxiliar)3) ` ϕ (1)

4) ` ψ → ϕ (I → (2,3))

3) La validez de la fórmula

{ϕ → ψ, ϕ → (ψ → χ)} ` ϕ → χ

se puede demostrar en el sistema de deducción natural usando la intro-ducción de la implicación, según el esquema:

90

1) ϕ → ψ (Premisa)2) ϕ → (ψ → χ) (Premisa)

3) ϕ (Premisa auxiliar)4) ` ψ (E → (3,1))5) ` ψ → χ (E → (3,2))6) ` χ (E → (4,5))

7) ` ϕ → χ (I → (3,6))

5.2.2 Reglas derivadas del sistema de GentzenA partir de la de�nición del sistema de Gentzen es posible demostrar losresultados más interesantes de la lógica proposicional. Vamos a enunciar unalarga lista de ellos para poder mirar a varios ejemplos de demostración yaprender como aplicar estas nuevas reglas.

Presentaremos sólo algunas de las demostraciones de estas deducciones,las demás se pueden encontrar en la bibliografía de estos apuntes.

• T1: Teorema de la identidad

ϕ ` ϕ

De toda fórmula se deduce ella misma.Esta deducción se puede demostrar por reducción al absurdo:

1) ϕ (Premisa)

2) ¬ϕ (Premisa auxiliar)3) ` ϕ ∧ ¬ϕ (I ∧ (1,2))

4) ` ϕ (I ¬ (2,3))

91

• T2: Regla del silogismo

{ϕ → ψ, ψ → χ} ` ϕ → χ

De dos implicaciones (ϕ → ψ y ψ → χ) tales que la conclusión dela primera es la premisa de la segunda se deduce la implicación de lapremisa de la primera fórmula a la conclusión de la segunda.Este teorema se puede pensar como una propiedad transitiva: de �todoslos hombres son animales� y �todos los animales son mortales� se deduceque �todos los hombres son mortales.�

• T3: Modus ponens, MP

{ϕ, ϕ → ψ} ` ψ

Es la regla de eliminación de la implicación: de una implicación y desu premisa se deduce su conclusión.Por ejemplo, de �Juan es un hombre� y �si Juan es un hombre entonceses mortal� se deduce que �Juan es mortal.�

• T4: Excontradictione Quodlibet

{ϕ, ¬ϕ} ` ψ

De una fórmula y de su negación se deduce cualquier fórmula (porreducción al absurdo).De �Juan es un hombre� y �Juan no es un hombre� se deduce que �lapared es blanca.�

• T5: Producto condicional

{ϕ → ψ, ϕ → χ} ` ϕ → ψ ∧ χ

De dos implicaciones con la misma premisa se deduce la implicación deesa premisa a la conjunción de sus conclusiones.Por ejemplo, de �si x es par, es divisible por dos� y �si x es par, no esimpar� se deduce que �si x es par, entonces x es divisible por dos y noes impar.�

92

• T6: Contraposición

T6.1) ϕ → ψ ` ¬ψ → ¬ϕ

T6.2) ϕ → ¬ψ ` ψ → ¬ϕ

T6.3) ¬ϕ → ψ ` ¬ψ → ϕ

De una implicación se deduce su contrapositiva (ver ejemplo (5.2.4)).Por ejemplo,T6.1) de �llevo paraguas sólo si llueve� se deduce que �si no llueve nollevo paraguas,�T6.2) de �llevo paraguas sólo si no hace sol� se deduce que �si hace solno llevo paraguas.�T6.3) de �no llevo paraguas sólo si hace sol� se deduce que �si no hacesol llevo paraguas.�

• T7: Interde�nición 1

T7.1) ϕ → ψ ` ¬(ϕ ∧ ¬ψ)

De una implicación se deduce la negación de la conjunción de su premisacon la negación de su conclusión.

T7.2) ¬(ϕ ∧ ¬ψ) ` ϕ → ψ

Es el recíproco del anterior: una implicación se deduce de la negaciónde la conjunción de su premisa con la negación de su conclusión.Por ejemplo,T7.1) de �llevo paraguas sólo si llueve� se deduce que �no es posible quelleve paraguas y no llueva,�T7.2) de �no es posible que lleve paraguas y no llueva� se deduce que�llevo paraguas sólo si llueve.�

• T8: Leyes de de Morgan

T8.1) ¬(ϕ ∨ ψ) ` ¬ϕ ∧ ¬ψ

93

De la negación de la disyunción de dos fórmulas se deduce la conjunciónde las negaciones de las mismas.

T8.2) ¬ϕ ∧ ¬ψ ` ¬(ϕ ∨ ψ)

Es la recíproca del anterior: de la conjunción de las negaciones de dosfórmulas se deduce la negación de la disyunción de las mismas.Por ejemplo,T8.1) de �no es posible que x sea un elemento de A o sea un elementode B� se deduce que �x no es elemento de A y x no es elemento de B,�T8.2) de �x no es elemento de A y x no es elemento de B� se deduceque �no es posible que x sea un elemento de A o sea un elemento de B.�

T8.3) ¬(ϕ ∧ ψ) ` ¬ϕ ∨ ¬ψ

De la negación de la conjunción de dos fórmulas se deduce la disyunciónde las negaciones de las mismas.

T8.4) ¬ϕ ∨ ¬ψ ` ¬(ϕ ∧ ψ)

Es la recíproca del anterior: de la disyunción de las negaciones de dosfórmulas se deduce la negación de la conjunción de las mismas.Por ejemplo,T8.3) de �no es posible que x sea un elemento de A y de B� se deduceque �x no es elemento de A o x no es elemento de B,�T8.4) de �x no es elemento de A o x no es elemento de B� se deduceque �no es posible que x sea un elemento de A y de B.�

• T9: Interde�nición 2

T9.1) ϕ → ψ ` ¬ϕ ∨ ψ

De una implicación se deduce la disyunción de la negación de su premisacon su conclusión.

T9.2) ¬ϕ ∨ ψ ` ϕ → ψ

Es la recíproca de la anterior: una implicación se deduce de la disyun-ción de la negación de su premisa con su conclusión.

94

Por ejemplo,T9.1) de �una función derivable es continua� se deduce que �una funciónno es derivable o es continua,�T9.2) de �una función no es derivable o es continua� se deduce que �unafunción derivable es continua.�

Ejemplo 5.2.5 Para veri�car que la fórmula

ϕ : p → (q → p),

del ejemplo (4.6.4) es válida en el sistema de Gentzen podemos usar laregla (I¬) de reducción al absurdo. Tendremos que demostrar que lafórmula ¬ϕ conduce a una contradicción.En la notación de Fitting:

1) ¬(p → (q → p)) (Premisa auxiliar)2) ` ¬(¬p ∨ (q → p)) (Interde�nición 2(1) y Contraposición (1))3) ` ¬¬p ∧ ¬(q → p) (Ley de de Morgan T8.1(2))4) ` ¬¬p (E ∧(3))5) ` ¬(q → p) (E ∧(3))6) ` p (E ¬(4))7) ` ¬(¬q ∨ p) (Interde�nición 2(5) y Contraposición (5))8) ` ¬¬q ∧ ¬p (Ley de de Morgan T8.3(7))9) ` ¬p (E ∧(8))10) ` p ∧ ¬p (I ∧(6,9))

11) ` p → (q → p) (I ¬(1,10))

Teoremas del conectivo conjunción• T10: Propiedad conmutativa

T10.1) ϕ ∧ ψ ` ψ ∧ ϕ

T10.2) ψ ∧ ϕ ` ϕ ∧ ψ

95

• T11: Propiedad asociativa

T11.1) ϕ ∧ (ψ ∧ χ) ` (ϕ ∧ ψ) ∧ χ

T11.2) (ϕ ∧ ψ) ∧ χ ` ϕ ∧ (ψ ∧ χ)

• T12: Propiedad distributiva

T12.1) ϕ ∧ (ψ ∨ χ) ` (ϕ ∧ ψ) ∨ (ϕ ∧ χ)

T12.2) (ϕ ∧ ψ) ∨ (ϕ ∧ χ) ` ϕ ∧ (ψ ∨ χ)

• T13: Propiedad de absorción

T13.1) ϕ ∧ (ϕ ∨ ψ) ` ϕ

De la conjunción de una fórmula ϕ con su disyunción con cualquierotra fórmula se deduce ϕ.

T13.2) ϕ ` ϕ ∧ (ϕ ∨ ψ)

Es la recíproca del anterior: de una fórmula ϕ se deduce la conjunciónde ella con su disyunción con cualquier otra fórmula.Por ejemplo,T13.1) de �x es un elemento de A y x es un elemento de A o de B� sededuce que �x es un elemento de A,�T13.2) de �x es un elemento de A� se deduce que �x es un elemento deA y x es un elemento de A o de B.�Demostración de T13.1:Tenemos que veri�car que

ϕ ∧ (ϕ ∨ ψ) ` ϕ

1) ϕ ∧ (ϕ ∨ ψ) (Premisa)2) ` ϕ (E ∧(1))

96

• T14: IdempotenciaT14.1) ϕ ∧ ϕ ` ϕ

T14.2) ϕ ` ϕ ∧ ϕ

La demostración de este teorema se propone como ejercicio.

Teoremas del conectivo disyunción• T15: Propiedad conmutativa

T15.1) ϕ ∨ ψ ` ψ ∨ ϕ

T15.2) ψ ∨ ϕ ` ϕ ∨ ψ

• T16: Propiedad asociativaT16.1) ϕ ∨ (ψ ∨ χ) ` (ϕ ∨ ψ) ∨ χ

T17.2) (ϕ ∨ ψ) ∨ χ ` ϕ ∨ (ψ ∨ χ)

• T17: Propiedad distributivaT17.1) ϕ ∨ (ψ ∧ χ) ` (ϕ ∨ ψ) ∧ (ϕ ∨ χ)

T17.2) (ϕ ∨ ψ) ∧ (ϕ ∨ χ) ` ϕ ∨ (ψ ∧ χ)

• T18: Propiedad de absorciónT18.1) ϕ ∨ (ϕ ∧ ψ) ` ϕ

De la disyunción de una fórmula ϕ con su conjunción con cualquierotra fórmula se deduce ϕ.

T18.2) ϕ ` ϕ ∨ (ϕ ∧ ψ)

Es la recíproca del anterior: de una fórmula ϕ se deduce la disyunciónde ella con su conjunción con cualquier otra fórmula.Por ejemplo,T18.1) de �x es un elemento de A o x es un elemento de A y de B� sededuce que �x es un elemento de A,�T18.2) de �x es un elemento de A� se deduce que �x es un elemento deA o x es un elemento de A y de B.�

97

• T19: Idempotencia

T19.1) ϕ ∨ ϕ ` ϕ

T19.2) ϕ ` ϕ ∨ ϕ

Teoremas del conectivo coimplicación• T20: Introducción de la coimplicación

{ϕ → ψ, ψ → ϕ} ` ϕ ↔ ψ

La coimplicación (doble implicación) entre dos fórmulas se deduce delas dos implicaciones que tienen estas dos fórmulas como premisa yconclusión y como conclusión y premisa, respectivamente.La demostración de este teorema se propone como ejercicio.

• T21: Eliminación de la coimplicación

T21.1) ϕ ↔ ψ ` ϕ → ψ

T21.2) ϕ ↔ ψ ` ψ → ϕ

De una coimplicación entre dos fórmulas se deducen las implicacionesde cada una a la otra.La demostración de este teorema se propone como ejercicio.

• T22: Propiedad re�exiva

` ϕ ↔ ϕ

Toda fórmula coimplica a sí misma.

• T23: Propiedad transitiva

{ϕ ↔ ψ, ψ ↔ χ} ` ϕ ↔ χ

Si una fórmula ϕ coimplica a una fórmula ψ y si ψ coimplica a unafórmula χ, entonces ϕ coimplica a χ.

98

• T24: Propiedad simétricaϕ ↔ ψ ` ψ ↔ ϕ

De ϕ coimplica a ψ se deduce que ψ coimplica a ϕ.

Observación 5.2.6 Sea R la relación binaria sobre L de�nida porla coimplicación:

(ϕ, ψ) ∈ R si y sólo si ϕ ↔ ψ.

La validez de la propiedad re�exiva, simétrica y transitiva para estarelación implica que R es una relación de equivalencia entre fórmulasproposicionales.

Teoremas del conectivo implicación• T25: Importación-Exportación

T25.1) {ϕ → (ψ → χ), ϕ ∧ ψ} ` χ

De una implicación cuya conclusión es la implicación ψ → χ y de laconjunción de las dos premisas ϕ ∧ ψ se deduce la conclusión χ.

T25.2) {ϕ ∧ ψ → χ, ϕ} ` ψ → χ

Es la recíproca del anterior: de una implicación cuya premisa es laconjunción de dos fórmulas se deduce la implicación de una de las dospremisas a la implicación de la otra premisa a la conclusión.

Ejemplo 5.2.7 Seanp = n es un número natural,q = n es par,r = el cuadrado de n es par.Entonces,T25.1) de �si n es número natural, entonces si n es par su cuadradoes par� y de �si n es un número natural y es par�, se deduce que �elcuadrado de n es par,�T25.2) de �si n es un número natural y es par, entonces su cuadrado espar� y de �n es número natural, se deduce que �si n es par, su cuadradoes par.�

99

Demostración de T25.1:Tenemos que veri�car que

{ϕ → (ψ → χ), ϕ ∧ ψ} ` χ.

1) ϕ → (ψ → χ) (Premisa)2) ϕ ∧ ψ (Premisa)3) ` ϕ (E ∧(2))4) ` ψ → χ (E →(3,1))5) ` ψ (E ∧(2))6) ` χ (E →(5,4))

• T26: Mutación de premisa

ϕ → (ψ → χ) ` ψ → (ϕ → χ)

Demostración de T26:

1) ϕ → (ψ → χ) (Premisa)

2) ψ (Premisa auxiliar)

3) ϕ (Premisa auxiliar)4) ` ψ → χ (E →(3,1))5) ` χ (E →(2,4))

6) ` ϕ → χ (I → (3,5))

7) ` ψ → (ϕ → χ) (I → (2,6))

• T27: Carga de premisa

ϕ ` (ψ → ϕ)

100

Demostración de T27:

1) ϕ (Premisa)

2) ψ (Premisa auxiliar)3) ` ϕ (Teorema de la identidad, T1(1))

4) ` ψ → ϕ (I → (2,3))

• T28: Modus tollens, MT

{ϕ → ψ,¬ψ} ` ¬ϕ

Notar que esta regla es la contraposición.

Demostración de T28: la demostración es la misma vista en el apar-tado 1) del ejemplo (5.2.4).

• T29: Tollendo ponens

{ϕ ∨ ψ,¬ψ} ` ϕ

Demostración de T29:

101

1) ϕ ∨ ψ (Premisa)2) ¬ψ (Premisa)

3) ϕ (Premisa auxiliar)4) ` ϕ (Teorema de la identidad, T1(3))

5) ψ (Premisa auxiliar)6) ` ψ ∧ ¬ψ (I ∧ (2,5))7) ` ϕ (Excontraditione Quodlibet, T4(6))

8) ` ϕ (E ∨ (1,(3,4),(5,7)))

• T30: Dilemas

T30.1) : Dilema constructivo simple:{ϕ ∨ ψ, ϕ → χ, ψ → χ} ` χ,

T30.2) : Dilema constructivo complejo:{ϕ ∨ ψ, ϕ → χ, ψ → σ} ` χ ∨ σ,

T30.3) : Dilema destructivo simple:{¬ϕ ∨ ¬ψ, χ → ϕ, χ → ψ} ` ¬χ,

T30.4) : Dilema destructivo complejo:{¬ϕ ∨ ¬ψ, χ → ϕ, σ → ψ} ` ¬χ ∨ ¬σ,

Demostración de T30:T30.1) : {ϕ ∨ ψ, ϕ → χ, ψ → χ} ` χ

Es la regla de eliminación de la disyunción (E ∨).

T30.2) : {ϕ ∨ ψ, ϕ → χ, ψ → σ} ` χ ∨ σ

102

1) ϕ ∨ ψ (Premisa)2) ϕ → χ (Premisa)3) ψ → σ (Premisa)

4) ϕ (Premisa auxiliar)5) ` χ (E →(4,2))6) ` χ ∨ σ (I ∨(5))

7) ψ (Premisa auxiliar)8) ` σ (E →(7,3))9) ` χ ∨ σ (I ∨(8))

10) ` χ ∨ σ (E ∨ (1,(4,6),(7,9)))

T30.3) : {¬ϕ ∨ ¬ψ, χ → ϕ, χ → ψ} ` ¬χ

1) ¬ϕ ∨ ¬ψ (Premisa)2) χ → ϕ (Premisa)3) χ → ψ (Premisa)

4) ¬ϕ (Premisa auxiliar)5) ` ¬χ (Modus Tollens, MT(2,4))

6) ¬ψ (Premisa auxiliar)7) ` ¬χ (Modus Tollens, MT(3,6))

8) ` ¬χ (E ∨ (1,(4,5),(6,7)))

T30.4) : {¬ϕ ∨ ¬ψ, χ → ϕ, σ → ψ} ` ¬χ ∨ ¬σ

103

1) ¬ϕ ∨ ¬ψ (Premisa)2) χ → ϕ (Premisa)3) σ → ψ (Premisa)

4) ¬ϕ (Premisa auxiliar)5) ` ¬χ (Modus Tollens, MT(2,4))6) ` ¬χ ∨ ¬σ (I ∨(5))

7) ¬ψ (Premisa auxiliar)8) ` ¬σ (Modus Tollens, MT(3,7))9) ` ¬χ ∨ ¬σ (I ∨(8))

10) ` ¬χ ∨ ¬σ (E ∨ (1,(4,6),(7,9)))

En el siguiente ejemplo vamos a emplear la regla (I¬) para demostrar lavalidez de una fórmula por refutación.

Ejemplo 5.2.8 Para veri�car que la fórmula

ϕ : p → (q → p),

del ejemplo (4.6.4) es válida en el sistema de Gentzen podemos usar la regla(I¬) : tendremos que demostrar que la fórmula ¬ϕ conduce a una contra-dicción.

104

En la notación de Fitting:

1) ¬(p → (q → p)) (Premisa auxiliar)2) ` ¬(¬p ∨ (q → p)) (Interde�nición 2(1))3) ` ¬¬p ∧ ¬(q → p) (Ley de de Morgan T8.1(2))4) ` ¬¬p (E ∧(3))5) ` ¬(q → p) (E ∧(3))6) ` p (E ¬(4))7) ` ¬(¬q ∧ p) (Interde�nición 2(5))8) ` q ∨ ¬p (Ley de de Morgan T8.3(7))9) ` ¬p (E ∧(8))10) ` p ∧ ¬p (I ∧(6,9))

11) ` p → (q → p) (I ¬(1,10))

En la sección (5.4) veremos que existen teoremas que demuestran la equi-valencia entre la teoría interpretativa (semántica) y el sistema de deducciónnatural.

Esta equivalencia entre teorías nos permite elegir, en cada caso, entre elmétodo más adecuado o e�ciente para desarrollar una demostración.

5.3 Tableaux sintácticosPodemos observar que la de�nición recursiva de tableaux semántico asociadoa un conjunto de fórmulas no requiere, en ningún paso, el cálculo de los valoresde verdad de las fórmulas consideradas. Eso quiere decir que el métodode refutación de los tableaux es, en realidad, un método de demostraciónsintáctico.

Los tableaux sintácticos usan el método de refutación para derivarla validez de un razonamiento o de una fórmula, sin tener que tomar enconsideración los valores de verdad de las fórmulas en estudio. Permitendemostrar teoremas y deducciones.

105

Ejemplo 5.3.1 En el ejemplo (4.6.9) demostramos la implicación lógica

{p ∧ q → r,¬r, p} |= ¬q.

Teniendo en cuenta las equivalencias entre fórmulas de�nidas por la coim-plicación de la teoría axiomática, la misma secuencia de tableaux empleadaen ese ejemplo demuestra la deducción

{p ∧ q → r,¬r, p} ` ¬q,

o, por el teorema de la deducción, el teorema

` (p ∧ q → r) → (¬r → (p → ¬q)).

5.4 Completitud, corrección y decidibilidadPara cualquier sistema axiomático es siempre imprescindible estudiar si éstecumple las tres propiedades de completitud, corrección y decidibilidad. Lasdos primeras propiedades permiten estudiar la relación del sistema con lasemántica del lenguaje y la tercera es una propiedad algorítmica.

Las demostraciones de la validez de estas propiedades para los sistemas dela lógica proposicional son complejas y fuera del alcance de esta asignatura.Nos limitaremos a enunciar los principales teoremas relacionados.

• CompletitudSe dice que un sistema de demostración axiomático es completo sies capaz de demostrar cualquier fórmula semánticamente válida (unatautología) y deducir cualquier consecuencia lógica.Teorema de Kalmar [A]: toda tautología en teoría interpretativa esuna fórmula válida en teoría de la demostración.El sistema de Gentzen es completo.Considerando la de�nición sintáctica de la teoría de los tableaux paraun conjunto arbitrario de fórmulas (posiblemente in�nito), se puededemostrar que el sistema axiomático así obtenido es completo [HLR].

106

• CorrecciónSe dice que un sistema de demostración es correcto (consistente,coherente) si todas las fórmulas demostrables en el sistema son tau-tologías y todas las fórmulas deducibles en el sistema a partir de unconjunto de premisas son consecuencia lógica de dichas premisas.Teorema de Post [A]: toda fórmula válida en teoría de la demostra-ción es una tautología en teoría interpretativa.El sistema de Gentzen y la de�nición sintáctica de la teoría de lostableaux son sistemas correctos [HLR] y [MH].

• DecidibilidadSe dice que un sistema de demostración es decidible si proporcionaun procedimiento general y �nito (aplicable a cualquier fórmula y quetermine) que permita decidir si una fórmula es válida o deducible apartir de un conjunto de fórmulas.Los teoremas anteriores permiten a�rmar que una fórmula proposicio-nal es un teorema si y sólo si es una tautología.Por tanto la evaluación de la tabla de verdad es un procedimientogeneral y �nito de decisión de la validez de una fórmula [A].Es también posible demostrar que el método de los tableaux, en sude�nición más general, tiene las mismas propiedades de generalidad y�nitud [HLR] que las tablas de verdad.Se sigue que los sistemas formales de la lógica proposicionales son de-cidibles.

En conclusión, los sistemas formales de la lógica proposicional (la lógicade orden 0) son completos, correctos y decidibles.

Las lógicas de orden superior son más generales, pero pierden algunas deestas propiedades. Veremos que la lógica de predicados (de primer orden) escompleta y correcta, pero no es decidible.

107

5.5 EjerciciosEjercicio 5.5.1 Usando el sistema de deducción natural, demuestra la idem-potencia de la conjunción (T14), la introducción del coimplicador (T20) y laeliminación del coimplicador (T21).

Ejercicio 5.5.2 Prueba que las siguientes equivalencias semánticas son tam-bién coimplicaciones demostrables en el sistema de deducción natural:

1. ¬¬p ≡ p

2. ¬(p ∨ q) ≡ ¬p ∧ ¬q

3. ¬(p ∧ q) ≡ ¬p ∨ ¬q

4. (p → q) ≡ ¬p ∨ q

5. ¬(p → q) ≡ p ∧ ¬q

Ejercicio 5.5.3 Formaliza los siguientes razonamientos:

1. Si llueve no iré al mercado. Si no iré al mercado, o bien no tendrécomida o bien iré al restaurante. Llueve y tengo comida. Por lo tanto:iré al restaurante.

2. Si f es diferenciable en [a, b], es continua y acotada en [a, b]. Si f nofuese acotada en [a, b] no podría ser diferenciable en [a, b]. Por tanto:si f es discontinua y acotada en [a, b], no es diferenciable en [a, b].

Ejercicio 5.5.4 Usando el sistema de deducción natural, prueba (si es posi-ble) la validez de los razonamientos anteriores.

Ejercicio 5.5.5 Usando el sistema de deducción natural, demuestra la vali-dez de las siguientes deducciones:

1. {(p ∧ q) → r, ¬(p ∨ r) → s, p → q} ` ¬s → r

2. {r → p, ¬q → ¬r, s → q, (p ∧ q) → t, ¬s ∨ p} ` (r ∨ s) → t

3. {p → (q → r), ¬s ∨ p, q} ` s → r

4. {s → (t → u), u → ¬u, (v → s) ∧ (p → t)} ` v → ¬p

108

Parte II

Lógica de predicados de primerorden

109

Capítulo 6

Sintaxis de la lógica de primerorden

La lógica de predicados o de primer orden (LPO, L1) es una generali-zación de la lógica de proposiciones (LP, L0). Introduciendo nuevos elementosdel lenguaje, permite estudiar la estructura interna de los enunciados (suspropiedades, las relaciones entre objetos, etc.).

Ejemplo 6.0.1 Consideremos el siguiente razonamiento:

Todos los hombres son mortales,Sócrates es un hombre,Sócrates es mortal.

Sean p = todos los hombres son mortales, q = Sócrates es un hombre yr = Sócrates es mortal.

La formalización del razonamiento dado en lógica proposicional es

pqr

y tiene el contraejemplo p : 1, q : 1 y r : 0. Por tanto, el razonamiento enestudio no es válido en lógica proposicional.

Es evidente que la conclusión de este ejemplo no satisface nuestra intui-ción. Necesitamos extender la lógica proposicional a una lógica que admitala validez de una clase más amplia de razonamientos.

111

112

Esta nueva lógica tendría que permitir una descripción más �na de la rea-lidad, pudiendo distinguir los objetos o términos (por ejemplo, los hombres)de sus propiedades o predicados (por ejemplo, la propiedad de ser morta-les). La lógica proposicional, cuyos elementos básicos son las proposicionesatómicas, no permite realizar esta distinción.

La lógica de predicados (Gottob Frege, 1879) nos permite dar una descrip-ción de la realidad más detallada. Por ejemplo, veremos que el razonamientoanterior se puede formalizar más precisamente como

∀x(H(x) → M(x)),H(s),M(s).

Como ya comentamos en varias ocasiones, la sintaxis es la de�nición axio-mática de los elementos básicos del lenguaje y de las reglas que permiten ob-tener nuevas expresiones correctas a partir de aquellos, las expresiones bienconstruidas. El objetivo de este capítulo es el estudio de la sintaxis de lalógica de predicados.

En el capítulo 2 estudiamos una breve introducción a las nociones básicasde la teoría de conjuntos, de las relaciones y de las funciones. Estos conceptosson fundamentales para la lógica de predicados y se aconseja su repaso.

Las principales referencias usadas en este capítulo son [A], [HLR] y [MH].

6.1 Alfabeto del lenguaje formal de la lógica depredicados

Los elementos básicos del alfabeto del la lógica de predicados son:

• Los símbolos de constantes: se denotan a, b, c, . . . y representanobjetos concretos. Las constantes son individuos o elementos dis-tinguidos del universo del discurso, que es la colección de objetossobre los cuales queremos razonar.

• Las variables: se denotan x, y, z, . . . y sirven para representar obje-tos, cuyo dominio hay que especi�car.

113

Tomaremos conjuntos de variables V �nitos o in�nitos numerables.Recordamos que un conjunto V es in�nito numerable si existe unafunción biyectiva entre V y el conjunto de los números naturales N.

Ejemplo 6.1.1 En las expresiones �Pedro es un estudiante� y �x es unnúmero primo,� Pedro es una constante en el conjunto de la personasy x es una variable en el conjunto de los números enteros.

• Los conectivos lógicos:

1. constantes (de aridad 0): > (verdadero) y ⊥ (falso)

2. conectivos unarios: ¬ (negación)

Ejemplo 6.1.2 Siendo �E(a) : Pedro es un estudiante,� apli-cando la negación se obtiene �¬(E(a)) : Pedro no es un estu-diante.� De forma similar, si � P (x) : x es un número primo,�� ¬(P (x)) : x� no es un número primo.

3. conectivos binarios:∧ (y: la conjunción),∨ (ó: la disyunción),→ (la implicación o condicional),↔ (la doble implicación o coimplicación).

NOTACIÓN: El símbolo ◦ se usará para representar un conec-tivo binario cualquiera.

Ejemplos 6.1.3 1) La frase �Sócrates es un �lósofo, sin embar-go no es un deportista� se escribe como (F (s) ∧ ¬(D(s))), donde�F (x) : x es un �lósofo,� �D(x) : x es un deportista� y x es unavariable en el conjunto de las personas.2) La frase �Sócrates es un �lósofo o Sócrates es un deportista� seescribe como (F (s) ∨D(s)).

3) La frase �La luna es de papel si y sólo si Carlos lee muchoslibros� se escribe como (P (l) ↔ L(c)), donde �P (x) : x es de pa-pel,� �L(y) : y lee muchos libros,� x es una variable en el conjuntode las cosas y y es una variable en el conjunto de las personas.

114

• Igualdad:Usaremos el símbolo de igualdad � = � para expresiones del tipo 4−1 =3 o mcm(2, 3) = 6.

Por tanto, estamos considerando la lógica de predicados con igual-dad.

Ejemplo 6.1.4 El comando �IF x > 0 THEN y =√

x� se escribecomo (P (x) → (y = f(x))), donde �P (x) : x es positivo,� �f(x) :

√x�

y x y y son variables en el conjunto de los números reales.

• Los cuanti�cadores:

1. ∀ : cuanti�cador universal (para todo). El cuanti�cador uni-versal permite referirse a todos los individuos del universo deldiscurso.

2. ∃ : cuanti�cador existencial (existe). El cuanti�cador existen-cial permite referirse a algunos de los individuos del universo deldiscurso.

Ejemplos 6.1.5 1) La frase �Todo número primo y mayor que 2 esimpar� se escribe como (∀x((P (x) ∧Q(x)) → R(x))), donde �P (x) : xes primo,� �Q(x) : x es mayor que 2,� �R(x) : x es impar� y x es unelemento cualquiera del conjunto de los números enteros.2) La frase �Todo hombre es mortal y hay hombres que no son �lósofos�se escribe como ((∀x(P (x) → Q(x))) ∧ (∃x(P (x) ∧ (¬(R(x))))), donde�P (x) : x es un hombre,� �Q(x) : x es mortal,� �R(x) : x es �lósofo� yx es un elemento cualquiera del conjunto de los seres.

• Los símbolos de puntuación (o símbolos auxiliares): paréntesisabiertos y cerrados, comas.

• Los símbolos de predicado: se denotan P,Q, R, . . . .

Todo predicado tiene un número n ∈ N ∪ {0} de argumentos. Elnúmero n es la aridad del predicado.En ocasiones se especi�cará la aridad n de un predicado P por mediodel símbolo P n.

115

1. Predicados constantes, n = 0: representan proposicionesatómicas.Para representar las proposiciones atómicas se suelen usar los sím-bolos p, q, r, s, t, . . .

2. Predicados monádicos, n = 1: representan propiedades deobjetos.

3. Predicados poliádicos, n > 1: representan relaciones entreobjetos.

Los predicados poliádicos de la lógica de primer orden son relacionessobre conjuntos según la de�nición del capítulo 2. Así, por ejemplo,todo predicado binario es una relación binaria R entre dos conjuntosA y B, es decir, R ⊆ A×B.

Un predicado monádico asocia a cada objeto de un dominio una pro-piedad.Nota: Por de�nición, un predicado es tal que al sustituir todas sussímbolos de variables por símbolos de constantes se obtiene una fórmulaproposicional.

Ejemplos 6.1.6 1) Los siguientes son ejemplos de predicados:a) �p : hoy llueve� es un predicado constante, una proposición atómica.b) �P (x) : la raíz cuadrada de x es irracional� (predicado monádico),siendo x un cualquier número real.Al sustituir x por un símbolo de constante, por ejemplo 2, se obtiene laproposición �P (2) : la raíz cuadrada de 2 es irracional.�c) P (x, y) : x es un hermano de y (predicado binario), siendo el dominioel conjunto de las personas.En particular, �P (l, j) : Luis es un hermano de Jose� es una fórmulaproposicional.d) P (x, y, z) : x pre�ere y a z (predicado ternario), siendo el dominio delas variable x el conjunto de las personas y el dominio de las variablesy y z el conjunto de los países.En particular, �P (l, f, i) : Luis pre�ere Francia a Italia� es una fór-mula proposicional.

116

2) Como vimos en el capítulo 2, los predicados permiten de�nir con-juntos.Por ejemplo, en el dominio de los puntos del plano real R × R, elconjunto S de las soluciones del sistema de dos ecuaciones

{3x + 2y = 1

x− 4y = 0

se puede de�nir por medio de los predicados �S1(z) : el punto z = (x, y)es tal que 3x + 2y = 1� y �S2(z) : el punto z = (x, y) es tal quex− 4y = 0.�En el siguiente capítulo, dedicado a la semántica de la lógica de primerorden, veremos como asignar valores de verdad a las expresiones bienconstruidas.Para nuestro ejemplo, podremos a�rmar que los elementos del conjuntoS son los puntos del plano z tales que S1(z) ∧ S2(z) es verdadera.

• Los símbolos de función: se denotan f, g, h, . . . .

Toda función tiene un número n ∈ N∪{0} de argumentos. El númeron es la aridad de la función.En ocasiones se especi�cará la aridad n de una función f por mediodel símbolo fn.

Nota: Las funciones de la lógica de primer orden son funciones segúnla de�nición del capítulo 2.

1. Funciones constantes, n = 0: son símbolos de constantes.Para representar las funciones constantes se suelen usar los sím-bolos a, b, c, . . .

2. Funciones monádicas, n = 1: representan un objeto en funciónde otro.

3. Funciones poliádicas, n > 1: representan un objeto en funciónde n otros objetos.

Ejemplos 6.1.7 1) Los siguientes son ejemplos de funciones:

117

a) f(x) :√

x es la función monádica raíz cuadrada de un numero realno negativo, f ⊆ [0,∞)× R.

b) f(x, y) : x + y es la función binaria suma de dos números reales,f ⊆ R× R× R.

c) f(x, g(y, z), a) : x(y +z)−a es la función ternaria, f ⊆ R×R×R×R, que multiplica las primeras dos variables reales y resta al productoobtenido la constante real a.

g es la función binaria, g ⊆ R× R× R, suma de dos números reales.

2) El siguiente es un ejemplo de un predicado que no es una función:En el conjunto de las personas, �P (x, y) = x es la madre de y� esun predicado (una relación binaria) que no es una función, ya que sudominio no es todo el conjunto de las personas y una madre puede tenermás que un hijo.

Observación 6.1.8 De los ejemplos anteriores se deduce que, si n esun número natural, toda función n−aria se puede escribir comoun predicado (n + 1)-nario. Sin embargo, en general, un predicadono se puede escribir como una función.Veremos que las funciones sirven para simpli�car la estructura de lafórmulas de la lógica de primer orden.

6.2 De�nición recursiva de las expresiones bienconstruidas: términos y fórmulas

Como en la lógica proposicional, los elementos básicos de un lenguaje y lasreglas de formación permiten de�nir cadenas �nitas de símbolos arbitrarias(palabras).

En la lógica proposicional la palabras que son expresiones bien construidasson las fórmulas. En la lógica de predicados las expresiones bien construidaspueden ser de dos tipos: términos (que representan objetos) y fórmulas(que expresan hechos relativos a objetos).

Los términos y las fórmulas son las expresiones bien construidas dela lógica de primer orden (ver �gura 6.1).

118

Los términos y las fórmulas de la lógica de predicados se obtienen a partirdel alfabeto dado sólo por medio de las reglas de formación que vamos ade�nir a continuación.

Como en la lógica proposicional, la de�nición de las expresiones bienconstruidas de la lógica de primer orden es recursiva y, como veremos, siguenvaliendo los principios de unicidad de estructura, de inducción y de recursiónestructural para términos y fórmulas.

• Términos

De�nición 6.2.1 (De�nición recursiva de los términos)1. (TAt): Todo símbolo de variable y todo símbolo de constante es

un término.Las variables y las constantes forman el conjunto de los términosatómicos.

2. (TF): Si f es un símbolo de función de aridad n > 0 y t1, t2, . . . , tnson términos, entonces f(t1, t2, . . . , tn) es un término.Estos términos se llaman términos compuestos.

3. Si una palabra no se obtiene mediante las dos reglas anteriores,entonces no es un término.

Ejemplo 6.2.2 Los siguientes son ejemplos de términos:x, a, f(x), g(x, y), g(x, f(x)),

donde x es una variable, a es una constante, f es una función monádicay g es una función binaria.Los primero dos términos de la lista son atómicos y los restantes soncompuestos.

• Fórmulas

De�nición 6.2.3 Una fórmula atómica es cualquier expresión dela forma P (t1, t2, . . . , tn), donde P es un símbolo de predicado conaridad n > 0 y t1, t2, . . . , tn son términos. Las proposiciones atómicas(los predicados constantes), los conectivos lógicos constantes > y ⊥y la igualdad entre términos, s = t, también se consideran fórmulasatómicas.

119

Ejemplo 6.2.4 Los siguientes son ejemplos de fórmulas atómicas:

>, p, R(f(x), y)

donde p es una proposición atómica, f es una función monádica y Res un predicado binario.

De�nición 6.2.5 (De�nición recursiva de las fórmulas)

1. (FAt): Toda fórmula atómica es una fórmula.2. (F¬): Si ϕ es una fórmula, entonces ¬ϕ es una fórmula.3. (F◦): Si ϕ y ψ son dos fórmulas entonces (ϕ◦ψ) es una fórmula.4. (F∀∃): Si ϕ es una fórmula y x es un símbolo de variable, en-

tonces ∃xϕ y ∀xϕ son fórmulas.5. Si una palabra no se obtiene mediante las cuatro reglas anteriores,

entonces no es una fórmula.

NOTACIÓN: Para representar las fórmulas se suelen usar las letrasdel alfabeto griego ϕ, ψ, χ, . . .

Ejemplos 6.2.6 1) Las fórmulas atómicas del ejemplo anterior sonfórmulas.2) La expresión

(∀x∃y(R(x, f(y)) ∧ (¬(f(x) = s)))

es una fórmula ya que:1. R(x, f(y)) y (f(x) = s) son fórmulas atómicas (aplicando (FAt)),2. (¬(f(x) = s)) es una fórmula (aplicando (F¬)),3. (R(x, f(y)) ∧ (¬(f(x) = s))) es una fórmula (aplicando (F◦)),4. ∃y(R(x, f(y)) ∧ (¬(f(x) = s))) es una fórmula (aplicando (F∀∃)),5. (∀x∃y(R(x, f(y)) ∧ (¬(f(x) = s)))) es una fórmula (aplicando(F∀∃)).

120

TÉRMINOS(objetos)

FÓRMULAS(hechos)

EXPRESIONES BIEN CONSTRUIDAS

Fórmulas atómicas

(relaciones)

Figura 6.1: Expresiones bien construidas

6.2.1 Variables libres y variables ligadasLas fórmulas se clasi�can en fórmulas abiertas y fórmulas cerradas,dependiendo de ciertas características de sus variables.

De�nición 6.2.7 Fórmulas abiertas y fórmulas cerradas

• Se dice que la ocurrencia de una variable x en una fórmula ϕ es ligada(o que la variable es ligada) si está afectada por algún cuanti�cador. Encaso de que una variable no aparezca ligada diremos que su ocurrenciaes libre (la variable es libre).

• Se dice que una fórmula ϕ es abierta si tiene alguna ocurrencia devariable libre. Se dice que una fórmula ϕ es cerrada (o que es unasentencia) si no tiene ninguna ocurrencia de variable libre.

Ejemplos 6.2.8 1) En la fórmula ∀xP (x, y) la variable x aparece ligada yla variable y aparece libre. La fórmula es abierta.

2) En la fórmula

∃x((P (x) ∧Q(x)) ∨ (P (x) ∧Q(x)))

la variable x aparece ligada en las dos componentes de la disyunción, ya queel cuanti�cador existencial la afecta en los dos casos. La fórmula es cerrada.

3) En la fórmula

(∃x(P (x) ∧Q(x)) ∨ (P (x) ∧Q(x)))

la variable x aparece ligada en la primera componente de la disyunción yaparece libre en la segunda. En este caso el cuanti�cador existencial afectax sólo en la primera componente de la disyunción y la fórmula es abierta.

121

Notar que esta última fórmula se puede reescribir como

(∃x(P (x) ∧Q(x)) ∨ (P (y) ∧Q(y))).

6.2.2 El principio de inducción estructural para expre-siones bien construidas

Como en el caso de la lógica de proposiciones, para poder estudiar las pro-piedades de las expresiones bien construidas de la lógica de primer orden unade las técnicas más adecuadas es el principio de inducción estructural.

Principio de inducción estructural para términosSea P una cierta propiedad tal que:

1. Base de inducción (TAt): Todos los términos atómicos cumplen lapropiedad P.

Pasos de inducción:

2. (TF): Si f es un símbolo de función de aridad n > 0 y los términost1, t2, . . . , tn cumplen la propiedad P (hipótesis de inducción), entoncesf(t1, t2, . . . , tn) cumple la propiedad P.

El principio de inducción estructural para términos a�rma quesi se veri�can las condiciones anteriores, entonces se puede concluir quetodo término cumple la propiedad P.

El principio de inducción estructural para fórmulasSea P una cierta propiedad tal que:

1. Base de inducción (FAt): Todas las fórmulas atómicas cumplen lapropiedad P.

Pasos de inducción:

2. (F¬): Si ϕ es una fórmula que cumple la propiedad P (hipótesis deinducción), entonces ¬(ϕ) cumple la propiedad P,

122

3. (F◦): Si ϕ y ψ son dos fórmulas que cumplen la propiedad P (hipótesisde inducción), entonces (ϕ ◦ ψ) cumple la propiedad P,

4. (F∀∃): Sean ϕ es una fórmula y x un símbolo de variable. Si ϕcumple la propiedad P (hipótesis de inducción), entonces ∀xϕ y ∃xϕcumplen la propiedad P.

El principio de inducción estructural para fórmulas a�rma quesi se veri�can las condiciones anteriores, entonces se puede concluir quetoda fórmula cumple la propiedad P.

6.3 Representación de las expresiones bien cons-truidas

Como ya hicimos en el caso de la lógica proposicional, vamos a ilustrar lasmaneras más usadas para representar las fórmulas de la lógica de primerorden.

6.3.1 Fórmulas en forma abreviadaPara reducir una fórmula a su forma abreviada podemos seguir los siguien-tes pasos:a) Se puede omitir el par de paréntesis externo.

Así, por ejemplo, la fórmula

((∃xP (x) ∧Q(x)) ∧ (∀yP (y)))

se puede escribir como:

(∃xP (x) ∧Q(x)) ∧ (∀yP (y)).

b) Se introducen las mismas reglas de precedencia y el mismo conveniode asociatividad entre conectivos que de�nimos para fórmulas proposicio-nales.

Así, por ejemplo, la fórmula anterior se escribiría (sin cambios) como:

(∃xP (x) ∧Q(x)) ∧ (∀yP (y)).

123

c) Se admite la precedencia de los cuanti�cadores: los cuanti�cadorestienen prioridad sobre los conectivos. Se obtienen los siguientes niveles deprecedencia:

Nivel 1: ∀ y ∃,Nivel 2: ¬,Nivel 3: ∨ y ∧,Nivel 4: → y ↔ .

Finalmente, la forma abreviada de nuestra fórmula es:

(∃xP (x) ∧Q(x)) ∧ ∀yP (y).

6.3.2 Principio de unicidad de estructura para expre-siones bien construidas

Como para la lógica proposicional, en la lógica de primer orden valen prin-cipios de unicidad de estructura para términos y fórmulas. Cada expresiónbien construida admite un análisis sintáctico único, es decir, existe una únicamanera de derivarla usando las reglas de formación dadas.

Estos principios nos permitirán representar expresiones bien construidaspor medio de árboles sintácticos (o estructurales).

Principio de unicidad de estructura para términosTodo término pertenece a una y sólo una de las siguientes categorías:

1. (TAt): es atómico,

2. (TF): se escribe como f(t1, t2, . . . , tn), donde f es un símbolo de fun-ción de aridad n > 0 y t1, t2, . . . , tn son términos.f y t1, t2, . . . , tn están unívocamente determinados.

124

Principio de unicidad de estructura para fórmulasToda fórmula ϕ pertenece a una y sólo una de las siguientes categorías:

1. (FAt)1 : ϕ es una proposición atómica o uno de los conectivos lógicosconstantes > y ⊥,

2. (FAt)2 : ϕ es una igualdad entre términos, s = t, donde s y t estánunívocamente determinados,

3. (FAt)3 : ϕ es P (t1, t2, . . . , tn), donde P es un símbolo de predicadocon aridad n > 0 y t1, t2, . . . , tn son términos.P y t1, t2, . . . , tn están unívocamente determinados,

4. (F¬): ϕ es ¬(ϕ1) para cierta fórmula ϕ1, unívocamente determinada,

5. (F◦): ϕ es (ϕ1 ◦ ϕ2) para cierto conectivo ◦ y ciertas fórmulas ϕ1 yϕ2 .

ϕ1 y ϕ2 están unívocamente determinadas,

6. (F∀∃): ϕ es ∀xϕ1 o ∃xϕ1 para cierta fórmula ϕ1 y cierto símbolo devariable x.

ϕ1 y x están unívocamente determinados.

6.3.3 Términos y fórmulas en forma de árbol estructuralUna primera consecuencia de los principios de unicidad de estructura es laposibilidad de representar términos y fórmulas por medio de árboles.

En los siguientes dos ejemplos veremos como construir el árbol sintácticode un término y de una fórmula.

Ejemplos 6.3.1 1) Consideremos el término compuesto

f(g(x, h(a, y)), i(x, l(y))).

Para representar su estructura sintáctica podemos dibujar el árbol con raízde la �gura 6.2.

125

a

x

y

h

g

f

i

x l

y¡¡

¡¡

¡¡

¡¡

@@

@@

@@

@@³³³³³³³³³³³HHHHHHHH

@@

@@

¡¡

¡¡

Figura 6.2: Árbol sintáctico del término f(g(x, h(a, y)), i(x, l(y))).

2) Sea ahora ϕ la fórmula

ϕ : ∀x∃y(∀z(a = f(z)) ∨ (¬R(g(x, h(a, y)), i(x, l(y))))).

Para representar la estructura sintáctica de ϕ, podemos dibujar el árbolcon raíz de la �gura 6.3.

Notar que las etiquetas de las hojas de los árboles sintácticos son lostérminos atómicos de las expresiones bien construidas representadas. Laexistencia de predicados y funciones que dependen de n variables, hace queen la lógica de predicados los árboles estructurales no tienen que ser binarioscomo es en el caso de la lógica proposicional.

6.3.4 El principio de recursión estructural para expre-siones bien construidas

Como ya vimos para la lógica proposicional, también en el caso de la lógicade predicados una segunda consecuencia de los principios de unicidad deestructura son los principios de recursión estructural para expresiones bienconstruidas. Estos principio permiten de�nir funciones sobre el conjunto delos términos y el conjuntos de las fórmulas.

126

a

x

y

h

g

R

¬

i

x l

y

z

fa

z =

∀

∨

∀∃

y

x

¡¡

¡¡

¡¡

¡¡

@@

@@

@@

@@³³³³³³³³³³³HHHHHHHH

@@

@@

¡¡

¡¡

¡¡

¡

@@

@

¡¡

@@

¡¡

¡¡

¡¡

@@

@@

@@

@@

@@

@

¡¡

¡¡

Figura 6.3: Árbol sintáctico de ϕ.

El principio de recursión estructural para términosSea A un conjunto no vacío. Para de�nir una función

f : T −→ A

cuyo dominio sea el conjunto de los términos y cuyo codominio sea un con-junto dado A, se puede emplear la siguiente de�nición recursiva:

1. Base (TAt): Si t es un término atómico, f(t) se de�ne explícitamen-te, es un elemento de A,

2. Paso recursivo (TF): si t es el término compuesto g(t1, t2, . . . , tn),se de�ne f(t) en función de f(t1), f(t2), . . . , f(tn).

127

Estas de�niciones determinan la función f sobre todo T.

Ejemplos 6.3.2 (HLR) 1) Sea Var el conjunto de todas las variables.Queremos de�nir recursivamente el conjunto V ar(t) de las variables libresde un cualquier término t.

Por el principio de recursión estructural para términos, podemos de�niruna función V ar : T −→ P (Var), (P (Var) es el conjunto de las partes deVar) que asocia a todo término t el conjunto de sus variables libres, V ar(t) :

1. Base (TAt): V ar(x) = {x}, y V ar(a) = ∅, donde ∅ es el conjuntovacío.

2. Paso recursivo (TF): si t es el término compuesto g(t1, t2, . . . , tn),se de�ne

V ar(t) = V ar(t1) ∪ V ar(t2) ∪ · · · ∪ V ar(tn).

2) Se denomina profundidad de un término t a la longitud de la ramamás larga del árbol estructural de t. Por tanto, la profundidad de t es laaltura de su árbol sintáctico.

Por ejemplo, la longitud del término f(g(x, h(a, y)), i(x, l(y))) de la �gura6.2 es 3.

Por el principio de recursión estructural, la de�nición recursiva de lafunción profundidad

pf : T −→ N ∪ {0}(que asocia a cada término t ∈ T su profundidad) es:

1. Base (TAt): Si t es un término atómico, pf(t) = 0,

2. Paso recursivo (TF): si t es el término compuesto g(t1, t2, . . . , tn),se de�ne

pf(t) = max{pf(t1), pf(t2), . . . , pf(tn)}+ 1.

128

El principio de recursión estructural para fórmulasSea A un conjunto no vacío. Para de�nir una función

f : F −→ A

cuyo dominio sea el conjunto de las fórmulas y cuyo codominio sea un con-junto dado A, se puede emplear la siguiente de�nición recursiva:

1. Base (FAt): Si ϕ es una fórmula atómica, f(ϕ) se de�ne explícita-mente, es un elemento de A.

Paso recursivo:

2. (F¬): f(¬(ϕ1)) se de�ne en función de f(ϕ1),

3. (F◦): f(ϕ1 ◦ ϕ2) se de�ne en función de f(ϕ1) y f(ϕ2),

4. (F∀∃): f(∀xϕ1) y f(∃xϕ1) se de�nen en función de f(ϕ1).

Estas de�niciones determinan la función f sobre todo F.

Ejemplo 6.3.3 [HLR]Sea Var el conjunto de todas las variables. Queremos de�nir recursiva-

mente el conjunto Lib(ϕ) de las variables libres de una cualquier fórmulaϕ.

Por el principio de recursión estructural para fórmulas, podemos de�niruna función Lib : F −→ P (Var), que asocia a toda fórmula ϕ el conjuntode sus variables libres, Lib(ϕ) :

1. Base (FAt): Si ϕ es una fórmula atómica, Lib(ϕ) es el conjuntoV ar(ϕ) de todas las variables de ϕ. En particular,Lib(>) = Lib(⊥) = Lib(p) = ∅, donde ∅ es el conjunto vacío,Lib(s = t) = V ar(s) ∪ V ar(t),

Lib(P (t1, t2, . . . , tn)) = V ar(t1) ∪ V ar(t2) ∪ · · · ∪ V ar(tn).

Paso recursivo:

2. (F¬): Lib(¬(ϕ1)) = Lib(ϕ1),

129

3. (F◦): Lib(ϕ1 ◦ ϕ2) = Lib(ϕ1) ∪ Lib(ϕ2),

4. (F∀∃): Lib(∀xϕ1) = Lib(∃xϕ1) = Lib(ϕ1) \ {x}.Estas de�niciones determinan la función Lib sobre todo F.

6.4 Formalización del lenguaje naturalComo ya vimos en lógica proposicional, formalizar una frase del lenguajenatural consiste en encontrar una expresión que la represente �elmente en ellenguaje formal.

No hay procedimientos generales para la formalización, pero se puedendeterminar algunas estrategias, como las que vamos a indicar a continuación.

La referencia principal para esta sección es [A].

• Si la frase que se quiere formalizar no tiene una estructura sintácticafácilmente reconocible, se puede intentar reescribirla en el lenguajenatural hasta llegar a una frase con una estructura más sencilla y quemantenga el mismo signi�cado.

• Tenemos que de�nir claramente el dominio o los dominios a loscuáles pertenecen los objetos que vamos a usar.

• En una frase necesitamos determinar:

� Las constantes, que son objetos concretos de uno o más dominios.� Las variables, que son objetos genéricos de uno o más dominios.� Las funciones de aridad n > 0 , que representan como un cierto

objeto queda determinado por otros (u otro).� Los predicados monádicos que representan propiedades de un

objeto.� Los predicados de aridad n > 0 que representan relaciones

entre objetos.

• Identi�cadas las conectivas lingüísticas y los cuanti�cadores (universa-les o existenciales), necesitamos sustituirlas por los conectivos y loscuanti�cadores de la lógica de primer orden.

130

• Para formalizar un razonamiento, necesitamos formalizar el conjuntode sus premisas y de su conclusión.

Observación 6.4.1 A la hora de formalizar frases o razonamientos hay al-gunas observaciones importantes que es oportuno tener en cuenta.

1. Ya que la formalización de una frase depende del dominio o de losdominios elegidos, se pueden obtener formalizaciones distintas de unmismo enunciado.

Ejemplo 6.4.2 Para formalizar la frase:

�Todos los niños juegan con la pelota,�

podemos de�nir los predicados

J(x) : x juega con la pelota

yJ(x, y) : x juega con y.

a) Sea D1 el conjunto de los niños. Entonces se obtiene

∀xJ(x).

b) Sean D2 el conjunto de las personas y sea �N(x) : x es un niño.� Eneste caso se obtiene

∀x(N(x) → J(x)).

c) Sean D1 el conjunto de los niños y D2 el conjunto de los juegos.Entonces �p = la pelota� es una constante en D2 y obtenemos la for-malización

∀xJ(x, p).

d) Sean D1 el conjunto de las personas y D2 el conjunto de los juegos.Entonces �p = la pelota� es una constante en D2 y, usando el predicado�N(x) : x es un niño,� obtenemos la formalización

∀x(N(x) → J(x, p)).

131

2. Toda función se puede representar mediante un predicado con un ar-gumento más que la función. Además, las funciones simpli�can la es-tructura de la fórmula obtenida.

Ejemplo 6.4.3 Consideremos la frase:

�Todo padre quiere mucho a sus hijos.�

a) Formalización con predicados.Podemos de�nir el dominio D de las personas y los predicados

P (x, y) : x es el padre de y,

yQ(x, y) : x quiere mucho a y.

Con estas de�niciones, la formalización sería

∀x∀y(P (x, y) → Q(x, y)).

b) Formalización con funciones.Podemos de�nir el dominio D de las personas, la función

f(x) : el padre de x,

yQ(x, y) : x quiere mucho a y.

Con estas de�niciones, la nueva formalización sería

∀x(Q(f(x), x)).

Notar que la formalización se ha simpli�cado y que la función de unargumento f(x) sustituye al predicado binario P (x, y).

Observar también que �el hijo de x � no es una función, ya que unmismo padre puede tener más que un hijo y, por tanto, el términoasociado a x (al padre) no quedaría unívocamente determinado.

132

Patrones más habituales en la formalización de los cuanti�cadores:

1. Universal a�rmativo∀x(ϕ1 → ϕ2),

∀x(¬ϕ2 → ¬ϕ1).

Es la forma de representar frases del tipo:Todo ϕ1 es ϕ2,

Sólo los ϕ2 son ϕ1,

Nadie es ϕ1 a menos que sea ϕ2,

No hay ningún ϕ1 que no sea ϕ2,

ϕ1 es su�ciente para ϕ2,

ϕ2 es necesario para ϕ1.

2. Universal negativo∀x(ϕ1 → ¬ϕ2).

Es la forma de representar frases del tipo:Ningún ϕ1 es ϕ2,

Todos los ϕ1 carecen de ϕ2.

3. Existencial a�rmativo

∃x(ϕ1 ∧ ϕ2).

Es la forma de representar frases del tipo:Algún ϕ1 es ϕ2,

Alguien es a la vez ϕ1 y ϕ2.

4. Existencial negativo∃x(ϕ1 ∧ ¬ϕ2).

Es la forma de representar frases del tipo:Algún ϕ1 no es ϕ2,

No todos los ϕ1 son ϕ2.

133

Ejemplos 6.4.4 1) (Universal a�rmativo)

�Nadie se levanta a menos que tenga que irse.�

La frase anterior se puede reescribir como

�Para todo x, si x no tiene que irse, entonces no se levanta,�

o como

�Para todo x, si x se levanta, entonces tiene que irse.�

Sea D el dominio de las personas y sean

P (x) : x se levanta,

Q(x) : x tiene que irse.Con estas de�niciones obtenemos la formalización:

∀x (P (x) → Q(x)).

2) (Universal negativo)

�Ningún emperador es odontólogo (L. Carroll).�

Sea D el dominio de las personas y sean

P (x) : x es emperador,

Q(x) : x es odontólogo.Con estas de�niciones obtenemos la formalización:

∀x (P (x) → ¬Q(x)).

3) (Existencial a�rmativo)

�Algunos estudiantes de informática sólo son amigosde los a�cionados a la lógica [C].�

Esta frase se puede reescribir como:

134

�Para algunos estudiantes de informática, una persona es un amigosólo si es a�cionado a la lógica [C].�

Sea D el dominio de las personas y sean

P (x) : x es estudiante de informática,

Q(x) : x es a�cionado a la lógica,R(x, y) : x es amigo de y.

Con estas de�niciones obtenemos la formalización:

∃x (P (x) ∧ (R(x, y) → Q(y))).

4) (Existencial negativo)

�Algunos gatos no saben silbar ni maullar (L. Carroll).�

Sea D el dominio de los animales y sean

P (x) : x es un gato,

Q(x) : x sabe silbar,R(x) : x sabe maullar.

Con estas de�niciones obtenemos la formalización:

∃x (P (x) ∧ ¬Q(x) ∧ ¬R(x)).

Negación de frases que contienen cuanti�cadoresVamos a ver como se escribe la negación de una frase que contiene uncuanti�cador.

Universal-ExistencialConsideremos la frase

�Todos los alumnos de esta clase aprobarán en febrero.�

135

Sean D el conjunto de los alumnos de esta clase y

P (x) : x aprobará en febrero.

La frase dada se puede escribir como:

∀xP (x).

La negación de �Todos los alumnos de esta clase aprobarán en febrero� es�No todos los alumnos de esta clase aprobarán en febrero,� es decir,

¬(∀xP (x)),

que podemos reescribir como:

�Existen alumnos de esta clase que no aprobarán en febrero.�

Con los mismos dominio y predicados anteriores, su formalización es

∃x(¬P (x)).

Existencial-UniversalConsideremos ahora la frase

�Algunos alumnos de esta clase suspenderán en febrero.�

Sean D el conjunto de los alumnos de esta clase y

P (x) : x suspenderá en febrero.

La frase dada se puede escribir como:

∃xP (x).

La negación de �Algunos alumnos de esta clase suspenderán en febrero�es �Ningún alumno de esta clase suspenderá en febrero,� es decir,

¬(∃xP (x)),

que podemos reescribir como:

�Todos los alumnos de esta clase no suspenderán en febrero.�

136

Con los mismos dominio y predicados anteriores, su formalización es

∀x(¬P (x)).

Ejemplo 6.4.5 (De�nición de límite de una sucesión) Sean R el conjuntode los números reales, R+ el conjunto de los números reales positivos y N elconjunto de los números naturales. Sea {an}n∈N una sucesión de númerosreales, es decir, una función

a : N −→ R.

Si ε ∈ R+ y n,m ∈ N, se dice que el número real L es el límite de {an}n∈N,lim

n→∞an = L, si

∀ε ∃n ∀m ((m ≥ n) → |am − L| < ε).

La formalización matemática de la condición limn→∞

an 6= L es

∃ε ∀n ∃m ((m ≥ n) ∧ |am − L| ≥ ε).

Ejemplo 6.4.6 Vamos a formalizar el siguiente razonamiento [C]:

Sólo las buenas personas ayudan a los pobres. Ninguna buenapersona es a�cionada a la fotografía. Antonio ayuda a Juan.Antonio es a�cionado a la fotografía. Entonces, Juan es pobre.

Sea D el dominio de las personas, a la constante Antonio y j la constanteJuan. De�namos los siguientes predicados:

P (x) : x es buena persona,

Q(x, y) : x ayuda a y,

R(x) : x es pobre,

S(x) : x es a�cionado a la fotografía.Con estas de�niciones el razonamiento dado se puede escribir como:

137

∀x∀y(Q(x, y) ∧R(y) → P (x)),

∀x(P (x) → ¬S(x)),

Q(a, j),

S(a)

R(j)

Observación 6.4.7 (Lógicas de predicados de orden superior)El cálculo de predicados de primer orden admite generalizaciones a cál-

culos de predicados de orden mayor que uno. En el cálculo de predicadosde primer orden los cuanti�cadores pueden afectar sólo a las variables y lospredicados se calculan sólo sobre términos.

En el cálculo de predicados de segundo orden, los cuanti�cadores afectantambién a predicados.

En el cálculo de tercer orden se de�nen predicados de predicados (no sólopredicados de términos).

Siguiendo añadiendo niveles de �predicados de predicados,� se sube el niveldel cálculo de predicados que se está de�niendo.

138

6.5 EjerciciosEjercicio 6.5.1 Determina cuáles de las siguientes fórmulas (en forma abre-viada) son abiertas y cuáles son cerradas. En cada caso, identi�ca las varia-bles libres y ligadas.

1. ∀x(f(x, y) → P (g(x), a, b)),

2. ∃y(∀xf(x, y) → P (g(x), a, b)),

3. ∃y∀xf(x, y) ∧ P (g(x), a, b),

4. ∃y∃xf(x, y) ∧ ¬∀xP (g(x), a, b).

Ejercicio 6.5.2 Representa en forma de árbol estructural las fórmulas delejercicio anterior y los siguientes términos:

1. f(g(a, x), h(x, i(y, b)), c),

2. f(g(x), h(x, y), i(y, b), l(x, c)).

Ejercicio 6.5.3 [HLR] Usando el principio de recursión estructural, de�nela función

Lig : F −→ P (Var),

que a cada fórmula ϕ asocia el conjunto Lig(ϕ) de sus variables ligadas.

Ejercicio 6.5.4 Formaliza las siguientes frases en lógica de primer orden.Para cada una de ellas, escribe su negación y vuelve a traducirla al lenguajenatural.

1. Sólo los cientí�cos que trabajan en áreas aplicadas son famosos.

2. Algunos caballos son salvajes.

3. Todas las personas tienen algún amigo.

4. En los números reales, el producto de cualquier número real positivopor cualquier número negativo es negativo. El producto de cualquiernúmero positivo por cualquier número positivo es positivo.

139

5. En los números naturales, el siguiente de cualquier número par no espar. El siguiente de cualquier número no par es par. El producto decualquier número par por cualquier natural es par.

6. Si el producto de dos números naturales es múltiplo de un primo, en-tonces uno de ellos es múltiplo del primo.

7. Sólo las buenas enfermeras atienden con paciencia a los enfermos tísi-cos.

8. Los a�cionados del Madrid son amigos de los a�cionados del Betis.Algunos a�cionados del Madrid son amigos de los a�cionados del Be-tis. Algunos a�cionados del Madrid sólo son amigos de a�cionados delBetis.

9. Dos hermanos nunca tienen la misma opinión respecto a todos los as-pectos de la vida.

Ejercicio 6.5.5 Formaliza el siguiente argumento en la lógica de primer or-den:

Dos personas son hermanas si tienen el mismo padre. Dos per-sonas son primas si tienen el mismo abuelo. El padre de Juan eshijo único. Por tanto: sus primos son sus hermanos.

140

Capítulo 7

Semántica de la lógica de primerorden. Teoría interpretativa

Como ya hicimos en el capítulo 4 para la lógica proposicional, en este capítulovamos a estudiar la semántica y sus sistemas de demostración en la lógica deprimer orden. Volvemos a recordar sus de�niciones:

La semántica es la de�nición de un conjunto de signi�cados (generalmen-te verdadero o falso) que se puedan asociar a una expresión bien construida.Permite de�nir la validez de un expresión o de un razonamiento.

Los sistemas de demostración son sistemas formales que permiten ave-riguar cuándo una expresión o un razonamiento son válidos. En el contextode la semántica se denominan teoría interpretativa.

Volveremos a estudiar los conceptos fundamentales de validez de una fór-mula, de consecuencia lógica y de equivalencia entre fórmulas en el contextomás complejo y detallado de la lógica de primer orden.

A pesar de las muchas analogías entre la semántica de la lógica proposi-cional y la de la lógica de primer orden, veremos que hay varias diferenciasentre ellas. La principal es que en la lógica de primer orden no hay un algorit-mo de decisión de validez de fórmulas (como veremos, se pierde la propiedadde decidibilidad). Los métodos de las tablas de verdad y de los tableaux dela lógica proposicional no se pueden extender a la lógica de primer orden.

141

142

7.1 Interpretaciones en lógica de primer ordenPara asignar un signi�cado a una expresión bien construida de la lógica deprimer orden necesitamos unos métodos más complejos que aquellos estudia-dos en la lógica proposicional. Este hecho es debido a la mayor precisión yvariedad de los elementos básicos del lenguaje de la lógica de primer ordeny, por tanto, a la necesidad de explicar cómo interpretar cada uno de ellosrespetando su naturaleza sintáctica.

Lo primero que se necesita es establecer un universo del discurso, undominio, para de�nir qué tipo de objetos estamos analizando.

A continuación, tendremos que de�nir cómo asignar un signi�cado, en eldominio elegido, a los elementos básicos del lenguaje.

Finalmente, los signi�cados de los elementos básicos nos proporcionarán,con un procedimiento de recursión estructural, los signi�cados de los términosy de las fórmulas.

Necesitamos entonces empezar con asignar signi�cados a constantes, fun-ciones, predicados (algo que llamaremos una interpretación) y a variables(una asignación).

Estos conceptos se corresponden al concepto de valoración visto en lalógica proposicional.

En la lógica de primer orden una signatura Σ es un conjunto de símbolosde funciones y de predicados con aridades asociadas.

Una signatura puede ser �nita o in�nita numerable. Supondremos quesea decidible, es decir, que sea posible reconocer efectivamente sus símboloscon sus aridades.

El lenguaje LΣ es el conjunto de todas las fórmulas que se pueden cons-truir a partir de los elementos de Σ.

Cuando no haga falta especi�car la signatura que se está usando, indica-remos un lenguaje simplemente con el símbolo L.

De�nición 7.1.1 Sea L un lenguaje de la lógica de primer orden. Unainterpretación es cualquier par I = (D, I) donde:

• D es un conjunto no vacío, denominado dominio de la interpretación,

• I es una función que asocia:

143

1. a cada símbolo de constante c del lenguaje un elemento cI delconjunto D,

2. a cada símbolo de función f del lenguaje con aridad n > 0 unafunción f I : Dn −→ D,

3. a cada símbolo de proposición atómica p un elemento pI delconjunto {0, 1} (una valoración),

4. a cada símbolo de predicado P del lenguaje con aridad n > 0una relación P I ⊆ Dn.

De�nición 7.1.2 Dada una interpretación I = (D, I) para un lenguaje deprimer orden, se llama asignación a una función A que asocia a cada sím-bolo de variable x un elemento xA perteneciente al conjunto D.

Observación 7.1.3 En la literatura la terminología empleada no es unifor-me: en varios textos se denomina interpretación al par formado por unaestructura (interpretación en nuestra notación) y un estado (asignaciónen nuestra notación).

En estos apuntes la de�nición de interpretación es la 7.1.1 y, por tanto,no incluye ninguna asignación. En cada caso, se tendrá que especi�car laasignación elegida para una dada interpretación.

La justi�cación de la notación elegida es que, como veremos, nuestrasde�niciones permiten de�nir más claramente los conceptos de fórmula satis-facible bajo una interpretación y de modelo de una fórmula (ver de�nición7.3.1).

Ejemplo 7.1.4 [F]Sea Σ = {a, f, g} una signatura, donde a es una constante, f es una

función unaria y g una función binaria.Vamos a ver tres posibles interpretaciones y asignaciones:1) De�nimos el dominio

D1 = {0, 1, 2, . . . } = N ∪ {0},la interpretación

I : aI = 0, f I = suc (el siguiente), gI = + (la suma),

144

y la asignaciónA : xA = 1.

2) De�nimos el dominio D2 como el conjunto de todas las posibles pala-bras que se pueden construir con el alfabeto {∗, @}, la interpretación

I : aI = ∗, f I = añade * al �nal de la palabra,

gI = + (la concatenación),y la asignación

xA = ∗@ ∗ .

3) De�nimos el dominio

D3 = {. . . ,−2,−1, 0, 1, 2, . . . } = Z,

la interpretación

I : aI = 1, f I = ant (el anterior), gI = − (la resta),

y la asignaciónA : xA = 1.

Observación 7.1.5 Hay una clara analogía entre el concepto de asignaciónde la de�nición 7.1.2 y de asignación de un estado a las variables de unprograma en un lenguaje de programación.

Si en un programa ejecutamos el comando �x := a,� el estado de la va-riable x se ha modi�cado y ahora su valor es el elemento a del conjunto deltipo de datos que se está considerando.

En nuestra notación, siendo D el dominio de una interpretación y Auna asignación para esa interpretación, el nuevo estado de la variable x esxA = a ∈ D.

NOTACIÓN: Si A es una asignación, escribiremos A[x/d] para indicaruna nueva asignación que di�ere de A sólo en la variable x, a la cual ya seha asignado el valor d ∈ D.

145

7.2 Interpretación semántica de términos y fór-mulas

El siguiente paso hacía la de�nición de signi�cados para expresiones bienconstruidas consiste en el usar el principio de recursión estructural para poderextender una interpretación y una asignación dadas a todos los términos ya todas las fórmulas. Esta extensión nos permitirá asociar valores de verdad{0, 1} a las fórmulas y estudiar su validez.

De�nición 7.2.1 (De�nición por recursión estructural de interpre-tación de términos)

Dada una interpretación I = (D, I) para un lenguaje de primer orden, ydada una asignación A para esa interpretación, se asocia a cada términodel lenguaje t un elemento tI,A perteneciente a D de la siguiente forma:

1. Base (TAt):

- si t es una constante c, entonces

tI,A = cI ,

- si t es una variable x, entonces

tI,A = xA,

2. Paso recursivo (TF): si t es un término de la forma f(t1, . . . , tn),entonces

tI,A = f I(tI,A1 , . . . , tI,A

n ).

Ejemplo 7.2.2 Usando las de�niciones del ejemplo anterior 7.1.4, los tér-minos

t1 = f(g(f(a), f(x)))

yt2 = {f(g(x, f(g(x, f(a)))))}

se interpretan como se describe a continuación:1)

tI,A1 = suc(suc(0) + suc(1)) = 4,

146

tI,A2 = suc(1 + suc(1 + suc(0))) = 5.

2)

tI,A1 = f I(f I(∗) + f I(∗@∗)) = f I(∗ ∗+ ∗@ ∗ ∗) = ∗ ∗ ∗@ ∗ ∗ ∗ .

tI,A2 = f I(∗@ ∗+f I(∗@ ∗+f I(∗))) =

= f I(∗@ ∗+ ∗@ ∗ ∗ ∗ ∗) = ∗@ ∗ ∗@ ∗ ∗ ∗ ∗ ∗ .

3)tI,A1 = ant(ant(1)− ant(1)) = −1,

tI,A2 = ant(xA − ant(xA − ant(1))) = ant(xA − ant(xA)) = ant(1) = 0.

El signi�cado de una fórmula, �jada una interpretación y una asignación,tiene que ser un valor de verdad. Seguiremos usando 0 para representar elvalor falso y 1 para representar el valor verdadero.

La siguiente de�nición nos permite calcular valores de verdad de fórmulas.

De�nición 7.2.3 (De�nición por recursión estructural de interpre-tación de fórmulas)

Dada una interpretación I = (D, I) para un lenguaje de primer orden, ydada una asignación A para esa interpretación, se asocia a cada fórmuladel lenguaje ϕ un valor de verdad ϕI,A perteneciente a {0, 1} de lasiguiente forma:

1. Base (FAt):

- ⊥I,A = 0 ; >I,A = 1,

- si p es una proposición atómica, pI,A = pI ,

- si s = t es la igualdad entre dos términos,

(s = t)I,A =

{1 si sI,A = tI,A,

0 si sI,A no es igual a tI,A,

- si ϕ = P (t1, . . . , tn), entonces

ϕI,A = 1 si y sólo si (tI,A1 , . . . , tI,A

n ) ∈ P I ,

es decir, si y sólo si los elementos (tI,A1 , . . . , tI,A

n ) están relaciona-dos mediante la relación P I ,

147

2. Paso recursivo:

- (F¬): si ϕ = ¬ψ, entonces

ϕI,A = ¬(ψI,A),

siendo ¬(0) = 1 y ¬(1) = 0,

- (F◦): si ϕ = (ϕ1 ◦ ϕ2), entonces

ϕI,A = ϕI,A1 ◦ ϕI,A

2 ,

donde el valor de ϕI,A1 ◦ ϕI,A

2 , viene dado por la tabla 7.1, quecoincide con la tabla 4.1 de la lógica proposicional:

ϕI,A1 ϕI,A

2 ¬ϕI,A1 ∧ ∨ → ↔

0 0 1 0 0 1 10 1 1 0 1 1 01 0 0 0 1 0 01 1 0 1 1 1 1

Tabla 7.1: Valores de verdad de los conectivos

- (F∃): si ϕ = ∃xψ, entonces ϕI,A = 1 si y sólo si existe algúnelemento del dominio D tal que, después de asignar ese valor a lavariable x en ψ, se tiene ψI,A = 1.

De forma equivalente, ϕI,A = 1 si y sólo si existe algún d ∈ D talque ψI,A[x/d] = 1,

- (F∀): si ϕ = ∀xψ, entonces ϕI,A = 1 si y sólo si se tiene ψI,A = 1para cualquier posible asignación de un elemento del dominio D ala variable x en ψ.

De forma equivalente, ϕI,A = 1 si y sólo si para todo d ∈ D severi�ca que ψI,A[x/d] = 1.

148

Ejemplos 7.2.4 1) Consideremos la fórmula

ϕ = ∃x(P (f(x), a)).

En la interpretación (D1, I1) de�nida por:

D1 = R, aI1 = 2, f I1(x) = x2, P I1 = {(x, y) ∈ Z× Z : x = y},

la fórmula ϕ se escribe∃x(x2 = 2)

y tiene valor 1 ya que existe la raíz cuadrada de 2.En la interpretación (D2, I2) de�nida por:

D2 = C, aI1 = −2, f I2(x) = x2, P I2 = {(x, y) ∈ Z× Z : x = y},

la fórmula ϕ se escribe∃x(x2 = −2)

tiene valor 1 ya que todo número complejo tiene dos raíces cuadradas com-plejas.

2) Consideremos la fórmula

ϕ = ∀x∀y(P (f(x, y), a) → P (x, y))

en la interpretación (D1, I1) de�nida por:

D1 = Z, aI1 = 0, f I1(x, y) = x− y, P I1 = {(x, y) ∈ Z× Z : x < y}.

Con la interpretación dada, la fórmula ϕ se escribe

∀x∀y((x− y < 0) → x < y)

y tiene valor 1.Sin embargo, si consideramos la interpretación (D2, I2) de�nida por:

D2 = Z, aI2 = 4, f I2(x, y) = x− y, P I2 = {(x, y) ∈ Z× Z : x < y},

entonces ϕI,A2 = 0. En efecto, si x = 5 y y = 2, se obtiene que (x−y < 4)es cierta, pero x < y es falsa.

149

7.3 Validez semántica de fórmulas: modelosLas de�niciones y resultados del párrafo anterior nos permiten de�nir el cál-culo de los valores de verdad de una fórmula. Las siguientes de�niciones sonanálogas a las de�niciones de satisfacibilidad y validez vistas para fórmulasproposicionales y nos permiten estudiar la validez y clasi�car las fórmulas dela lógica de primer orden.

De�nición 7.3.1

• Se dice que una fórmula ϕ es satisfacible bajo una interpretación(D, I) cuando se veri�ca ϕI,A = 1 para alguna asignación A.

• Se dice que una fórmula ϕ es satisfacible cuando es satisfacible bajoalguna interpretación (D, I). Por tanto, una fórmula ϕ es satisfacible siexisten al menos una interpretación (D, I) y una asignación A (relativaa esa interpretación) tales que ϕI,A = 1.

• Si una fórmula no es satisfacible se dice que es insatisfacible.

• Se dice que una fórmula ϕ es verdadera bajo una interpretaciónI = (D, I) cuando se veri�ca ϕI,A = 1 para cualquier asignación A.En este caso se dice también que I es un modelo de ϕ y se escribeI |= ϕ.

• Se dice que una fórmula ϕ es válida cuando es verdadera bajo cualquierinterpretación, y se denota |= ϕ. Por tanto, una fórmula ϕ es válidasi para toda interpretación (D, I) y una asignación A (relativa a esainterpretación) se veri�ca que ϕI,A = 1.

• Si una fórmula no es válida se dice que es falsi�cable.

Observación 7.3.2 El concepto de fórmula insatisfacible en LPO se corres-ponde al concepto de fórmula insatisfacible (o contradicción) en LP. Es unafórmula que es siempre falsa.

El concepto de fórmula válida en LPO se corresponde al concepto de fór-mula válida (o tautología) en LP. Es una fórmula que es siempre verdadera.

Ejemplo 7.3.3 [F] Sea

ϕ : ∃yR(x, f(y, y)).

150

Siendo la variable x libre, ϕ es abierta.Sean D = {1, 2, 3, . . . } = N, RI = “ =� y f I = +.Entonces, para una asignación A ,

ϕI,A : ∃y(xA = 2y).

Si A es tal que xA es un numero par, entonces ϕI,A = 1.Si A es tal que xA es un numero impar, entonces ϕI,A = 0.Se sigue que ϕ es satisfacible bajo (D, I), pero no es verdadera bajo

(D, I). En particular, ϕ no es válida.Ejemplo 7.3.4 [C] Sea

ϕ : ∀x(P (x) → R(x)) → ∃yQ(y).

Sean D = {a, b, c}, P I = {a, b}, RI = {b} y QI = ∅.Usando la siguiente tabla (el dominio D contiene sólo tres elementos)

podemos determinar el valor de la subfórmula ∀x(P (x) → R(x)) :

x P I(x) RI(x) (P (x) → R(x))I (∀x(P (x) → R(x)))I

a 1 0 0b 1 1 1 0c 0 0 1

Se sigue que (∀x(P (x) → R(x)))I = 0 (esta conclusión se podría haber dedu-cido mirando sólo a la primera �la de la tabla). Por tanto, la fórmula inicialϕ tiene valor 1 bajo la interpretación dada, siendo una implicación con pre-misa siempre falsa. Se deduce que la interpretación (D, I) es un modelo deϕ.

Observación 7.3.5 1) Una fórmula ϕ es válida si y sólo si su negación,¬ϕ, es insatisfacible.

2) Si una fórmula ϕ es cerrada, dada una interpretación (D, I), su valorde verdad no depende de la asignación elegida y se puede denotar ϕI .

En este caso ϕ es satisfacible bajo (D, I) si y sólo si es verdadera bajo(D, I).

3) Si una fórmula ϕ (no cerrada) contiene las variables libres {x1, x2, . . . , xn},se llama cierre universal de ϕ a la fórmula cerrada

∀x1∀x2 . . . ∀xnϕ(x1, x2, . . . , xn).

Por tanto, en el caso de una fórmula ϕ no cerrada:

151

• ϕ es verdadera bajo (D, I) si y sólo si ∀x1∀x2 . . . ∀xnϕ(x1, x2, . . . , xn)es verdadera bajo (D, I) y

• ϕ es válida si y sólo si ∀x1∀x2 . . . ∀xnϕ(x1, x2, . . . , xn) es válida.

NOTA: de las anteriores observaciones se sigue que basta estudiar lavalidez de fórmulas cerradas.

7.4 Evaluación semántica de deduccionesOtro concepto fundamental que vamos a de�nir es el concepto de consecuen-cia lógica.

Las de�niciones son similares a las vistas en lógica proposicional, teniendoen cuenta que tenemos que reemplazar el concepto de valoración por los deinterpretación y asignación.

De�nición 7.4.1 Se dice que una fórmula ϕ es consecuencia lógica de unconjunto �nito de fórmulas Φ = {ϕ1, ϕ2, . . . ϕn} si cualquier interpretación(D, I) y cualquier asignación A que satisfacen todo elemento del conjuntoΦ satisfacen también la fórmula ϕ.

De forma equivalente, ϕ es consecuencia lógica de Φ si ϕI,Ai = 1 para

todo i ∈ {1, 2, . . . , n} implica ϕI,A = 1.Si ϕ es consecuencia lógica de Φ también se dice que Φ implica lógi-

camente a ϕ y se escribe Φ |= ϕ.

A continuación recordamos la de�nición de razonamiento válido y la no-tación empleada en el capítulo 4.

De�nición 7.4.2 Sean Φ = {ϕ1, ϕ2, . . . ϕn} un conjunto �nito de fórmulasy ϕ una fórmula. Se de�ne deducción o razonamiento a la fórmula

((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) → ϕ).

Se dice que el razonamiento anterior es correcto o lógicamente válidosi

(ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) |= ϕ,

es decir, si el conjunto Φ de las premisas o hipótesis del razonamientoimplica lógicamente a la conclusión o tesis ϕ.

152

Usando la notación ya empleada para la lógica proposicional, para dis-tinguir las premisas de la conclusión, el razonamiento anterior se suele repre-sentar por

ϕ1...

ϕn

ϕ

El siguiente teorema extiende a la lógica de primer orden la relación exis-tente entre la validez de una fórmula y el concepto de de consecuencia lógicaya vista en el contexto de la lógica proposicional.

Teorema 7.4.3 [HLR]Sean Φ = {ϕ1, ϕ2, . . . ϕn} un conjunto �nito de fórmulas y ϕ una fór-

mula.La siguientes a�rmaciones son equivalentes:1) ϕ es consecuencia lógica de Φ,2) (ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) → ϕ es una fórmula válida (y se escribe |=

((ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn) → ϕ)),3) ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn ∧ ¬ϕ es insatisfacible (Reducción al absurdo).

Ejemplo 7.4.4 Volvamos a considerar el razonamiento

Todos los hombres son mortales,Sócrates es un hombre,Sócrates es mortal.

Vimos que este razonamiento no es válido en lógica proposicional.Su formalización en lógica de primer orden es

∀x(H(x) → M(x)),H(s),M(s).

En este caso Φ = {∀x(H(x) → M(x)), H(s)} y ϕ : M(s).Queremos veri�car si Φ implica lógicamente ϕ.

153

|= t = t Re�exividad de la igualdadt = t′ |= t′ = t Simetría de la igualdad{t = t′, t′ = t′′} |= t = t′′ Transitividad de la igualdad{ϕ[x/t], t = t′} |= ϕ[x/t′] Sustitutividad de la igualdad∀xϕ(x) |= ϕ[x/t] Hipótesis universalϕ[x/t] |= ∃xϕ(x) Tesis existencial

Tabla 7.2: Tabla de algunas implicaciones lógicas

Sean (D, I) y A tales que

(∀x(H(x) → M(x)))I,A = 1, (H(s))I,A = 1.

Se trata de veri�car si, necesariamente, tiene que ser M(s)I,A = 1.Por de�nición, (∀x(H(x) → M(x)))I,A = 1 si y sólo si (H(x) →

M(x)))I,A = 1 para todo xA ∈ D. En particular, (H(s) → M(s)))I,A = 1.Siendo H(s)I,A y M(s)I,A fórmulas proposicionales, la condición anterior esequivalente a (¬H(s) ∨M(s)))I,A = 1.

Por hipótesis sabemos que (H(s))I,A = 1, es decir, sabemos que (¬H(s))I,A =0.

Se sigue que para que se veri�que (¬H(s) ∨M(s)))I,A = 1 tiene que ser(M(s))I,A = 1.

Por tanto Φ implica lógicamente ϕ.

Ejemplo 7.4.5 [HLR] Se puede veri�car (ver ejercicio 7.6.7) que las fór-mulas de la tabla 7.2 son implicaciones lógicas.

7.5 Equivalencia de fórmulas7.5.1 Sustitución de una variable por un términoSea ϕ una fórmula que contenga una variable x. Si queremos sustituir la va-riable x por un término t para obtener la nueva fórmula ϕ[x/t], es necesariono modi�car el signi�cado de la fórmulas original.

En la nueva fórmula ϕ[x/t], ver [HLR],

• sólo las apariciones libres de x en ϕ se reemplazan por t,

154

• si algún cuanti�cador de ϕ hace que queden ligadas variables de tdespués de la sustitución, la variable ligada de esa cuanti�cación sereemplaza por otra.

Ejemplo 7.5.1 [MH]Sea

ϕ : ∀xR(x, y)

y sea I = (D, I) la interpretación con dominio D = N (los números natu-rales) y RI(x, y) = {(x, y) ∈ N × N : x ≤ y} (la relación de orden usual enN ).

Sustituyendo la variable libre y por z obtenemos la fórmula

ϕ[y/z] : ∀xR(x, z),

y no se altera el signi�cado de ϕ. Las dos fórmulas son falsas bajo I =(D, I), ya que el conjunto N no tiene máximo.

Sin embargo, si sustituimos y por x obtenemos la fórmula

ϕ[y/x] : ∀xR(x, x)

que es verdadera bajo I = (D, I), siendo cierto que un cualquier númeronatural n veri�ca que n ≤ n (es la propiedad re�exiva de la relación).

Para sustituir y por x sin alterar el signi�cado de la fórmula y el tipode ocurrencia de sus variables, tendríamos que cambiar de nombre tambiéna la variable x. Por ejemplo, se puede sustituir x por v y y por x. Así seobtiene la fórmula:

ϕ[x/v, y/x] : ∀vR(v, x).

Respetando los dos criterios anteriores, se puede de�nir recursivamentey rigurosamente la noción de sustitución de una variable por un término.Además, se puede demostrar el lema de sustitución [HLR], que a�rmaque interpretar la fórmula ϕ[x/t] en una interpretación I = (D, I) y unaasignación A es lo mismo que interpretar la fórmula original ϕ en la mismainterpretación I = (D, I) y en la asignación A[x/t].

Ejemplo 7.5.2 [HLR] Sea ϕ : ∃z(x · z = y) en el dominio de los númerosnaturales N con el producto y la suma usuales. Para sustituir correctamentela variable y por z + z, tendremos que escribir

ϕ[y/z + z] : ∃u(x · u = z + z).

155

Observación 7.5.3 En informática, la operación de sustitución es impor-tante en la veri�cación de programas. La ejecución de un programa tienecomo efecto la transformación del estado de unas variables de una condicióninicial a una condición �nal. Veri�car un programa consiste en demostrarque, si el estado inicial de las variables cumple una cierta condición inicial,entonces su estado �nal cumple con la condición �nal deseada. Las condicio-nes iniciales y �nales se suelen representar por medio de fórmulas de la lógicade primer orden. Para asignar valores a estas condiciones se introduce unainterpretación que representa el tipo de datos sobre el cuál se puede operar(ver, por ejemplo, [HLR] o [C]).

7.5.2 Equivalencia de fórmulasEl último concepto fundamental que vamos a estudiar en este capítulo es elconcepto de equivalencia lógica entre fórmulas. Las de�niciones y resultadosson similares a los ya estudiados para la lógica proposicional en el capítulo4. Para la lógica de primer orden tendremos que añadir a nuestra lista lasequivalencias relativas a los cuanti�cadores, que no aparecen en la lógicaproposicional.

De�nición 7.5.4 Sean ϕ y ψ dos fórmulas. Se dice que ϕ equivale ló-gicamente a ψ si y sólo si

ϕ |= ψ y ψ |= ϕ.

Si ϕ y ψ son equivalentes se escribe ϕ ≡ ψ.

Observación 7.5.5 Se sigue de la de�nición que si ϕ y ψ son dos fór-mulas equivalentes, entonces tienen los mismos valores de verdad bajo unacualquier interpretación y asignación. Por tanto, no es difícil veri�car quelas siguientes a�rmaciones son equivalentes:

• ϕ ≡ ψ.

• |= ϕ ↔ ψ.

• |= ϕ → ψ y |= ψ → ϕ.

156

ϕ ∧ > ≡ ϕ ϕ ∧ ⊥ ≡ ⊥ Leyes de Identidadϕ ∨ > ≡ > ϕ ∨ ⊥ ≡ ϕϕ ∧ ¬ϕ ≡ ⊥ No contradicciónϕ ∨ ¬ϕ ≡ > Tercio exclusoϕ ∧ ϕ ≡ ϕ ϕ ∨ ϕ ≡ ϕ Idempotenciaϕ1 ∧ (ϕ1 ∨ ϕ2) ≡ ϕ1 ϕ1 ∨ (ϕ1 ∧ ϕ2) ≡ ϕ1 Absorciónϕ1 ∧ ϕ2 ≡ ϕ2 ∧ ϕ1 ϕ1 ∨ ϕ2 ≡ ϕ2 ∨ ϕ1 Conmutatividad(ϕ1 ↔ ϕ2) ≡ (ϕ2 ↔ ϕ1)(ϕ1 ∧ ϕ2) ∧ ϕ3 ≡ ϕ1 ∧ (ϕ2 ∧ ϕ3) Asociatividad(ϕ1 ∨ ϕ2) ∨ ϕ3 ≡ ϕ1 ∨ (ϕ2 ∨ ϕ3)ϕ1 ∧ (ϕ2 ∨ ϕ3) ≡ (ϕ1 ∧ ϕ2) ∨ (ϕ1 ∧ ϕ3) Distributividadϕ1 ∨ (ϕ2 ∧ ϕ3) ≡ (ϕ1 ∨ ϕ2) ∧ (ϕ1 ∨ ϕ3)ϕ1 → (ϕ2 ∧ ϕ3) ≡ (ϕ1 → ϕ2) ∧ (ϕ1 → ϕ3)ϕ1 → (ϕ2 ∨ ϕ3) ≡ (ϕ1 → ϕ2) ∨ (ϕ1 → ϕ3)ϕ1 ↔ (ϕ2 ∧ ϕ3) ≡ (ϕ1 ↔ ϕ2) ∧ (ϕ1 ↔ ϕ3)ϕ1 ↔ (ϕ2 ∨ ϕ3) ≡ (ϕ1 ↔ ϕ2) ∨ (ϕ1 ↔ ϕ3)¬(¬ϕ) ≡ ϕ Doble negación(ϕ1 → ϕ2) ≡ (¬ϕ2 → ¬ϕ1) Ley de contraposición¬(ϕ1 ∧ ϕ2) ≡ ¬ϕ1 ∨ ¬ϕ2 Leyes de De Morgan¬(ϕ1 ∨ ϕ2) ≡ ¬ϕ1 ∧ ¬ϕ2

ϕ1 → ϕ2 ≡ ¬ϕ1 ∨ ϕ2 Interde�niciónϕ1 ↔ ϕ2 ≡ (ϕ1 → ϕ2) ∧ (ϕ2 → ϕ1) Coimplicación

Tabla 7.3: Equivalencias relativas a conectivos lógicos

¬∀xϕ ≡ ∃x¬ϕ ¬∃xϕ ≡ ∀x¬ϕ

∀xϕ1 ∧ ∀xϕ2 ≡ ∀x(ϕ1 ∧ ϕ2) ∃xϕ1 ∨ ∃xϕ2 ≡ ∃x(ϕ1 ∨ ϕ2)

∀x∀yϕ ≡ ∀y∀xϕ ∃x∃yϕ ≡ ∃y∃xϕ

(∀xϕ1) ∨ ϕ2 ≡ ∀x(ϕ1 ∨ ϕ2) ∗ (∀xϕ1) ∧ ϕ2 ≡ ∀x(ϕ1 ∧ ϕ2) ∗(∃xϕ1) ∨ ϕ2 ≡ ∃x(ϕ1 ∨ ϕ2) ∗ (∃xϕ1) ∧ ϕ2 ≡ ∃x(ϕ1 ∧ ϕ2) ∗

∗ Sólo si x no aparece libre en ϕ2

Tabla 7.4: Equivalencias relativas a cuanti�cadores

157

Las tablas 7.3 (ver la correspondiente tabla 4.4 para la lógica proposi-cional) y 7.4 contienen las principales equivalencias relativas a conectivos ycuanti�cadores, respectivamente.

Observación 7.5.6 También en la lógica de primer orden la relación deequivalencia entre fórmulas es re�exiva, simétrica y transitiva (ver la obser-vación 4.5.4 del capítulo 4). Por tanto es una relación binaria de equivalenciasobre el conjunto de todas las fórmulas. Dos fórmulas pertenecen a la mismaclase de equivalencia si y sólo si tienen los mismos valores de verdad bajouna cualquier interpretación y asignación.

7.5.3 Equivalencia lógica y reemplazamientoLos siguientes resultados, ver [HLR], garantizan que la equivalencia lógica sepreserva si, en una dada fórmula χ, reemplazamos una subfórmula ϕ porotra subfórmula ψ, equivalente a ϕ.

Teorema 7.5.7 Sea χ(ϕ) una fórmula que contiene una subfórmula ϕ ysea χ(ψ) la fórmula obtenida reemplazando la subfórmula ϕ por ψ.

Si ϕ ≡ ψ, entoncesχ(ϕ) ≡ χ(ψ).

Teorema 7.5.8 Sean χ1 y χ2 dos fórmulas equivalentes. Reemplazando enχ1 y χ2 unos símbolos de proposiciones {p1, p2, · · · , pn} por unas fórmulas{ϕ1, ϕ2, · · · , ϕn}, se obtiene la equivalencia

χ1[p1/ϕ1, p2/ϕ2, · · · , pn/ϕn] ≡ χ2[p1/ϕ1, p2/ϕ2, · · · , pn/ϕn].

Ejemplo 7.5.9 Sea χ : ∀x(P (x, p, q) → Q(f(y))). Sabemos, por interde�ni-ción, que la subfórmula ϕ : P (x, p, q) → Q(f(y)) es equivalente a la fórmulaψ : ¬P (x, p, q) ∨Q(f(y)). Entonces

∀x(P (x, p, q) → Q(f(y))) ≡ ∀x(¬P (x, p, q) ∨Q(f(y))).

Además, si en esta última equivalencia sustituimos las proposiciones {p, q}por las fórmulas {f(y), g(u, v)}, se obtiene la equivalencia

∀x(P (x, f(y), g(u, v)) → Q(y)) ≡ ∀x(¬P (x, f(y), g(u, v)) ∨Q(y)).

158

Observación 7.5.10 (Conjuntos de conectivos)Como vimos en el capítulo 4 para la lógica proposicional, a partir de las

equivalencias de las tablas 7.3 y 7.4 es posible demostrar que en el lenguaje dela lógica de primer orden es su�ciente emplear sólo los conectivos {∃,¬,∧}.

De forma similar, los conjuntos {∃,¬,∨} y {∀,¬,∧,∨} permiten repre-sentar cualquier fórmula bien construida por medio de una fórmula equiva-lente, en la cual aparecen sólo los conectivos de los conjuntos indicados (verejercicio 7.6.11).

159

7.6 EjerciciosEjercicio 7.6.1 Dada la fórmula

ϕ : ∃y(P (y) ∨ ∀x(P (x) → Q(z))),

calcula todas las posibles interpretaciones de ϕ en el dominio de dos elemen-tos D = {a, b}.

Ejercicio 7.6.2 [C] Considera la fórmula P (y) ∨ (∀x(q → P (x))), dondeq es una proposición atómica. Se pide evaluar la fórmula anterior en lainterpretación I = (D, I) donde D = {a, b, c}, qI = 1, P I = {a, b} y con unaasignación A tal que yA = c.

Ejercicio 7.6.3 [A]Sea la frase �Todos los del vecindario odian a una persona.�a) Formaliza la frase dada en lógica de primer orden, siendo el dominio

D el conjunto de las personas.b) Sea D = {p1, p2, p3} y sea I de�nida por las condiciones:- p1 y p2 pertenecen al vecindario, pero p3 no.- p3 no odia a nadie.- p1 y p2 sólo odian a p3.Evalúa el valor de la fórmula obtenida en el apartado a) bajo la interpre-

tación (D, I).

Ejercicio 7.6.4 [A] Sea ϕ : (P (x) ∧ ∀x(R(x) ∧ P (y))) → ∃yQ(x, y).Evalúa ϕ con D = {a, b}, P I = {a}, RI = {b}, QI = {(a, a), (b, b)} yxA = a, yA = b.

Ejercicio 7.6.5 Dada la fórmula:

ϕ : (∃xP (x)) ∧ (∃xQ(x)) → ∃x(P (x) ∧Q(x)),

de�ne una interpretación tal que ϕ sea válida y una tal que no lo sea. Con-cluye que esa formula no es semánticamente válida.

Ejercicio 7.6.6 Tomando como dominio D el conjunto de las personas, for-maliza las siguientes frases. Para cada una de ellas halla una interpretaciónI = (D, I), con dominio el conjunto de las personas, que la hace falsa.

160

1. Dos hermanos que compartan el mismo coche y tengan la misma edad,necesariamente son amigos y tienen alguna a�ción en común.

2. Los jugadores de fútbol son amigos de los jugadores de pelota vasca.

3. Algunos jugadores de fútbol son amigos de los jugadores de pelota vasca.

4. Algunos jugadores de fútbol sólo son amigos de jugadores de pelota vas-ca.

Ejercicio 7.6.7 Veri�ca las implicaciones lógicas de la tabla 7.2.

Ejercicio 7.6.8 Formaliza el siguiente argumento a la lógica de primer or-den:

Los que salen hoy de viaje cogerán el autobús. Los ejecutivosviajan siempre en avión. Todos los de mi empresa viajan conmaletín. Nadie que haya viajado en avión volverá a hacerlo enautobús. Nadie viaja con maletín a no ser que sea un ejecutivo.Por tanto: nadie en mi empresa sale hoy de viaje.

Prueba la validez semántica de dicho argumento.

Ejercicio 7.6.9 Considera el dominio D = {a, b}. Sabemos inicialmenteque P (a) es cierto y P (b) es falso. Estudia la satisfacibilidad de los siguientesargumentos bajo cualquier interpretación con dominio D :

∀x(P (x) → ¬Q(x))∀x(P (x) ∧R(x))∀x(R(x) ∧ ¬Q(x))

,∃x(P (x) → ¬Q(x))∃x(P (x) ∧R(x))∃x(R(x) ∧ ¬Q(x))

Estudia la satisfacibilidad de los argumentos anteriores eliminando lashipótesis sobre P (a) y P (b). ¾Son razonamientos válidos?

Ejercicio 7.6.10 Usando las equivalencias estudiadas, simpli�ca las expre-siones halladas como negaciones formales de las frases del ejercicio 6.5.4 delcapítulo 6.

Ejercicio 7.6.11 Veri�ca que los conjuntos de conectivos de la observación7.5.10

{∃,¬,∧}, {∃,¬,∨} y {∀,¬,∧,∨}son completos en la lógica de primer orden.

161

Ejercicio 7.6.12 En cada apartado, veri�ca si las dos fórmulas dadas sonequivalentes:

a) ϕ1 : P (x) → ∀xQ(x), ϕ2 : ∀x(P (x) → Q(x)).b) ϕ1 : ∃xP (x) ∧Q(x), ϕ2 : ∃x(P (x) ∧Q(x)).

162

Capítulo 8

Teoría de la demostración

En este capítulo estudiaremos la extensión del sistema de deducción naturala la lógica de primer orden.

Recordamos que la teoría de la demostración nos proporciona métodosalternativos a los métodos semánticos para averiguar

• la validez de una fórmula: si ϕ es una fórmula válida se dice quees demostrable y se escribe ` ϕ.

• si una fórmula ϕ es consecuencia lógica de un conjunto depremisas Φ : si ϕ es consecuencia lógica de Φ se dice que ϕ esdeducible en el sistema a partir de Φ y se escribe Φ ` ϕ.

Las de�niciones generales de sistema formal axiomático, teorema, de-ducción, métodos directos y por refutación son las mismas estudiadas enla sección 5.1 del capítulo 5. Las iremos empleando a lo largo de todo elcapítulo.

También valen el teorema de la deducción 5.1.9 y su corolario 5.1.10,que permiten establecer la relación entre deducciones correctas y fórmulasválidas:

Teorema 8.0.1 (Teorema de la deducción) Sean {ϕ1, ϕ2, . . . ϕn} unconjunto de fórmulas y ϕ una fórmula. Entonces

{ϕ1, ϕ2, . . . ϕn} ` ϕ si y sólo si {ϕ1, ϕ2, . . . ϕn−1} ` (ϕn → ϕ).

Corolario 8.0.2 Dada una demostración de una deducción, es siempre po-sible encontrar una fórmula válida que la represente.

163

164

Ya comentamos que en la lógica de primer orden no existe ningún métodode demostración que sea decidible. Por tanto, la extensión de la teoría de lostableaux sintácticos a la lógica de primer orden no puede proporcionar unmétodo e�caz y �nito para establecer la satisfacibilidad de una fórmula.

8.1 De�nición del sistema de deducción naturalde Gentzen

La extensión del sistema de deducción natural de la lógica proposicional ala lógica de predicados mantiene su carácter intuitivo, ya que se basa endeducciones. Las ocho reglas de inferencia de la de�nición de este sistemadel capítulo 5 siguen valiendo y tienen ahora que ser completadas por reglasde inferencia para los cuanti�cadores.

Reglas del sistema de deducción natural para los cuanti�cadores:(I ∀): Regla de introducción del cuanti�cador universal

ϕ(y) ` ∀xϕ(x).

NOTA: la forma de interpretar esta regla NO es que de la validez deϕ(y) para un elemento del dominio y se deduce la validez de ϕ(x)para todo elemento x.

Lo que se entiende con la notación empleada es que en ϕ(y) la varia-ble y representa un cualquier elemento del dominio, no un elementoespeci�cado.Con la notación de Fitting (I ∀) se representa como:

y......` ϕ(y)

` ∀xϕ(x)

165

Notar también que y NO es una premisa auxiliar de una subdeducción.La notación de Fitting que estamos empleando es de una subdeduc-ción sin premisa y se interpreta como: si y es un símbolo de variableque no ha aparecido antes en la deducción madre y resulta que ϕ(y)es válida, entonces ∀xϕ(x) es válida.

Ejemplo 8.1.1 [A] Para poder deducir que �Todos los leones son car-nívoros� en el dominio D de los leones, siendo H(x) : x es carnívoro,se puede usar la regla (I ∀) y escribir

y` C(y)

` ∀xC(x)

(E ∀): Regla de eliminación del cuanti�cador universal

∀xϕ(x) ` ϕ(t)

para cualquier término t.

Una fórmula que se veri�ca para todo elemento del dominio, se veri�capara cualquier t.

Ejemplo 8.1.2 [A]Queremos demostrar la deducción

{∀x(ϕ(x) → ψ(x)), ϕ(a)} ` ψ(a).

1) ∀x(ϕ(x) → ψ(x)) (Premisa)2) ϕ(a) (Premisa)3) ` ϕ(a) → ψ(a) (E ∀(1))4) ` ψ(a) (E→(2,3)).

166

(I ∃): Regla de introducción del cuanti�cador existencial

ϕ(a) ` ∃xϕ(x),

para cualquier constante del dominio a.

Si ϕ(a) es verdadera, entonces ∃xϕ(x) es verdadera.

Ejemplo 8.1.3 [A] Queremos demostrar la deducción

{ϕ(b),∃xϕ(x) → ψ(a)} ` ψ(a),

siendo a y b constantes del dominio.

1) ϕ(b) (Premisa)2) ∃xϕ(x) → ψ(a) (Premisa)3) ` ∃xϕ(x) (I ∃(1))4) ` ψ(a) (E→(3,2)).

(E ∃): Regla de eliminación del cuanti�cador existencial

{∃xϕ(x), ϕ(y) → ψ} ` ψ,

donde ψ no contiene la variable libre y.

NOTA: (E ∃) NO tiene la forma ∃xϕ(x) ` ϕ(y), ya que no sabemossi y hace que ϕ(y) sea verdadera.Con la notación de Fitting (E ∃) se representa como:

1) ∃xϕ(x)

2) ϕ(y) (Premisa auxiliar)......k) ` ψ

k+1) ` ϕ(y) → ψ (I →(2,k))k+2) ` ψ (E ∃(1,(2,k))).

167

Ejemplo 8.1.4 [A]Queremos demostrar la deducción

{∃xϕ(x), ∃xψ(x)} ` ∃x∃y(ϕ(x) ∧ ψ(y)).

1) ∃xϕ(x) (Premisa)2) ∃xψ(x) (Premisa)

3) ϕ(z) (Premisa auxiliar)

4) ψ(u) (Premisa auxiliar)5) ` ϕ(z) ∧ ψ(u) (I ∧(3,4))6) ` ∃x∃y(ϕ(x) ∧ ψ(y)) (I ∃(5))

7) ` ψ(u) → ∃x∃y(ϕ(x) ∧ ψ(y)) (I →(4,6))8) ` ∃x∃y(ϕ(x) ∧ ψ(y)) (E ∃(2,7))

9) ` ϕ(z) → ∃x∃y(ϕ(x) ∧ ψ(y)) (I →(3,8))10) ` ∃x∃y(ϕ(x) ∧ ψ(y)) (E ∃(1,9)).

8.1.1 Reglas derivadas del sistema de deducción naturalA partir de las reglas de introducción y eliminación relativas a los cuanti�-cadores, podemos obtener nuevos resultados.

A continuación enunciamos algunos de ellos [A]:

• T31: (Cambio de variable cuanti�cada)

T31.1 :∀xϕ(x) ` ∀yϕ(y),

T31.2 :∀yϕ(y) ` ∀xϕ(x),

T31.3 :∃xϕ(x) ` ∃yϕ(y),

T31.4 :∃yϕ(y) ` ∃xϕ(x).

168

Demostración de T31.1 y T31.2:

1) ∀xϕ(x) (Premisa)

2) z3) ` ϕ(z) (E∀(1))

4) ` ∀yϕ(y) (I∀(2,3))

La demostración de T31.3 y T31.4 es similar.

• T32: Descenso cuanti�cacional∀xϕ(x) ` ∃xϕ(x).

• T33: ConmutatividadT33.1 :∃x∃yϕ(x, y) ` ∃y∃xϕ(x, y),

T33.2 :∃y∃xϕ(x, y) ` ∃x∃yϕ(x, y).

T33.3 :∀x∀yϕ(x, y) ` ∀y∀xϕ(x, y),

T33.4 :∀y∀xϕ(x, y) ` ∀x∀yϕ(x, y).

• T34: Reglas de la conjunciónT34.1 :∃x(ϕ(x) ∧ ψ(x)) ` ∃xϕ(x) ∧ ∃xψ(x).

T34.2 :∀xϕ(x) ∧ ∀xψ(x) ` ∀x(ϕ(x) ∧ ψ(x)),

T34.3 :∀x(ϕ(x) ∧ ψ(x)) ` ∀xϕ(x) ∧ ∀xψ(x).

T34.3 :∃x(ϕ ∧ ψ(x)) ` ϕ ∧ ∃xψ(x),

T34.4 :ϕ ∧ ∃xψ(x) ` ∃x(ϕ ∧ ψ(x)).

T34.5 :∀x(ϕ ∧ ψ(x)) ` ϕ ∧ ∀xψ(x),

T34.6 :ϕ ∧ ∀xψ(x) ` ∀x(ϕ ∧ ψ(x)).

169

• T35: Reglas de la disyunción

T35.1 :∃x(ϕ(x) ∨ ψ(x)) ` ∃xϕ(x) ∨ ∃xψ(x),

T35.2 :∃xϕ(x) ∨ ∃xψ(x) ` ∃x(ϕ(x) ∨ ψ(x)).

T35.3 :∀xϕ(x) ∨ ∀xψ(x) ` ∀x(ϕ(x) ∨ ψ(x)).

T35.4 :ϕ ∨ ∃xψ(x) ` ∃x(ϕ ∨ ψ(x)),

T35.5 :∃x(ϕ ∨ ψ(x)) ` ϕ ∨ ∃xψ(x).

T35.6 :ϕ ∨ ∀xψ(x) ` ∀x(ϕ ∨ ψ(x)),

T35.7 :∀x(ϕ ∨ ψ(x)) ` ϕ ∨ ∀xψ(x).

• T36: Reglas de la implicación

T36.1 :∃xϕ(x) → ∃xψ(x) ` ∃x(ϕ(x) → ψ(x)),

T36.2 :∀x(ϕ(x) → ψ(x)) ` ∀xϕ(x) → ∀xψ(x).

T36.3 :∃xψ(x) → ϕ ` ∃x(ψ(x) → ϕ),

T36.4 :∀x(ψ(x) → ϕ) ` ∀xψ(x) → ϕ.

T36.5 :∀x(ϕ → ψ(x)) ` ϕ → ∀xψ(x).

• T37: Reglas de eliminación de la negación de un cuanti�cador

T37.1 (E¬∀) :¬∀xϕ(x) ` ¬ϕ(a),

T37.2 (E¬∃) :¬∃xϕ(x) ` ¬ϕ(y),

donde a es una constante e y es un cualquier elemento del dominio(ver ejercicios 8.3.2 y 8.3.3).

170

8.2 Corrección, completitud y decidibilidadEn el capítulo 5 vimos que los sistemas de demostración estudiados para lalógica proposicional cumplen las tres propiedades de completitud, correccióny decidibilidad.

Existen varios sistemas de demostración en lógica de primer orden que soncompletos y correctos (la completitud fue demostrada por Gödel en 1930).

Sin embargo, no existe ningún sistema de demostración en LPO que seadecidible.

La coherencia entre teoría interpretativa y teoría de la demostración axio-mática sigue valiendo para la lógica de primer orden:

Teorema 8.2.1 [A] Una fórmula de la lógica de primer orden es semánti-camente válida en teoría interpretativa si y sólo si es formalmente válida enteoría de la demostración axiomática.

A continuación veremos como este teorema implica la completitud y lacoherencia de los sistemas de demostración de la lógica de primer orden.

• CompletitudRecordamos que se dice que un sistema de demostración axiomático escompleto si es capaz de demostrar cualquier fórmula semánticamenteválida y deducir cualquier consecuencia lógica.Por tanto, el teorema 8.2.1 anterior tiene como consecuencia la com-pletitud del cálculo de predicados de primer orden.

• CorrecciónRecordamos que se dice que un sistema de demostración es correcto(consistente, coherente) si todas las fórmulas demostrables en elsistema son semánticamente válidas y todas las fórmulas deducibles enel sistema a partir de un conjunto de premisas son consecuencia lógicade dichas premisas.Por tanto, el teorema 8.2.1 anterior tiene como consecuencia tambiénla corrección del cálculo de predicados de primer orden.

171

• DecidibilidadFinalmente, recordamos que se dice que un sistema de demostración esdecidible si proporciona un procedimiento general y �nito (aplicablea cualquier fórmula y que termine) que permita decidir si una fórmulaes válida o deducible a partir de un conjunto de fórmulas.No existe ningún sistema de demostración en LPO que seadecidible: Church demostró en 1936 que no existe ningún algoritmoque permita decidir si una fórmula cualquiera de la lógica de primerorden es o no es válida, es decir, la validez de fórmulas en LPO es unproblema indecidible (obsérvese que el mismo problema en lógica deproposiciones sí es decidible: en este caso, para saber si una fórmula esválida basta con calcular su tabla de verdad).Aunque la validez de las fórmulas en LPO no es decidible en general,sí lo es en los siguientes casos particulares:

� cuando se consideran exclusivamente dominios �nitos,� cuando se admiten exclusivamente predicados monádicos,� incluso en el caso de dominios in�nitos y predicados poliádicos,

existen algunas clases particulares de fórmulas para las que suvalidez sí es decidible.

Por otro lado, la validez de las fórmulas en LPO, aunque indecidible,es un problema semi-decidible en el siguiente sentido: existen sistemasde demostración tales que

� si una fórmula es válida, son capaces de demostrar que lo es,� para fórmulas no válidas, el proceso puede no terminar nunca.

172

8.3 EjerciciosEjercicio 8.3.1 En el sistema de deducción natural, demuestra las reglas dedescenso cuanti�cacional T32 y de conmutatividad T33.

Ejercicio 8.3.2 En el sistema de deducción natural, demuestra los siguien-tes teoremas:

` ∃x¬ϕ(x) → ¬∀xϕ(x),

` ∀x¬ϕ(x) → ¬∃xϕ(x),

` ¬∃xϕ(x) → ∀x¬ϕ(x),

` ¬∀xϕ(x) → ∃x¬ϕ(x).

Ejercicio 8.3.3 [MH] Usando los resultados del ejercicio anterior, demues-tra la validez de las siguientes reglas en el sistema de deducción natural:

(E¬∀) : ¬∀xϕ(x) ` ¬ϕ(a),

(E¬∃) : ¬∃xϕ(x) ` ¬ϕ(y),

donde a es una constante e y es un cualquier elemento del dominio.

Ejercicio 8.3.4 [A] Formaliza el siguiente razonamiento en el dominio Dde todos los seres. En el sistema de deducción natural, demuestra su validez.

Ningún pato baila el vals cuando se lo piden.Ningún o�cial declina una petición de bailar el vals.Todas mis aves del corral son patos.Por tanto: mis aves del corral no son o�ciales.

Bibliografía

[A] L. Arenas, Lógica formal para informáticos. Ed. Diaz de Santos,1996.

[AFJM] J. Aranda, J.L. Fernández, J. Jiménez, F. Morilla,Fundamentosde Lógica Matemática. Ed. Sanz y Torres, 1999.

[C] J. Cuena, Lógica matemática. Alianza Editorial, 1985.

[CM] R. Criado, R. Muñoz, Apuntes de Matemática Discreta,www.escet.urjc.es/ matemati/md_iti/apuntes/md00.pdf.

[F] M. Fitting, First�order logic and automated theorem proving.Springer Graduate Texts in Computer Science. Berlín, 1996.

[HLR] M. A. Hortalá, J. Leach, M. Rodríguez. Matemática Discreta yLógica Matemática. Editorial Complutense, 2001.

[MH] M. Manzano, A. Huertas, Lógica para Principiantes. AlianzaEditorial, 2004.

[R] K. H. Rosen. Matemática discreta y sus aplicaciones. McGrawHill, 2004.

[UNED1] http://www.educajob.com/xmoned/temarios_elaborados/�loso�a/Delalógica%20cl%E1sica%20a%20la%20l%F3gica%20simb% F3lica.htm.