Lógica matemática y fundamentos (2014-15) - Contribuciones del usuario [es]

Relación 2b

2015-02-20T18:15:27Z

Javrodviv1:

=== Relación 2b: Sintaxis y semántica de la Lógica proposicional ===

----
'''Ejercicio 1.'''
Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos
puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente.
Se informa al prisionero que en cada una de las habitaciones puede haber un
tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a
la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada
puerta hay un letrero:

* puerta 1: en esta habitación hay una dama y en la otra un tigre.
* puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones
hay un tigre.

Sabiendo que uno de los carteles dice la verdad y el otro no, determinar la puerta que
debe de elegir el prisionero.
----

'''Solución:'''
(Nota: Podemos suponer que en una habitacion hay un tigre o una dama
exclusivamente pues si se diera que en una misma habitación estuviera
el tigre y la dama, el prisionero no debería estar buscando
la habitación de la dama, pues si la encontrara el resultado sería desastroso)

Entonces podemos suponer que si el tigre no está en una entonces está en la otra
y análogamente con la dama.

p:"Tigre en 1 y Dama en 2"
¬p:"Tigre en 2 y Dama en 1"

Luego tenemos, segun lo que ha dicho el Rey que:

(p ⋁ ¬p)

Puerta 1 dice "En esta habitacion hay una dama y en la otra un tigre"
es decir 1 dice: p

q: "En una habitacion hay una dama"
s: "En una habitacion hay un tigre"

Puerta 2 dice "En una de estas habitaciones hay un tigre
y en una de estas habitaciones hay una dama"
es decir 2 dice: q ⋀ s

a: 1 dice verdad
b: 2 dice verdad

Tenemos entonces por el enunciado que a<--->¬b

Supongamos: que 1 dice la verdad (I(a)=1)si y solo si2 miente(I(¬b)=1)
y entonces tenemos que en la habitacion 1 hay una dama y en la otra un tigre(I(p)=1) y que en ninguna
habitacion hay una tigre y en ninguna hay una dama(I(¬(q ⋀ s), y esto
implicaria que en 1 no hay dama ni tigre y en dos tampoco.

F= (p ⋁ ¬p) ⋀ ((a <––> ¬b) ——> (p ⋀ (¬(q ⋀ s)—–>(¬(p ⋁ ¬p)))))

Pero para nuestra interpretación I(F)={I(a) = I(¬b) = I(p) = I(¬(q ⋀ s)) = 1}
nos sale que I(F)=0

Luego La puerta 1 no dice la verdad y la puerta 2 dice la verda, y por tanto en la habitación 1 está el tigre
y en la habitacion 2 está la dama que es por donde debe escapar el prisionero

----
'''Ejercicio 2.'''
Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes
afirmaciones:
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
----

'''Solución:'''

----
'''Ejercicio 3.'''
Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea
insatisfactible y donde cualquier conjunción de todas ellas menos una sea
satisfactible. Generalízalo a n fórmulas.
----

'''Solución:'''

Daremos un ejemplo del caso general. Para ello basta tomar F_i tautología, F_j satisfacible con i=/j y el resto de fórmulas F_k insatisfacibles con k=/i,j siendo i,j,k \in {1,2,...,n}

'''Pablo José Gerlach Mena'''

''' Solución 2:'''

Eso es falso Pablo, no puedo haber ninguna insatisfacible, ya que dada si existe una insatisfacible cuando coges esa y n-2 fórmulas mas, la conjunción de dichas es insatisfacible y no cumple la segunda propiedad de que cualquier conjunción de todas ellas menos una sea satisfacible.

La solución sería:

F₁= p

F₂ = p->¬q

F₃ = (p/\¬q) -> q

Con estas fórmulas se da que la conjunción de todas es insatisfacible y la conjunción de dos a dos es satisfacible.

La generalización a n fórmulas no la he demostrado aún.(3 minutos mas tarde)

Demostrada la generalización en n

Sean p_i con i= 1,2.. n-1. Denotamos por:

F₁=p_1

F_j= p_1-> ¬p_j j=2,3..n-1.

F_n= (p_1\/¬p_1)-> p_2\/p_3\/..\/p_n-1

Se puede comprobar mediante recursión que esto funciona.

----
'''Ejercicio 4.'''
* Probar que la fórmula (((p → q) → p) → p) es una tautología
* Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué
valores de n es A es una tautología?
----

'''Solución:'''

se puede hacer con tablas de verdad:
suponemos que es falsa

(((p → q) → p) → p)
0
1 '''0'''
0 '''1'''

(((p → q) → p) → p)
0
1 '''0'''
0 0
'''1''' 0

(((p → q) → p) → p)
0
1 '''0'''
1 '''1'''
estas son todas las interpretaciones posibles y vemos que en todas hay contradicción (en negrita) asi que es siempre verdadera

Relación 2b

2015-02-20T18:12:56Z

Javrodviv1:

=== Relación 2b: Sintaxis y semántica de la Lógica proposicional ===

----
'''Ejercicio 1.'''
Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos
puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente.
Se informa al prisionero que en cada una de las habitaciones puede haber un
tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a
la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada
puerta hay un letrero:

* puerta 1: en esta habitación hay una dama y en la otra un tigre.
* puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones
hay un tigre.

Sabiendo que uno de los carteles dice la verdad y el otro no, determinar la puerta que
debe de elegir el prisionero.
----

'''Solución:'''
(Nota: Podemos suponer que en una habitacion hay un tigre o una dama
exclusivamente pues si se diera que en una misma habitación estuviera
el tigre y la dama, el prisionero no debería estar buscando
la habitación de la dama, pues si la encontrara el resultado sería desastroso)

Entonces podemos suponer que si el tigre no está en una entonces está en la otra
y análogamente con la dama.

p:"Tigre en 1 y Dama en 2"
¬p:"Tigre en 2 y Dama en 1"

Luego tenemos, segun lo que ha dicho el Rey que:

(p ⋁ ¬p)

Puerta 1 dice "En esta habitacion hay una dama y en la otra un tigre"
es decir 1 dice: p

q: "En una habitacion hay una dama"
s: "En una habitacion hay un tigre"

Puerta 2 dice "En una de estas habitaciones hay un tigre
y en una de estas habitaciones hay una dama"
es decir 2 dice: q ⋀ s

a: 1 dice verdad
b: 2 dice verdad

Tenemos entonces por el enunciado que a<--->¬b

Supongamos: que 1 dice la verdad (I(a)=1)si y solo si2 miente(I(¬b)=1)
y entonces tenemos que en la habitacion 1 hay una dama y en la otra un tigre(I(p)=1) y que en ninguna
habitacion hay una tigre y en ninguna hay una dama(I(¬(q ⋀ s), y esto
implicaria que en 1 no hay dama ni tigre y en dos tampoco.

F= (p ⋁ ¬p) ⋀ ((a <––> ¬b) ——> (p ⋀ (¬(q ⋀ s)—–>(¬(p ⋁ ¬p)))))

Pero para nuestra interpretación I(F)={I(a) = I(¬b) = I(p) = I(¬(q ⋀ s)) = 1}
nos sale que I(F)=0

Luego La puerta 1 no dice la verdad y la puerta 2 dice la verda, y por tanto en la habitación 1 está el tigre
y en la habitacion 2 está la dama que es por donde debe escapar el prisionero

----
'''Ejercicio 2.'''
Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes
afirmaciones:
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
----

'''Solución:'''

----
'''Ejercicio 3.'''
Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea
insatisfactible y donde cualquier conjunción de todas ellas menos una sea
satisfactible. Generalízalo a n fórmulas.
----

'''Solución:'''

Daremos un ejemplo del caso general. Para ello basta tomar F_i tautología, F_j satisfacible con i=/j y el resto de fórmulas F_k insatisfacibles con k=/i,j siendo i,j,k \in {1,2,...,n}

'''Pablo José Gerlach Mena'''

Eso es falso Pablo, no puedo haber ninguna insatisfacible, ya que dada si existe una insatisfacible cuando coges esa y n-2 fórmulas mas, la conjunción de dichas es insatisfacible y no cumple la segunda propiedad de que cualquier conjunción de todas ellas menos una sea satisfacible.

La solución sería:

F₁= p

F₂ = p->¬q

F₃ = (p/\¬q) -> q

Con estas fórmulas se da que la conjunción de todas es insatisfecible y la conjunción de dos a dos es satisfacible.

La generalización a n fórmulas no la he demostrado aún.(3 minutos mas tarde)

Demostrada la generalización en n

Sean p_i con i= 1,2.. n-1. Denotamos por:

F₁=p_1

F_j= p_1-> ¬p_j j=2,3..n-1.

F_n= (p_1\/¬p_1)-> p_2\/p_3\/..\/p_n-1

Se puede comprobar mediante recursión que esto funciona.

----
'''Ejercicio 4.'''
* Probar que la fórmula (((p → q) → p) → p) es una tautología
* Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué
valores de n es A es una tautología?
----

'''Solución:'''

se puede hacer con tablas de verdad:
suponemos que es falsa

(((p → q) → p) → p)
0
1 '''0'''
0 '''1'''

(((p → q) → p) → p)
0
1 '''0'''
0 0
'''1''' 0

(((p → q) → p) → p)
0
1 '''0'''
1 '''1'''
estas son todas las interpretaciones posibles y vemos que en todas hay contradicción (en negrita) asi que es siempre verdadera

Relación 2b

2015-02-20T18:12:23Z

Javrodviv1:

=== Relación 2b: Sintaxis y semántica de la Lógica proposicional ===

----
'''Ejercicio 1.'''
Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos
puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente.
Se informa al prisionero que en cada una de las habitaciones puede haber un
tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a
la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada
puerta hay un letrero:

* puerta 1: en esta habitación hay una dama y en la otra un tigre.
* puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones
hay un tigre.

Sabiendo que uno de los carteles dice la verdad y el otro no, determinar la puerta que
debe de elegir el prisionero.
----

'''Solución:'''
(Nota: Podemos suponer que en una habitacion hay un tigre o una dama
exclusivamente pues si se diera que en una misma habitación estuviera
el tigre y la dama, el prisionero no debería estar buscando
la habitación de la dama, pues si la encontrara el resultado sería desastroso)

Entonces podemos suponer que si el tigre no está en una entonces está en la otra
y análogamente con la dama.

p:"Tigre en 1 y Dama en 2"
¬p:"Tigre en 2 y Dama en 1"

Luego tenemos, segun lo que ha dicho el Rey que:

(p ⋁ ¬p)

Puerta 1 dice "En esta habitacion hay una dama y en la otra un tigre"
es decir 1 dice: p

q: "En una habitacion hay una dama"
s: "En una habitacion hay un tigre"

Puerta 2 dice "En una de estas habitaciones hay un tigre
y en una de estas habitaciones hay una dama"
es decir 2 dice: q ⋀ s

a: 1 dice verdad
b: 2 dice verdad

Tenemos entonces por el enunciado que a<--->¬b

Supongamos: que 1 dice la verdad (I(a)=1)si y solo si2 miente(I(¬b)=1)
y entonces tenemos que en la habitacion 1 hay una dama y en la otra un tigre(I(p)=1) y que en ninguna
habitacion hay una tigre y en ninguna hay una dama(I(¬(q ⋀ s), y esto
implicaria que en 1 no hay dama ni tigre y en dos tampoco.

F= (p ⋁ ¬p) ⋀ ((a <––> ¬b) ——> (p ⋀ (¬(q ⋀ s)—–>(¬(p ⋁ ¬p)))))

Pero para nuestra interpretación I(F)={I(a) = I(¬b) = I(p) = I(¬(q ⋀ s)) = 1}
nos sale que I(F)=0

Luego La puerta 1 no dice la verdad y la puerta 2 dice la verda, y por tanto en la habitación 1 está el tigre
y en la habitacion 2 está la dama que es por donde debe escapar el prisionero

----
'''Ejercicio 2.'''
Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes
afirmaciones:
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
----

'''Solución:'''

----
'''Ejercicio 3.'''
Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea
insatisfactible y donde cualquier conjunción de todas ellas menos una sea
satisfactible. Generalízalo a n fórmulas.
----

'''Solución:'''

Daremos un ejemplo del caso general. Para ello basta tomar F_i tautología, F_j satisfacible con i=/j y el resto de fórmulas F_k insatisfacibles con k=/i,j siendo i,j,k \in {1,2,...,n}

'''Pablo José Gerlach Mena'''

Eso es falso Pablo, no puedo haber ninguna insatisfacible, ya que dada si existe una insatisfacible cuando coges esa y n-2 fórmulas mas, la conjunción de dichas es insatisfacible y no cumple la segunda propiedad de que cualquier conjunción de todas ellas menos una sea satisfacible.

La solución sería:
F₁= p
F₂ = p->¬q
F₃ = (p/\¬q) -> q

Con estas fórmulas se da que la conjunción de todas es insatisfecible y la conjunción de dos a dos es satisfacible.

La generalización a n fórmulas no la he demostrado aún.(3 minutos mas tarde)

Demostrada la generalización en n

Sean p_i con i= 1,2.. n-1. Denotamos por:

F₁=p_1

F_j= p_1-> ¬p_j j=2,3..n-1.

F_n= (p_1\/¬p_1)-> p_2\/p_3\/..\/p_n-1

Se puede comprobar mediante recursión que esto funciona.

----
'''Ejercicio 4.'''
* Probar que la fórmula (((p → q) → p) → p) es una tautología
* Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué
valores de n es A es una tautología?
----

'''Solución:'''

se puede hacer con tablas de verdad:
suponemos que es falsa

(((p → q) → p) → p)
0
1 '''0'''
0 '''1'''

(((p → q) → p) → p)
0
1 '''0'''
0 0
'''1''' 0

(((p → q) → p) → p)
0
1 '''0'''
1 '''1'''
estas son todas las interpretaciones posibles y vemos que en todas hay contradicción (en negrita) asi que es siempre verdadera

Relación 2b

2015-02-20T18:11:13Z

Javrodviv1:

=== Relación 2b: Sintaxis y semántica de la Lógica proposicional ===

----
'''Ejercicio 1.'''
Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos
puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente.
Se informa al prisionero que en cada una de las habitaciones puede haber un
tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a
la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada
puerta hay un letrero:

* puerta 1: en esta habitación hay una dama y en la otra un tigre.
* puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones
hay un tigre.

Sabiendo que uno de los carteles dice la verdad y el otro no, determinar la puerta que
debe de elegir el prisionero.
----

'''Solución:'''
(Nota: Podemos suponer que en una habitacion hay un tigre o una dama
exclusivamente pues si se diera que en una misma habitación estuviera
el tigre y la dama, el prisionero no debería estar buscando
la habitación de la dama, pues si la encontrara el resultado sería desastroso)

Entonces podemos suponer que si el tigre no está en una entonces está en la otra
y análogamente con la dama.

p:"Tigre en 1 y Dama en 2"
¬p:"Tigre en 2 y Dama en 1"

Luego tenemos, segun lo que ha dicho el Rey que:

(p ⋁ ¬p)

Puerta 1 dice "En esta habitacion hay una dama y en la otra un tigre"
es decir 1 dice: p

q: "En una habitacion hay una dama"
s: "En una habitacion hay un tigre"

Puerta 2 dice "En una de estas habitaciones hay un tigre
y en una de estas habitaciones hay una dama"
es decir 2 dice: q ⋀ s

a: 1 dice verdad
b: 2 dice verdad

Tenemos entonces por el enunciado que a<--->¬b

Supongamos: que 1 dice la verdad (I(a)=1)si y solo si2 miente(I(¬b)=1)
y entonces tenemos que en la habitacion 1 hay una dama y en la otra un tigre(I(p)=1) y que en ninguna
habitacion hay una tigre y en ninguna hay una dama(I(¬(q ⋀ s), y esto
implicaria que en 1 no hay dama ni tigre y en dos tampoco.

F= (p ⋁ ¬p) ⋀ ((a <––> ¬b) ——> (p ⋀ (¬(q ⋀ s)—–>(¬(p ⋁ ¬p)))))

Pero para nuestra interpretación I(F)={I(a) = I(¬b) = I(p) = I(¬(q ⋀ s)) = 1}
nos sale que I(F)=0

Luego La puerta 1 no dice la verdad y la puerta 2 dice la verda, y por tanto en la habitación 1 está el tigre
y en la habitacion 2 está la dama que es por donde debe escapar el prisionero

----
'''Ejercicio 2.'''
Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes
afirmaciones:
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
----

'''Solución:'''

----
'''Ejercicio 3.'''
Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea
insatisfactible y donde cualquier conjunción de todas ellas menos una sea
satisfactible. Generalízalo a n fórmulas.
----

'''Solución:'''

Daremos un ejemplo del caso general. Para ello basta tomar F_i tautología, F_j satisfacible con i=/j y el resto de fórmulas F_k insatisfacibles con k=/i,j siendo i,j,k \in {1,2,...,n}

'''Pablo José Gerlach Mena'''

Eso es falso Pablo, no puedo haber ninguna insatisfacible, ya que dada si existe una insatisfacible cuando coges esa y n-2 fórmulas mas, la conjunción de dichas es insatisfacible y no cumple la segunda propiedad de que cualquier conjunción de todas ellas menos una sea satisfacible.

La solución sería:
F₁= p
F₂ = p->¬q
F₃ = (p/\¬q) -> q

Con estas fórmulas se da que la conjunción de todas es insatisfecible y la conjunción de dos a dos es satisfacible.
La generalización a n fórmulas no la he demostrado aún.(3 minutos mas tarde)
Demostrada la generalización en n
Sean p_i con i= 1,2.. n-1. Denotamos por:
F₁=p_1
F_j= p_1-> ¬p_j j=2,3..n-1.
F_n= (p_1\/¬p_1)-> p_2\/p_3\/..\/p_n-1
Se puede comprobar mediante recursión que esto funciona.

----
'''Ejercicio 4.'''
* Probar que la fórmula (((p → q) → p) → p) es una tautología
* Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué
valores de n es A es una tautología?
----

'''Solución:'''

se puede hacer con tablas de verdad:
suponemos que es falsa

(((p → q) → p) → p)
0
1 '''0'''
0 '''1'''

(((p → q) → p) → p)
0
1 '''0'''
0 0
'''1''' 0

(((p → q) → p) → p)
0
1 '''0'''
1 '''1'''
estas son todas las interpretaciones posibles y vemos que en todas hay contradicción (en negrita) asi que es siempre verdadera

Relación 2b

2015-02-20T17:45:03Z

Javrodviv1:

=== Relación 2b: Sintaxis y semántica de la Lógica proposicional ===

----
'''Ejercicio 1.'''
Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos
puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente.
Se informa al prisionero que en cada una de las habitaciones puede haber un
tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a
la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada
puerta hay un letrero:

* puerta 1: en esta habitación hay una dama y en la otra un tigre.
* puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones
hay un tigre.

Sabiendo que uno de los carteles dice la verdad y el otro no, determinar la puerta que
debe de elegir el prisionero.
----

'''Solución:'''
(Nota: Podemos suponer que en una habitacion hay un tigre o una dama
exclusivamente pues si se diera que en una misma habitación estuviera
el tigre y la dama, el prisionero no debería estar buscando
la habitación de la dama, pues si la encontrara el resultado sería desastroso)

Entonces podemos suponer que si el tigre no está en una entonces está en la otra
y análogamente con la dama.

p:"Tigre en 1 y Dama en 2"
¬p:"Tigre en 2 y Dama en 1"

Luego tenemos, segun lo que ha dicho el Rey que:

(p ⋁ ¬p)

Puerta 1 dice "En esta habitacion hay una dama y en la otra un tigre"
es decir 1 dice: p

q: "En una habitacion hay una dama"
s: "En una habitacion hay un tigre"

Puerta 2 dice "En una de estas habitaciones hay un tigre
y en una de estas habitaciones hay una dama"
es decir 2 dice: q ⋀ s

a: 1 dice verdad
b: 2 dice verdad

Tenemos entonces por el enunciado que a<--->¬b

Supongamos: que 1 dice la verdad (I(a)=1)si y solo si2 miente(I(¬b)=1)
y entonces tenemos que en la habitacion 1 hay una dama y en la otra un tigre(I(p)=1) y que en ninguna
habitacion hay una tigre y en ninguna hay una dama(I(¬(q ⋀ s), y esto
implicaria que en 1 no hay dama ni tigre y en dos tampoco.

F= (p ⋁ ¬p) ⋀ ((a <––> ¬b) ——> (p ⋀ (¬(q ⋀ s)—–>(¬(p ⋁ ¬p)))))

Pero para nuestra interpretación I(F)={I(a) = I(¬b) = I(p) = I(¬(q ⋀ s)) = 1}
nos sale que I(F)=0

Luego La puerta 1 no dice la verdad y la puerta 2 dice la verda, y por tanto en la habitación 1 está el tigre
y en la habitacion 2 está la dama que es por donde debe escapar el prisionero

----
'''Ejercicio 2.'''
Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes
afirmaciones:
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
----

'''Solución:'''

----
'''Ejercicio 3.'''
Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea
insatisfactible y donde cualquier conjunción de todas ellas menos una sea
satisfactible. Generalízalo a n fórmulas.
----

'''Solución:'''

Daremos un ejemplo del caso general. Para ello basta tomar F_i tautología, F_j satisfacible con i=/j y el resto de fórmulas F_k insatisfacibles con k=/i,j siendo i,j,k \in {1,2,...,n}

'''Pablo José Gerlach Mena'''

Eso es falso Pablo, no puedo haber ninguna insatisfacible, ya que dada si existe una insatisfacible cuando coges esa y n-2 fórmulas mas, la conjunción de dichas es insatisfacible y no cumple la segunda propiedad de que cualquier conjunción de todas ellas menos una sea satisfacible.

La solución sería:
F₁= p
F₂ = p->¬q
F₃ = (p/\¬q) -> q

Con estas fórmulas se da que la conjunción de todas es insatisfecible y la conjunción de dos a dos es satisfacible.
La generalización a n fórmulas no la he demostrado aún

----
'''Ejercicio 4.'''
* Probar que la fórmula (((p → q) → p) → p) es una tautología
* Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué
valores de n es A es una tautología?
----

'''Solución:'''

se puede hacer con tablas de verdad:
suponemos que es falsa

(((p → q) → p) → p)
0
1 '''0'''
0 '''1'''

(((p → q) → p) → p)
0
1 '''0'''
0 0
'''1''' 0

(((p → q) → p) → p)
0
1 '''0'''
1 '''1'''
estas son todas las interpretaciones posibles y vemos que en todas hay contradicción (en negrita) asi que es siempre verdadera

Relación 2b

2015-02-20T17:28:23Z

Javrodviv1:

=== Relación 2b: Sintaxis y semántica de la Lógica proposicional ===

----
'''Ejercicio 1.'''
Un rey somete a un prisionero a la siguiente prueba: lo enfrenta a dos
puertas, de las que el prisionero debe elegir una, y entrar en la habitación correspondiente.
Se informa al prisionero que en cada una de las habitaciones puede haber un
tigre o una dama. Como es natural, el prisionero debe elegir la puerta que le lleva a
la dama (entre otras cosas, para no ser devorado por el tigre). Para ayudarle, en cada
puerta hay un letrero:

* puerta 1: en esta habitación hay una dama y en la otra un tigre.
* puerta 2: en una de estas habitaciones hay una dama y en una de estas habitaciones
hay un tigre.

Sabiendo que uno de los carteles dice la verdad y el otro no, determinar la puerta que
debe de elegir el prisionero.
----

'''Solución:'''
(Nota: Podemos suponer que en una habitacion hay un tigre o una dama
exclusivamente pues si se diera que en una misma habitación estuviera
el tigre y la dama, el prisionero no debería estar buscando
la habitación de la dama, pues si la encontrara el resultado sería desastroso)

Entonces podemos suponer que si el tigre no está en una entonces está en la otra
y análogamente con la dama.

p:"Tigre en 1 y Dama en 2"
¬p:"Tigre en 2 y Dama en 1"

Luego tenemos, segun lo que ha dicho el Rey que:

(p ⋁ ¬p)

Puerta 1 dice "En esta habitacion hay una dama y en la otra un tigre"
es decir 1 dice: p

q: "En una habitacion hay una dama"
s: "En una habitacion hay un tigre"

Puerta 2 dice "En una de estas habitaciones hay un tigre
y en una de estas habitaciones hay una dama"
es decir 2 dice: q ⋀ s

a: 1 dice verdad
b: 2 dice verdad

Tenemos entonces por el enunciado que a<--->¬b

Supongamos: que 1 dice la verdad (I(a)=1)si y solo si2 miente(I(¬b)=1)
y entonces tenemos que en la habitacion 1 hay una dama y en la otra un tigre(I(p)=1) y que en ninguna
habitacion hay una tigre y en ninguna hay una dama(I(¬(q ⋀ s), y esto
implicaria que en 1 no hay dama ni tigre y en dos tampoco.

F= (p ⋁ ¬p) ⋀ ((a <––> ¬b) ——> (p ⋀ (¬(q ⋀ s)—–>(¬(p ⋁ ¬p)))))

Pero para nuestra interpretación I(F)={I(a) = I(¬b) = I(p) = I(¬(q ⋀ s)) = 1}
nos sale que I(F)=0

Luego La puerta 1 no dice la verdad y la puerta 2 dice la verda, y por tanto en la habitación 1 está el tigre
y en la habitacion 2 está la dama que es por donde debe escapar el prisionero

----
'''Ejercicio 2.'''
Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes
afirmaciones:
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
----

'''Solución:'''

----
'''Ejercicio 3.'''
Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea
insatisfactible y donde cualquier conjunción de todas ellas menos una sea
satisfactible. Generalízalo a n fórmulas.
----

'''Solución:'''

Daremos un ejemplo del caso general. Para ello basta tomar F_i tautología, F_j satisfacible con i=/j y el resto de fórmulas F_k insatisfacibles con k=/i,j siendo i,j,k \in {1,2,...,n}

'''Pablo José Gerlach Mena'''

Eso es falso Pablo, no puedo haber ninguna insatisfacible, ya que dada si existe una insatisfacible cuando coges esa y n-2 fórmulas mas, la conjunción de dichas es insatisfacible y no cumple la segunda propiedad de que cualquier conjunción de todas ellas menos una sea satisfacible.

----
'''Ejercicio 4.'''
* Probar que la fórmula (((p → q) → p) → p) es una tautología
* Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué
valores de n es A es una tautología?
----

'''Solución:'''

se puede hacer con tablas de verdad:
suponemos que es falsa

(((p → q) → p) → p)
0
1 '''0'''
0 '''1'''

(((p → q) → p) → p)
0
1 '''0'''
0 0
'''1''' 0

(((p → q) → p) → p)
0
1 '''0'''
1 '''1'''
estas son todas las interpretaciones posibles y vemos que en todas hay contradicción (en negrita) asi que es siempre verdadera

Relación 2a

2015-02-13T16:23:55Z

Javrodviv1:

<source lang = "haskell">
-- SintaxisSemanticaProp.hs
-- Lógica proposicional: Sintaxis y semántica
-- José A. Alonso Jiménez <jalonso@us.es>
-- ---------------------------------------------------------------------

module SintaxisSemantica where

-- ---------------------------------------------------------------------
-- Librerías auxiliares --
-- ---------------------------------------------------------------------

import Data.List

-- ---------------------------------------------------------------------
-- Gramática de fórmulas prosicionales --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 1: Definir los siguientes tipos de datos:
-- * SímboloProposicional para representar los símbolos de proposiciones
-- * Prop para representar las fórmulas proposicionales usando los
-- constructores Atom, Neg, Conj, Disj, Impl y Equi para las fórmulas
-- atómicas, negaciones, conjunciones, implicaciones y equivalencias,
-- respectivamente.
-- ---------------------------------------------------------------------

type SímboloProposicional = String

data Prop = Atom SímboloProposicional
| Neg Prop
| Conj Prop Prop
| Disj Prop Prop
| Impl Prop Prop
| Equi Prop Prop
deriving (Eq,Ord)

instance Show Prop where
show (Atom p) = p
show (Neg p) = "no " ++ show p
show (Conj p q) = "(" ++ show p ++ " /\\ " ++ show q ++ ")"
show (Disj p q) = "(" ++ show p ++ " \\/ " ++ show q ++ ")"
show (Impl p q) = "(" ++ show p ++ " --> " ++ show q ++ ")"
show (Equi p q) = "(" ++ show p ++ " <--> " ++ show q ++ ")"

-- ---------------------------------------------------------------------
-- Ejercicio 2: Definir las siguientes fórmulas proposicionales
-- atómicas: p, p1, p2, q, r, s, t y u.
-- ---------------------------------------------------------------------

p, p1, p2, q, r, s, t, u :: Prop
p = Atom "p"
p1 = Atom "p1"
p2 = Atom "p2"
q = Atom "q"
r = Atom "r"
s = Atom "s"
t = Atom "t"
u = Atom "u"

-- ---------------------------------------------------------------------
-- Ejercicio 3: Definir la función
-- no :: Prop -> Prop
-- tal que (no f) es la negación de f.
-- ---------------------------------------------------------------------

no :: Prop -> Prop
no = Neg

-- ---------------------------------------------------------------------
-- Ejercicio 4: Definir los siguientes operadores
-- (/\), (\/), (-->), (<-->) :: Prop -> Prop -> Prop
-- tales que
-- f /\ g es la conjunción de f y g
-- f \/ g es la disyunción de f y g
-- f --> g es la implicación de f a g
-- f <--> g es la equivalencia entre f y g
-- ---------------------------------------------------------------------

infixr 5 \/
infixr 4 /\
infixr 3 -->
infixr 2 <-->
(/\), (\/), (-->), (<-->) :: Prop -> Prop -> Prop
(/\) = Conj
(\/) = Disj
(-->) = Impl
(<-->) = Equi

-- ---------------------------------------------------------------------
-- Símbolos proposicionales de una fórmula --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 5: Definir la función
-- símbolosPropFórm :: Prop -> [Prop]
-- tal que (símbolosPropFórm f) es el conjunto formado por todos los
-- símbolos proposicionales que aparecen en f. Por ejemplo,
-- símbolosPropFórm (p /\ q --> p) ==> [p,q]
-- ---------------------------------------------------------------------

simbolosPropForm :: Prop -> [Prop]
simbolosPropForm (Atom p) = [Atom p]
simbolosPropForm (Neg p) = simbolosPropForm p
simbolosPropForm (Conj p q) = nub ((simbolosPropForm p) ++ (simbolosPropForm q))
simbolosPropForm (Disj p q) = nub ((simbolosPropForm p) ++ (simbolosPropForm q))
simbolosPropForm (Impl p q) = nub ((simbolosPropForm p) ++ (simbolosPropForm q))
simbolosPropForm (Equi p q) = nub ((simbolosPropForm p) ++ (simbolosPropForm q))

-- Luis Curquejo

-- ---------------------------------------------------------------------
-- Interpretaciones --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 6: Definir el tipo de datos Interpretación para
-- representar las interpretaciones como listas de fórmulas atómicas.
-- ---------------------------------------------------------------------

type Interpretación = [Prop]

-- ---------------------------------------------------------------------
-- Significado de una fórmula en una interpretación --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 7: Definir la función
-- significado :: Prop -> Interpretación -> Bool
-- tal que (significado f i) es el significado de f en i. Por ejemplo,
-- significado ((p \/ q) /\ ((no q) \/ r)) [r] ==> False
-- significado ((p \/ q) /\ ((no q) \/ r)) [p,r] ==> True
-- ---------------------------------------------------------------------

significado :: Prop -> Interpretacion -> Bool
significado (Atom f) xs | elem (Atom f) xs = True
| otherwise = False
significado (Neg f) xs = not (significado f xs)
significado (Conj f q) xs = (significado f xs) && (significado q xs)
significado (Disj f q) xs = (significado f xs) || (significado q xs)
significado (Impl f q) xs | (significado f xs) == True = significado q xs
| otherwise = True
significado (Equi f q) xs = (significado f xs) == (significado q xs)

--Luis Curquejo

-- ---------------------------------------------------------------------
-- Interpretaciones de una fórmula --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 8: Definir la función
-- subconjuntos :: [a] -> [[a]]
-- tal que (subconjuntos x) es la lista de los subconjuntos de x. Por
-- ejmplo,
-- subconjuntos "abc" ==> ["abc","ab","ac","a","bc","b","c",""]
-- ---------------------------------------------------------------------

subconjuntos :: [a] -> [[a]]
subconjuntos [] = [[]]
subconjuntos [a] = [[],[a]]
subconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub
where sub = subconjuntos xs
-- Me acordaba de primero (seguro) Javier Rodríguez Vivas

-- ---------------------------------------------------------------------
-- Ejercicio 9: Definir la función
-- interpretacionesFórm :: Prop -> [Interpretación]
-- tal que (interpretacionesFórm f) es la lista de todas las
-- interpretaciones de f. Por ejemplo,
-- interpretacionesFórm (p /\ q --> p) ==> [[p,q],[p],[q],[]]
-- ---------------------------------------------------------------------

interpretacionesForm :: Prop -> [Interpretacion]
interpretacionesForm f = subconjuntos (simbolosPropForm f)

--Luis Curquejo

-- ---------------------------------------------------------------------
-- Modelos de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 10: Definir la función
-- esModeloFórmula :: Interpretación -> Prop -> Bool
-- tal que (esModeloFórmula i f) se verifica si i es un modelo de f. Por
-- ejemplo,
-- esModeloFórmula [r] ((p \/ q) /\ ((no q) \/ r)) ==> False
-- esModeloFórmula [p,r] ((p \/ q) /\ ((no q) \/ r)) ==> True
-- ---------------------------------------------------------------------

esModeloFormula :: Interpretacion -> Prop -> Bool
esModeloFormula i f = significado f i

-- Luis Curquejo

-- ---------------------------------------------------------------------
-- Ejercicio 11: Definir la función
-- modelosFórmula :: Prop -> [Interpretación]
-- tal que (modelosFórmula f) es la lista de todas las interpretaciones
-- de f que son modelo de F. Por ejemplo,
-- modelosFórmula ((p \/ q) /\ ((no q) \/ r))
-- ==> [[p,q,r],[p,r],[p],[q,r]]
-- ---------------------------------------------------------------------

modelosFórmula :: Prop -> [Interpretación]
modelosFórmula f = undefined

-- ---------------------------------------------------------------------
-- Fórmulas válidas, satisfacibles e insatisfacibles --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 12: Definir la función
-- esVálida :: Prop -> Bool
-- tal que (esVálida f) se verifica si f es válida. Por ejemplo,
-- esVálida (p --> p) ==> True
-- esVálida (p --> q) ==> False
-- esVálida ((p --> q) \/ (q --> p)) ==> True
-- ---------------------------------------------------------------------

esValida :: Prop -> Bool
esValida f = subconjuntos (simPro f) == modelosFormula f

-- Javier Rodríguez Vivas

-- ---------------------------------------------------------------------
-- Ejercicio 13: Definir la función
-- esInsatisfacible :: Prop -> Bool
-- tal que (esInsatisfacible f) se verifica si f es insatisfacible. Por
-- ejemplo,
-- esInsatisfacible (p /\ (no p)) ==> True
-- esInsatisfacible ((p --> q) /\ (q --> r)) ==> False
-- ---------------------------------------------------------------------

esInsatisfacible :: Prop -> Bool
esInsatisfacible f = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 14: Definir la función
-- esSatisfacible :: Prop -> Bool
-- tal que (esSatisfacible f) se verifica si f es satisfacible. Por
-- ejemplo,
-- esSatisfacible (p /\ (no p)) ==> False
-- esSatisfacible ((p --> q) /\ (q --> r)) ==> True
-- ---------------------------------------------------------------------

esSatisfacible :: Prop -> Bool
esSatisfacible f = undefined

-- ---------------------------------------------------------------------
-- Símbolos proposicionales de un conjunto de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 15: Definir la función
-- uniónGeneral :: Eq a => [[a]] -> [a]
-- tal que (uniónGeneral x) es la unión de los conjuntos de la lista de
-- conjuntos x. Por ejemplo,
-- uniónGeneral [] ==> []
-- uniónGeneral [[1]] ==> [1]
-- uniónGeneral [[1],[1,2],[2,3]] ==> [1,2,3]
-- ---------------------------------------------------------------------

unionGeneral :: Eq a => [[a]] -> [a]
unionGeneral [] = []
unionGeneral (x:xs) = nub(x++ unionGeneral xs)

--Javier Rodríguez Vivas

-- ---------------------------------------------------------------------
-- Ejercicio 16: Definir la función
-- símbolosPropConj :: [Prop] -> [Prop]
-- tal que (símbolosPropConj s) es el conjunto de los símbolos
-- proposiciones de s. Por ejemplo,
-- símbolosPropConj [p /\ q --> r, p --> s] ==> [p,q,r,s]
-- ---------------------------------------------------------------------

símbolosPropConj :: [Prop] -> [Prop]
símbolosPropConj s = undefined

-- ---------------------------------------------------------------------
-- Interpretaciones de un conjunto de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 17: Definir la función
-- interpretacionesConjunto :: [Prop] -> [Interpretación]
-- tal que (interpretacionesConjunto s) es la lista de las
-- interpretaciones de s. Por ejemplo,
-- interpretacionesConjunto [p --> q, q --> r]
-- ==> [[p,q,r],[p,q],[p,r],[p],[q,r],[q],[r],[]]
-- ---------------------------------------------------------------------

interpretacionesConjunto :: [Prop] -> [Interpretación]
interpretacionesConjunto s = undefined

-- ---------------------------------------------------------------------
-- Modelos de conjuntos de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 18: Definir la función
-- esModeloConjunto :: Interpretación -> [Prop] -> Bool
-- tal que (esModeloConjunto i s) se verifica si i es modelo de s. Por
-- ejemplo,
-- esModeloConjunto [p,r] [(p \/ q) /\ ((no q) \/ r), q --> r]
-- ==> True
-- esModeloConjunto [p,r] [(p \/ q) /\ ((no q) \/ r), r --> q]
-- ==> False
-- ---------------------------------------------------------------------

esModeloConjunto :: InterpretaciÃ³n -> [Prop] -> Bool
esModeloConjunto i s = elem False xs == False
where xs = [esModeloFormula i f | f<-s]

--Javier Rodriguez Vivas

-- ---------------------------------------------------------------------
-- Ejercicio 19: Definir la función
-- modelosConjunto :: [Prop] -> [Interpretación]
-- tal que (modelosConjunto s) es la lista de modelos del conjunto
-- s. Por ejemplo,
-- modelosConjunto [(p \/ q) /\ ((no q) \/ r), q --> r]
-- ==> [[p,q,r],[p,r],[p],[q,r]]
-- modelosConjunto [(p \/ q) /\ ((no q) \/ r), r --> q]
-- ==> [[p,q,r],[p],[q,r]]
-- ---------------------------------------------------------------------

modelosConjunto :: [Prop] -> [Interpretación]
modelosConjunto s = undefined

-- ---------------------------------------------------------------------
-- Conjuntos consistentes e inconsistentes de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 20: Definir la función
-- esConsistente :: [Prop] -> Bool
-- tal que (esConsistente s) se verifica si s es consistente. Por
-- ejemplo,
-- esConsistente [(p \/ q) /\ ((no q) \/ r), p --> r]
-- ==> True
-- esConsistente [(p \/ q) /\ ((no q) \/ r), p --> r, no r]
-- ==> False
-- ---------------------------------------------------------------------

esConsistente :: [Prop] -> Bool
esConsistente s = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 21: Definir la función
-- esInconsistente :: [Prop] -> Bool
-- tal que (esInconsistente s) se verifica si s es inconsistente. Por
-- ejemplo,
-- esInconsistente [(p \/ q) /\ ((no q) \/ r), p --> r]
-- ==> False
-- esInconsistente [(p \/ q) /\ ((no q) \/ r), p --> r, no r]
-- ==> True
-- ---------------------------------------------------------------------

esInconsistente :: [Prop] -> Bool
esInconsistente s = undefined

-- ---------------------------------------------------------------------
-- Consecuencia lógica --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 22: Definir la función
-- esConsecuencia :: [Prop] -> Prop -> Bool
-- tal que (esConsecuencia s f) se verifica si f es consecuencia de
-- s. Por ejemplo,
-- esConsecuencia [p --> q, q --> r] (p --> r) ==> True
-- esConsecuencia [p] (p /\ q) ==> False
-- ---------------------------------------------------------------------

esConsecuencia :: [Prop] -> Prop -> Bool
esConsecuencia s f = undefined

</source>