Relación 6
De Lógica matemática y fundamentos (2012-13)
Revisión del 12:56 3 abr 2013 de Pedrosrei (discusión | contribuciones)
theory R6
imports Main R3
begin
lemma notnotI: "P ⟹ ¬¬ P"
by auto
lemma mt: "⟦F ⟶ G; ¬G⟧ ⟹ ¬F"
by auto
text {*
---------------------------------------------------------------------
El objetivo de esta relación es formalizar en lógica de primer orden
argumentos expresados en lenguaje natural.
Antes de escribir la soluciones, comprobar con APLI2 la corrección de la
formalización.
------------------------------------------------------------------ *}
text {* ---------------------------------------------------------------
Ejercicio 1. Formalizar el siguiente argumento
Sócrates es un hombre.
Los hombres son mortales.
Luego, Sócrates es mortal.
Usar s para Sócrates
H(x) para x es un hombre
M(x) para x es mortal
------------------------------------------------------------------ *}
-- "En clase"
lemma ejercicio_1a:
assumes "∀x. (H(x) ⟶ M(x))"
"H(s)"
shows "M(s)"
proof -
have 0: "H(s) ⟶ M(s)" using assms(1) ..
thus "M(s)" using assms(2) ..
qed
text {* ---------------------------------------------------------------
Ejercicio 2. Formalizar el siguiente argumento
Hay estudiantes inteligentes y hay estudiantes trabajadores. Por
tanto, hay estudiantes inteligentes y trabajadores.
Usar I(x) para x es inteligente
T(x) para x es trabajador
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_2a:
assumes 0:"(∃x. I(x)) ∧ (∃x. T(x))"
shows "∃x. (I(x)∧T(x))"
quickcheck (* Es falso *)
oops
text {* ---------------------------------------------------------------
Ejercicio 3. Formalizar el siguiente argumento
Todos los participantes son vencedores. Hay como máximo un
vencedor. Hay como máximo un participante. Por lo tanto, hay
exactamente un participante.
Usar P(x) para x es un participante
V(x) para x es un vencedor
------------------------------------------------------------------ *}
-- "Alejandro Ballesteros"
lemma ejercicio_3a:
assumes 0: "(∀x.(P(x)⟶V(x))"
1: "(∃x.(V(x)∧∀y.(V(y)⟶x=y))"
shows "∃x.(P(x)∧∀y.(P(y)⟶x=y))"
oops
-- "Pedro Ros"
lemma ejercicio_3b:
assumes 0: "(∀x.(P(x)⟶V(x)))"and
1: "(∃x.(V(x)⟶ (∀y.(V(y)⟶(x=y)))))"
shows "∃x.(P(x)∧ (∀y.(P(y)⟶(x=y))))"
quickcheck (*Obviamente vuelve a ser falso *)
oops
text {* ---------------------------------------------------------------
Ejercicio 4. Formalizar el siguiente argumento
Todo aquel que entre en el país y no sea un VIP será cacheado por
un aduanero. Hay un contrabandista que entra en el país y que solo
podrá ser cacheado por contrabandistas. Ningún contrabandista es un
VIP. Por tanto, algún aduanero es contrabandista.
Usar A(x) para x es aduanero
Ca(x,y) para x cachea a y
Co(x) para x es contrabandista
E(x) para x entra en el pais
V(x) para x es un VIP
------------------------------------------------------------------ *}
-- "Alejandro Ballesteros"
lemma ejercicio_4a:
assumes 0: "(∀x.(E(x)∧¬V(x)⟶∃y.(Ca(y,x)∧A(y)))"
1: "(∃x.(Co(x)∧E(x)∧∃y.(Ca(y,x)∧Co(y)))"
2: "(∀x.(Co(x)⟶¬V(x)))"
shows "∃x.(A(x)∧Co(x))"
oops
-- "Pedro Ros"
lemma ejercicio_4a:
assumes 0: "(∀x.((E(x)∧(¬V(x)))⟶ (∃y.(Ca(y,x)∧A(y)∧(¬(x=y))))))" and
1: "(∃x.(Co(x)∧E(x)∧(∃y.(Ca(y,x)∧Co(y)∧(A(y))∧(¬(x=y))))))" and
2: "(∀x.(Co(x)⟶(¬V(x))))"
shows "∃x.(A(x)∧Co(x))"
proof -
obtain a where 3: "(Co(a)∧E(a)∧(∃y.(Ca(y,a)∧Co(y)∧(A(y))∧(¬(a=y)))))" using 1..
hence "E(a)∧(∃y.(Ca(y,a)∧Co(y)∧(A(y))∧(¬(a=y))))"..
hence 4:"(∃y.(Ca(y,a)∧Co(y)∧(A(y))∧(¬(a=y))))"..
obtain b where 5: "(Ca(b,a)∧Co(b)∧(A(b))∧(¬(a=b)))" using 4..
hence 6:"Co(b)∧(A(b))∧(¬(a=b))"..
hence 7:"Co(b)"..
have "(A(b))∧(¬(a=b))"using 6..
hence "A(b)"..
hence "A(b)∧Co(b)" using 7..
thus ?thesis ..
qed
text {* ---------------------------------------------------------------
Ejercicio 5. Formalizar el siguiente argumento
Juan teme a María. Pedro es temido por Juan. Luego, alguien teme a
María y a Pedro.
Usar j para Juan
m para María
p para Pedro
T(x,y) para x teme a y
------------------------------------------------------------------ *}
-- "Antonio Jesús Molero"
lemma ejercicio_5:
assumes "T(j,m)"
"T(j,p)"
shows "∃ x. ( T(x,m) ∧ T(x,p)) "
using assms by auto
-- "Pedro Ros"
lemma ejercicio_5b:
assumes 1:"T(j,m)"and
2:"T(j,p)"
shows "∃ x. ( T(x,m) ∧ T(x,p)) "
proof -
have "T(j,m)∧T(j,p)" using 1 2..
thus ?thesis ..
qed
text {* ---------------------------------------------------------------
Ejercicio 6. Formalizar el siguiente argumento
Los hermanos tienen el mismo padre. Juan es hermano de Luis. Carlos
es padre de Luis. Por tanto, Carlos es padre de Juan.
Usar H(x,y) para x es hermano de y
P(x,y) para x es padre de y
j para Juan
l para Luis
c para Carlos
------------------------------------------------------------------ *}
(* Pedro Ros. Los tres sin número son información adicional para demostrar el problema*)
lemma ejercicio_6:
assumes 1: "∀x. ∀y. (H(x,y)⟶(∃z. (P(z,x)∧P(z,y))))" and
2: "H(j,l)" and
3: "P(c,l)"
"∀x. ∀y.(H(x,y) ⟷H(y,x))" and
"∀x. (∃y. (P(y,x)))" and
"∀x. ∀y. (P(x,y)⟷(¬P(y,x)))"
shows "P(c,j)"
quickcheck
using assms by auto
lemma ejercicio_6b:
assumes 1: "∀x. ∀y. (H(x,y)⟶(∃z. (P(z,x)∧P(z,y))))" and
2: "H(j,l)" and
3: "P(c,l)"
"(∀x. ∀y. (P(x,y)⟶ (∀z. (¬(z=x))⟶ ¬P(z,y))))" (* padre sólo hay uno *)
shows "P(c,j)"
proof (rule ccontr)
have "∀y. H(j,y)⟶(∃z. (P(z,j)∧P(z,y)))" using 1..
hence "H(j,l)⟶(∃z. (P(z,j)∧P(z,l)))" ..
hence 4:"(∃z. (P(z,j)∧P(z,l)))" using 2 ..
assume 6:"¬P(c,j)"
obtain t where 5: "P(t,j)∧P(t,l)" using 4..
hence 7:"P(t,l)"..
have "∀y. P(c,y)⟶ (∀z. (z≠c)⟶ ¬P(z,y))" using assms(4) ..
hence "P(c,l)⟶ (∀z. (z≠c)⟶ ¬P(z,l))" ..
hence "(∀z. (z≠c)⟶ ¬P(z,l))" using `P(c,l)` by (rule mp)
hence 8:"(t≠c)⟶¬P(t,l)" ..
show False using 7 8
proof -
have "(t=c)∨(¬(t=c))" by auto
moreover
{assume a:"t=c"
have b:"P(t,j)" using 5..
have "P(c,j)" using a b by auto
with 6 have False ..}
moreover
{assume a:"t≠c"
have "¬P(t,l)" using 8 a ..
hence False using 7 by (rule notE)}
ultimately
show False ..
qed
qed
text {* ---------------------------------------------------------------
Ejercicio 7. Formalizar el siguiente argumento
La existencia de algún canal de TV pública, supone un acicate para
cualquier canal de TV privada; el que un canal de TV tenga un
acicate, supone una gran satisfacción para cualquiera de sus
directivos; en Madrid hay varios canales públicos de TV; TV5 es un
canal de TV privada; por tanto, todos los directivos de TV5 están
satisfechos.
Usar Pu(x) para x es un canal de TV pública
Pr(x) para x es un canal de TV privada
A(x) para x posee un acicate
D(x,y) para x es un directivo del canal y
S(x) para x está satisfecho
t para TV5
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_7:
assumes 1:"(∃x. (Pu(x)))⟶ (∀y. (Pr(y)⟶A(y)))" and
2:"(∀x. (A(x)⟶ (∀y. (D(y,x)⟶S(y)))))" and
3:"∃x. (Pu(x)) " and
4:"Pr(t)"
shows "∀x. (D(x,t)⟶(S(x)))"
quickcheck
proof-
obtain a where 5: "Pu(a)" using 3..
have 6: "∃x. (Pu(x))" using 5 ..
with 1 have 7: "∀y. Pr(y)⟶ A(y)" ..
hence 8:"Pr(t)⟶A(t)"..
hence 9: "A(t)" using 4..
have 10:"A(t)⟶(∀y. (D(y,t)⟶S(y)))" using 2..
thus "∀y. D(y,t)⟶S(y)" using 9..
qed
text {* ---------------------------------------------------------------
Ejercicio 8. Formalizar el siguiente argumento
Quien intente entrar en un país y no tenga pasaporte, encontrará
algún aduanero que le impida el paso. A algunas personas
motorizadas que intentan entrar en un país le impiden el paso
únicamente personas motorizadas. Ninguna persona motorizada tiene
pasaporte. Por tanto, ciertos aduaneros están motorizados.
Usar E(x) para x entra en un país
P(x) para x tiene pasaporte
A(x) para x es aduanero
I(x,y) para x impide el paso a y
M(x) para x está motorizada
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo."
(* Apli2 dice que está bien, pero Isabelle no lo demuestra. No da con-
traejemplo. *)
lemma ejercicio_8a:
assumes "∀x.∃y.(E(x) ∧ ¬P(x) ⟶ A(y) ∧ I(y,x))"
"∃x.∀y.(M(x) ∧ E(x) ∧ (I(y,x) ⟶ M(y)))"
"∀x.(M(x) ⟶ ¬P(x))"
shows "∃x.(A(x) ∧ M(x))"
oops
-- "Pedro Ros"
(* Uso esta función más adelante *)
lemma aux:
assumes "¬(p ∧ q)"
shows "¬p ∨ ¬q"
proof -
have "¬p∨p"..
moreover
{assume "¬p"
hence "¬p∨¬q"..}
moreover
{assume "p"
have "¬q∨q"..
moreover
{assume "¬q"
hence "¬p∨¬q"..}
moreover
{assume "q"
with `p`have "p∧q"..
with `¬(p∧q)` have "¬p∨¬q"..}
ultimately have "¬p∨¬q"..}
ultimately show "¬p∨¬q"..
qed
lemma ejercicio_8b:
assumes 1:"∀x.∃y.(E(x) ∧ ¬P(x) ⟶ A(y) ∧ I(y,x))" and
2:"∃x.∀y.(M(x) ∧ E(x) ∧ (I(y,x) ⟶ M(y)))" and
3:"∀x.(M(x) ⟶ ¬P(x))"
shows "∃x.(A(x) ∧ M(x))"
proof (rule ccontr)
assume 0:"¬(∃x.(A(x) ∧ M(x)))"
obtain a where 4: "∀y.(M(a) ∧ E(a) ∧ (I(y,a) ⟶ M(y)))" using 2..
have 11: "∃y.(E(a) ∧ ¬P(a) ⟶ A(y) ∧ I(y,a))" using 1..
obtain b where b: "((E(a) ∧ ¬P(a)) ⟶ (A(b) ∧ I(b,a)))" using 11 ..
have 5:"¬(A(b)∧M(b))"
proof (rule ccontr)
assume "¬¬ (A(b)∧M(b))"
hence "(A(b)∧M(b))" by (rule notnotD)
hence "∃x. (A(x)∧M(x))" by (rule exI)
with 0 show False by (rule notE)
qed
have 6: "(M(a) ∧ E(a) ∧ (I(b,a) ⟶ M(b)))" using 4..
have 7: "¬A(b) ∨ ¬M(b)" using 5 by (rule aux)
have 17:"E(a) ∧ (I(b,a) ⟶ M(b))" using 6..
hence 12:"E(a)"..
have 8: "M(a)⟶ ¬P(a)" using 3..
have 9: "M(a)" using 6..
with 8 have 10: "¬P(a)"..
with 12 have 13:"(E(a)∧ ¬P(a))"..
have 14:"A(b) ∧ I(b,a)" using b 13 by (rule mp)
hence "A(b)"..
hence "¬¬A(b)"by (rule notnotI)
with 7 have 15:"¬M(b)" by (rule ejercicio_43)
have 16:"I(b,a)" using 14 ..
have 17: "(I(b,a) ⟶ M(b))" using 17..
hence "M(b)" using 16 ..
with 15 show False ..
qed
text {* ---------------------------------------------------------------
Ejercicio 9. Formalizar el siguiente argumento
Los aficionados al fútbol aplauden a cualquier futbolista
extranjero. Juanito no aplaude a futbolistas extranjeros. Por
tanto, si hay algún futbolista extranjero nacionalizado español,
Juanito no es aficionado al fútbol.
Usar Af(x) para x es aficicionado al fútbol
Ap(x,y) para x aplaude a y
E(x) para x es un futbolista extranjero
N(x) para x es un futbolista nacionalizado español
j para Juanito
------------------------------------------------------------------ *}
-- "Reme Sillero"
lemma ejercicio_9:
assumes "∀ x. ∀ y. ((Af(x) & E(y))⟶ Ap(x,y)) "
"∀y. (E(y) ⟶ (¬Ap(j,y)))"
shows "(∃x. (E(x) ∧ N(x))) ⟶(¬Af(j))"
using assms by auto
-- "Pedro Ros"
lemma ejercicio_9:
assumes "∀ x. ∀ y. ((Af(x) ∧ E(y))⟶ Ap(x,y)) "
"∀y. (E(y) ⟶ (¬Ap(j,y)))"
shows "(∃x. (E(x) ∧ N(x))) ⟶(¬Af(j))"
proof
assume 1:"(∃x. (E(x) ∧ N(x)))"
obtain a where 2: "(E(a)∧N(a))" using 1..
have 3:"E(a)⟶ (¬Ap(j,a))" using assms(2)..
have 0:"E(a)" using 2..
with 3 have 4:"(¬Ap(j,a))"..
have 5:" ∀ y. ((Af(j) ∧ E(y))⟶ Ap(j,y)) "using assms(1)..
hence "((Af(j) ∧ E(a))⟶ Ap(j,a))"..
hence "¬(Af(j) ∧ E(a))" using 4 by (rule mt)
hence 6:"¬Af(j) ∨ ¬E(a)" by (rule ejercicio_57)
thus "¬Af(j)"
proof
assume ?thesis
thus ?thesis.
next
assume "¬E(a)"
hence False using 0 ..
hence "¬¬E(a)"..
with 6 show ?thesis by (rule ejercicio_42)
qed
qed
text {* ---------------------------------------------------------------
Ejercicio 10. Formalizar el siguiente argumento
Ningún aristócrata debe ser condenado a galeras a menos que sus
crímenes sean vergonzosos y lleve una vida licenciosa. En la ciudad
hay aristócratas que han cometido crímenes vergonzosos aunque su
forma de vida no sea licenciosa. Por tanto, hay algún aristócrata
que no está condenado a galeras.
Usar A(x) para x es aristócrata
G(x) para x está condenado a galeras
L(x) para x lleva una vida licenciosa
V(x) para x ha cometido crímenes vergonzoso
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo"
lemma ejercicio_10a:
assumes "∀x.(A(x) ∧ G(x) ⟶ V(x) ∧ L(x))"
"∃x.(A(x) ∧ V(x) ∧ ¬L(x))"
shows "∃x.(A(x) ∧ ¬G(x))"
proof -
obtain a where 1:"A(a) ∧ V(a) ∧ ¬L(a)" using assms(2)..
have 2: "A(a) ∧ G(a) ⟶ V(a) ∧ L(a)" using assms(1)..
have "V(a)∧¬L(a)" using 1..
hence 3: "¬L(a)"..
have "¬(V(a)∧L(a))"
proof
assume "(V(a)∧L(a))"
hence "L(a)"..
with 3 show False ..
qed
with 2 have "¬(A(a)∧G(a))" by (rule mt)
hence 4:"¬A(a)∨ ¬G(a)" by (rule ejercicio_57)
have 5:"A(a)" using 1..
have "¬G(a)"
proof -
have "A(a)" using 5.
hence "¬¬A(a)" by (rule notnotI)
with 4 show "¬G(a)" by (rule ejercicio_43)
qed
with 5 have "A(a)∧ ¬G(a)" ..
thus ?thesis ..
qed
text {* ---------------------------------------------------------------
Ejercicio 11. Formalizar el siguiente argumento
Todo individuo que esté conforme con el contenido de cualquier
acuerdo internacional lo apoya o se inhibe en absoluto de asuntos
políticos. Cualquiera que se inhiba de los asuntos políticos, no
participará en el próximo referéndum. Todo español, está conforme
con el acuerdo internacional de Maastricht, al que sin embargo no
apoya. Por tanto, cualquier individuo o no es español, o en otro
caso, está conforme con el contenido del acuerdo internacional de
Maastricht y no participará en el próximo referéndum.
Usar C(x,y) para la persona x conforme con el contenido del acuerdo y
A(x,y) para la persona x apoya el acuerdo y
I(x) para la persona x se inibe de asuntos políticos
R(x) para la persona x participará en el próximo referéndum
E(x) para la persona x es española
m para el acuerdo de Maastricht
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_11:
assumes 1:"∀x. (∀y. ((y≠x)∧C(x,y)⟶(A(x,y)∨I(x))))"and
2:"∀x. (I(x)⟶ ¬R(x))" and
3:"∀x. ((E(x)⟶C(x,m)))" and
"∀x. (x≠m)"
shows "∀x. ((¬E(x)∨(C(x,m)∧¬R(x))))"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 12. Formalizar el siguiente argumento
Toda persona pobre tiene un padre rico. Por tanto, existe una
persona rica que tiene un abuelo rico.
Usar R(x) para x es rico
p(x) para el padre de x
------------------------------------------------------------------ *}
-- "Antonio Jesús Molero"
lemma ejercicio_12:
assumes " ∀ x. (¬R(x) ⟶ R(P(x)))"
shows "∃x. (R(x) ∧ R(P (P(x))))"
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 13. Formalizar el siguiente argumento
Todo deprimido que estima a un submarinista es listo. Cualquiera
que se estime a sí mismo es listo. Ningún deprimido se estima a sí
mismo. Por tanto, ningún deprimido estima a un submarinista.
Usar D(x) para x está deprimido
E(x,y) para x estima a y
L(x) para x es listo
S(x) para x es submarinista
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo."
(* Apli2 dice que está bien, pero Isabelle no lo demuestra y da un con-
traejemplo.*)
lemma ejercicio_13a:
assumes "∀x.(D(x) ∧ (∃y.(S(y) ∧ E(x,y))) ⟶ L(x))"
"∀x.(E(x,x) ⟶ L(x))"
"∀x.(D(x) ⟶ ¬E(x,x))"
shows "∀x.∀y.(D(x) ∧ S(y) ⟶ ¬E(x,y))"
oops
text {* ---------------------------------------------------------------
Ejercicio 14. Formalizar el siguiente argumento
Todos los robots obedecen a los amigos del programador jefe.
Alvaro es amigo del programador jefe, pero Benito no le
obedece. Por tanto, Benito no es un robot.
Usar R(x) para x es un robot
Ob(x,y) para x obedece a y
A(x) para x es amigo del programador jefe
b para Benito
a para Alvaro
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo"
lemma ejercicio_14a:
assumes "∀x.∀y.(R(x) ∧ A(y) ⟶ Ob(x,y))"
"A(a)"
"¬Ob(b,a)"
shows "¬R(b)"
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 15. Formalizar el siguiente argumento
En una pecera nadan una serie de peces. Se observa que:
* Hay algún pez x que para cualquier pez y, 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.
* No hay ningún pez que se coma a todos los demás.
* Ningún pez protege a ningún otro.
Por tanto, existe algún tiburón en la pecera.
Usar C(x,y) para x se come a y
P(x,y) para x protege a y
T(x) para x es un tiburón
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo"
lemma ejercicio_15a:
assumes "∃x.∀y.(¬C(x,y) ⟶ (∃z.(T(z) ∨ P(z,y))))"
"∀x.∃y.(¬C(x,y))"
"∀x.∀y.(¬P(x,y))"
shows "∃x.(T(x))"
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 16. Formalizar el siguiente argumento
Supongamos conocidos los siguientes hechos acerca del número de
aprobados de dos asignaturas A y B:
* Si todos los alumnos aprueban la asignatura A, entonces todos
aprueban la asignatura B.
* Si algún delegado de la clase aprueba A y B, entonces todos los
alumnos aprueban A.
* Si nadie aprueba B, entonces ningún delegado aprueba A.
* Si Manuel no aprueba B, entonces nadie aprueba B.
Por tanto, si Manuel es un delegado y aprueba la asignatura A,
entonces todos los alumnos aprueban las asignaturas A y B.
Usar A(x,y) para x aprueba la asignatura y
D(x) para x es delegado
m para Manuel
a para la asignatura A
b para la asignatura B
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo"
(* Apli2 dice que está bien, pero Isabelle no lo prueba y además da un
contraejemplo. *)
lemma ejercicio_16a:
assumes "(∀x.(A(x,a))) ⟶ (∀x.(A(x,b)))"
"(∃x.(D(x) ∧ A(x,a) ∧ A(x,b))) ⟶ (∀x.(A(x,a)))"
"(∀x.(¬A(x,b))) ⟶ (∀x.(D(x) ⟶ ¬A(x,a)))"
"¬A(m,b) ⟶ (∀x.(¬A(x,b)))"
shows "D(m) ∧ A(m,a) ⟶ (∀x.(A(x,a) ∧ A(x,b)))"
oops
text {* ---------------------------------------------------------------
Ejercicio 17. Formalizar el siguiente argumento
En cierto país oriental se ha celebrado la fase final del
campeonato mundial de fútbol. 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.
* Algún portero jugó con botas blancas y sólo le marcaron goles
jugadores con botas blancas.
* Ningún portero se marcó un gol a sí mismo.
* Ningún jugador con botas blancas vistió camiseta negra.
Por tanto, algún delantero europeo jugó con botas blancas.
Usar P(x) para x es portero
D(x) para x es delantero europeo
N(x) para x viste camiseta negra
B(x) para x juega con botas blancas
M(x,y) para x marcó un gol a y
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo."
(* Apli2 dice que está bien, pero Isabelle no lo prueba. No da contra-
ejemplo. *)
lemma ejercicio_17a:
assumes "∀x.∃y.(¬N(x) ∧ P(x) ⟶ D(y) ∧ M(y,x))"
"∃x.∀y.(P(x) ∧ B(x) ∧ (M(y,x) ⟶ B(y)))"
"∀x.(P(x) ⟶ ¬M(x,x))"
"∀x.(B(x) ⟶ ¬N(x))"
shows "∃x.(D(x) ∧ B(x))"
oops
text {* ---------------------------------------------------------------
Ejercicio 18. Formalizar el siguiente argumento
Las relaciones de parentesco verifican la siguientes propiedades
generales:
* Si x es hermano de y, entonces y es hermano de x.
* Todo el mundo es hijo de alguien.
* Nadie es hijo del hermano de su padre.
* Cualquier padre de una persona es también padre de todos los
hermanos de esa persona.
* Nadie es hijo ni hermano de sí mismo.
Tenemos los siguientes miembros de la familia Peláez: Don Antonio,
Don Luis, Antoñito y Manolito y sabemos que Don Antonio y Don Luis
son hermanos, Antoñito y Manolito son hermanos, y Antoñito es hijo
de Don Antonio. Por tanto, Don Luis no es el padre de Manolito.
Usar A para Don Antonio
He(x,y) para x es hermano de y
Hi(x,y) para x es hijo de y
L para Don Luis
a para Antoñito
m para Manolito
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo."
(*Otra vez Isabelle no lo demuestra en auto, pero no da contraejemplo.
Está hecho con apli2, asi que supongo que está bien.*)
lemma ejercicio_18a:
assumes "∀x.∃y.(Hi(x,y))"
"∀x.∀y.∀z.(He(x,y) ∧ Hi(z,x) ⟶ ¬Hijo(z,y))"
"∀x.∀y.∀z.(Hi(x,z) ∧ He(y,x) ⟶ Hi(y,z))"
"∀x.(¬He(x,x) ∧ ¬Hi(x,x))"
"He(A,L)"
"He(a,m)"
"Hi(a,A)"
shows "¬Hi(m,L)"
oops
-- "Pedro Ros"
lemma ejercicio_18b:
assumes "∀x.∃y.(Hi(x,y))"
"∀x.∀y.∀z.(He(x,y) ∧ Hi(z,x) ⟶ ¬Hi(z,y))"
"∀x.∀y.∀z.(Hi(x,z) ∧ He(y,x) ⟶ Hi(y,z))"
"∀x.(¬He(x,x) ∧ ¬Hi(x,x))"
"He(A,L)"
"He(a,m)"
"Hi(a,A)"
shows "¬Hi(m,L)"
proof -
have 1:"He(A,L)∧Hi(a,A)" using assms(5,7) ..
have "∀y.∀z.(He(A,y) ∧ Hi(z,A) ⟶ ¬Hi(z,y))" using assms(2)..
hence "∀z.(He(A,L) ∧ Hi(z,A) ⟶ ¬Hi(z,L))"..
hence "(He(A,L) ∧ Hi(a,A) ⟶ ¬Hi(a,L))"..
hence 2:"¬Hi(a,L)" using 1..
have "∀y.∀z.(Hi(m,z) ∧ He(y,m) ⟶ Hi(y,z))"using assms(3)..
hence "∀z.(Hi(m,z) ∧ He(a,m) ⟶ Hi(a,z))" ..
hence 3:"(Hi(m,L) ∧ He(a,m) ⟶ Hi(a,L))" ..
hence "¬(Hi(m,L) ∧ He(a,m))" using 2 by (rule mt)
hence 4:"¬Hi(m,L) ∨ ¬He(a,m)" by (rule ejercicio_57)
have 5:"¬¬He(a,m)" using assms(6) by (rule notnotI)
show ?thesis using 4 5 by (rule ejercicio_42)
qed
text {* ---------------------------------------------------------------
Ejercicio 19. [Problema del apisonador de Schubert (en inglés,
"Schubert’s steamroller")] Formalizar el siguiente argumento
Si uno de los miembros del club afeita a algún otro (incluido a
sí mismo), entonces todos los miembros del club lo han afeitado
a él (aunque no necesariamente al mismo tiempo). Guido, Lorenzo,
Petruccio y Cesare pertenecen al club de barberos. Guido ha
afeitado a Cesare. Por tanto, Petruccio ha afeitado a Lorenzo.
Usar g para Guido
l para Lorenzo
p para Petruccio
c para Cesare
B(x) para x es un miembro del club de barberos
A(x,y) para x ha afeitado a y
------------------------------------------------------------------ *}
text {* ---------------------------------------------------------------
Ejercicio 20. Formalizar el siguiente argumento
Carlos afeita a todos los habitantes de Las Chinas que no se
afeitan a sí mismo y sólo a ellos. Carlos es un habitante de las
Chinas. Por consiguiente, Carlos no afeita a nadie.
Usar A(x,y) para x afeita a y
C(x) para x es un habitante de Las Chinas
c para Carlos
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo"
lemma ejercicio_20a:
assumes "∀x.(A(c,x) ⟷ C(x) ∧ ¬A(x,x))"
"C(c)"
shows "∀x.(¬A(c,x))"
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 21. Formalizar el siguiente argumento
Quien desprecia a todos los fanáticos desprecia también a todos los
políticos. Alguien no desprecia a un determinado político. Por
consiguiente, hay un fanático al que no todo el mundo desprecia.
Usar D(x,y) para x desprecia a y
F(x) para x es fanático
P(x) para x es político
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_21:
assumes 1:"∀x. ((∀y. ((F(y)∧D(x,y)))⟶(∀z. P(z)⟶D(x,z)))) "and
2:"∃x. (∃y. P(y)∧(¬D(x,y)))" and
"∀x. (P(x)⟶F(x))"
shows "¬(∀x. (∃y. (F(y)∧D(x,y))))"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 22. Formalizar el siguiente argumento
El hombre puro ama todo lo que es puro. Por tanto, el hombre puro
se ama a sí mismo.
Usar A(x,y) para x ama a y
H(x) para x es un hombre
P(x) para x es puro
------------------------------------------------------------------ *}
-- "Reme Sillero"
lemma ejercicio_22:
assumes "∀x. ∀y. ((H(x) ∧ P(x) ∧ P(y))⟶ A(x,y))"
shows "∀x. ((H(x)∧ P(x))⟶A(x,x))"
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 23. Formalizar el siguiente argumento
Ningún socio del club está en deuda con el tesorero del club. Si
un socio del club no paga su cuota está en deuda con el tesorero
del club. Por tanto, si el tesorero del club es socio del club,
entonces paga su cuota.
Usar P(x) para x es socio del club
Q(x) para x paga su cuota
R(x) para x está en deuda con el tesorero
a para el tesorero del club
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_23:
assumes 1:"¬(∃x. P(x)∧R(x))" and
2:"∀x. ((¬Q(x))⟶R(x))"
shows "P(a)⟶Q(a)"
quickcheck
using assms by auto
-- "Reme Sillero"
lemma ejercicio_23a:
assumes "∀x. (P(x)⟶¬R(x))"
"∀x.((P(x)∧(¬Q(x)))⟶R(x))"
shows "P(a) ⟶Q(a)"
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 24. Formalizar el siguiente argumento
1. Los lobos, zorros, pájaros, orugas y caracoles son animales y
existen algunos ejemplares de estos animales.
2. También hay algunas semillas y las semillas son plantas.
3. 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.
4. Las orugas y los caracoles son mucho más pequeños que los
pájaros, que son mucho más pequeños que los zorros que a su vez
son mucho más pequeños que los lobos.
5. A los lobos no les gusta comer ni zorros ni semillas, mientras
que a los pájaros les gusta comer orugas pero no caracoles.
6. Las orugas y los caracoles gustan de comer algunas plantas.
7. Luego, existe un animal al que le gusta comerse un animal al que
le gusta comer semillas.
Usar A(x) para x es un animal
Ca(x) para x es un caracol
Co(x,y) para x le gusta comerse a y
L(x) para x es un lobo
M(x,y) para x es más pequeño que y
Or(x) para x es una oruga
Pa(x) para x es un pájaro
Pl(x) para x es una planta
S(x) para x es una semilla
Z(x) para x es un zorro
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_24:
assumes 1:"∀x. ((L(x)∨Ca(x)∨Or(x)∨Pa(x)∨Z(x))⟶A(x))" and "(∃x. L(x))∧(∃x. Ca(x))∧(∃x. Or(x))∧(∃x. Pa(x))∧(∃x. Z(x))"and
2:"(∃x. S(x))∧(∀y. S(y)⟶Pa(y))"and
3:"∀x. (A(x) ⟶ ((∀y.∀z.(Pa(z)⟶(A(y)∧M(y,x)∧Co(y,z))⟶Co(x,y))∧(Pa(y)⟶Co(x,y)) )))" and
4:"∀x. ((Or(x)∨Ca(x))⟶(∀y. (Pa(y)⟶M(x,y))))" and "∀x. (∀y. ((Z(y)∧Pa(x))⟶M(x,y)))" and "∀x. (∀y. ((L(y)∧Z(x))⟶M(x,y)))"and
5:"∀x. ∀y. ∀z. ((L(x)∧S(y)∧Z(z))⟶ (¬Co(x,y)∧ ¬Co(x,z)))" and "∀x. ∀y. ∀z.((Pa(x)∧Or(y)∧Ca(z))⟶ (Co(x,y)∧¬Co(x,z)))" and
6:"∀x. ∀y. (∃z. ((Pa(z)∧Ca(x)∧Or(y))⟶(Co(x,z)∨Co(y,z))))"
shows "∃x. (∃y. (∃z. (S(z)∧A(y)∧Co(y,z)∧A(x)∧Co(x,y))))"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 25. Formalizar el siguiente argumento
Rosa ama a Curro. Paco no simpatiza con Ana. Quien no simpatiza con
Ana ama a Rosa. Si una persona ama a otra, la segunda ama a la
primera. Hay como máximo una persona que ama a Rosa. Por tanto,
Paco es Curro.
Usar A(x,y) para x ama a y
S(x,y) para x simpatiza con y
a para Ana
c para Curro
p para Paco
r para Rosa
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_25:
assumes 1:"A(r,c)" and
2:"¬S(p,a)" and
3:"∀x. ((¬S(x,a))⟶(A(x,r)))" and
4:"∀x. ∀y. (A(x,y)⟷A(y,x))" and
5:"(∃x. A(x,r))⟶(∀y. (A(y,r)⟶(y=x)))" and
"r∧c∧p∧a" (*para que la demostración sea posible*)
shows "p=c"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 26. Formalizar el siguiente argumento
Sólo hay un sofista que enseña gratuitamente, y éste es
Sócrates. Sócrates argumenta mejor que ningún otro sofista. Platón
argumenta mejor que algún sofista que enseña gratuitamente. Si una
persona argumenta mejor que otra segunda, entonces la segunda no
argumenta mejor que la primera. Por consiguiente, Platón no es un
sofista.
Usar G(x) para x enseña gratuitamente
M(x,y) para x argumenta mejor que y
S(x) para x es un sofista
p para Platón
s para Sócrates
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_26:
assumes 1:"(∀x. (S(x)∧G(x)⟷ (x=s)))∧(∃x. (S(x)∧G(x)))" and
2:"∀x. (S(x)⟶ M(s,x))" and
3:"∃x. ((S(x)∧G(x))∧M(p,x))" and
4:"∀x. (∀y. (M(x,y)⟷¬M(y,x)))" and
"p∧s" and "¬(∃x. M(x,x))" and "¬(p=s)" and "(∃x. ((x=s)∧M(p,x)))⟷ s∧M(p,s)" (*Para la demostración *)
shows "¬S(p)"
proof
assume 5:"S(p)"
have 6:"S(p)⟶M(s,p)" using 2..
hence 7: "M(s,p)" using 5..
have 8: "∀y. (M(s,y)⟷¬M(y,s))" using 4..
hence 9: "M(s,p)⟷¬M(p,s)" ..
hence 10:"¬M(p,s)" using 7..
have 11: "∀x. (S(x)∧G(x)⟷(x=s))" using 1..
have 12: "p≠s" using assms(7) .
have 13: "(∀x. (S(x)∧G(x)⟷ (x=s)))" using 1..
hence 14: "(S(p)∧G(p)) ⟷ (p=s)" ..
have "(¬G(p)) ∨G(p)" ..
moreover
{assume "¬G(p)"
have 15: "(∀x. (S(x)∧G(x)⟷ (x=s)))⟶((∃x. ((S(x)∧G(x))∧M(p,x)))⟷(∃x. ((x=s)∧M(p,x))))" by auto
hence 16: "((∃x. ((S(x)∧G(x))∧M(p,x)))⟷(∃x. ((x=s)∧M(p,x))))" using 11 ..
hence 17: "(∃x. ((x=s)∧M(p,x)))" using 3..
with assms(8) have 18: "s∧M(p,s)" ..
hence 19:"M(p,s)" ..
with 10 have 20: False ..}
moreover
{assume "G(p)"
with 5 have 15: "(S(p)∧G(p))" ..
with 14 have 16: "p=s" ..
with 12 have False ..}
ultimately
show False ..
qed
text {* ---------------------------------------------------------------
Ejercicio 27. Formalizar el siguiente argumento
Todos los filósofos se han preguntado qué es la filosofía. Los que
se preguntan qué es la filosofía se vuelven locos. Nietzsche es
filósofo. El maestro de Nietzsche no acabó loco. Por tanto,
Nietzsche y su maestro son diferentes personas.
Usar F(x) para x es filósofo
L(x) para x se vuelve loco
P(x) para x se ha preguntado qué es la filosofía.
m para el maestro de Nietzsche
n para Nietzsche
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_27:
assumes 1:"∀x. (F(x)⟶P(x))" and
2:"∀x. (P(x)⟶L(x))" and
3:"F(n)"and
4:"¬L(m)"
shows "m≠n"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 28. Formalizar el siguiente argumento
Los padres son mayores que los hijos. Juan es el padre de Luis. Por
tanto, Juan es mayor que Luis.
Usar M(x,y) para x es mayor que y
p(x) para el padre de x
j para Juan
l para Luis
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo"
lemma ejercicio_28:
assumes "∀x.(M(p(x),x))"
"j = p(l)"
shows "M(j,l)"
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 29. Formalizar el siguiente argumento
El esposo de la hermana de Toni es Roberto. La hermana de Toni es
María. Por tanto, el esposo de María es Roberto.
Usar e(x) para el esposo de x
h para la hermana de Toni
m para María
r para Roberto
------------------------------------------------------------------ *}
-- "Raúl Montes Pajuelo"
lemma ejercicio_29a:
assumes "e(h) = r"
"h = m"
shows "e(m) = r"
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 30. Formalizar el siguiente argumento
Luis y Jaime tienen el mismo padre. La madre de Rosa es
Eva. Eva ama a Carlos. Carlos es el padre de Jaime. Por tanto,
la madre de Rosa ama al padre de Luis.
Usar A(x,y) para x ama a y
m(x) para la madre de x
p(x) para el padre de x
c para Carlos
e para Eva
j para Jaime
l para Luis
r para Rosa
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_30:
assumes 1:"p(l)=p(j)"and
2:"e=m(r)"and
3:"A(e,c)"and
4:"c=p(j)"
shows "A((m(r)),(p(l)))"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 31. Formalizar el siguiente argumento
Si dos personas son hermanos, entonces tienen la misma madre y el
mismo padre. Juan es hermano de Luis. Por tanto, la madre del padre
de Juan es la madre del padre de Luis.
Usar H(x,y) para x es hermano de y
m(x) para la madre de x
p(x) para el padre de x
j para Juan
l para Luis
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_31:
assumes 1:"∀x. ∀y. (H(x,y)⟶ ((p(x)⟷p(y))∧(m(x)⟷m(y))))"and
2: "H(j,l)"
shows "m(p(j))= m(p(l))"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 32. Formalizar el siguiente argumento
Todos los miembros del claustro son asturianos. El secretario forma
parte del claustro. El señor Martínez es el secretario. Por tanto,
el señor Martínez es asturiano.
Usar C(x) para x es miembro del claustro
A(x) para x es asturiano
s para el secretario
m para el señor Martínez
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_32:
assumes 1:"∀x. (C(x)⟶A(x))" and
2:"C(s)"and
3:"m=s" and "s"
shows "A(m)"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 33. Formalizar el siguiente argumento
Eduardo pudo haber visto al asesino. Antonio fue el primer testigo
de la defensa. O Eduardo estaba en clase o Antonio dio falso
testimonio. Nadie en clase pudo haber visto al asesino. Luego, el
primer testigo de la defensa dio falso testimonio.
Usar C(x) para x estaba en clase
F(x) para x dio falso testimonio
V(x) para x pudo haber visto al asesino
a para Antonio
e para Eduardo
p para el primer testigo de la defensa
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_33:
assumes 1:"(V(e))"and
2:"a=p"and
3:"C(e) ∨ F(a)"and
4:"∀x. (C(x)⟶¬V(x))"
shows "F(a)"
using 3
proof
assume 5:"C(e)"
have "C(e)⟶¬(V(e))" using 4..
hence 6:"¬V(e)" using 5..
hence False using 1 ..
hence "¬C(e)"..
with 3 show "F(a)" by (rule ejercicio_43)
next
assume 5: "F(a)"
thus ?thesis .
qed
text {* ---------------------------------------------------------------
Ejercicio 34. Formalizar el siguiente argumento
La luna hoy es redonda. La luna de hace dos semanas tenía forma de
cuarto creciente. Luna no hay más que una, es decir, siempre es la
misma. Luego existe algo que es a la vez redondo y con forma de
cuarto creciente.
Usar L(x) para la luna del momento x
R(x) para x es redonda
C(x) para x tiene forma de cuarto creciente
h para hoy
d para hace dos semanas
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_34:
assumes 1:"R(L(h))" and
2:"C(L(d))" and
3:"∀x. (∀y. (L(x)⟷L(y)))" and
"L(h)∧L(d)"(*Para demostrarlo*)
shows "∃x. (C(x)∧R(x))"
quickcheck
using assms by auto
text {* ---------------------------------------------------------------
Ejercicio 35. Formalizar el siguiente argumento
Juana sólo tiene un marido. Juana está casada con Tomás. Tomás es
delgado y Guillermo no. Luego, Juana no está casada con Guillermo.
Usar D(x) para x es delgado
C(x,y) para x está casada con y
g para Guillermo
j para Juana
t para Tomás
------------------------------------------------------------------ *}
-- "Pedro Ros"
lemma ejercicio_35:
assumes 1:"(∃x. C(j,x))∧(∀y. C(j,y)⟶(y=x))"and
2: "C(j,t)" and
3:"D(t)∧¬D(g)"
"g≠t"
shows "¬C(j,g)"
quickcheck
proof
assume 4:"C(j,g)"
have "C(j,t)∧(∀y. C(j,y)⟶(y=t))" using 1 2 by auto
hence "(∀y. C(j,y)⟶(y=t))"..
hence "C(j,g)⟶(g=t)"..
hence "g=t" using 4..
with assms(4) show False..
qed
text {* ---------------------------------------------------------------
Ejercicio 36. Formalizar el siguiente argumento
Sultán no es Chitón. Sultán no obtendrá un plátano a menos que
pueda resolver cualquier problema. Si el chimpancé Chitón trabaja
más que Sultán resolverá problemas que Sultán no puede resolver.
Todos los chimpancés distintos de Sultán trabajan más que Sultán.
Por consiguiente, Sultán no obtendrá un plátano.
Usar Pl(x) para x obtiene el plátano
Pr(x) para x es un problema
R(x,y) para x resuelve y
T(x,y) para x trabaja más que y
c para Chitón
s para Sultán
------------------------------------------------------------------ *}
-- "Pedro G. Ros Reina"
lemma ejercicio_36:
assumes 1:"c≠s" and
2:"(∀x. (Pr(x)⟶R(s,x)))⟷ Pl(s)" and
3:"T(c,s)⟶(∃x. (Pr(x)∧(¬R(s,x))∧R(c,x)))" and
4:"∀x. ((x≠s)⟶T(x,s))"and
"¬(∃x. R(x,x))" and "¬(∃x. T(x,x))"
shows "¬Pl(s)"
quickcheck
using assms by auto
end