Source: https://www.scribd.com/document/68800767/ejercicios-LI-2011-12
Timestamp: 2016-09-28 11:19:38+00:00

Document:
ejercicios-LI-2011-12
BrowseBrowseInterestsBiography & MemoirBusiness & LeadershipFiction & LiteraturePolitics & EconomyHealth & WellnessSociety & CultureHappiness & Self-HelpMystery, Thriller & CrimeHistoryYoung AdultBrowse byBooksAudiobooksComicsSheet MusicBrowse allUploadSign inJoinBooksAudiobooksComicsSheet MusicWelcome to Scribd! Start your free trial and access books, documents and more.Find out moreEjercicios de “Lógica informática” (2011–12)
José A. Alonso Jiménez Andrés Cordón Franco María J. Hidalgo Doblado
Grupo de Lógica Computacional Dpto. de Ciencias de la Computación e Inteligencia Artiﬁcial Universidad de Sevilla Sevilla, 15 de Septiembre de 2011
Se permite: copiar, distribuir y comunicar públicamente la obra hacer obras derivadas Bajo las condiciones siguientes: Reconocimiento. Debe reconocer los créditos de la obra de la manera especiﬁcada por el autor. No comercial. No puede utilizar esta obra para ﬁnes comerciales. Compartir bajo la misma licencia. Si altera o transforma esta obra, o genera una obra derivada, sólo puede distribuir la obra generada bajo una licencia idéntica a ésta. Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licencia de esta obra. Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular de los derechos de autor.
Esto es un resumen del texto legal (la licencia completa). Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie una carta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.
1. Sintaxis y semántica de la lógica proposicional 7 1.1. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2. Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3. Ejercios de exámenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2. Deducción natural proposicional 15 2.1. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2. Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3. Ejercicios de exámenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3. Tableros semánticos 3.1. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Ejercicios de exámenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Formales normales 4.1. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Ejercicios de exámenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Resolución proposicional 5.1. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Ejercicios de exámenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 23 24 25 29 29 31 32 35 35 38 40
6. Sintaxis y semántica de la lógica de primer orden 43 6.1. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.2. Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.3. Ejercicios de exámenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 7. Deducción natural de primer orden 59 7.1. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3
. . . . . . . . . . Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . Modelos de Herbrand 73 10. . . . . . . .2. . . . Resolución 77 11. . . .1. . . . . . . . . . . . 69 10. 60 7. . . . . Ejercicios resueltos . . . . 67 9. Cláusulas. . .1. . . . . . . . . . . . . . . . . . 77 11. Ejercicios resueltos . Tableros semánticos 67 8. . . . . . . . . . . . . . . . . . . . . . . . . . . Ejercicios de exámenes . . Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . .2. . . . . . . .2. . . . . . . . . . . . . . . . . Ejercicios propuestos . . . . . . 79 Bibliografía 92
. . . . . . Ejercicios propuestos . . . . Modelos de Herbrand. . . . . . . . . . . . . . . . . . . . . Ejercios propuestos . . . . . . .1. . . . . . . . . . . . . . . . Formas normales. . . . . . . . . . . . 63 8. . . . . . . . .3. . . 73 11.4
7. . . .1. . . . . 67 8. Cláusulas 69 9. . . . .
Ejercicios de exámenes: son ejercicios de exámenes de cursos anteriores y sus soluciones se encuentran en Soluciones de exámenes de Lógica informática. Ejercicios propuestos.Introducción
En el presente volumen se presentan los enunciados de los ejercicios del curso de “Lógica informática (2010–11)”. Este volumen es complementario de Temas de "Lógica informática"(2010-11) y Soluciones de exámenes de Lógica informática.
. En cada tema los ejercicios se han dividido en tres grupos: Ejercicios resueltos: son ejercicios comentados en las clases cuyas soluciones se encuentran en las transparencias y en Temas de "Lógica informática"(2010-11).
2 Deﬁnir por recursión sobre fórmulas las siguientes funciones 1. np(( p → (¬q ∨ p))) = 4. p 2. 2.Tema 1 Sintaxis y semántica de la lógica proposicional
. Ejercicio 1. ( p) 3. ¬q ∨ p. ( p ∨ ∧q) Ejercicio 1. p ∨ ¬q 5.1. ( p ∨ ¬q) 4. Ejercicios resueltos
Ejercicio 1. Por ejemplo. p. Subf ( F ) que calcula el conjunto de las subfórmulas de la fórmula F. ¬( p ∨ p) 6. (( p → q) ∨ (q → p)) 7. np( F ) que calcula el número de paréntesis de la fórmula F. q}.3 Demostrar por inducción que todas las fórmulas proposicionales tienen un número par de paréntesis. ¬q.1 Determinar cuáles de las siguientes expresiones son fórmulas proposicionales: 1. Subf ( p → ¬q ∨ p) = { p → ¬q ∨ p. Por ejemplo.
10 En cada caso.5 Calcular el valor de la fórmula ( p ∨ q) ∧ (¬q ∨ r ) en las siguientes interpretaciones 1.7 Determinar cuáles de las siguientes interpretaciones es modelo de la fórmula ( p ∨ q) ∧ (¬q ∨ r ) 1. 2. determinar todos los modelos de la fórmula proposicional correspondiente: 1. construir el árbol de análisis y determinar todas sus subfórmulas. I1 tal que I1 ( p) = I1 (r ) = 1. p ∧ ¬ p Ejercicio 1.9 Demostrar o refutar las siguientes proposiciones: 1. I1 tal que I1 ( p) = I1 (r ) = 1.4 Para la siguiente fórmula p → ¬q ∨ p escribir la fórmula con paréntesis. Ejercicio 1.8 Determinar si las siguientes fórmulas son satisfacible o insatisfacible. Si F es satisfacible. p → q
. Ejercicio 1. entonces I1 ( F ) = I2 ( F ). ( p → q) ∧ (q → r ) 2. I2 ( p) = I2 (q) = 0 Ejercicio 1. Ejercicio 1. I2 tal que I2 (r ) = 1. Sintaxis y semántica de la lógica proposicional
Ejercicio 1. ( p → q) ∨ (q → p) 2. I1 (q) = 0 2. I2 . ( p → q) ∧ ¬( p → q) 3. entonces F es satisfacible. entonces ¬ F es insatisfacible.8
Tema 1. Si F es tautología. F es tautología syss ¬ F es insatisfacible. I2 tal que I2 (r ) = 1. 1. I2 ( p) = I2 (q) = 0 Ejercicio 1. 3. si I1 ( p) = I2 ( p) para todos las variables proposicionales de F.6 Demostrar que para toda fórmula F se tiene que para todo par de intepretaciones I1 . I1 (q) = 0 2.
Conmutatividad: F ∨ G ≡ G ∨ F F∧G ≡ G∧F 3. ( p → q) ∨ (q → p) 7. contingentes y contradicciones. p ∧ ¬ p 6. 7. 7. ¿Cuáles son satisfacibles? ¿Cuáles son insatisfacibles? Ejercicio 1. 6. ( p ↔ q) ∨ (q ↔ p) Clasiﬁcar las fórmulas anteriores en tautologías. 4. p ∨ ¬ p 5. Leyes de De Morgan: ¬( F ∧ G ) ≡ ¬ F ∨ ¬ G ¬( F ∨ G ) ≡ ¬ F ∧ ¬ G
. Distributividad: F ∧ ( G ∨ H ) ≡ ( F ∧ G ) ∨ ( F ∧ H ) F ∨ (G ∧ H ) ≡ ( F ∨ G) ∧ ( F ∨ H ) 6.1. Asociatividad: F ∨ ( G ∨ H ) ≡ ( F ∨ G ) ∨ H F ∧ (G ∧ H ) ≡ ( F ∧ G) ∧ H 4.11 Demostrar que las fórmulas que aparecen en la transparencia 19 del tema 1 son tautologías: 1. Absorción: F ∧ ( F ∨ G ) ≡ F F ∨ ( F ∧ G) ≡ F 5.1. 3. Idempotencia: F ∨ F ≡ F F∧F ≡ F 2. 2. 8.12 Demostrar las equivalencias lógicas que aparecen en la transparencia 20 del tema 1: 1. 5. F→F F ∨ ¬F ¬( F ∧ ¬ F ) (¬ F → F ) → F ¬ F → ( F → G) (( F → G ) → F ) → F ( F → G) ∧ F → G ( F → G) ∧ ¬G → ¬ F ley de identidad ley del tercio excluso principio de no contradicción ley de Clavius ley de Duns Scoto ley de Peirce modus ponens modus tollens
Ejercicio 1. Doble negación: ¬¬ F ≡ F. Ejercicios resueltos
entonces S |= G. I1 (r ) = 1. q → r }. { p → q. ¬r } Ejercicio 1. Para todo conjunto de fórmula S1 y toda fórmula F. Juan no ha llegado tarde a la reunión. Para todo conjunto de fórmula S1 y todo par de fórmulas F. { p} |= p ∧ q Ejercicio 1. q → r } |= p → r 2. 3. si S1 |= F y S1 ⊆ S2 .17 Demostrar o refutar las siguientes proposiciones: 1. G. I2 (r ) = 0. El tren llegó a las 7. Ejercicio 1. entonces S2 |= F. I1 tal que I1 ( p) = 1. Fn .
. 1. { F1 . I2 tal que I2 ( p) = 0. Para todo conjunto de fórmula S. ¬( F1 ∧ · · · ∧ Fn → G ) es insatisfacible 4. Sintaxis y semántica de la lógica proposicional
Ejercicio 1. . I2 (q) = 1. . entonces Juan llegará tarde a la reunión. S2 = {( p ∨ q) ∧ (¬q ∨ r ). I1 (q) = 0.19 Determinar si los siguientes argumentos son lógicamente correctos: 1. 2. Fn } |= G 2. 2. { F1 . ¬ G } es inconsistente Ejercicio 1.15 Calcular los modelos de los siguientes conjuntos de fórmulas y decidir cuáles son consistente. p → r. . . . habían taxis en la estación. .14 Determinar cuáles de las siguientes interpretaciones es modelo del conjunto de fórmulas S = {( p ∨ q) ∧ (¬q ∨ r ). . Por tanto. S |= S. .16 Decidir cuáles de las siguientes aﬁrmaciones son verdaderas: 1. S1 = {( p ∨ q) ∧ (¬q ∨ r ).18 Demostrar que las siguientes condiciones son equivalentes: 1.10
Tema 1. Ejercicio 1. Si el tren llega a las 7 y no hay taxis en la estación.13 Demostrar que F ≡ G syss |= F ↔ G. si S |= F y { F } |= G. p → r } 2. Ejercicio 1. 1. |= F1 ∧ · · · ∧ Fn → G 3.
Ejercicio 1. Por ejemplo. se concluye que el animal es una cebra. entonces B y C son veraces y A es mentiroso” 3. B y C. 2. npd(( p → (¬q ∨ p))) = 2. la de los veraces (que siempre dicen la verdad) y la de los mentirosos (que siempre mienten). npi(( p → (¬q ∨ p))) = 2.22 Deﬁnir por recursión sobre fórmulas las siguientes funciones 1. Los ungulados de cuello largo son jirafas. pezuñas y rayas negras.
1. npi( F ) que calcula el número de paréntesis izquierdos de la fórmula F. Los ungulados con rayas negras son cebras. A dice “B y C son veraces syss C es veraz” 2.21 En una isla hay dos tribus.1.20 Determinar la corrección del siguiente argumento.2. 2. Por tanto. npd( F ) que calcula el número de paréntesis derechos de la fórmula F. 3. Si hay corriente y la lámpara no está fundida. Hay corriente. ¬q ∧ q ∧ p → r
. Por consiguiente. entonces está encendida. B dice “Si A y C son veraces. Los animales con pelo o que dan leche son mamíferos. Por ejemplo. Ejercicio 1. la lámpara está fundida. Un viajero se encuentra con tres isleños A.2. 1.
Ejercicio 1. La lámpara no está encendida. Ejercicio 1. Se sabe que 1. Se observa un animal que tiene pelos. B y C y cada uno le dice una frase 1.23 Demostrar por inducción que todas las fórmulas proposicionales tienen el mismo número de paréntesis izquierdos que de derechos. 4. C dice “B es mentiroso syss A o B es veraz” Determinar a qué tribu pertenecen A. Ejercicio 1.24 Para cada una de las siguientes fórmulas. Los mamíferos que tienen pezuñas o que rumian son ungulados. Ejercicios propuestos
¿Cuáles son satisfacibles? ¿Cuáles son insatisfacibles? Ejercicio 1. n_variables( F ) ≤ 2profundidad( F) .26 En cada caso. profundidad( F ) que calcula la profundidad del árbol de análisis de la fórmula F. A → B → C y A ∧ B → C 2. ¬r → ¬q} |= p → r
. construir el árbol de análisis y determinar todas sus subfórmulas. p → q → ¬r ∨ s ∨ p escribir la fórmula con paréntesis. Ejercicio 1. que para toda fórmula F.27 Para cada uno de los siguientes pares de fórmulas. determinar todos los modelos de la fórmula proposicional correspondiente: 1. profundidad( p → p ∨ q) = 2. p → (q → r ∧ q) 2.25 Deﬁnir por recursión sobre fórmulas las siguientes funciones 1. Ejercicio 1. { p → q.28 ¿Existe un conjunto S de tres fórmulas tal que de todos los subconjuntos de S sólo uno es consistente? Ejercicio 1. Demostrar por inducción. Sintaxis y semántica de la lógica proposicional
2. n_variables( F ) que calcula el número variables proposicionales que ocurren en la fórmula F.29 Decidir cuáles de las siguientes aﬁrmaciones son verdaderas: 1. ¬( A ↔ B) y A ↔ ¬ B Ejercicio 1. ( p ∧ r ) ∨ (¬ p ∧ q) → ¬q Clasiﬁcar las fórmulas anteriores en tautologías. A → ( B ∧ ¬C ) y A → B → C 3. q → ( p ∧ ¬ p) → r 3. 2. decidir si son o no equivalentes: 1. { p ∨ q} |= p → q 2. Por ejemplo. ( p ↔ q) ∧ ( p → ¬q) ∧ p 4. Por ejemplo.12
Tema 1. n_variables( p → p ∨ q) = 3. contingentes y contradicciones.
Si no es cierto.32 [Examen 5–Mayo–2005] ¿Es cierto que si F → G y F son satisfacibles. 4. Como es natural. cuando hemos empleado un fármaco A. El número x no acaba en 0. entonces Juan es europeo. el paciente ha mejorado considerablemente. en caso de que llueva. Por tanto. el prisionero debe elegir la puerta que le lleva a la dama (entre otras cosas.3. Luego. dar una explicación. 2. Sabiendo que uno de los carteles dice la verdad y el otro no.
1.1. { p ∧ ¬ p} |= r ↔ r ∨ q 4. Para ayudarle. podemos aﬁrmar que si no hemos empleado el fármaco B. de las que el prisionero debe elegir una. entonces G es satisfacible? Si es cierto. En consecuencia. Ejercios de exámenes
3. y entrar en la habitación correspondiente.
Ejercios de exámenes
Ejercicio 1. Siempre que un número x es divisible por 10. Además. Ejercicio 1. La temperatura permanece constante. y sólo en el caso. Juan es europeo. q → p ∧ r } |= p → ( p → q) → r Ejercicio 1. Juan es andaluz. no llueve. x no es divisible por 10. puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones hay un tigre. para no ser devorado por el tigre).30 Determinar si los siguientes argumentos son lógicamente correctos: 1. determinar la puerta que debe de elegir el prisionero. en que no se haya empleado también un fármaco B. Cuando tanto la temperatura como la presión atmosférica permanecen contantes. { p → q.
. o se ha empleado el fármaco A o se ha empleado el fármaco B. 3. En consecuencia. acaba en 0. Si Juan es andaluz. En cierto experimento. el paciente ha mejorado considerablemente en el caso. en cada puerta hay un letrero: puerta 1: en esta habitación hay una dama y en la otra un tigre. dar un contraejemplo.3.31 Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos puertas. Se informa al prisionero que en cada una de las habitaciones puede haber un tigre o una dama. la presión atmosférica no permanece constante.
Tema 1.33 [Examen 30–Junio–2005] Demostrar o refutar las siguientes proposiciones: 1. Sintaxis y semántica de la lógica proposicional
Ejercicio 1. F } es consistente. 2. 2.
. entonces S1 ∪ S2 es consistente. Existe un conjunto de fórmulas S y una fórmula F tal que S |= F y S |= ¬ F. Ejercicio 1. Existen fórmulas válidas tales que todas sus subfórmulas son válidas. Si S1 y S2 son dos conjuntos inconsistentes de fórmulas.36 [Examen 7–Abril–2006] Demostrar o refutar las siguientes proposiciones: 1. Si F es una fórmula satisfacible.35 [Examen 26–Junio–2006] Demostrar o refutar las siguiente proposición: Si { F → G. Ejercicio 1. 2. entonces { G } es consistente.34 [Examen 5–Abril–2006] Demostrar o refutar las siguientes proposiciones: 1. entonces S1 ∩ S2 es inconsistente. Ejercicio 1. entonces todas las subfórmulas de F son satisfacibles.37 [Examen 23–Septiembre–05] Demostrar o refutar las siguiente proposición: Para todo conjunto de fórmula S y para toda fórmula F se veriﬁca que si S |= F entonces S |= ¬ F. Existe un conjunto de fórmulas S y una fórmula F tal que S |= F y S |= ¬ F. Si S1 y S2 son dos conjuntos consistentes de fórmulas.
2. p → (q → r ).1. p → q p
p → ¬¬q
8. ¬r 6. Ejercicios resueltos
Ejercicio 2. ¬ p ∧ q → r ∨ ¬ p 4. p → (q → r ) 5.1 Probar mediante deducción natural: 1. ¬ p ∨ q
15. q → r 13. p ∨ q 12.
p → (q → p) p→q
14. ¬ p → q. p → q. ¬¬(q ∧ r )
¬¬ p ∧ r
r ∨ ¬p r
3. p. ¬ p ∧ q. p → q. p. p → ¬q
. ¬q → ¬ p 9. ¬q 7. 10.Tema 2 Deducción natural proposicional
2. p. p→p
(q → r ) → ((¬q → ¬ p) → ( p → r ))
q∨p p∨q → p∨r
11. p ∧ q.
Introducción de la doble negación: F
¬¬ F
¬¬i
3. → e: { F. ¬¬e: {¬¬ F } |= F 5. ¬¬i: { F } |= ¬¬ F 6. G } |= F ∧ G 2. ∧i: { F. ⊥e: ⊥ |= F 9.2 Demostrar la adecuación de las reglas de deducción natural: 1.16
Tema 2. 1. ∧e: F ∧ G |= F 3. . Reducción al absurdo: ¬F . ∧e: F ∧ G |= G 4. entonces |= F → G.3 Demostrar las reglas derivadas. F → G } |= G 7. p ∧ q ↔ q ∧ p 17. p ↔ q. Ejercicio 2. ¬i: Si F |= ⊥. Deducción natural proposicional
16. 8. ¬e: { F. Modus tollens: F → G ¬G MT ¬F 2. → i: Si F |= G. Ley del tercio excluido: F ∨ ¬F LEM
Ejercicio 2. entonces |= ¬ F. p → q p∧q
Ejercicio 2. p ∨ q 18.
4.4 Demostrar las equivalencias lógicas que aparecen en la transparencia 20 del tema 1:
. . ¬ F } |= ⊥ 10.
2. Distributividad: F ∧ ( G ∨ H ) ≡ ( F ∧ G ) ∨ ( F ∧ H ) F ∨ (G ∧ H ) ≡ ( F ∨ G) ∧ ( F ∨ H ) 6.5 Probar mediante deducción natural: 1.
Ejercicio 2.2. Idempotencia: F ∨ F ≡ F F∧F ≡ F 2. q → r 5. Ejercicios propuestos
1. p → q. p → (q → r ). p 8. p → q
(q → r ) → ( p → r )
r → (q → ( p → s))
( p → (q → r )) → (( p → q) → ( p → r ))
p → (q → r )
12. p → (q → r ) 7. q → r. p → q. Doble negación: ¬¬ F ≡ F. p 4. p → (q → r ) 6. p → q. Absorción: F ∧ ( F ∨ G ) ≡ F F ∨ ( F ∧ G) ≡ F 5. Asociatividad: F ∨ ( G ∨ H ) ≡ ( F ∨ G ) ∨ H F ∧ (G ∧ H ) ≡ ( F ∧ G) ∧ H 4. Leyes de De Morgan: ¬( F ∧ G ) ≡ ¬ F ∨ ¬ G ¬( F ∨ G ) ≡ ¬ F ∧ ¬ G
2. p.2. p → (q → (r → s)) 11. Conmutatividad: F ∨ G ≡ G ∨ F F∧G ≡ G∧F 3. 7. ( p → q) → r
.2. q→p p → (q → p) p→r
q → ( p → r)
( p → q) → ( p → r )
( p ∧ q) → r 23.18
Tema 2. p ∨ (q ∧ r )
( p ∨ q) ∧ ( p ∨ r )
p ∨ (q ∧ r )
34. p → (q → r ) 22. ( p ∨ q) ∧ ( p ∨ r ) 35. q 14. ( p → q) ∧ ( p → r ) 20. p ∧ q
p∧q p q
( p ∨ q) → ( p ∨ r )
29. ( p ∧ q) ∨ ( p ∧ r 33. p ∨ q 26. Deducción natural proposicional
13. ( p ∨ q) → r 37. q → r 27. p ∨ (q ∨ r ) 30. p ∧ q 15. p 24. p ∨ p 28. p ∧ (q ∨ r )
p ∨ (q ∨ r )
( p ∧ q) ∨ ( p ∧ r )
p ∧ (q ∨ r )
32. p ∧ (q ∧ r ) 17. ( p ∧ q) ∧ r 18. p. q p∨q p∨q q∨p
( p → q) ∧ ( p → r ) ( p ∧ q) → r
25. ( p ∨ q) ∨ r 31. p → (q ∧ r ) 21. ( p → r ) ∧ (q → r ) 36. p
( p ∨ q) → r
( p → r ) ∧ (q → r )
. p ∧ q
p ∧ (q ∧ r )
p→q p → (q ∧ r )
por deducción natural.
¬( p ∧ ¬ p)
48. Los ungulados de cuello largo son jirafas. p ∨ q 43. 3. 51. p ∧ ¬ p 49. Los animales con pelo que dan leche son mamíferos. ¬¬ p 50. ¬( p ∧ q) 56.2. p ∨ q. p ∧ q
¬(¬ p ∧ ¬q) ¬(¬ p ∨ ¬q) ¬ p ∧ ¬q ¬( p ∨ q) ¬( p ∧ q)
.6 Demostrar. ¬(¬ p ∨ ¬q) 55. 4. ¬(¬ p ∧ q) 54. ¬ p 42. p → q 40. Los mamíferos que tienen pezuñas o que rumian son ungulados. 2. ¬q → ¬ p 53. p ∨ q.
(( p → q) → p) → p
p→q p∨q p∧q
52. Los ungulados con rayas negras son cebras. ¬ p
¬ p ∨ ¬q
( p → q) ∨ (q → p)
Ejercicio 2. la corrección del siguiente argumento: Se sabe que 1. ¬ p ∨ ¬q 47. ¬( p ∨ q) 45. ¬q 41. ¬ p ∧ ¬q 46.2. Ejercicios propuestos
8 Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos puertas. Se informa al prisionero que en cada una de las habitaciones puede haber un tigre o una dama. Ejercicio 2.7 Demostrar por deducción natural cada una de las argumentaciones válidas del ejercicio 1. el animal es una cebra. y entrar en la habitación correspondiente. ¬q ∨ r c) p∨r p
( p → q) → ((¬ p → q) → q)
d) ( p ∨ (q → p)) ∧ q e) ¬( p ∧ ¬q)
f ) ( p → q) ∧ ( p → r ) |= p → (q ∧ r ) g) ( p1 → p2) ∧ (q1 → q2) h) ¬(¬ p ∨ ¬q) p∧q
( p1 ∧ q1 → p2 ∧ q2)
. [Examen de Junio de 2004]
(E ∨ F) → G
(E → G) ∧ ( F → G)
2. de las que el prisionero debe elegir una. r → ¬q} |= ¬( p ∧ q) b) p ∨ q. Por tanto.9 Probar mediante deducción natural: 1. en cada puerta hay un letrero: puerta 1: en esta habitación hay una dama y en la otra un tigre. Ejercicio 2. [Examen de Abril de 2005] a) { p → r. Deducción natural proposicional
Se observa un animal que tiene pelos.3. demostrar por deducción natural que la dama está en la segunda puerta.
Ejercicio 2. Sabiendo que uno de los carteles dice la verdad y el otro no. puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones hay un tigre. pezuñas y rayas negras. [Examen de Septiembre de 2004]
( E → ( F ∧ G )) → ( E → F ) ∨ ( E → G )
3. Para ayudarle.30. el prisionero debe elegir la puerta que le lleva a la dama (entre otras cosas.20
Tema 2. para no ser devorado por el tigre). Como es natural.
[Examen de Septiembre de 2005]
(( p → (q ∧ ¬r )) → p) → p
6. [Examen de Diciembre de 2006]
(¬q → ¬ p) ∨ (q → p)
. ¬q → ¬( p ∧ r ). ¬( p ∧ ¬s).3. p ∨ r.
8. [Examen de Junio de 2005] p ∧ ¬(q → r )
( p ∧ q ) ∧ ¬r
f ) ( p ∨ ¬q) → p ∧ r h)
g) ( p → q) ∧ ((¬r ∨ q) → s)
(¬(s ∨ ( p → q))) → ( p ∧ ¬q ∧ ¬s). [Examen de Diciembre de 2005]
( p → ¬q) ∧ ( p → ¬r ) → ( p → ¬(q ∨ r ))
d) ¬ p ∨ (r → q)
p → ¬q. [Examen de Junio de 2006]
(( p ∧ q) → (r ∨ s)) → (( p → r ) ∨ (q → s))
(¬ p → q) → (( p → q) → q). [Examen de Septiembre de 2006]
( p → r ) ∨ (q → s)
( p ∧ q ) → (r ∨ s )
10. Ejercicios de exámenes
(( p → q) ∨ ( p → r )) → ( p → q ∨ r ) ¬q ∨ ( p ∨ r )
j) ((¬ p ∨ ¬q) → (¬ p ∧ r )) 4. ¬q ∨ (¬ p ∨ r ). [Examen de Abril de 2006] a) ( p ∨ q) ∧ ( p → r ) b) c) ¬(¬q ∧ p) e) ¬( p ∧ q) p → q.2.
Tema 2. Deducción natural proposicional
Ejercicio 3. { p → q. I |= F ∧ G syss I |= F e I |= G.1. I |= F ∨ G syss I |= F ó I |= G. mediante tableros semánticos. q → r } 4.1 Calcular. Ejercicios resueltos
¬ p ∨ ¬q → ¬( p ∧ q).2 Demostrar o refutar las siguientes proposiciones: 1.Tema 3 Tableros semánticos
3. { p ∨ q}
p → r.4 Decidir si 1.3 Construir dos tableros completos distintos de ( p ∨ q) ∧ (¬ p ∧ ¬q) Ejercicio 3.
p ∧ q. los modelos de las siguientes fórmulas
¬(¬ p ∨ ¬q → ¬( p ∧ r )). ¬(¬ p ∨ ¬q → ¬( p ∧ q)). 2.
Ejercicio 3. 2. ¬ p ∨ ¬q → ¬( p ∧ r ).
2. 1. r } |= r → ( p ∧ q). 4. 1.5 mediante el procedimiento de los tableros semánticos. 4.
.34. ¬( B1 ↔ B2 ) ≡ ¬( B1 → B2 ) ∨ ¬( B2 → B1 ). Tableros semánticos
3.7 Sea A la fórmula proposicional p ∧ q ↔ ¬ p ∨ r.30 y 6. 2. 3. si: 1. A1 ↔ A2 ≡ ( A1 → A2 ) ∧ ( A2 → A1 ).20. Escribir un tablero completo para A y otro para ¬ A. Ejercicio 3. ¬¬ F ≡ F. la corrección de los argumentos válidos de los ejercicios 1.9 Demostrar todos los apartados de los ejercicios 7.6 Demostrar por deducción natural las equivalencias de la notación uniforme: 1. mediante tableros semánticos. 6.10 Demostrar. Ejercicio 3. F ∧ G es satisfacible syss F es satisfacible y G es satisfacible. F ∨ G es satisfacible syss F es satisfacible o G es satisfacible. { p → (q ↔ r ). ¬r → ¬ p ∧ ¬q ≡ p ∨ q → r ∨ s. Ejercicio 3. F ∨ G es válida syss F es válida ó G es válida.24
Tema 3. Ejercicio 3.4 y 7. ¬( A1 ∨ A2 ) ≡ ¬ A1 ∧ ¬ A2 .5 Demostrar o refutar las siguientes proposiciones: 1. ¬( A1 → A2 ) ≡ A1 ∧ ¬ A2 . 2. ( p → q → r ) ↔ ( p ∧ q → r ) es una tautología. 7.8 Decidir. mediante tableros semánticos. ¬( B1 ∧ B2 ) ≡ ¬ B1 ∨ ¬ B2 . 2. 5. Describir todos los modelos y todos los contramodelos de la fórmula A.2. B1 → B2 ≡ ¬ B1 ∨ B2 . Ejercicio 3. F ∧ G es válida syss F es válida y G es válida. 3.
Ejercicio 3. 3.
que la fórmula
( p → r ) → ((q → r ) → ( p ∨ q → r ))
es una tautología.3.11 [Examen de diciembre de 2000] Probar. Ejercicio 3. que la fórmula
( p → ¬q ∧ r ) → ( p → (q → r ))
es una tautología. Ejercicio 3.
Ejercicio 3. mediante tableros semánticos que A y B son lógicamente equivalentes. r ∧ ¬t → ¬u} |= p → s ∨ ¬u
Ejercicio 3. Ejercicio 3. que S es consistente. Probar.12 [Examen de junio de 2001] Decidir. Ejercicio 3.15 [Examen de diciembre de 2001] Demostrar por el método de tableros semánticos que
( p ∨ q ↔ ¬r ) ∧ (¬ p → s) ∧ (¬t → q) ∧ (s ∧ t → u) |= r → u
Ejercicio 3. si la fórmula
( p ∧ q ↔ p ∨ q) → ( p → q)
es insatisfactible o una tautología. Ejercicio 3.16 [Examen de junio de 2002] Probar. mediante tableros semánticos. usando tableros semánticos. ¬q} 1. ¬s ∧ r → q. mediante tableros semánticos. que
(r → p) ∧ (¬r → q ∨ s) → p ∨ q ∨ s
es una tautología. usando tableros semánticos. Probar.14 [Examen de septiembre de 2001 Probar. r ∧ t → s.13 [Examen de junio de 2001] Decidir.18 [Examen de junio de 2003] Se considera el conjunto de fórmulas S = { p → q.3. q ↔ r ∧ s.
.17 [Examen de septiembre de 2002] Sean A : ¬r → s ∧ ¬ u y B : (r ∨ s ) ∧ ( u → r ). mediante tableros semánticos. Ejercicios de exámenes
{ p ∨ q → r ∨ s.3. mediante tableros semánticos.
mediante tableros semánticos. 1. Si Carlos no está en la barbería. Ejercicio 3. 2. razonadamente. Describir todos los modelos de E → ( F → G ) que no son modelos de ( E → F ) → G. Probar que A |= B. mientras que el tío Jaime aﬁrma que sólo puede concluirse que Carlos y Alberto no pueden estar ausentes a la vez. Los dos tíos aceptan las siguientes premisas: 1. el tío Jorge y el tío Jaime discuten acerca de la barbería del pueblo.22 [Examen de septiembre de 2004] En un texto de Lewis Carroll. entonces ocurrirá que si tampoco está Alberto. Ejercicio 3. utilizando la deﬁnición de consecuencia lógica. atendida por tres barberos: Alberto. ¿es una tautología? Razonar la respuesta. Benito tendrá que estar para atender el establecimiento. Probar E → ( F → G ) |= ( E → F ) → G mediante tableros semánticos. se pide 1.21 [Examen de junio de 2004] Este ejercicio tiene tres apartados.20 [Examen de diciembre de 2003] Probar mediante un tablero semántico que
( p → q) ∧ ((r → ¬t) ∧ (q → r )) → ( p → ¬t)
es una tautología. 2. tampoco estará Benito. 2. Describir. Si Alberto no está.
. La fórmula E → ( F → G ) → ( E → F ) → G. 3. todos los modelos de A y.19 [Examen de septiembre de 2003] Dadas las fórmulas A : (s → p) ∨ (t → q) y B : ( s → q ) ∨ ( t → p ). Ejercicio 3. Tableros semánticos
2. a continuación. Decidir con el método de los tableros semánticos cuál de los dos tiene razón. Benito y Carlos. Ejercicio 3.26
Tema 3. El tío Jorge concluye de todo esto que Carlos no puede estar ausente.23 [Examen de septiembre de 2004] Probar que la fórmula
es una tautología por tableros semánticos. Obtener todos los modelos de S. Ejercicio 3. probar nuevamente que A |= B.
31 [Examen de junio de 2006] Sea F la fórmula ( p → q) → ¬(q ∨ r ) ∧ ¬ p.26 [Examen de junio de 2005] Decidir.3. |= (( p → q) → r ) → (q → r ) En el caso de que no se veriﬁque. si la fórmula p ∧ (q ∨ s) → ( p ↔ q) ∨ ( p ↔ r ) es una tautología. 1. obtener un contramodelo a partir del tablero. si la fórmula ( p → q) → ((q → ¬r ) → ¬q) es una tautología.27 [Examen de septiembre de 2005] Decidir. si
{¬ p → (q ∧ r )} |= q → p
En el caso de que no se veriﬁque.28 [Examen de diciembre de 2005] Mediante tableros semánticos. 1. obtener un contramodelo a partir del tablero. mediante tableros semánticos. mediante tableros semánticos. construir un contramodelo a partir del tablero. ((¬ p → q) ∨ (¬q → r )) → (¬r → ( p ∨ q)) 2. determinar cuáles de las siguientes fórmulas son tautologías y calcular los contramodelos de las que no lo sean. Ejercicio 3.30 [Examen de abril de 2006] Decidir. Ejercicio 3. En el caso de que no lo sea.3. Decidir. si F es una tautología. mediante tablero semántico. mediante tablero semántico.25 [Examen de abril de 2005] Decidir.
Ejercicio 3. mediante tableros semánticos. mediante tableros semánticos. calcular a partir de un tablero completo sus contramodelos. si
{ p → r. si
( p → q) ∨ ( p → r ) |= p → (q ∧ r ). Ejercicio 3. (( p → r ) → (¬q ↔ r )) ∧ ¬r } |= q 2.24 [Examen de abril de 2005] Decidir. Ejercicios de exámenes
Ejercicio 3. si 1.29 [Examen de abril de 2006] Decidir. En el caso de que no lo sea.
. mediante tablero semántico. q → r } |= p ∨ q → r
Ejercicio 3. ((¬ p → q) ∨ (¬q → r )) → ((¬ p ∨ ¬q) → r ) Ejercicio 3. {r → ¬( p ∧ ¬q). Ejercicio 3.
33 [Examen de septiembre de 2006] Sea F la fórmula
(( p ∨ q) ↔ ¬( p ∨ q)) ∨ (((¬ p ∨ q) → ¬((q ∧ r ) → ¬ p)) ∧ (r → ¬(q ∨ p)))
Decidir. En el caso de que lo sea. Tableros semánticos
2. calcular.28
Tema 3. Ejercicio 3. Si F no es una tautología. calcular un modelo v de F a partir del tablero y comprobar que v es modelo de F. mediante tablero semántico. a partir de su tablero semántico y los contramodelos de F. si F es satisfacible.32 [Examen de junio de 2006] Demostrar o refutar la siguiente proposición: Si S es un conjunto inconsistente de fórmulas. entonces el tablero semántico cerrado de S obtenido aplicando las reglas α antes que las reglas β tiene menos nodos que el tablero semántico cerrado de S obtenido aplicando las reglas β antes que las reglas α.
. Ejercicio 3.
4. (¬ p ∨ q) ∧ (¬q ∨ p). ¬( p ∧ (q → r )). Ejercicio 4. 2. Ejercicios resueltos
Ejercicio 4.Tema 4 Formales normales
4. 3. (¬ p ∨ q) ∧ (q → p). ( p → q) ∨ (q → p). 2.1 Para cada una de las siguientes fórmulas. Ejercicio 4. 29
. . F1 ∧ · · · ∧ Fn es una tautología syss F1 .1. ¬(¬ p ∨ ¬q → ¬( p ∧ q)). Ejercicio 4. . (¬ p ∧ q) ∨ (q → p). en FND. (¬ p ∧ q) ∨ (¬q ∧ p). 2.3 Calcular una forma normal disjuntiva de cada una de las siguientes fórmulas 1. 1. ¬( p ∧ (q → r )). en ambas o en ninguna de las dos.4 Demostrar o refutar las siguientes proposiciones: 1. determinar si están en FNC. .2 Calcular una forma normal conjuntiva de cada una de las siguientes fórmulas 1. 3. Fn lo son. . ( p ↔ q) → r.
mediante forma normal disyuntiva. F1 ∨ · · · ∨ Fn es satisfacible syss alguna de las fórmulas F1 .9 Calcular. L1 ∨ · · · ∨ Ln es una tautología syss { L1 . ¬( p ∧ (q → r )). Fn lo es. una forma normal disyuntiva de ¬( p ∨ q → p ∧ q).e. . . . Formales normales
2. j tales que Li = Lc ). j Ejercicio 4. Ejercicio 4. una forma normal conjuntiva p ∨ q → p ∧ q. ¬( p ∧ (q → r )). L1 ∧ · · · ∧ Ln es satisfacible syss { L1 . 2. ¬(¬ p ∨ ¬q → ¬( p ∧ q)). 1.8 Calcular. si las siguientes fórmulas son tautotologías.5 Decidir. . si las siguientes fórmulas son satisfacibles.
. Ejercicio 4. ( p → q) ∨ (q → p). En el caso de de que lo sean calcular sus modelos a partir de su FND. mediante tableros semánticos. 2. 1. . .7 Decidir. . Ejercicio 4. 2.6 Demostrar o refutar las siguientes proposiciones 1. mediante tableros semánticos. . los modelos y una forma normal disyuntiva de las siguientes fórmulas
¬(¬ p ∨ ¬q → ¬( p ∧ r )). . . Ejercicio 4. Ln } no contiene ningún par de literales complementarios. existen i. En el caso de de que no lo sean calcular sus contramodelos a partir de su FNC. 3. ( p ↔ q) → r. 1. mediante forma normal conjuntiva. . 2. Ln } contiene algún par de literales complementarios (i. . ¬(¬ p ∨ ¬q → ¬( p ∧ q)).30
3. A ↔ B ≡ ( A → B) ∧ ( B → A). a. Calcular una FND. todos sus contramodelos. ( p ∨ q) ∧ (r ∨ ¬ p) ∧ s. Ejercicio 4. ¬( p ↔ q → r ). A → B ≡ ¬ A ∨ B. 7.2. 9. 4. decidir si es o no una tautología y determinar. ¬( p ∧ q ∧ r ) ∨ ( p ∧ q ∨ r ). b. Ejercicios propuestos
4. 2. en ambas o en ninguna de las dos.2. ¬( A ∨ B) ≡ ¬ A ∧ ¬ B. 1.
. 8. 6. en su caso. Ejercicio 4. p ∧ (¬ p ∨ q) ∧ ( p → s). por deducción natural. 2. ¬( A ∧ B) ≡ ¬ A ∨ ¬ B. decidir si es o no satisfacible y determinar. 3.10 Para cada una de las siguientes fórmulas. ¬¬ A ≡ A.12 Para cada una de las siguientes fórmulas 1. en FND. ( p → r ∨ s) ∧ (r → s) ∧ ¬( p → s). las reglas de normalización: 1. 3. A ∨ ( B ∧ C ) ≡ ( A ∨ B) ∧ ( A ∨ C ). 5. A ∧ ( B ∨ C ) ≡ ( A ∧ B) ∨ ( A ∧ C ). determinar si están en FNC. t ∨ q ∨ r ∧ s. p ∨ q ∨ s. ( A ∨ B) ∧ C ≡ ( A ∧ C ) ∨ ( B ∧ C ). ( A ∧ B) ∨ C ≡ ( A ∨ C ) ∧ ( B ∨ C ).
Ejercicio 4. 4. Calcular una FNC.11 Demostrar. 2. en su caso. todos sus modelos.4.
Escribir un tablero completo para A y otro para ¬ A.
Ejercicio 4. decidir cuáles de las siguientes aﬁrmaciones son verdaderas: 1.17 [Examen de Junio de 2001] Decidir. Ejercicio 4. 2. 1. si la fórmula ( p → ¬(q → ¬r )) ∧ (r → ¬q) es insatisfactible o una tautología.
4. 2. mediante forma normal conjuntiva. utilizando formas normales. según consideres más adecuado.3.
. Calcular una FNC y una FND de A.32
Tema 4. 3. p → q ≡ ¬q → ¬ p.13 Empleando una FNC o bien una FND. q ∨ s} |= s → p. { p ↔ q. Formales normales
Ejercicio 4. que la fórmula ( p → ¬q ∧ r ) → ( p → (q → r )) es una tautología Ejercicio 4.16 [Examen de Diciembre de 2000] Probar. Describir todos los modelos y todos los contramodelos de la fórmula A.14 Determinar una FNC y una FND de la fórmula F cuya tabla de verdad es la siguiente: p 1 1 1 1 0 0 0 0 q 1 1 0 0 1 1 0 0 r 1 0 1 0 1 0 1 0 F 0 0 1 1 1 0 1 1
Ejercicio 4.15 Sea A la fórmula proposicional p ∧ q ↔ ¬ p ∨ r.
Ejercicio 4. Para toda fórmula F se tiene que si G1 es una forma normal conjuntiva de F y G2 es una forma normal normal disyuntiva de F.22 [Examen de Abril de 2005] Calcular una forma normal disyuntiva de A y una forma normal conjuntiva de ¬ A siendo A la fórmula cuya tabla de verdad es p 1 1 1 1 0 0 0 0 q 1 1 0 0 1 1 0 0 r 1 0 1 0 1 0 1 0 A 1 0 0 0 0 1 0 0
Ejercicio 4. Ejercicio 4.19 [Examen de Septiembre de 2004] Probar. que la fórmula ( E → ( F ∧ G )) → ( E → F ) ∨ ( E → G ) es una tautología. Ejercicio 4.3. se tiene que I ( F) = 1. a partir de ella. Si F1 y F2 son equivalentes. entonces G1 y G2 son fórmulas iguales. si I ( p) = I (¬q ∨ r ) 0. para toda interpretación I. 2.20 [Examen de Abril de 2005] Sea F la fórmula p ∨ q ↔ ¬r.
. usando formas normales.21 [Examen de Abril de 2005] Calcular una forma normal conjuntiva de la fórmula F sabiendo que está compuesta con las tres variables p. entonces G1 y G2 son fórmulas distintas. en caso contrario
Ejercicio 4.23 [Examen de Diciembre de 2005] Demostrar o refutar las siguientes proposiciones: 1. q y r y que.18 [Examen de Diciembre de 2003] Utilizando una forma normal. determinar los contramodelos de F y decidir si F es una tautología. probar que ¬(¬t ↔ (¬t ∧ p)) → ¬( p → ¬t) es satisfactible.4. Calcular una forma normal conjuntiva de F y. Sean G1 una forma normal disyuntiva de F1 y G2 una forma normal disyuntiva de F2 . Ejercicios de exámenes
Formales normales
. L1. . . Lm. . . L1.1 . p → q.1 ∨ · · · ∨ L1. .nm }}. . 3. ¬¬r ∧ (¬q → ¬ p). Entonces. . La cláusula { L1 .
Ejercicio 5. El conjunto de cláusulas {{ L1. L2 . .nm }} es equivalente a la fórmula ( L1. .1 Demostrar las siguientes proposiciones:
. . Fn .4 Demostrar que si S1 .1 .n1 ) ∧ · · · ∧ ( Lm. . . 4. Si ( L1. 2. sus formas clausales son distintas. Fn }. . Ejercicio 5.n1 }. . .2 Calcular una forma clausal de las siguientes fórmulas: 1. ( p → q) ∧ r. .n1 }. . ¬( p ∧ (q → r )).1 ∨ · · · ∨ Lm. Sn son formas clausales de F1 .3 Demostrar o refutar: Si dos fórmulas son distintas. . . { Lm. Ejercicio 5. .1. Ejercicio 5. .nm ).1 ∨ · · · ∨ Lm. . . . Ln } es equivalente a la fórmula L1 ∨ L2 ∨ · · · ∨ Ln . . .1 . . . .1 . { Lm. . .Tema 5 Resolución proposicional
5. . . . . Ejercicios resueltos
En cualquier interpretación I.1 ∨ · · · ∨ L1.n1 ) ∧ · · · ∧ ( Lm. entonces S1 ∪ · · · ∪ Sn es una forma clausal de { F1 . . .nm ) es una forma normal conjuntiva de la fórmula F. . una forma clausal de F es {{ L1. I ( ) = 0. Lm. .
. Res p ({q. ¬q}). 2. {q. Fn ¬ G } es inconsistente. . r }). ¬ p}. {¬q. Res({¬ p. . . . . p}). { p. {¬ p.12 Demostrar por resolución la fórmula p ∧ q a partir del conjunto de fórmulas { p ∨ q. q}. p ↔ q}. . {q. 3. . 2. .36
Tema 5. r }). q}. . . {¬ p. { p.8 Demostrar que { F1 . Fn } es consistente syss S1 ∪ · · · ∪ Sn es consistente.10 Calcular: 1. q}. 2. ¬q}}. . { p. {{¬ p. ¬ p}.
. 4. Ejercicio 5. ¬q}}. q}.5 Decidir si la interpretación I tal que I ( p) = I (q) = 1 es un modelo del conjunto de cláusulas {{¬ p. Res({¬ p. { p. q}. . {¬ p.6 Decidir si los siguientes conjuntos de cláusulas son consistentes: 1. ¬q}). ¿Pertenece a Res({ p. Ejercicio 5. {¬ p. Resq ({ p. . Ejercicio 5. Demostrar que son equivalentes 1. Sn formas clausales de las fórmulas F1 . { p. Resolución proposicional
Ejercicio 5. {¬ p}). {{¬ p. { F1 . ¬q})?
Ejercicio 5. ¬q}}. ¬q}). Fn } |= G. q}). 5.
Ejercicio 5. 7. 8. q}. { p. Res p ({q. Ejercicio 5. . q}. Resq ({q. . . . Fn y S una forma clausal de ¬ G. 3. Res p ({ p}. ¬ p}.11 Construir una refutación por resolución del conjunto de cláusulas {{ p. entonces S es inconsistente. ¬q}}. q}. { F1 . { p. . ¬q}. S1 ∪ · · · ∪ Sn ∪ S es inconsistente.7 Demostrar que si
∈ S. { p. .9 Sean S1 . Res({¬ p. { p. q}. 6. q}. Ejercicio 5. q}. ¬q}.
¬q}}. q}. q}. Si el conjunto de cláusulas S es refutable. {¬ p. entonces S es inconsistente. q}.16 Construir el grafo de resolución por saturación simpliﬁcada de los siguientes conjuntos y. {¬ p. entonces {C1 . la corrección del siguiente argumento: Se sabe que 1. C2 } |= C. entonces existe una refutación de S mediante resolución por entradas.20 Demostrar. Si C es una resolvente de C1 y C2 .5. Ejercicio 5.14 [T] 1. {{ p}. hallar una refutación o un modelo del conjunto. {¬ p. ¬q}. Encontrar dos cláusulas C1 y C2 tales que {C1 } |= C2 pero C2 no es demostrable por resolución a partir de {C1 }. q}. 2. Ejercicio 5. { p. {¬ p. entonces { F1 } Res F2 . Ejercicio 5. entonces existe una refutación de S mediante resolución unitaria. {¬q.18 Demostrar o refutar las siguientes proposiciones: 1. Si S es un conjunto de cláusulas inconsistente. ¬q}}. 2. Si S es un conjunto de fórmulas y F es una fórmula tal que S S |= F.15 Construir el grafo de resolución por saturación de {{ p. {¬ p. entonces
. { p. q}. ¬q}. mediante resolución lineal.17 Contruir un grafo de resolución positiva del conjunto {{ p. 2. 2. q}.13 Demostrar las siguientes proposiciones: 1. Ejercicio 5. Los animales con pelo que dan leche son mamíferos.19 Decidir mediante resolución lineal si el siguiente conjunto es consistente {{ p. ¬r }}. Ejercicios resueltos
Ejercicio 5. q}.1. { p. 1. respectivamente. {¬ p. q}. 3. Ejercicio 5. Ejercicio 5. Si S es un conjunto de cláusulas inconsistente.
F. {{ p. { p. ¬q}}. {¬ p. {¬ p. q}. a partir del grafo. {¬ p. Ejercicio 5. ¬q}. Demostrar que si F1 y F2 son dos fórmulas cuyas formas clausales son C1 y C2 . ¬q}. ¬q}}.
{ p → q. q → p ∧ r } |= p → (( p → q) → r ). { p} es una resolvente de { p. ¬ p ∨ ¬q. En este último caso. ¬r } es una resolvente de {r. ¬r ∨ s} es consistente. Vulpix y Onix.24 Ash. r } y { p. q ∨ r } |= r. ¬r } y {r. ¬r }.
4. Los ungulados con rayas negras son cebras. q} y { p. Ejercicio 5. Misty y Brock han organizado una batalla entre sus Pokemon. {r. de los siguientes Pokemon fue el vencedor: Pikachu. 3. 3. Starmie. Bulbasaur. 2. pezuñas y rayas negras. Ejercicio 5. { p. ¬q}.
. ¬q} y {¬ p. y sólo uno. (c) Si o bien Togepi o bien Starmie fue el vencedor. escribir las resolventes correctas. Se observa un animal que tiene pelos. ¬q ∨ r. ¬ p ∨ q. ¬r. Togepi. ¬ p ∨ q ∨ r. Se conocen los siguientes datos al respecto: (a) Uno.23 Usando resolución proposicional. ( p ↔ (q → r )) ∧ ( p ↔ q) ∧ ( p → ¬r ) es una contradicción. s}. (b) Ash ganó la batalla si el Pokemon vencedor fue Pikachu o Bulbasaur. Resolución proposicional
2. q}. demostrar que: 1. 4.38
Tema 5. Ejercicio 5. { p ∨ q ∨ r. p ∨ r } es consistente. Los ungulados de cuello largo son jirafas. Misty ganó la batalla. s} es una resolvente de { p.21 Indicar en cuáles de los siguientes ejemplos se ha aplicado correctamente la regla de resolución proposicional y en cuáles no. Por tanto. p ∨ ¬q. q. { p ∨ q. Los mamíferos que tienen pezuñas o que rumian son ungulados. q. q.2. r. {¬ p ∨ ¬q ∨ r. 2.
Ejercicio 5. 3. 1. es una resolvente de { p. determinar si: 1.
5. p ∨ r. el animal es una cebra.22 Usando resolución proposicional (traduciendo previamente las fórmulas a conjuntos de cláusulas). 2.
26 Dados los conjuntos de fórmulas: S = { p → q. ¬s ∧ r → q. 2. puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones hay un tigre.25 Probar.2. 3. Se informa al prisionero que en cada una de las habitaciones puede haber un tigre o una dama. s → p. Ejercicio 5. que {r ↔ p ∨ q.30. Como es natural. Ejercicio 5. y entrar en la habitación correspondiente. Para ayudarle. ¬q} T = {q ∨ r. Se pide: 1. que S ∪ T es inconsistente. en cada puerta hay un letrero: puerta 1: en esta habitación hay una dama y en la otra un tigre. Starmie también. mediante resolución lineal. (i) Si Vulpix fue derrotado. (g) Si Pikachu fue derrotado. para no ser devorado por el tigre). escribir un conjunto de cláusulas equivalente.28 Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos puertas. de las que el prisionero debe elegir una.27 Demostrar por resolución cada una de las argumentaciones válidas del ejercicio 1. Formalizar los datos anteriores en el lenguaje de la lógica proposicional. el prisionero debe elegir la puerta que le lleva a la dama (entre otras cosas.5. ¬q ∨ ¬r } Probar. entonces Ash no ganó la batalla. Sabiendo que uno de los carteles dice la verdad y el otro no. demostrar que Ash fue el ganador.
. Ejercicio 5. (f) Bulbasaur fue derrotado. mediante resolución lineal. Para cada fórmula obtenida. (h) Brock no ganó la batalla si Bulbasaur fue derrotado. ¬s ∧ ¬r → s ∨ t} |= ¬ p → (q ∨ t). demostrar mediante resolución que la dama está en la segunda puerta. Ejercicios propuestos
(d) Brock ganó la batalla si el vencedor fue Onix o Vulpix. Usando resolución proposicional. Ejercicio 5. Togepi y Onix también corrieron la misma suerte. q ↔ r ∧ s. (e) Si Onix fue derrotado.
3. s ∧ t → u} |= r → u. mediante resolución. mediante resolución lineal. si la siguiente fórmula es una tautología (q → p ∧ r ) ∧ ¬( p ↔ p ∨ q) Ejercicio 5. E → F ∨ G.34 [Examen de septiembre de 2003] Probar. E → ¬ F } Ejercicio 5. por resolución.
Ejercicio 5.33 [Examen de septiembre de 2002] Probar. ¬t → q.36 [Examen de junio de 2004] Probar. Resolución proposicional
5. q → ¬ p. G → F. por resolución. Ejercicio 5. ¬ A2 ∨ B2 .29 [Examen de diciembre de 2000] Sea U = {¬ A1 ∨ ¬ B1 ∨ C2 .40
Tema 5. la inconsistencia del conjunto {¬ E → F ∨ G. que U |= C2 . que (s → p) ∨ (t → q) |= (s → q) ∨ (t → p). que { F. Ejercicio 5. t → u. Ejercicio 5. Ejercicio 5.30 [Examen de junio de 2001] Decidir. que la siguiente fórmula es una tautología: ( p → r ) → ((q → r ) → ( p ∨ q → r )) Ejercicio 5. ¬( B ∧ C ∧ G → E)} |= A ∧ B ∧ D. r → q ∨ t. A2 }. por resolución. A1 . p}.35 [Examen de diciembre de 2003] Sean F y G las siguientes fórmulas: F : ( p → q) ∧ ((r → ¬t) ∧ (q → r )) G : ¬(¬t ↔ (¬t ∧ p)) → ¬( p → ¬t) Probar. G → D. Juan comenta que
. que ( E ∨ F ) → G |= ( E → G ) ∧ ( F → G ) Ejercicio 5.39 [Examen de aabril de 2006] Juan está matriculado en tres asignaturas. ¬ p → s. construir un contramodelo a partir de la resolución. u → ¬s.32 [Examen de diciembre de 2001] Probar por resolución que { p ∨ q ↔ ¬r.38 [Examen de Abril de 2006] Decidir. G } |= r → p.31 [Examen de septiembre de 2001] Probar. Álgebra. Probar. que la fórmula ¬r → s ∧ ¬ u es consecuencia lógica de U = {q ∨ r ∨ s. ¬ A1 ∨ B1 . mediante resolución por entradas. mediante resolución. Ejercicio 5. mediante resolución. si {C → A. F → E. Ejercicio 5. mediante resolución lineal. En el caso que no lo sea.37 [Examen de septiembre de 2004] Probar. Lógica y Dibujo.
Si me gustase el Álgebra pero no el Dibujo. ¬ p → r. si los comentarios de Juan son consistentes y.
. O me gusta el Dibujo y la Lógica. mediante resolución. Ejercicios de exámenes
Me gusta al menos una de las tres asignaturas. ¬s ∧ t}. si r es consecuencia lógica de { p ↔ q.40 [Examen de abril de 2006] Decidir. mediante resolución. Ejercicio 5. ¬ p → r. construir un contramodelo a partir de la resolución. me gustaría la Lógica. D → A} Decidir. q ∨ r → s} |= s. o bien ninguna de las dos. calcular sus modelos a partir de la resolución. mediante resolución.5. construir un contramodelo a partir de la resolución. ¿Qué asignaturas le gustan a Juan? Ejercicio 5. si { p → q. En el caso que no lo sea. en su caso.41 [Examen de Abril de 2006] Decidir. ( D ∧ L) ∨ (¬ D ∧ ¬ L). entonces me gustaría el Álgebra.3. ¬s ∧ ¬t → q. Si me gustase el Dibujo. En el caso que no lo sea. ( A ∧ ¬ D ) → L. Los comentarios de Juan pueden formalizarse por { A ∨ D ∨ L.
Resolución proposicional
Sevilla es vecina de Cádiz. Representar la siguiente propiedad: el bloque central de cualquier pila no está libre. y. y) se veriﬁca si el bloque x está debajo del bloque y. libre( x ) se veriﬁca si el bloque x no tiene bloques encima pila( x. z) se veriﬁca si el bloque x está sobre el y.1. y) se veriﬁca si el bloque x está colocado sobre el bloque y sobre_mesa( x ) se veriﬁca si el bloque x está sobre la mesa Deﬁnir las siguientes relaciones: bajo( x. Cádiz es vecina de Sevilla”. entonces la segunda es vecina de la primera.3 Otra representación del mundo de los bloques se basa en los conceptos primitivos: 43
.Tema 6 Sintaxis y semántica de la lógica de primer orden
6.2 Para representar el mundo de los bloque se parte de los siguientes predicados primitivos: sobre( x. Ejercicio 6. y) se veriﬁca si el bloque x está encima del bloque y. el y sobre el z y el z sobre la mesa.1 Formalizar el siguiente argumento: “Si una ciudad es vecina de otra. Por tanto. encima( x. Ejercicio 6. Ejercicios resueltos
Ejercicio 6. pudiendo haber otros bloques entre ellos.
8. Sintaxis y semántica de la lógica de primer orden
es_bloque( x ) se veriﬁca si x es un bloque. La Luna no es un planeta.4 Formalizar las siguientes expresiones. 7. Algún planeta gira alrededor de la Luna. Hay por lo menos un satélite. usando la conceptualización planeta(x) Tierra Luna satélite(x) satélite(x.44
Tema 6. 11. 9. La Luna es un satélite de la Tierra. 12. 6. libre( x ) se veriﬁca si el bloque x no tiene bloques encima. Ningún objeto celeste gira alrededor de sí mismo. 13. Ejercicio 6.
. Ningún planeta es un satélite. La Tierra gira alrededor del Sol. Deﬁnir los siguientes conceptos: sobre_mesa( x ) se veriﬁca si el bloque x está sobre la mesa. 5. 2. y) gira(x. La Luna es un satélite. 4. Alrededor de los satélites no giran objetos. Todo planeta es un satélite. y) Sol x es un planeta la Tierra la Luna x es un satélite x es un satélite de y x gira alrededor de y el Sol
1. Todo planeta gira alrededor del Sol. Hay exactamente un satélite. 10. tope( x ) es el bloque libre que está encima de x. 3. La Tierra es un planeta. superior( x ) es el bloque que está sobre el bloque x.
y) 2. y) = ·( x. ∀ x ∃y < ( x. 2. 19.9 Decidir si las siguientes expresiones son fórmulas en el lenguaje de la aritmética: 1. Algún planeta no tiene satélites.8 Decidir si las siguientes expresiones son fórmulas atómicas en el lenguaje del mundo de los bloques: 1. superior(superior(c)). Ejercicio 6.
. Hay exactamente dos planetas. +(·( x.6. 2. Ejercicio 6. s(y)). 1). y). 2. <). ∀ x ∃y + ( x.5 Decidir si las siguientes expresiones son términos en el lenguaje de la aritmética: 1. 17. Todo satélite es satélite de algún planeta. libre(superior(c)). < (·( x. s(y)). La Luna no gira alrededor de dos planetas diferentes. 16. La Tierra no tiene satélites. Ejercicio 6.1. Ejercicio 6. y). tope(c) = superior(b). Sólo los planetas tienen satélites. 15. 2. libre(superior(c)). Ejercicio 6. 1). s(y)).7 Decidir si las siguientes expresiones son fórmulas atómicas en el lenguaje de la aritmética: 1. Ejercicios resueltos
14. +(·( x. 20. 18. Todo planeta tiene un satélite.6 Decidir si las siguientes expresiones son términos en el lenguaje del mundo de los bloques: 1. +( x.
15 Calcular el conjunto de variables libres y el conjunto de variables ligadas de cada una de las siguientes fórmulas: 1. P( x ) → R( x. y)). ∀ x ( R( x. y)). y)). ∃ xR( x.14 Determinar las ocurrencias libres y ligadas de las variables de las siguientes fórmulas: 1. c) → P( f (y))).17 Se considera el lenguaje L cuyos símbolos propios son: constante: 0. y) ∨ ∀yP(y) 3.46
Tema 6.10 Decidir si la siguiente expresión es una fórmula en el lenguaje del mundo de los bloques: 1.16 Determinar si las siguientes fórmulas son abiertas o cerradas: 1. c) → P( f (y))).13 Calcular los conjuntos de variables de las siguientes fórmulas: 1. y) ∨ ∀yP(y). ∀ x ( P( x ) → R( x. ∃ xR( x. símbolo de función monaria: s. Ejercicio 6. 2. Ejercicio 6. Ejercicio 6. símbolo de función binaria: + y
. ∀z( P( x ) → R( x. ∀ x ( P( x ) → R( x. Ejercicio 6. ∀ x (tope( x ) = x ↔ libre( x )).12 Calcular las subfórmulas de ∀ x ( R( x. c) → P( f (y))). y)). y)) → (∃yP(y) → R( x. y)) → (∃yP(y) → R(z. ∀ x ( P( x ) → ∃yR( x. 3. c) → P( f (y))). Ejercicio 6. ∀ x ( P( x ) → ∃yR( x. ∀ x ( R( a.11 Dibujar el árbol de análisis de la fórmula ∀ x ( R( x. 2. 2. y) Ejercicio 6. 2. Sintaxis y semántica de la lógica de primer orden
Ejercicio 6. z)). ∀ x ( P( x ) → ∃yR( x. 4. x )). Ejercicio 6.
1}∗ } (siguiente) • I2 (+) = {(w1 . w2 ∈ {0. 1}∗ (cadenas de 0 y 1) • I2 (0) = (cadena vacía) • I2 (s) = {(w. I1 ) con
• U1 = N • I1 (0) = 0 • I1 (s) = {(n. cerrado } • I3 (0) = cerrado • I3 (s) = {( abierto. a + b) : a.6. 1}∗ } (concatenación) • I2 (≤) = {(w1 . w2 ) : w1 . m) : n. abierto )} I3 (s)(e) e abierto cerrado cerrado abierto • I3 (+) = { ( abierto. abierto. w1 es preﬁjo de w2 } (preﬁjo)
I3 = (U3 . cerrado ). I2 ) con
• U2 = {0. 1}∗ . abierto. ( abierto. b ∈ N} (suma) • I1 (≤) = {(n. Ejercicios resueltos
símbolo de relación binaria: ≤ y las siguientes estructuras de L
I1 = (U1 . (cerrado. abierto ). cerrado. abierto ). abierto ). I3 ) con
• U3 = { abierto. cerrado )} I3 (≤) abierto cerrado abierto 1 0 cerrado 1 1 Calcular el valor del término s( x + s(0)) en
. n + 1) : n ∈ N} (sucesor) • I1 (+) = {( a. n ≤ m}
I2 = (U2 . w2 . cerrado )} I3 (+) abierto cerrado abierto abierto abierto cerrado abierto cerrado • I3 (≤) = { ( abierto. (cerrado. cerrado. w2 ∈ {0. m ∈ N. (cerrado. abierto ). (cerrado. w1 w2 ) : w1 . abierto ). (cerrado. b. w1) : w ∈ {0.1.
2). A(y) = 2. 4. Ejercicio 6. I3 con la asignación A( x ) = abierto. ∃ x ∀yR( x.18 Calcular el valor de la fórmula ∀ x ∃yP( x. x ). x ) en I = (U. 2. b) U = N.
. es una realización de f ( x. Determinar si I es un modelo de f ( x. (2. Determinar si (I . y) en I = (U. 3. y) en I = (U. y) = g( x. y) = f (y. 1). es una realización de f ( x. I1 con la asignación A( x ) = 3. Ejercicio 6. Ejercicio 6. A). I ) con a) U = N e I ( R) = ≤ b) U = N e I ( R) = ≥ 3. 2)}. I2 con la asignación A( x ) = 10. 2} e I ( P) = {(1. y).20 Calcular el valor de las siguientes fórmulas. ∃ xP( x ) ∨ ∀ x ¬ P( x ). y). 1)}. donde A es una asignación en I tal que A( x ) = A(y) = 2.21 Sea I = (N. y) = g( x. Ejercicio 6. I ) con a) U = Z e I ( R) = < b) U = N e I ( R) = < 2. 2} e I ( g) = {(1. y) en la estructura I = (U.19 Calcular el valor de la fórmula ∀ xg( g( x )) = x en la estructura I = (U. I ) con a) U = N. I ( R) = ≤ y A una asignación en I tal que A( x ) = 0. satisfacibles o insatisfacibles: 1. I ) una estructura tal que I ( f ) = + e I ( g) = ∗. ∀yR( x. Sintaxis y semántica de la lógica de primer orden
1. 1. I ( R) = ≤ y A una asignación en I tal que A( x ) = 5. I ) tal que U = {1. ∀ x ∃yR(y.48
Tema 6. I ) tal que U = {1. donde A es una asignación en I tal que A( x ) = 1. Ejercicio 6. A). 3.22 Determinar si las siguientes fórmulas son válidas. (2. 2. y). 1. Determinar si (I . y) = g( x. Determinar si I es un modelo de f ( x.
Determinar si (I . P(c)} |= Q(c). 3. I ). y) = y}. f I = +. xn las variables libres de F. y).1. R I = ≤.26 Determinar si los siguientes conjuntos son consistentes: 1.
. . F es satisfacible syss ∃ x1 . y) = y}. S = { P( x ) → Q( x ). I ). . { P(c). 5. Si F es satisfacible. Ejercicio 6. . {∀ x ( P( x ) → Q( x )). y). Si F es válida. 2. A( x ) = 0. . 2.25 Sea S = { R(e. P(y) |= ∀ xP( x ). f I = +. A) es un modelo de S 1. 3. ∀ xP( x ) |= P(y). xn las variables libres de F. . 3. S = {∀yR( x. e I = 0. F es válida syss ∀ x1 . e I = 0. ∀ xP( x ) ∧ ∃ x ¬ P( x ). ∀y f ( x. entonces ¬ F es insatisfacible. . 6. y). f I = +. Entonces. Entonces. . . 4. ∀y f ( x. Ejercicio 6. y) = y}. ∃ xP( x ) ∧ ∃ x ¬ P( x ). A) es una realización de S 1. 5. ∀yP(y). {∀ x ( P( x ) → Q( x )).27 Decidir si se veriﬁcan las siguientes relaciones de consecuencia lógica: 1. Sea F una fórmula de L y x1 . ¬ Q( x )}. . 2. . Determinar si (I . Ejercicio 6.24 Sea S = {∀yR( x. Q(c)} |= P(c). 2. F es válida syss ¬ F es insatisfacible. Ejercicios resueltos
2. ∀ xn F es válida. f (e. Ejercicio 6. f I = +. I ) con R I = <. . Ejercicio 6. ¬ Q(c)} |= ¬ P(c). 4. (∃ xn ) F es satisfacible.23 Demostrar o refutar las siguientes proposiciones: 1. 2.6. A( x ) = 0. entonces F es satisfacible. I = (N. . R I = ≤. I = (N. I = (N. Sea F una fórmula de L y x1 . R I = <. ¬ P(d)} |= c = d. {∀ x ( P( x ) → Q( x )).
∀ xQ( f ( x ). {∀ x ∀y[ P( x. donde a es un símbolo de constante. ∃ x ∃z [ P( x. (c. x ).29 Sea F la fórmula P( x ) → P( a). y) → P( x ). ∀ x ¬ P( x. Q( x. ∀ x ¬ R( x )} 2. a). (b. Decidir cuáles de las siguientes fórmulas de L son válidas en I : 1. { Q( x ). y) → P(y. (d. x ). ¿Es F satisfacible? ¿Tiene modelos? ¿Es F una fórmula válida? Ejercicio 6. z) ∧ ∃ x ( P(y. x )]. z) ∧ Q( x. I ( f ) = {( a.50
Tema 6. b). Sea I = (U. Sintaxis y semántica de la lógica de primer orden
6. d}. {∀ x [ P( x ) → Q( x )]} |= ∀ xP( x ) li f ∀ xQ( x ) 3. Ejercicio 6. b). f . c)}. x ). ∃yP( x.32 Decidir si son correctas o no las siguientes relaciones de consecuencia: 1. z) → ∃y ( P(y. 4. 3. x ) → Q( x.2. x ). b)}. P (de aridad 1). ∀ x ¬ P( x. c. (b. b. x )} 3. I ( P) = { a. y)} Ejercicio 6. y). ∀ x ∃z [ P( x. y))] Ejercicio 6. b). {∀ xP( x ) → ∀ xQ( x )} |= ∀ x [ P( x ) → Q( x )]
Ejercicio 6. y))] 2. P( x ) → ∃yQ(y.28 Determinar las variables libres y ligadas de las siguientes fórmulas: 1. ∀ x [ Q( x ) → R( x )]. I ) la estructura dada por: U = { a. y) → P( x. Q (de aridad 2) y un símbolo de función. de aridad 1. (c. b}. {∀ x [ P( x ) ∨ Q( x )]} |= ∀ xP( x ) ∨ ∀ xQ( x ) 2.31 ¿Cuáles de los siguientes conjuntos de fórmulas son consistentes? 1. b). I ( Q) = {( a. y) → R( x.30 Sea L un lenguaje de primer orden con dos símbolos de predicado. Q( f ( x ). z) ∨ R( x. {∀ xP( x. 2.
Todos los participantes son vencedores. Hay estudiantes inteligentes y hay estudiantes trabajadores. 6. Hay como máximo un participante. para cada argumentación.2. es decir. determinar la simbolización y formalizarla en lógica de primer orden. Los hermanos tienen el mismo padre. Por tanto. en Madrid hay varios canales públicos de TV. Pedro es temido por Juan. Hay como máximo un vencedor. 1. La existencia de algún canal de TV pública. Juan teme a María. hay estudiantes inteligentes y trabajadores. Ejercicio 6. Escribir las formalizaciones en APLI2 y demostrar en APLI2 las argumentaciones válidas. 5. Sócrates es un hombre. todos los directivos de TV5 están satisfechos. Luego. Probar que ninguna de estas fórmulas es consecuencia lógica de las dos restantes. Jorge es padre de Juan. Ningún contrabandista es un VIP. 7.
. el que un canal de TV tenga un acicate. 2. Ejercicios propuestos
4. hay exactamente un participante.6. 3. F2 := ∀ x ∀y[ f ( x ) = f (y) → x = y]. entonces todas las personas pagan. Juan es hermano de Luis. f }. 8. Todo aquel que entre en el país y no sea un VIP será cacheado por un aduanero.34 Formalizar las siguientes argumentaciones. Luego. F3 := ∀ x [ x = a → ∃y[ f (y) = x ]]. TV5 es un canal de TV privada. Los hombres son mortales. por tanto.33 En el lenguaje con igualdad L = { a. alguien teme a María y a Pedro. { P( x ) ∨ Q( f ( x ))} |= P( x ) ∨ Q( x ) Ejercicio 6. Jorge es padre de Luis. Sócrates es mortal. siendo f un símbolo de función de aridad 1 y a una constante. 4. supone un acicate para cualquier canal de TV privada. algún aduanero es contrabandista. Por lo tanto. Por tanto. supone una gran satisfacción para cualquiera de sus directivos. Existe una persona en la Feria tal que si dicha persona paga. se consideran las siguientes fórmulas: F1 := ∀ x [ f ( x ) = a]. Por tanto. Hay un contrabandista que entra en el país y que solo podrá ser cacheado por contrabandistas.
ningún deprimido estima a un submarinista. Por tanto. Luego hay una causa de todo lo existente. 13. 10. Juanito no aplaude a futbolistas extranjeros. está conforme con el contenido del acuerdo internacional de Maastricht y no participará en el próximo referéndum. está conforme con el acuerdo internacional de Maastricht.
. no participará en el próximo referéndum. Toda persona pobre tiene un padre rico. Cualquiera que se estime a sí mismo es listo. 17. cualquier individuo o no es español. A algunas personas motorizadas que intentan entrar en un país le impiden el paso únicamente personas motorizadas. Por tanto. al que sin embargo no apoya. Por tanto. Por tanto. 12. b) No hay ningún pez que se coma a todos los demás. o en otro caso. 15. Quien intente entrar en un país y no tenga pasaporte. Por tanto. Por tanto. Todo español. 16. Ningún deprimido se estima a sí mismo. Por tanto. ciertos aduaneros están motorizados. Ningún aristócrata debe ser condenado a galeras a menos que sus crímenes sean vergonzosos y lleve una vida licenciosa. si hay algún futbolista extranjero nacionalizado español. existe una persona rica que tiene un abuelo rico. Por tanto. encontrará algún aduanero que le impida el paso. En una pecera nadan una serie de peces. c) Ningún pez protege a ningún otro. Juanito no es aﬁcionado al fútbol. Todo deprimido que estima a un submarinista es listo. 11. pero Benito no le obedece. si el pez x no se come al pez y entonces existe un pez z tal que z es un tiburón o bien z protege al pez y.52
Tema 6. Todos los robots obedecen a los amigos del programador jefe. En la ciudad hay aristócratas que han cometido crímenes vergonzosos aunque su forma de vida no sea licenciosa. Los aﬁcionados al fútbol aplauden a cualquier futbolista extranjero. Benito no es un robot. Ninguna persona motorizada tiene pasaporte. hay algún aristócrata que no está condenado a galeras. Se observa que: a) Hay algún pez x que para cualquier pez y. Todo individuo que esté conforme con el contenido de cualquier acuerdo internacional lo apoya o se inhibe en absoluto de asuntos políticos. Todo lo existente tiene una causa. Alvaro es amigo del programador jefe. Cualquiera que se inhiba de los asuntos políticos. existe algún tiburón en la pecera. Sintaxis y semántica de la lógica de primer orden
d) Si Manuel no aprueba B. Ejercicios propuestos
18. algún delantero europeo jugó con botas blancas. Todo el mundo es hijo de alguien. 19. si Manuel es un delegado y aprueba la asignatura A. Supongamos conocidos los siguientes hechos acerca del número de aprobados de dos asignaturas A y B: a) Si todos los alumnos aprueban la asignatura A. y Antoñito es hijo de Don Antonio. Por tanto. Cierto diario deportivo ha publicado las siguientes estadísticas de tan magno acontecimiento: A todos los porteros que no vistieron camiseta negra les marcó un gol algún delantero europeo.
. b) Si algún delegado de la clase aprueba A y B. entonces y es hermano de x. Nadie es hijo del hermano de su padre. Por tanto. Nadie es hijo ni hermano de sí mismo. entonces todos aprueban la asignatura B. Antoñito y Manolito y sabemos que Don Antonio y Don Luis son hermanos. entonces ningún delegado aprueba A. Antoñito y Manolito son hermanos. Cualquier padre de una persona es también padre de todos los hermanos de esa persona. entonces nadie aprueba B. Por tanto.6. c) Si nadie aprueba B. Ningún portero se marcó un gol a sí mismo. entonces todos los alumnos aprueban A. En cierto país oriental se ha celebrado la fase ﬁnal del campeonato mundial de fútbol. entonces todos los alumnos aprueban las asignaturas A y B. Ningún jugador con botas blancas vistió camiseta negra. Don Luis. Don Luis no es el padre de Manolito. Las relaciones de parentesco veriﬁcan la siguientes propiedades generales: Si x es hermano de y.2. Algún portero jugó con botas blancas y sólo le marcaron goles jugadores con botas blancas. Tenemos los siguientes miembros de la familia Peláez: Don Antonio. 20.
Ningún socio del club está en deuda con el tesorero del club. 25. entonces paga su cuota. Los padres son mayores que los hijos. 31. Carlos afeita a todos los habitantes de Las Chinas que no se afeitan a sí mismo y sólo a ellos. la madre del padre de Juan es la madre del padre de Luis. Los caballos son animales. Por tanto. El maestro de Nietzsche no acabó loco. Por tanto. La hermana de Toni es María. 23. Si dos personas son hermanos. 24. entonces todos los miembros del club lo han afeitado a él (aunque no necesariamente al mismo tiempo). Petruccio ha afeitado a Lorenzo. Por consiguiente. Mónica ama a Pedro. Si un socio del club no paga su cuota está en deuda con el tesorero del club. si el tesorero del club es socio del club. Alguien no desprecia a un determinado político. Quien desprecia a todos los fanáticos desprecia también a todos los políticos. las colas de caballo son colas de animales. La madre de María es Mónica. Por tanto. Guido. 27. Carlos no afeita a nadie. Por tanto. Lorenzo. el esposo de María es Roberto. Si uno de los miembros del club afeita a algún otro (incluido a sí mismo). 28. 29. Los que se preguntan qué es la ﬁlosofía se vuelven locos. Nietzsche y su maestro son diferentes personas. Juan es hermano de Luis. Sólo hay un soﬁsta que enseña gratuitamente. Carlos es un habitante de las Chinas. Por tanto. Por consiguiente. y éste es Sócrates. Por tanto. 30. 26. El esposo de la hermana de Toni es Roberto. Platón no es un soﬁsta. Sócrates argumenta mejor que ningún otro soﬁsta. entonces la segunda no argumenta mejor que la primera. Sintaxis y semántica de la lógica de primer orden
21. Si una persona argumenta mejor que otra segunda. Por tanto. Todos los ﬁlósofos se han preguntado qué es la ﬁlosofía. Guido ha afeitado a Cesare. Por consiguiente. entonces tienen la misma madre y el mismo padre. Por tanto. 22. El hombre puro ama todo lo que es puro. Platón argumenta mejor que algún soﬁsta que enseña gratuitamente. Por tanto. el hombre puro se ama a sí mismo. la madre de María ama al padre de Juan. Juan es mayor que Luis. Petruccio y Cesare pertenecen al club de barberos.
. Juan es el padre de Luis.54
Tema 6. hay un fanático al que no todo el mundo desprecia. Juan y Jaime tienen el mismo padre. Pedro es el padre de Jaime. 32. Nietzsche es ﬁlósofo.
El señor Martínez es el secretario. Quien mucho abarca poco aprieta. Por tanto. Luego. Ejercicios propuestos
33. El mayor de los hermanos es un líder. 35. Paco es Curro. Eduardo pudo haber visto al asesino. Por consiguiente. Juana está casada con Tomás. Juana sólo tiene un marido. 45. 43. Aristóteles fue discípulo de alguien cuyo maestro fue Sócrates. La sal no es azúcar. Nadie tiene más de un discípulo.
. La luna hoy es redonda. Platón fue un autodidacta. siempre es la misma. Por consiguiente. Sultán no obtendrá un plátano a menos que pueda resolver cualquier problema.6. Paco no simpatiza con Ana. Tomás es delgado y Guillermo no. Luego existe algo que es a la vez redondo y con forma de cuarto creciente. Luna no hay más que una. Por tanto. Si el chimpancé Chitón trabaja más que Sultán resolverá problemas que Sultán no puede resolver. el primer testigo de la defensa dio falso testimonio. Soy hijo único.2. Todos los chimpancés distintos de Sultán trabajan más que Sultán. Por tanto. Juana no está casada con Guillermo. La sal y el azúcar son blancos. Un autodidacta es aquel que ha sido maestro de sí mismo. Enrique o el cajero tomaron la maleta. Antonio fue el primer testigo de la defensa. Juan no es el mayor de los hermanos. Rosa ama a Curro. Todos los miembros del claustro son asturianos. Luego. El padre de Gutiérrez es el hijo de mi padre. El secretario forma parte del claustro. nada es blanco. Nadie en clase pudo haber visto al asesino. 42. Platón fue el maestro de Aristóteles. Sólo será líder quien aprieta poco. 41. Por tanto. 36. Luego. yo soy el padre de Gutiérrez. 40. Luego. O Eduardo estaba en clase o Antonio dio falso testimonio. Hay como máximo una persona que ama a Rosa. Sócrates era el maestro de Platón. La luna de hace dos semanas tenía forma de cuarto creciente. Por tanto. Si una persona ama a otra. Platón fue discípulo de un autodidacta. Juan abarca mucho porque ha estudiado cuatro carreras. Juan era un licenciado con sobresaliente. Por tanto. es decir. 37. un discípulo. 39. 44. a lo sumo. El gestor que contrató a Juan sólo contrata licenciados con sobresaliente. Alguien que tenía una llave cogió la maleta. Nadie sino Enrique y el cajero tenía una llave. Sultán no es Chitón. Sultán no obtendrá un plátano. 38. Sócrates tuvo. 34. el señor Martínez es asturiano. Quien no simpatiza con Ana ama a Rosa. la segunda ama a la primera.
Ejercicio 6. pájaros. A los lobos no les gusta comer ni zorros ni semillas. y nunca es más rico que su víctima. tal que I |= F3 pero I |= F2 . Las orugas y los caracoles son mucho más pequeños que los pájaros. El mayordomo odia a los que no son más rico que la tía Ágata. R} y el conjunto de fórmulas de L
. Carlos no odia a nadie de los que odia la tía Ágata. Alguien que vive en la casa del crimen ha asesinado a la tía Ágata. f (y)). I . La pareja de Juan es amiga de Eva.56
Tema 6. f (y)) y F3 : ∃y∀ xP( x. Luego.35 [Examen de Junio de 2002] Se considera el lenguaje de primer orden L = { P. y). Por tanto. Por tanto. 49. Todos tiene exactamente dos progenitores. Un asesino siempre odia a sus víctimas. Ejercicio 6. (Schubert’s Steamroller) Los lobos.36 [Examen de Diciembre de 2003] Se considera el lenguaje de primer orden L = { a. Hallar una L estructura. 2. Ágata se ha suicidado. El mayordomo odia a todos los que odia la tía Ágata. A todo animal le gusta o bien comer todo tipo de plantas o bien le gusta comerse a todos los animales más pequeños que él mismo que gustan de comer algunas plantas. Nadie odia a todos. Juan es amigo de Eva. f } y las fórmulas de L: F1 : ∀ x ∃yP( x. todos tienen exactamente un abuelo paterno. Ágata odia a todos excepto al mayordomo. 47. entonces y es amiga de x. Todos tiene exactamente un padre. Si x es amiga de y. el mayordomo y Carlos viven en la casa del crimen y son las únicas personas que viven en la casa del crimen. 48.3. entonces x es amiga de la pareja de y. existe un animal al que le gusta comerse un animal al que le gusta comer semillas. I . La pareja de la pareja de x es x.
6. Luego. 50. P. tal que I |= F1 pero I |= F2 . que son mucho más pequeños que los zorros que a su vez son mucho más pequeños que los lobos. F2 : ∃y∀ xP( x. f . Ágata. También hay algunas semillas y las semillas son plantas. orugas y caracoles son animales y existen algunos ejemplares de estos animales. Sintaxis y semántica de la lógica de primer orden
46. Por tanto. 1. Si dos personas x e y son amigas. Las orugas y los caracoles gustan de comer algunas plantas. todos tienen exactamente cuatro abuelos. Hallar una L estructura. Q. zorros. mientras que a los pájaros les gusta comer orugas pero no caracoles.
∀ x [ R( x ) ↔ P( x. x ) → Q( x. y) → ∀ x ∃yP( x. c)}. x )]. 2. x ) → Q( f ( x ))]. Q( f ( a))} Construir razonadamente un modelo I de S cuyo universo sea U = {1. x )] Ejercicio 6.
.3. ( a. se tiene ∃ x [ F ∧ G ] ≡ ∃ xF ∧ ∃ xG.38 [Examen de Septiembre de 2004] Sea L un lenguaje de primer orden con un símbolo de predicado P de aridad 2. Para ninguna fórmula F y ninguna fórmula G. 5}. y) c) ¬[∀ x ∃yP( x. a)}. 4. dando una estructura que sea modelo de la primera pero no de la segunda. I ) cuyo universo es U = { a. a). f I ( a) = a y f I (b) = a. toda subfórmula G de F y toda variable libre x de G. Q I = {( a.37 [Examen de Junio de 2004] Sea L un lenguaje de primer orden con un símbolo de predicado. ∀ x [ Q( f ( x ). x ) → Q( x. b). b). f ( x ))]. ¿cuáles de las siguientes fórmulas se satisfacen y cuáles no? a) ∀ x ∃yP( x. se tiene que x es una variable libre de F. se tiene ∃ x [ F ∧ G ] ≡ ∃ xF ∧ ∃ xG. ∀ x ¬ P( x. Para toda fórmula F y toda fórmula G. 2.6. y)] Ejercicio 6. 3. y) y ∃ x ∀yP( x. f (de aridad 1). Q (de aridad 2) y un símbolo de función. y) ∧ ∃ x ∀yP( x. y) → ∃ x ∀yP( x. En la estructura I = (U. 3. y) → P(y. Para toda fórmula F. b}. y) b) ∃ x ∀yP( x. 1. Probar que las fórmulas ∀ x ∃yP( x. ( a. Se considera la estructura I dada por: Universo: { a. y) no son equivalentes. Decidir cuáles de las siguientes fórmulas se satisfacen en la estructura: 1. c} y P I = {( a. 2. b. ∃ x [ Q( f ( x ). (b. ∀ x [ P( f ( x ). x ). ∀ x ∀y[ P( x.39 [Examen de Septiembre de 2006] Demostrar o refutar las siguientes proposiciones: 1. Ejercicio 6. Ejercicios de exámenes
S = { ∀ x [ Q( x ) → R( x )]. x )] 2.
Sintaxis y semántica de la lógica de primer orden
3. y)))σ. y). x. Calcular 1. 2. aσ. a). h( a. (∀ x ( Q( x ) → R( x. f ( x. (∀ x ( Q( x ) → ∀y R( x.4 Demostrar mediante deducción natural 59
.1 Sea σ la sustitución [ x/ f (y. y)))σ. 2. σ es [y/g(y)] y F es ∀ x ( P( x ) → Q( x.1. h( a. 3. f (y))). Ejercicios resueltos
Ejercicio 7. 2. y))σ. Ejercicio 7. w)σ. f ( x. y)σ. wσ. ( Q( x ) → ∀ x R( x.3 Decidir si la sustitución σ es libre para la fórmula F en cada uno de los siguientes casos: 1. Ejercicio 7. 5. w)σ. y/z].Tema 7 Deducción natural de primer orden
7. 3. σ es [y/x ] y F es ∃ x ( x < y). Calcular 1. Ejercicio 7. y/b]. f (y))). 4.2 Sea σ la sustitución [ x/ f (y). σ es [y/g( x )] y F es ∀ x ( P( x ) → Q( x.
10. ∀ x ∀y[ P( x ) → Q(y)] ∀yQ(y) 7. ∃ xP( x ) ∃ xQ( x ) 5. ∀ x [ P( x ) → ¬ Q( x )] ¬ Q(c) 2. ∃ x [ P( x ) ∧ Q( x )] ∃ x [ P( x ) ∧ R( x )] 6. Deducción natural de primer orden
1. y) ↔ ∃y∃ xP( x. y)
7. ∀ x [ P( x ) → ¬ Q( x )]. P(c). ∀ x [ P( x ) → Q( x )].2. ∀ x [ P( x ) → Q( x )] ∀ xP( x ) → ∀ xQ( x ) 2. ∀ xP( x ) ∃ xP( x ) 4.
Ejercicio 7. ∃ x ¬ P( x ) ¬∀ xP( x ) 3.5 Demostrar mediante deducción natural 1. 8.
¬∀ xP( x ) ↔ ∃ x ¬ P( x ) ∀ x [ P( x ) ∧ Q( x )] ↔ ∀ xP( x ) ∧ ∀ xQ( x ) ∃ xP( x ) ∨ ∃ xQ( x ) ↔ ∃ x [ P( x ) ∨ Q( x )] ∃ x ∃yP( x. 9. ∀ x [ Q( x ) → R( x )]. ∃ xP( x ).60
Tema 7. ∀ xP( x ) ∀yP(y)
. ∀ xP( x ) ∀ x ¬ Q( x ) 3.
∃ x [ P( a) → Q( x )] 11. ∃ x [ P( x ) ∧ Q( x )] ∃ xP( x ) ∧ ∃ xQ( x ) 15. P( a) → ∃ xQ( x ). ∀ x [ P( x ) → ¬ Q( x )] ¬∃ x [ P( x ) ∧ Q( x )] 6. ∀ x [ P( x ) → Q( a)]. ∃ x [ P( a) → Q( x )] P( a) → ∃ xQ( x ) 10. ∃ x ∀yP( x. ∃ xP( x ) → Q( a) ∀ x [ P( x ) → Q( a)] 12. ∃ xP( x ) 17. ∀ x ∀yP( x. ∀ x ∀y[ P(y) → Q( x )] ∃yP(y) → ∀ xQ( x ) 16. ∀ xP( x ) ∨ ∀ xQ( x ) ∀ x [ P( x ) ∨ Q( x )] 14. ∃ x [ P( x ) → Q( a)] 13. Ejercicios propuestos
4. y) ∃u∃vP(u. v) 7. y) ∀u∀vP(u. v) 8. ¬∀ x ¬ P( x ). ∀ x [ P( x ) → Q( x )] ∀ x ¬ Q( x ) → ∀ x ¬ P( x ) 5. ∀ x ¬ P( x ) ¬∃ xP( x ) 18.7.2. y) 9. ∃ x ∃yP( x. y) ∀y∃ xP( x. ∃ xP( x ) ¬∀ x ¬ P( x )
y. x ) ∀ x ∀y[ R( x. x )] ∃ x ∃yR( x. y) ∧ R(y. ∀ x [ R( x ) → ¬ P( x )] ∃ x ¬ R( x ) 22. t1 = t2 t2 = t1 3. y) ∨ R(y.62
Tema 7. y. y. ∀ x ∀y∀z[ R( x. x ) ∃ x ∃y¬( x = y) 5. ∀ x [ P( x ) → ( Q( x ) ∨ R( x ))]. ∀ xP( a. ∀ x [ P( x ) ∨ Q( x )]. x. ∀ x ∀y∀z( P( x. a. z) → R( x. ∃ x ¬ Q ( x ). P( a) ∀ x (( x = a) → P( x )) 4. ∀ xP( a. f (z)) P( f ( a). y. x )] 21. t1 = t2 . y) → ¬ R(y. z) → P( f ( x ). f ( a) 6. ∃ x ∃y[ R( x. y) ∨ R(y. f ( f ( a)))
. Deducción natural de primer orden
19. P( a) → ∀ xQ( x ) ∀ x [ P( a) → Q( x )] 20. ∀ x ¬ R( x. z. x ). ∃ x ∃y( R( x. z) → P( f ( x ).6 Demostrar mediante deducción natural 1. y) Ejercicio 7. x )) ¬∃ xR( x. x ). ¬∃ x [ P( x ) ∧ R( x )] ∀ x [ P( x ) → Q( x )] 23. t2 = t3 t1 = t3 2. z)]. ∀ x ∀y∀z( P( x. f (z)) ∃zP( f ( a). x.
7.3. Ejercicios de exámenes
7. ∀yQ( a, y), ∀ x ∀y( Q( x, y) → Q(s( x ), s(y)) ∃z( Q( a, z) ∧ Q(z, s(s( a)))) Ejercicio 7.7 Demostrar por deducción natural cada una de las argumentaciones válidas del ejercicio 6.34.
Ejercicio 7.8 Demostrar mediante deducción natural 1. ∀ xP( x ) ∨ ∀ xQ( x ) ∀ x [ P( x ) ∨ Q( x )] 2. ∃ x [ P( x ) ∧ Q( x )] ∃ xP( x ) ∧ ∃ xQ( x ) 3. ∀ x [ R( x ) → Q( x )], ∃ x [ P( x ) ∧ ¬ Q( x )] ∃ x [ P( x ) ∧ ¬ R( x )] 4. ∃ x [ P( x ) ∧ Q( x )], ∀y[ P(y) → R(y)] ∃ x [ R( x ) ∧ Q( x )] 5. ∀ xR( x, x ), ∀ x ∀y∀z[¬ R( x, y) ∧ ¬ R(y, z) → ¬ R( x, z)] ∀ x ∀y[ R( x, y) ∨ R(y, x )] 6. ∃ x ∃y[ R( x, y) ∨ R(y, x )] ∃ x ∃yR( x, y) 7. ∀ x [ P( x ) → ∃yQ(y)], ∀ x ∃y[ P( x ) → Q(y)] 8. ∀ x [ P( x ) → ¬C ( x )], ∃ x [C ( x ) ∧ B( x )] ∃ x [ B( x ) ∧ ¬ P( x )] 9. ∀ x ∃y[ P( x ) → Q(y)] ∀ x [ P( x ) → ∃yQ(y)] 10. ¬∀ x [ P( x ) → Q( a)] ∃ xP( x ) ∧ ¬ Q( a)
Tema 7. Deducción natural de primer orden
11. ∀ xP( x ), ∀ x [ P( x ) → Q( x ) ∨ R( x )], ∃ x ¬ Q( x ) ∃ xR( x ) 12. ∀ x ∀y[ R( x, y) → R(y, x )], ∀ x ∀y[ R( x, y) ∨ R(y, x )] ∀ x ∀y∀z[¬ R( x, y) ∧ ¬ R(y, z) → ¬ R( x, z)] 13. ¬∀ xP( x ) ∃ x ¬ P( x ) 14. ∀ x ∀y[(∃zR(y, z)) → R( x, y)], ∃ x ∃yR( x, y) ∀ x ∀yR( x, y) 15. ∃ x [ P( x ) ∧ ¬ Q( x )] → ∀y[ P(y) → R(y)], ∃ x [ P( x ) ∧ S( x )], ∀ x [ P( x ) → ¬ R( x )] ∃ x [S( x ) ∧ Q( x )] 16.
¬∃ x ∀y[ P(y, x ) ↔ ¬ P(y, y)]
17. ∀ x [∃yR( x, y) → ∃y[∀zR(y, z) ∧ R( x, y)]], ∃ x ∃yR( x, y) ∃ x ∀yR( x, y) 18. ∀ x [ P( x ) → ∀y[ Q(y) → R( x, y)]], ∃ x [ P( x ) ∧ ∃y¬ R( x, y)] ¬∀ xQ( x ) 19. ∃ x [ P( x ) → ∀yQ(y)] ∃ x ∀y[ P( x ) → Q(y)] 20. ∃y∃z[∀ x ¬ R( x, y) ∨ ∀ x ¬ R( x, z)] ¬∀y∀z∃ x [ R( x, y) ∧ R( x, z)] 21. ∃ x [ P( x ) → ∀y[ P(y) → Q(y)]], ¬∃ xQ( x ) ¬∀ xP( x ) 22. ¬∃ x [ P( x ) ∧ ¬∀y[ Q(y) → R( x, y)]], ∃ x [ P( x ) ∧ ∃y¬ R( x, y)] ∃ x ¬ Q( x )
23. ∀ x ∀y[∃z[ R(z, y) ∧ ¬ R( x, z)] → R( x, y)], ¬∃ xR( x, x ) ∀ x ∀y[¬ R(y, x ) → ¬ R( x, y)] 24. P( a) → ¬∀ x ¬ R( x ), ¬∀ x [¬ R( x ) ∧ P( a)] 25. ∀ x ∀y∀z[ P( x, y) ∧ P(y, z) → R( x, z)], ∀ x ∃yP( x, y) ∀ x ∃yR( x, y) 26. ∀ x [ P( x ) → (∃yQ( x, y) → ∃yQ(y, x ))], ∀ x [∃yQ(y, x ) → Q( x, x )], ¬∃ xQ( x, x ) ∀ x [ P( x ) → ∀y¬ Q( x, y)] 27. ∀ x [ Q( x ) → ¬ R( x )], ∀ x [ P( x ) → Q( x ) ∨ S( x )], ∃ x [ P( x ) ∧ R( x )] ∃ x [ P( x ) ∧ S( x )] 28. ∀ x [ P( x ) → ( R( x ) → S( x ))], ∃ x [ P( x ) ∨ ¬ R( x )] ∃ x [ R( x ) → S( x )] Ejercicio 7.9 [Examen de Junio 2005] Se sabe que: Si todo el que estudia aprueba, entonces todo el que estudia recibe un regalo. Hay quien estudia y no recibe ningún regalo. No es verdad que todo el que estudia aprueba. Formalizar los conocimientos anteriores y probar que el conjunto de fórmulas obtenidas es consistente, proporcionando una estructura que sea modelo de cada una de las fórmulas.
∃ xP( x )}
2. {∀ x [ P( x ) → Q( x )].3 [Segundo parcial de 2005] Decidir.1.2. si 1. mediante tableros semánticos.1 Demostrar mediante tableros semánticos 1. Ejercicios resueltos
∃ xQ( x )
Ejercicio 8. ∀ x [ Q( x ) → R( x )]}
∀ x [ P( x ) → R( x )]
Ejercicio 8.2 Refutar mediante tablero semántico
∀ x [ P( x ) ∨ Q( x )] |= ∀ xP( x ) ∨ ∀ xQ( x )
y construir un contramodelo a partir del tablero. ¬∃ xP( x )
Ejercicio 8. {∀ x [ P( x ) → Q( x )].
8. {∃ xP( x ) → ∀ xQ( x )}
.Tema 8 Tableros semánticos
∀y[(∃zP(z)) → P(y)]. ∀ x [ P( x ) → Q( x )].
Tema 8. Tableros semánticos
1 Decidir si las siguientes fórmulas están en forma rectiﬁcada. Ejercicio 9. y). ∀ x P( x ) → ∀ x Q(z. ∀ x P( x ) ∨ ∃y Q(y) 4. y). ∀ x ∃y [ P( x ) ∧ ¬ P(y)] 3. ¬(∀ x [ P( x ) → Q( x )] ∧ ∀ x [ Q( x ) → R( x )] → ∀ x [ P( x ) → R( x )]) 7. 1. ∀ x P( x ) → ∀y Q( x. ∀ x P( x ) → ∀ x Q(z. 3. Cláusulas
9.1. ∀ x P( x ) → ∀y Q( x. ¬∃ x [ P( x ) → ∀ x P( x )] 2. ∀ x P( x ) → ∀y Q(z. y).3 Determinar cuáles de las siguientes fórmulas están en forma normal prenexa: 1.Tema 9 Formas normales. ∀ x ∃y [ P( x ) ∨ Q(y)] 5. x ).2 Calcular una fórmula equivalente en forma rectiﬁcada para cada una de las siguientes fórmulas: 1. Ejercicio 9. Ejercicios resueltos
Ejercicio 9. ∃y ∀ x [ P( x ) ∨ Q(y)] 6. 2. ∃z ∀ x ∀y [((¬ P( x ) ∨ Q( x )) ∧ (¬ Q(y) ∨ R(y))) ∧ P(z)] 69
. x ). 2.
Ejercicio 9. f ( x )). 3. ¬∃ x [ P( x ) → ∀ x P( x )]. ∀ x P( x ) ∨ ∃y Q(y). Ejercicio 9. u.
. Ejercicio 9. ∃ x Q( x ) y Q( a). ¬(∀ x [ P( x ) → Q( x )] ∧ ∀ x [ Q( x ) → R( x )] → ∀ x [ P( x ) → R( x )]).6 Decidir si los siguientes pares de fórmulas son equisatisfacibles y equivalentes: 1. 2.70
Tema 9. 2. ∀ x ∃y P( x. 6. ∀ x ∃y ∀z ∃w [¬ P( a. v. y)]. 4. ∃ x ∀y ∀z ∃u ∀v ∃w P( x. 4. ∀ x P( x ) ∨ ∃y Q(y). Formas normales. 5. 5. ∀ x P( x ) ∨ ∃y Q(y). ¬(∀ x [ P( x ) → Q( x )]. w)). ¬∃ x [ P( x ) → ∀ x P( x )].4 Calcular una forma normal prenexa de cada una de las siguientes fórmulas: 1. 2. ∀ x P( x ) ∨ ∃y Q(y). ¬(∀ x [ P( x ) → Q( x )] ∧ ∀ x [ Q( x ) → R( x )] → ∀ x [ P( x ) → R( x )]).7 Calcular una forma de Skolem de cada una de las siguientes fórmulas: 1. ¬∃ x [ P( x ) → ∀ x P( x )]. z. ¬(∀ x [ P( x ) → Q( x )] ∧ ∃ x P( x ) → ∃ x Q( x )). 3. 3.
Ejercicio 9. Ejercicio 9. 2.8 Calcular una forma clausal de cada una de las siguientes fórmulas: 1.5 Calcular una forma normal prenexa conjuntiva de la fórmula
∀ x ∃y [ P( x ) ∨ ( Q(y) ∧ ¬ R(y))]. y) y ∀ x P( x. w) ∨ Q( f ( x ). y. ∀ x P( x ) ∨ ∃y Q(y). ∀ x P( x ) ∨ ∃y Q(y).
10 Reducir cada uno de los siguientes problemas a un problema de inconsistencia de conjuntos de cláusulas. ∃ x P( x ). ∃ x P( x )} |= ∃ x Q( x ) 2.1. ¬∃ x Q( x )}. {∀ x [ P( x ) → Q( x )].
Ejercicio 9.9 Calcular una forma clausal del conjunto de fórmulas
{∀ x [ P( x ) → Q( x )]. Ejercicios resueltos
Ejercicio 9. ∀ x [ Q( x ) → R( x )]} |= ∀ x [ P( x ) → R( x )]
. 1.9. {∀ x [ P( x ) → Q( x )].
Tema 9. Formas normales.
b. b} y F = { f /2}. P(b) → ¬∃z ∃u Q(z. 4. 2.1. Q/1. la base de Herbrand de S y 3. los modelos de Herbrand de S. R/1}. P( a) → P(c). u)}. F son: 1. ¬ P(b) ∨ P(c). ¬ P(b) ∨ P(c). C = { a. F y símbolos de relaciones. Ejercicios resueltos
Ejercicio 10. calcular todos sus modelos. C = { a. ¬ P(c)} es consistente y. C = { a. ¬ P(c)}. C = { a. F = { f /1} y R = { P/1.Tema 10 Modelos de Herbrand
10. Calcular: 1. Ejercicio 10. Ejercicio 10. Ejercicio 10. P( a) → P(c). C = ∅ y F = { f /1}. 2. x ) → P( a) ∨ R(y)].5 Sea S = {∀ x ∀y [ Q(b. el universo de Herbrand de S. Ejercicio 10.2 Calcular el universo de Herbrand de los lenguajes cuyos conjuntos de constantes. b.1 Decidir si el conjunto { P( a) ∨ P(b). Calcular: 73
. 2. b} y F = { f /1. en el caso de que lo sea. c}.4 Sea S = { P( a) ∨ P(b). F = ∅ y R = { P/1}. Si C = { a}. R. c} y F = ∅. son: 1. C . 3. y símbolos de funciones.3 Calcular la base de Herbrand de los lenguajes cuyos conjuntos de constantes. C . símbolos de funciones. g/1}.
x ). ¬ P( x. Ejercicio 10. Comprobar que I ∗ |= S. 2} e interpretación I deﬁnida por a I = 1. 2). a). {¬ P(b). { Q(y. 2)}. f (y))} y σ la sustitución [ x/a. Calcular la instancia Cσ de C. 2. f ( f ( a)))}. u)}} e I = (U. ¬ P( a)}. I ) la estructura con universo U = {1. P I = {1}. R(y)}. ¬ P( f ( f ( a)). f ( a))}. 3. P( a). Calcular un conjunto de cláusulas S equisatisfacible con S (es decir. ¬ P( f ( a). un modelo de Herbrand de S.9 Sea C la cláusula { P( x. 3. 1.10 Sea C la cláusula { P( x. 1. a). P I = {1} y Q I = {(1. I ) la estructura con universo U = {1. Comprobar que I |= S. 1.7 Sea S el conjunto de cláusulas {{ P( a)}. Calcular un modelo de Herbrand de S . Modelos de Herbrand
1. { P( f ( a). Ejercicio 10. f (y))}. 2. Ejercicio 10. el universo de Herbrand de S. 3. (2. (2. una forma clausal de S). 4. 2). Ejercicio 10. f ( a))}} e I = (U. Ejercicio 10. Comprobar que S es consistente. b I = 2. 2. Comprobar que S no tiene modelo de Herbrand. la base de Herbrand de S y 3. Decidir si las siguientes cláusulas son instancias básicas de C: 1. Comprobar que I |= S. Comprobar que I ∗ |= S. 2. ¬ P( x.74
Tema 10.6 Sea S el conjunto de cláusulas {{¬ Q(b.8 Sea S = {∃ x P( x ). 1). { P( f ( a). 1)}. 2. (2. a). y/ f ( a)]. Calcular la interpretación de Herbrand I ∗ correspondiente a I . 2)} y R I = {2}. a). Q I = {(1. Calcular la interpretación de Herbrand I ∗ correspondiente a I . f I = {(1.
. 2} e interpretación I deﬁnida por a I = 1. ¬ Q(z.
Q( f ( x ). f ( a))}. 3. {¬ P( f ( x ))}}. { P( g(b))}. S2 = {{¬ P( x ). decidir la inconsistencia de los siguientes conjuntos de cláusulas: 1. Ejercicio 10. 2. ¬ P( f ( f ( a)). Q( x )}. 3. { P( a)}.
. {¬ R( a)}}. {¬ R( a)}}. {¬ Q(y). S1 = {{¬ P( x ). Q( x )}. 2. a). S1 = {{ P( x )}. {¬ Q(y). Q( x )}. {¬ Q(z)}}. {¬ P( f ( x ))}}. z)}}. Ejercicio 10. { P( x. R(y)}.13 Sea S el conjunto de cláusulas {{¬ P( x ). S3 = {{ P( x )}. Q( x )}. Calcular un subconjunto ﬁnito de la extensión de Herbrand de S que sea inconsistente.1. {¬ Q(z)}}. { P( a)}. R(y)}.10. { P( a)}. Ejercicio 10. Ejercicios resueltos
3. {¬ Q(y. { P( a)}. x )}. S3 = {{¬ P( x ). S2 = {{¬ P( x ).12 Mediante el procedimiento de semidecisión basado en el teorema de Herbrand.11 Calcular la extensión de Herbrand de cada uno de los siguientes conjuntos de cláusulas: 1.
Modelos de Herbrand
calculando una instancia común: 1 2 3 4 5 6 t1 t2 f ( x. z/y] [ x/g( a). y) f (y. x ) f ( x. {∀ x [ P( x ) → Q( x )]. a). x ) σ [ x/g(z). y/a] [ x/a. y/w] y σ2 = [ x/b. σ1 = [ x/g(z). g(z)) f ( g(y).3 Calcular la composición de las siguientes sustituciones σ1 = [ x/ f (z. σ1 = [ x/g(z). g(z)) f ( g(y). 77
. g(z)) f ( g(y). 2. y/z] y σ2 = [ x/g(y). z/y] y σ3 = [ x/g( a).2 Decidir si la sustitución σ es un uniﬁcador de los términos t1 y t2 en cada uno de los siguientes casos. z/g(w)]. y/a] [y/x ] [ x/y]
Ejercicio 11. σ2 = [ x/g(y).4 Comparar los siguientes pares de sustituciones: 1.1. Ejercicios resueltos
∃ x Q( x ) ∀ x [ P( x ) → R( x )]
Ejercicio 11. ∀ x [ Q( x ) → R( x )]}
Ejercicio 11. y) f (y. x ) f ( x. 3. y) f (y.Tema 11 Cláusulas.1 Demostrar por resolución 1. {∀ x [ P( x ) → Q( x )]. y/a]. Modelos de Herbrand. x ) f ( x. z/y]. Ejercicio 11. y/a]. x ) f ( x. y/z] y σ3 = [ x/g( a). x ) f ( x. ∃ x P( x )}
11. y/z] [ x/g(y).
5 Determinar si las siguientes parejas de términos son uniﬁcables y. z). z). h(w)) y j( f ( x. y) y f ( a. x ). ∀ x ∃ y ¬( P(y. v). x ) y f ( a. por resolución. f ( x. h(w)) y j( f ( x. 4. x ). S1 = {{¬ P( x. P(y. ∀ x [ Q( x ) → R( x )] 3. S = {{ P( x.10 Demostrar. en el caso de que lo sean. Cláusulas. f ( x. j(w. b). y).
∀ x [ P( x ) → R( x )]}. ∃ x P( x )}
∃ x Q ( x ). f ( x. 3. x ). a. f ( x. y). ¬ Q(z. {∀ x [ P( x ) → Q( x )]. j(w. y). { Q(u. f ( a. 5. P(y. Q( f ( x ))} y C2 = {¬ Q( x ). { P( a. a)}}. Modelos de Herbrand. {∀ x [ P( x ) → Q( x )]. f ( x. y). y))}. y)} y C2 = { R( f ( x. El gobernador de la isla ha publicado la siguiente norma:
. {¬ P( f ( x ))}}. 6. 2. y). 2. x ) ↔ ¬ P(y. Q( a)}. 3. R( g( x ))}.8 Calcular un factor de la cláusula { P( x. Ejercicio 11. S2 = {{ P( x )}. x )}. v)}. ¬ P(v. Ejercicio 11.78
Tema 11. x. y/a] y σ5 = [y/x ] Ejercicio 11. Ejercicio 11. y)). a. b) y f ( a.
2. y))}. Ejercicio 11.9 Demostrar por resolución que los siguientes conjuntos de cláusulas son inconsistentes: 1. x. 4. Resolución
4. 7. 1. Q( x. b). y). calcular un uniﬁcador de máxima generalidad: 1. g(y)) y f (y. σ4 = [ x/a.11 (Paradoja del barbero de Russell) En una isla pequeña hay sólo un barbero.6 Calcular una separación de variables de las cláusulas C1 = { P( x ). {¬ P(u. Ejercicio 11. g(z)) y f ( g(y).
∃ x [ P( x ) → ∀y P(y)].7 Calcular una resolvente binaria de las cláusulas C1 = {¬ P( x ).
Ejercicio 11. u)}}.
y) 3. ∃ x P( x ) ∧ ∃ x Q( x ) → ∃ x ( P( x ) ∧ Q( x )) 7. z) j(y. sim´trica} |= reﬂexiva. que ∀ x [ P( x ) ∨ Q( x )] |= ∀ x P( x ) ∨ ∀ x Q( x ) y obtener un contamodelo a partir de la resolución.13 Para cada uno de los siguientes pares de términos determinar si son uniﬁcables y calcular un uniﬁcador de máxima generalidad en el caso de que lo sean. y) → R(y.
11.11. ∃ x P( x ) ∧ ∀ x Q( x ) → ∃ x ( P( x ) ∧ Q( x )) Ejercicio 11. a) j( g( x ). ∃ x ( P( x ) ∨ Q( x )) → ∃ x P( x ) ∨ ∃ x Q( x ) 5. x )) R( x. z ) j( x. z) j(z. x. z))
Ejercicio 11. f (z.15 Se consideran las siguientes fórmulas transitiva sim´trica e reﬂexiva notrivial := := := :=
∀x ∀x ∀x ∀x
∀y ∀z [ R( x. ∃ x ( P( x ) ∧ Q( x )) → ∃ x P( x ) ∧ ∃ x Q( x ) 6.2. z. Ejercios propuestos
“El barbero afeita a todas las personas que no se afeitan a sí misma y sólo a dichas personas”. x ) j( f ( x ). y) → ∃ x ∀y R( x. mediante resolución. y. e
. y). ∀y ∃ x R( x. y) 2. cada una de las siguientes fórmulas: 1. Demostrar que la norma es inconsistente. 1 2 3 4 5 f ( g ( x ). z) → R( x. z)] ∀y ( R( x. ∃ x ∀y R( x. x ) ∃y R( x. ∃ x ( P( x ) → ∀y P(y)) 4.2. y)
1. a.14 Demostrar o refutar.12 Comprobar. y) f (y. f (y). y) ∧ R(y. h(y)) j( f (y. z).
Ejercios propuestos
Ejercicio 11. a)) j(y. Ejercicio 11. por resolución. f (z. z. z) j( x. Demostrar que {transitiva. y. y) → ∀y ∃ x R( x. f ( a.
p(2. s(s(0)). a partir de la demostración encontrar términos t1 y t2 tales que T |= suma(t1 . Demostrar por resolución que T |= ∃ x suma( x. Modelos de Herbrand. entonces existe una persona rica que tiene un abuelo rico. Por ejemplo. 2. s(s(0))) y. p(2. s(s(0))). s(s(0))). t2 . el símbolo de función p y constantes atómicas. s(s(0)). nil ) y p(2. 4. t2 ) ∧ suma(t1 . En dicha representación pueden deﬁnirse las relaciones
. sim´trica.19 Las listas pueden representarse mediante la constante vacía nil. x ) y. y. y) representa la lista cuyo primer elemento es x y cuyo resto es y.s(0))] y. e Ejercicio 11. t2 . nil ). Ejercicio 11. p( p(1. que si toda persona pobre tiene un padre rico. 3. Cláusulas. notrivial} |= reﬂexiva. z) → suma(s( x ). s(s(0)). el número 3 se representa por s(s(s(0))).17 Demostrar mediante resolución cada una de las argumentaciones correctas de la relación de “50 ejercicios de argumentación”. p(1. Demostrar por resolución que T |= ∃ x ∃y suma( x. z). Ejercicio 11. Demostrar que {transitiva. p( x. y.16 Demostrar. a partir de la demostración encontrar un término t tal que T |= suma(t. En dicha representación puede deﬁnirse la relación suma( x. y). y. y. Ejercicio 11. t). y) ∧ suma( x. nil representa la lista vacía. nil )) representa la lista cuyos elementos son las listas p(1. x. s(z))]} 1. Demostrar por resolución que T |= ∃ x ∃y [suma(s(0). y.18 Los números naturales pueden representarse mediante la constante 0 y el símbolo de función s. a partir de la demostración encontrar términos t1 y t2 tales que T |= suma(s(0). mediante el siguiente conjunto de fórmulas T = {∀y suma(0. s(s(0)). ∀ x ∀y ∀z [suma( x. a partir de la demostración encontrar un término t tal que T |= suma(s(0). nil ). por resolución. y. Por ejemplo. t1 .s(0)). nil )) representa la lista cuyos elementos son 1 y 2. que signiﬁca que z es la suma de x e y. Resolución
2. s(s(0))) y.80
Tema 11. Demostrar por resolución que T |= ∃ x suma(s(0).
p(1.2. 3. y e( x. p(2. Demostrar por resolución que T |= ∃ x ∃y c( x. nil ))) y. que signiﬁca que z es la concatenación de x e y. nil ))). Demostrar por resolución que T |= ∃ x c( p(1. x )]
es consecuencia lógica de la fórmula
∃y ∀ x [ P( x. p(2. p(2. nil )))) y. p(2. a partir de la demostración encontrar términos t tales que T |= e(t.20 Demostrar por resolución cada una de las argumentaciones válidas del ejercicio 6. y) ↔ P( x. Ejercicio 11.21 [Examen de Septiembre de 2006] Decidir si el siguiente conjunto de fórmulas es consistente S = { ∀ x [ A( x ) ∧ ∃y [¬ B(y) → C ( x. p(2. p(2. y)]]. Demostrar por resolución que T |= ∃ x c( x. y). ∃ x A ( x ). x ). p(1. p(2. y) → e( x. y. 2. a partir de la demostración encontrar un término t tal que T |= c(t. ∀y ∃ x ∀z [( B( x ) → A(z)) → (¬C (y. z) → c( p(u. y). z).11. p(1. y. p(1. nil )). ∀ x ∀y ∀z ∀u [c( x. p(1. nil )).22 [Examen de Septiembre de 2006] Decidir. x )]. Ejercios propuestos
c( x. a partir de la demostración encontrar un término t tal que T |= c(t1 . Demostrar por resolución que T |= ∃ x e( x. nil )).
Ejercicio 11. por resolución. t). p(1. p(2. p(1. 4. nil ))) y. y. p(1. y)]} 1. ¬∀y ∃z C (z. nil ). p(u. p(1. si la fórmula
∀ x ∃y ∀z [ P(z. p(1. y) ↔ ¬ P(z. nil ))). p(2. nil ). t2 . y. z))] ∀ x ∀y [∃u ∃v c(u. a partir de la demostración encontrar un término t tal que T |= c( p(1. obtener razonadamente un modelo de S. p(1. z) → ¬ B(y))] } Si S es consistente. y).34. que signiﬁca que x es un elemento de y. Ejercicio 11. y. p(2. nil )). p(1. x ) y. nil )))). mediante el siguiente conjunto de fórmulas T = {∀y c(nil. p( x.
. v).
la validez del argumento. Modelos de Herbrand. x1 . Dedidir. y. Decidir si S tiene o no un modelo. 2. y): x simpatiza con y.82
Tema 11. z1 ) F2 = ∃ x ∀ x1 ∃y ∀y1 ∃z ∃u P(z. 1. z1 ) Decidir. y1 . ∀ x ∀y ∀z [ P( x. 2. x1 .23 [Examen de Junio de 2006] Se considera el siguiente argumento: Algunas personas admiran a los que tienen bigote. y)]]
En el caso de que no se veriﬁque. por resolución.27 [Examen de Junio de 2006 (segundo parcial)] Se considera el siguiente conjunto de fórmulas T = { ∀y P(0. ∀ x [ Q( x ) → Q(s(s( x )))] } Demostrar por resolución lineal que
. y1 . z. v). mediante resolución. y. y): x admira y. Luego algunas personas no son simpáticas a todos. obtener un contramodelo a partir de la resolución. F1 |= F2 F3 |= F2
Ejercicio 11. A( x. Cláusulas. y1 . justiﬁcando la respuesta. Para las que no se veriﬁquen. y) ∨ ¬ Q(y)] → ∀ x ∀y [ Q(y) → P( x. S( x. ∃u Q(u)} 1. 2. Ejercicio 11. 1. Q (0). y). x.26 [Examen de Junio de 2006 (segundo parcial)] Decidir. y. mediante cualquiera de los métodos de demostración estudiados en el curso. Ejercicio 11. dar un contramodelo. Algunas personas no simpatizan con nadie que admire a los que tienen bigote. z) → P(s( x ). y) → ¬ Q(z)]. u) F3 = ∃ x ∀ x1 ∃y ∃y1 ∀z ∃z1 P( x. Ejercicio 11. y. s(z))].25 [Examen de Junio de 2006] Se consideran las siguientes fórmulas: F1 = ∀ x ∃ x1 ∀y ∃y1 ∀z ∃z1 P( x. si
|= ∃ x [∀y [ P( x. Probar que S es consistente. Resolución
Ejercicio 11. y. y.24 [Examen de Junio de 2006] Se considera el conjunto S = {∀ x [ P( x. x1 . Formalizar el argumento utilizando los símbolos B( x ): x tiene bigote. z. las siguientes relaciones. P( x.
y)] → Q( x. z) → R( x. p( a. S( x ) signiﬁca que x es submarinista.30 [Examen de Junio de 2006 (segundo parcial)] Decidir. si el argumento es válido. Decidir. Por tanto. Ningún deprimido se estima a sí mismo.29 [Examen de Junio de 2006 (segundo parcial)] Se considera el siguiente conjunto de fórmulas T = { ∀ x ∀z R( x. utilizando el método de resolución. y)] |= ∀ x Q( x. si |= ∃ x [ P( x ) → Q( x )] → ∃ x P( x → ∃ x Q( x )) En el caso de que no se veriﬁque. x ) En el caso de que no se veriﬁque.32 [Examen de Diciembre de 2005] Consideremos los dos siguientes enunciados en castellano E1 : Algunos robots sólo obedecen a los amigos del programador jefe. p( a.) Ejercicio 11. Cualquiera que se estime a sí mismo es listo. Ejercicio 11.11. si ∀ x ∀y [∀z [ P(z. p(b.31 [Examen de Diciembre de 2005] Se considera el siguiente argumento: Todo deprimido que estima a un submarinista es listo. Ejercicio 11. x ) → P(z. obtener un contramodelo a partir de la resolución. (N OTA : En la formalización.28 [Examen de Junio de 2006 (segundo parcial)] Decidir. s(y).2. a partir de la demostración encontrar todos los términos t tales que T |= R(t. nil ))) Ejercicio 11. p( x. ∀ x ∀y ∀z [ R( x. z)).
. Si no es válido encontrar una interpretación en la que las premisas sean todas verdaderas y la conclusión sea falsa. usar el siguiente vocabulario D ( x ) signiﬁca que x está deprimido. mediante resolución. ningún deprimido estima a un submarinista. obtener un contramodelo a partir de la resolución. s(t2 ). p(b. z))]} Demostrar por resolución lineal que T |= ∃ x R( x. mediante resolución. s(s(0))) ∧ Q(s(t1 )) Ejercicio 11. p(y. L( x ) signiﬁca que x es listo y E( x. a partir de la demostración encontrar todos los términos t1 y t2 tales que T |= P(t1 . s(s(0))) ∧ Q(s( x ))] y. Ejercios propuestos
T |= ∃ x ∃y [ P( x. y) signiﬁca que x estima a y. nil ))) y.
3. E4 : Benito no es un robot. Ejercicio 11. que las dos fórmulas correspondientes a E1 son lógicamente equivalentes.
Tema 11. obtener un contramodelo a partir de la resolución. c) → ¬∃ x [ P( x ) ∧ ¬ R( x. que E4 es consecuencia de E2 y E3 . 3. Hacer lo mismo con las dos fórmulas correspondientes a E2 . pero Benito no le obedece. Hay algún pez x que para cualquier pez y.34 [Examen de Septiembre de 2005] Decidir. P( x. Ningún pez protege a ningún otro. 2. Explicar cuál es la interpretación y cuáles son las fórmulas que corresponden a cada uno de los dos enunciados. Demostrar. y las cuatro fórmulas que siguen F1 : ∀ x ∀y [ P( x ) ∧ S(y. Modelos de Herbrand. usar el siguiente glosario C ( x. mediante resolución. (N OTA : En la formalización. No hay ningún pez que se coma a todos los demás. si el pez x no se come al pez y entonces existe un pez z tal que z es un tiburón o bien z protege al pez y. dos de las fórmulas formalizan E1 y las otras dos formalizan E2 . En una interpretación adecuada. y) signiﬁca que “x se come a y”. c)]] F3 : ∀y [S(y. y) signiﬁca que “x protege a y” y T ( x ) signiﬁca que “x es un tiburón”. c) → R( x. Se observa que: 1. y)] F2 : ∃ x [ P( x ) ∧ ∀y [ R( x.33 [Examen de Septiembre de 2005] En una pecera nadan una serie de peces. calculando sus forma clausales. si
|= ∃ x ∀y ∀z [( P(y) → Q(z)) → ( P( x ) → Q( x )))]
En el caso de que no se veriﬁque. y) ∧ ¬S(y. y)]] F4 : ∃ x ∀y [ P( x ) ∧ ¬( R( x. Decidir. Demostrar. c))] 1. mediante resolución. y) → S(y. Cláusulas. si de las observaciones se deduce que existe algún tiburón en la pecera. utilizando el método de resolución.) Ejercicio 11. 2. Consideremos ahora los nuevos enunciados: E3 : Alvaro es amigo del programador jefe. Resolución
E2 : Todos los robots obedecen a los amigos del programador jefe.
entonces todo el que estudia recibe un regalo.36 [Examen de Junio de 2005] Se sabe que: Si todo el que estudia aprueba. y)] En el caso de que no se veriﬁque. proporcionando una estructura que sea modelo de cada una de las fórmulas.39 [Segundo parcial del 2004–05 (Grupo 2)] Decidir.2. z) → ¬ R(z. a partir de la resolución. Ejercicio 11.
Obtener un contramodelo en el caso de que no sea válida. si la siguiente fórmula es válida ¬∀ x ∀y ∃z [ R( x. Ejercicio 11. Para todo conjunto de fórmula S y para toda fórmula F se veriﬁca que si S |= F entonces S |= ¬ F. y) → ∀ x ∀y P( x. un contramodelo en el caso de que no sea válida. z))]. si ∃ x ∃y [( R( x. w) ∧ Q(z.
Obtener un contramodelo en el caso de que no sea válida. Obtener. Para toda fórmula F se tiene que si G es una forma de Skolem de F entonces |= F ↔ G. 2. Formalizar los conocimientos anteriores y probar que el conjunto de fórmulas obtenidas es consistente. Ejercicio 11. obtener un contramodelo a partir de la resolución.37 [Examen de Junio de 2005] Decidir.35 [Examen de Septiembre de 2005] Demostrar o refutar las siguientes proposiciones: 1. y)) → ∀z ∀w [ R(z. ∃ x P( x )} |= ∀ x Q( x ). si
|= ∃ x ∃y [ P( x. mediante resolución. mediante resolución. y) → P( x. Ejercicio 11. Ejercicio 11. No es verdad que todo el que estudia aprueba.38 [Segundo parcial del 2004–05 (Grupo 2)] Decidir. mediante resolución. mediante resolución. Hay quien estudia y no recibe ningún regalo.11. y) ∨ P( x. y) ∧ ( R(y. si
{∀ x [ P( x ) → Q( x )].40 [Segundo parcial del 2004–05 (Grupo 1)] Decidir.
. w)]] es consecuencia lógica de ¬∃ x ∃y [ Q( x. y)]. Ejercios propuestos
Tema 11. Cláusulas. Modelos de Herbrand. Resolución
Ejercicio 11.41 [Segundo parcial del 2004–05 (Grupo 1)] Decidir, mediante resolución, si
{∀ x P( x ) → ∀ x Q( x )} |= ∀ x [ P( x ) → Q( x )]
En el caso de que no se veriﬁque, obtener un contramodelo a partir de la resolución. Ejercicio 11.42 [Examen de Diciembre de 2004] Sean S1 y S2 los conjuntos de fórmulas S1 = {∀ x ∀y [ P( x, y) → P(y, x )], S2 = {∃ x Q( x ),
∀ x ¬ P( x, x ),
∃ x ∃y P( x, y)}
∀ x [ Q( x ) → R( x )],
∀ x ¬ R( x )}
e I1 = (U1 , I1 ), I2 = (U2 , I2 ) las interpretaciones tales que U1 = { a, b} I1 ( P) = {( a, b), (b, a)} I1 ( Q) = { a, b} I1 ( R) = {b} U2 = { a, b, c} I2 ( P) = {( a, b), (b, c), (c, a)} I2 ( Q) = {b} I2 ( R) = { a} Para cada uno de los conjuntos S1 y S2 determinar cuáles de las interpretaciones I1 e I2 es modelo de dicho conjunto. Ejercicio 11.43 [Examen de Septiembre de 2004] Decidir cuáles de las siguientes aﬁrmaciones se cumplen. Para ello, dar una prueba por resolución y otra por deducción natural de cada una de las válidas y calcular un modelo de Herbrand de las que no lo son. 1. ∀ x P( x ) ∨ ∀ x Q( x ) |= ∀ x [ P( x ) ∨ Q( x )] 2. ∀ x [ P( x ) ∨ Q( x )] |= ∀ x P( x ) ∨ ∀ x Q( x ) 3. ∃ x [ P( x ) ∧ Q( x )] |= ∃ x P( x ) ∧ ∃ x Q( x ) Ejercicio 11.44 [Examen de Septiembre de 2004] Sea L un lenguaje de primer orden con un símbolo de predicado P de aridad 2. (a) Probar que las fórmulas ∀ x ∃y P( x, y) y ∃ x ∀y P( x, y) no son equivalentes dando una estructura que sea modelo de la primera pero no de la segunda. (b) En la estructura M cuyo universo es | M| = { a, b, c} y P M = {( a, a), ( a, b), ( a, c)}, ¿cuáles de las siguientes fórmulas se satisfacen y cuáles no? 1. ∀ x ∃y P( x, y) → ∃ x ∀y P( x, y) 2. ∃ x ∀y P( x, y) → ∀ x ∃y P( x, y) 3. ¬[∀ x ∃y P( x, y) ∧ ∃ x ∀y P( x, y)] Ejercicio 11.45 [Examen de Junio de 2004] Sabemos que 1. Cualquiera que estudie lo suﬁciente aprueba todas las asignaturas.
11.2. Ejercios propuestos
2. Cuando alguien que celebra su cumpleaños en julio ha aprobado todas las asignaturas, se le obsequia con un regalo. 3. Quien recibe un regalo sin estudiar lo suﬁciente, nunca es obsequiado con un móvil. 4. Pablo es un alumno que, a pesar de no estudiar lo suﬁciente, recibió un móvil como regalo. Se pide: (a) Formalizar los conocimientos anteriores teniendo en cuenta que los predicados del texto se representan así: C ( x ) = “x celebra su cumpleaños en julio”; A( x ) = “x ha aprobado todas las asignaturas”; S( x ) = “x estudia lo suﬁciente”; R( x, y) = “x recibe el regalo y”. Y las constantes a y b representan respectivamente a Pablo y al móvil. (b) Obtener el conjunto de cláusulas de las fórmulas anteriores y probar que es inconsistente dando un subconjunto de su extensión de Herbrand que lo sea. (c) Probar, mediante resolución, que el enunciado “Si Pablo recibe un móvil como regalo, entonces ha aprobado todas las asignaturas” es consecuencia lógica de los enunciados 1 y 3. Ejercicio 11.46 [Examen de Junio de 2004] Sea L un lenguaje de primer orden con un símbolo de predicado, Q, (de aridad 2) y un símbolo de función, f , (de aridad 1). Se considera la estructura I dada por: Universo: { a, b}, Q I = {( a, b), (b, a)}, f I ( a) = a y f I (b) = a. Decidir cuáles de las siguientes fórmulas se satisfacen en la estructura: 1. ∀ x [ Q( f ( x ), x ) → Q( x, x )] 2. ∃ x [ Q( f ( x ), x ) → Q( x, x )] Ejercicio 11.47 [Examen de Septiembre de 2003] Consideremos los siguientes hechos acerca de la sucesión de los integrantes de la monarquía inglesa: 1. El primogénito de un rey hereda la corona de dicho rey. 2. Si alguien derrota a un rey entonces hereda su corona. 3. Si alguien hereda la corona de un rey entonces se convierte en rey. 4. Enrique VIII era el primogénito de Enrique VII. 5. Ricardo III era rey y Enrique VII derrotó a Ricardo III. Se pide:
(a) Formalizar los enunciados anteriores en un lenguaje de primer orden usando los símbolos de predicado: D ( x, y): x derrota a y, H ( x, y): x hereda la corona de y, R( x ): x es rey, P( x, y): x es el primogénito de y. Las constantes a, b, c denotarán, respectivamente, a Ricardo III, Enrique VII y Enrique VIII. (b) A partir de la información anterior, probar, mediante resolución, que Enrique VIII fue rey. Ejercicio 11.48 [Examen de Septiembre 2003] Se considera el lenguaje L1 = { P, f , a, b} y el conjunto de fórmulas: S = { ∀ x [ P( a, x ) → P(b, f ( x ))], ∀ x [ P( f ( x ), x ) → ∀z P(z, b)], P( a, f ( a)) ∧ P( f (b), b)} Probar, proporcionando un modelo de Herbrand, que S |= ∃ x [ P( x, a) ∧ P( f ( x ), b)]. Ejercicio 11.49 [Examen de Septiembre de 2003] Hallar las formas prenexa, de Skolem y clausal de la fórmula: ¬∃ x ∀z [ P( x ) → ¬ Q(z)] ∨ ∃z A(y, z → ∃u B(y, u)) Ejercicio 11.50 [Examen de Junio de 2003] Supongamos conocidos los siguientes hechos acerca del número de aprobados de dos asignaturas A y B: 1. Si todos los alumnos aprueban la asignatura A, entonces todos aprueban la asignatura B. 2. Si algún delegado de la clase aprueba A y B, entonces todos los alumnos aprueban A. 3. Si nadie aprueba B, entonces ningún delegado aprueba A. 4. Si Manuel no aprueba B, entonces nadie aprueba B. Se pide: (a) Formalizar los enunciados anteriores en un lenguaje de primer orden usando los siguientes símbolos de predicado: D ( x ): “x es un delegado”, Ap( x, y): “x aprueba la asignatura y”. Las constantes a, b, m denotarán la asignatura A, la asignatura B y a Manuel, respectivamente. (b) Obtener una forma clausal para el conjunto de fórmulas del apartado anterior. (c) Probar, mediante resolución, que si Manuel es un delegado y aprueba la asignatura A, entonces todos los alumnos aprueban las asignaturas A y B.
. Algún portero jugó con botas blancas y sólo le marcaron goles jugadores con botas blancas. B( x ): “x juega con botas blancas”. M( x. D ( x ): “x es delantero europeo”. ¬ P(b. Formalizar los enunciados anteriores en un lenguaje de primer orden usando los siguientes símbolos de predicado: P( x ): “x es portero”. mediante resolución. f . a) ∨ ¬ P( f (b). Probar. a) → ∀z P(z. Hallar una L estructura I tal que I |= F2 pero I |= F1 . proporcionando un modelo de Herbrand. a. Probar que F2 y F3 son lógicamente equivalentes. x ) → ∀z P(z. Probar que todo modelo de F1 es modelo de F2 . Todos los ordenadores son máquinas. Ejercicio 11.54 [Examen de Septiembre de 2001] Se conocen los siguientes hechos: 1. 2. x )]. Q} y las fórmulas de L: F1 : ∃ x [ P( x ) ∧ Q( x )]. Ejercicio 11. que S |= P( f ( a). F2 : ∃ x P( x ) ∧ ∃ x Q( x ). y): “x marcó un gol a y”. c)} Probar. b). b. 3.52 [Examen de Septiembre de 2002] Se considera el lenguaje de primer orden L = { P. Ejercicio 11. Cierto diario deportivo ha publicado las siguientes estadísticas de tan magno acontecimiento: A todos los porteros que no vistieron camiseta negra les marcó un gol algún delantero europeo. ∀ x [ P( f ( x ). N ( x ): “x viste camiseta negra”. b). Ningún portero se marcó un gol a sí mismo. c} y el conjunto de fórmulas: S = { P(c. Ningún jugador con botas blancas vistió camiseta negra. Se pide: 1. que algún delantero europeo jugó con botas blancas. F3 : ∃ x ∃y [ P( x ) ∧ Q(y)] 1.2.53 [Examen de Junio de 2002] En cierto país oriental se ha celebrado la fase ﬁnal del campeonato mundial de fútbol. 2. Ejercios propuestos
Ejercicio 11. Obtener una forma clausal para el conjunto de fórmulas del apartado anterior. 3.11.51 [Examen de Junio 2003] Consideramos el lenguaje L1 = { P.
b como constantes para TX–150 y Félix.
. Antoñito y Manolito y sabemos que Don Antonio y Don Luis son hermanos. A( x. Modelos de Herbrand. 6. respectivamente. y): “x puede arreglar y”. y) = “x es hermano de y”. y): “x desespera a y” . El TX–150 es un ordenador.55 [Examen de Junio de 2001] Las relaciones de parentesco veriﬁcan la siguientes propiedades generales: Si x es hermano de y. Todo el mundo es hijo de alguien. Ninguna máquina puede ser arreglada por sí misma. Nadie es hijo ni hermano de sí mismo. respectivamente. Resolución
2. (b) Utilizando resolución responder a las siguientes preguntas: ¿Puede arreglar Félix el TX–150? ¿Estropea Félix el TX–150? Ejercicio 11. Y a. L. Se pide: 1. m como constantes para D. y) = “x es hijo de y”. M( x ): “x es una máquina”. y): “x estropea y” y D ( x. 5. Nadie es hijo del hermano de su padre. 4. Los predicados: Her( x. Antoñito y Manolito son hermanos.90
Tema 11. Félix puede arreglar. 3. 7. Antonio. Antoñito y Manolito. Tenemos los siguientes miembros de la familia Peláez: Don Antonio. Se pide: (a) Formalizar los hechos anteriores utilizando los siguientes símbolos de predicado: O( x ): “x es un ordenador”. Formalizar los conocimientos anteriores en un lenguaje de primer orden usando tan solo: A. y Antoñito es hijo de Don Antonio. E( x. cualquier máquina. Cualquier padre de una persona es también padre de todos los hermanos de esa persona. Don Luis. D. o bien estropear. Hijo( x. Luis. Cada cosa puede ser arreglada por alguien. El TX–150 desespera a Félix. a. Cláusulas. Las cosas solamente desesperan a quienes no son capaces de arreglarlas. entonces y es hermano de x.
Obtener una forma clausal para el conjunto de fórmulas obtenido en el apartado 1.2. Ejercios propuestos
. 3. Decidir mediante resolución si Don Luis es el padre de Manolito o no.
Tema 11. Modelos de Herbrand. Cláusulas. Resolución
T. Jané y R. 1996) [12] J.J. [3] L. Leach. Díez Iniciación a la Lógica (Ed. QMW. (Ed. M.) (Springer.. Gallier Logic for computer science (foundations of automatic theorem Proving) (June 2003) [13] M. 2002) [10] J. Manzano y A. [7] C. Arenas Lógica formal para informáticos. 1985) [9] J. de Sevilla. I. Ariel. Chang y R. Díez Lógica computacional. Fernández. Badesa. Complutense. Lee Symbolic Logic and Mechanical Theorem Proving (Academic Press. 2004) 93
. Díaz de Santos. 2003) [11] M. (UNED.A. (U. 2008). 1998) [16] M.A. y Rogríguez. Matemática discreta y lógica matemática (Ed.. A. Huth y M. 1996) [4] C. 2000) [5] M. 1998). Manjarrés y F. Jansana Elementos de lógica formal (Ariel. Fitting First–Order Logic and Automated Theorem Proving (2nd ed. Hölldobler Computational logic.A. 2003) [14] S.H. 2000) [17] M. Bornat Using ItL Jape with X (Department of Computer Science.–L. [2] J. de Sevilla. 2001) [6] R.C. de Dresden. Genesereth Computational Logic (Stanford University.–T.Bibliografía
[1] J.) (Springer. Alonso Temas de "Lógica informática"(2008-09) (Univ. 1973). Alonso Soluciones de exámenes de Lógica informática (Univ. M. [8] J.L. J. Cuena Lógica Informática (Alianza Ed. Ryan Logic in Computer Science: Modelling and Reasoning about Systems (Cambridge University Press. Huertas Lógica para principiantes (Alianza editorial. 2004) [15] Hortalá. Ben–Ari Mathematical Logic for Computer Science (2nd ed. 2008).
J. Ojeda e I. Nieuwenhuis Lógica de primer orden. R. (Birkäuser. 2001). A. Sánchez y F.94
[18] Nerode. 1997) [19] R. J. Politénica de Cataluña.L. [21] M. Logic for Applications (Springer.A. Nilsson Inteligencia artiﬁcial (Una nueva síntesis) (McGraw–Hill. 1997) [22] E. Paulson Logic and proof (U. Martín Lógica computacional (Thomson. Schöning Logic for Computer Scientists. 1989)
. Paniagua. (U. 2003) [20] N. Pérez de Guzmán Lógica para la computación (Ágora. y Shore. Cambridge. 2002) [24] U. 2003) [23] L.
ejercicios-LI-2011-12Uploaded by Jaime Ernesto Suarez Ortega2.7K viewsDownloadEmbedSee MoreCopyright: Attribution Non-Commercial (BY-NC)List price: $0.00Download as PDF, TXT or read online from ScribdFlag for inappropriate content
Documents similar to ejercicios-LI-2011-12logica_predicados_ejerciciosForma Normal ConjuntivaEjercicios LMF 2011 12geometria analiticaUn cálculo de Deducción NaturalLogica ProposicionalEjercicios Basados en Reglas PrologMore from Jaime Ernesto Suarez OrtegaTeam Foundation Service en Visual Studio 2013Visual Studio 2013 WIndows FormGuia SmartArtConvocatoria2010Manual1 redesFórmulas, FuncionesListado de Funciones de Excel 2003Backtrack manual

References: Resolución 
 Resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 

Resolución 
 resolución 
 resolución 
 Resolución

 resolución 
 resolución 
 resolución 
 resolución 
 Resolución

 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución

 resolución 
 Resolución

 Resolución

 resolución 
 Resolución

 resolución 
 resolución 
 Resolución