Diferencia entre revisiones de «Práctica 4 (LyC Verano)»

De Cuba-Wiki
Sin resumen de edición
 
(No se muestran 47 ediciones intermedias de 7 usuarios)
Línea 1: Línea 1:
<p class="unicode">
{{Back|Lógica y Computabilidad}}
 
== Ejercicio 01 ==
== Ejercicio 01 ==
<br>a) v(α) = v(¬p1) = 1
<br>a) v(α) = v(¬p1) = 1
Línea 9: Línea 10:
== Ejercicio 02 ==
== Ejercicio 02 ==
===a)===
===a)===
<br>1) v(α1) = 1 ↔ p1=0 ٧ p3=1 ٧ p1=1
<br>1) v(α1) = 1 ↔ p1=1 ٧ p3=1 ٧ p4=1
<br>2) v(α2) = 1 ↔ p2=1 ٧ (p3=0 ٨ p1=0)
<br>2) v(α2) = 1 ↔ p2=1 ٨ (p3=0 ٧ p1=0)
<br>3) v(α3) = 1 ↔ (p2=0 ٨ p3=0) ٧ (p2=1) ٧ (p5=0 ٧ p3=1)
<br>3) v(α3) = 1 ↔ (p2=0 ٨ p3=0) ٧ (p2=1) ٧ (p5=0) ٧ (p3=1)
 
===b)===
===b)===
<br>1) Esto vale si pasa a.1) ٨  
<br>1) Esto vale si pasa a.1) ٨  
Línea 26: Línea 28:
<br> ←) Si v(α)=0 ٧ v(β)=1 → v(α→β)=1
<br> ←) Si v(α)=0 ٧ v(β)=1 → v(α→β)=1
<br> →) Sup que no. Hay 4 casos:
<br> →) Sup que no. Hay 4 casos:
*α T y β F → v(α→β)=0
*α T y β F → v(α→β)=0 (ABS)
*α T y β C → si v(β)=0 → v(α→β)=0
*α T y β C → si v(β)=0 → v(α→β)=0 (ABS)
*α C y β F → si v(α)=1 → v(α→β)=0
*α C y β F → si v(α)=1 → v(α→β)=0 (ABS)
*α C y β C → Sea el caso α=β → v(α→β)=1, pero <math> Var(\alpha) \cap Var(\beta) \neq \empty </math> (ABS)
*α C y β C → Sea el caso α=β → v(α→β)=1, pero <math> Var(\alpha) \cap Var(\beta) \neq \empty </math> (ABS)


Línea 49: Línea 51:


== Ejercicio 06 ==
== Ejercicio 06 ==
===a)===
*Reflexiva:
*Antisimetrica:
*Transitiva:
===b)===
===c)===
== Ejercicio 07 ==
== Ejercicio 07 ==
===a)===
===a)===
Línea 69: Línea 78:
===b)===
===b)===
<br> 1) {¬} Como α solo usa el ¬, α siempre sera contingencia
<br> 1) {¬} Como α solo usa el ¬, α siempre sera contingencia
<br> 2) {٧,٨} Sup que lo es. Sea f | f(p)=1 para todo p, y vf la valuacion que extiende a f. Usando induccion en complejidad de α:
<br> 2) {٧,٨} Sup que lo es. Sea f | f(p)=1 para toda variable p, y vf la valuacion que extiende a f. Usando induccion en complejidad de α:
*Si α=p → vf(α)=vf(p)=1
*Si α=p → vf(α)=vf(p)=1
*Si α=p٧q → vf(α)=vf(p٧q)=max{vf(p),vf(q)}=max{1,1}=1
*Si α=p٧q → vf(α)=vf(p٧q)=max{vf(p),vf(q)}=max{1,1}=1
*Si α=p٨q → vf(α)=vf(p٨q)=min{vf(p),vf(q)}=min{1,1}=1
*Si α=p٨q → vf(α)=vf(p٨q)=min{vf(p),vf(q)}=min{1,1}=1
→ No es posible construir un α tq α=¬p, por lo que no hay un v | v(α)=0 → No es adecuado (ABS)
→ No es posible construir un α tq α=¬p, por lo que no hay un α | v(α)=0 → No es adecuado (ABS)
<br> 3) {٧,→} Sale muy similar a 2), si tomamos
<br> 3) {٧,→} Sale muy similar a 2), si tomamos
*Si α=p→q → vf(α)=vf(p→q)=max{1-vf(p),vf(q)}=max{0,1}=1
*Si α=p→q → vf(α)=vf(p→q)=max{1-vf(p),vf(q)}=max{0,1}=1
Línea 89: Línea 98:
Como se puede ver, α|β equivale a NAND y α↓β a NOR.
Como se puede ver, α|β equivale a NAND y α↓β a NOR.
===b)===
===b)===
Definimos los conectivos:
Sabemos que {¬,٨} es un conjunto de conectivos adecuado demostrado en 7a, tratemos de armar sus equivalentes
 
<br>Para {|}:
<br>Para {|}:
*¬p = p|p
*¬p = p|p
*p٨q = ¬(p|q)
*p٨q = (p|p)|(q|q)
*El resto sale ya que {¬,٨} es adecuado
 
Por lo tanto {|} es adecuado  
 
<br>Para {↓}:
<br>Para {↓}:
*¬p = p↓p
*¬p = p↓p
*p٧q = ¬(p↓q)
*p٧q = (p↓p)↓(q↓q)
*El resto sale ya que {¬,٧} es adecuado
 
Por lo tanto {} es adecuado


===c)===
===c)===
Sup. que hay otro conectivo adecuado (Sea * ese conectivo). Entonces ese conectivo no puede cumplir (1*1)=1 o (0*0)=0 (sino no podria construirse la negacion). Tomando eso en cuenta, de todas las posibilidades quedan los siguientes 4 casos:
<pre>
α β  ↓ *1 *2 |
1 1  0  0  0  0
1 0  0  0  1  1
0 1  0  1  0  1
0 0  1  1  1  1
</pre>
Como se ve, entre esos conectivos estan ↓ y |, que por a) son adecuados. Vemos los otros 2:
<br> α *1 β = (¬α٨β)٧(¬α٨¬β) = ¬α
<br> α *2 β = (α٨¬β)٧(¬α٨¬β) = ¬β
<br> Es decir, ambos usan el conjunto {¬} que no era adecuado, con lo cual no hay otros conectivos adecuados ademas de ↓ y | (ABS)


== Ejercicio 09 ==
== Ejercicio 09 ==
Línea 119: Línea 144:


===b)===
===b)===
No es adecuado (se prueba similar al ej. 7)
No es adecuado. Solo se pueden dar 2 casos:
* p→T = T
* T→p = p
Claramente no puede construirse la negacion → {T,→} no es adecuado


== Ejercicio 11 ==
== Ejercicio 11 ==
===a)===
===a)===
<math>
Γ satisfacible <math>\rightarrow (\exists v)(\forall p \in \Gamma) v(p)=1 \rightarrow (\forall p \in \Gamma') v(p)=1 \rightarrow</math> Γ' satisfacible
\Gamma satisfacible \rightarrow (\exists v)(\forall p \in \Gamma) v(p)=1 \rightarrow (\forall p \in \Gamma') v(p)=1 \rightarrow \Gamma' satisfacible
 
</math>
===b)===
===b)===
<br> ←) Con(Γ) es satisfacible y Γ <math>\subseteq</math> Con(Γ) ( ver 12.a ) →  por a) Γ es satisfacible
<br> ←) Con(Γ) es satisfacible y Γ <math>\subseteq</math> Con(Γ) ( ver 12.a ) →  por a) Γ es satisfacible
Línea 136: Línea 163:
Sea α Є Con(Γ1). Si v satisface a Γ2, tambien satisface a Γ1, luego a α → α Є Con(Γ2). Por lo tanto, Con(Γ1) <math>\subseteq</math> Con(Γ2)
Sea α Є Con(Γ1). Si v satisface a Γ2, tambien satisface a Γ1, luego a α → α Є Con(Γ2). Por lo tanto, Con(Γ1) <math>\subseteq</math> Con(Γ2)
===c)===
===c)===
Sea α Є Con(Γ1)
Como Γ1 <math>\subseteq</math> Con(Γ2) luego si v(Con(Γ2))=1 → v(Γ1)=1.
Como Γ2 <math>\subseteq</math> Con(Γ3) luego si v(Con(Γ3))=1 → v(Γ2)=1.
Entonces si v(Con(Γ3)) = 1 → v(Con(Γ2)) = 1 → v(Γ1)=1.
Luego v(Con(Γ3)) = 1 → v(Γ1)=1.
Por lo tanto vale que Γ1 <math>\subseteq</math> Con(Γ3)


===d)===
===d)===
Línea 143: Línea 176:


== Ejercicio 13 ==
== Ejercicio 13 ==
===a)===
===a)===
<br> →) supongamos que no. Vale Con({β})<math>\subseteq</math> Con({α}) y v(α→β)=0
Existe una v valuacion tal que v(α→β)=0. v(α)=1 y v(β)=0 entonces v(Con({α}))=1 y v(Con({β}))=0 pero esto es abusurdo.
<br> ←)
importa ver que cuando v(α)=1 obliga a v(β)=1 para ser tautologia entonces cuando v(Con({α}))=1 obliga v(Con({β}))=1 entonces Con({β}) <math>\subseteq</math> Con({α})
===b)===
===b)===
<br> 1. F α٨β no es consecuencia de α ni de β
<br> 2. F ni α ni β son consecuencias de α٧β
    Un ejemplo, si alfa es insatisfacible, con(alfa) es FORM y sea beta = p1, con(alfa) V con(beta) es FORM, pero esto es falso por que (no p1) pertenece a FORM pero no a con(alfa V beta).
<br> 3. V Sup. que no. Entonces existe ψ tq ψ ε Con(α→β) y ¬( ψ ε Con(β) ).
* ψ ε Con(α→β) -> (<math>\forall</math>v) (¬v(α) ٧ v(β)) → v(ψ)) -> (<math>\forall</math>v) (¬v(α) → v(ψ)) ٨ (v(β) → v(ψ)). En particular, (<math>\forall</math>v) v(β) → v(ψ).
* ¬( ψ ε Con(β) ) -> (<math>\exists</math>v) (v(β) ٨ ¬v(ψ)), entonces (<math>\exists</math>v) ¬(v(β) → v(ψ)), que es lo mismo que ¬(<math>\forall</math>v) (v(β) → v(ψ)) (ABS)


== Ejercicio 14 ==
== Ejercicio 14 ==
===a)===
<br>a)->b) Facil
===b)===
<br>b)->c) Esto implica que no hay valuacion que satisfaga {α1,..,αn}, por lo tanto no es satisfacible -> no es consistente -> <math>\exists</math>β tq {α1,..αn}|=β y {α1,..,αn}|=¬β
===c)===
<br>c)->d) (<math>\forall</math>β) β ε Con({α1,..αn}) -> (<math>\forall</math>v) v({α1,..αn})=1 -> v(β)=1. Como {α1,..αn} es insatisfacible, no hay v que cumpla esto -> la implicacion siempre es verdadera
===d)===
<br>d)->a) Como (<math>\forall</math>β) {α1,..αn}|=β, en particular {α1,..,αn}|=F. Entonces α1 ٨ .. ٨ αn |= F. Por teorema de la deduccion, |= α1 ٨ .. ٨ αn -> F, entonces |= ¬(α1 ٨ .. ٨ αn). Con lo cual ¬(α1 ٨ .. ٨ αn) ε Con(Ø)


== Ejercicio 15 ==
== Ejercicio 15 ==
===a)===
===a)===
Si ambas estan → Γ es inconsistente. Sup. que ninguna esta. Como Γ es MC →
*ΓU{α} es inconsistente → Γ|-¬α
*ΓU{¬α} es inconsistente → Γ|-α
Entonces Γ es inconsistente (ABS)
===b)===
===b)===
Sup. que no es maximal. Entonces hay una formula α tal que al agregarla no se pierde la consistencia. Sup. que ¬α ε Γ, con lo cual Γ|=¬α. Pero entonces si tomamos ΓU{α}, se cumple que ΓU{α}|=¬α, con lo cual no es consistente -> Γ no es satisfacible (ABS)


== Ejercicio 16 ==
== Ejercicio 16 ==
<br>←) Como Γ <math>\subseteq</math> Con(Γ), α ε Γ → α ε Con(Γ) → Γ|=α
<br>→) Sup. ¬(α ε Γ). Como Γ es MC → ¬α ε Γ. Entonces Γ|=¬α, y por HI Γ|=α → Γ es inconsistente → Γ es insatisfacible (ABS)


== Ejercicio 17 ==
== Ejercicio 17 ==
<br>Sup. que no. Entonces α <math>\notin</math> Γ y β <math>\notin</math> Γ. Como Γ es MC -> ¬α <math>\in</math> Γ y ¬β <math>\in</math> Γ. Entonces debera valer (¬α٨¬β)
<br>Por lo mismo, como α٧β <math>\in</math> Γ -> ¬(α٧β) <math>\notin</math> Γ -> (¬α٨¬β) <math>\notin</math> Γ. Con lo cual Γ no hace valer (¬α٨¬β) (ABS)
[[Category:Prácticas]]

Revisión actual - 20:29 28 feb 2009

Plantilla:Back

Ejercicio 01


a) v(α) = v(¬p1) = 1
b) v(α) = v( (p5 ٧ 0) → 0 ) = v(p5 → 0) = v(p5) = ?
c) v(α) = v( (0 ٧ 0) → 0 ) = v(0 → 0) = 1
d) v(α) = v(¬p4) = ?
e) v(α) = v( (p8 → p5)→(p8 ٨ p0) ) = ?

Ejercicio 02

a)


1) v(α1) = 1 ↔ p1=1 ٧ p3=1 ٧ p4=1
2) v(α2) = 1 ↔ p2=1 ٨ (p3=0 ٧ p1=0)
3) v(α3) = 1 ↔ (p2=0 ٨ p3=0) ٧ (p2=1) ٧ (p5=0) ٧ (p3=1)

b)


1) Esto vale si pasa a.1) ٨
2) Idem 1) para α2
3) Idem 1) para α3

Ejercicio 03

(Para simplificar, T=tautologia, F=contradiccion, C=contingencia)
a) v(α٨β)=1 ↔ v(α)=1 ٨ v(β)=1 ↔ α T y β T
b) v(α٧β)=0 ↔ ¬v(α)=1 ٨ ¬v(β)=1 ↔ v(α)=0 ٨ v(β)=0 ↔ α F y β F
c) v(α→β)=0 ↔ v(α)=1 ٨ v(β)=0 ↔ α T y β F
d)
←) Si v(α)=0 ٧ v(β)=1 → v(α→β)=1
→) Sup que no. Hay 4 casos:

  • α T y β F → v(α→β)=0 (ABS)
  • α T y β C → si v(β)=0 → v(α→β)=0 (ABS)
  • α C y β F → si v(α)=1 → v(α→β)=0 (ABS)
  • α C y β C → Sea el caso α=β → v(α→β)=1, pero (ABS)

Ejercicio 04

a)

Sup que no. Hay 4 casos:

  • α T y β T → v(α٨β)=1
  • α T y β F → v(α٨β)=0
  • α F y β T → v(α٨β)=0
  • α F y β F → v(α٨β)=0

→ α٨β nunca es C (ABS)

b)

Sup que no. Hay 2 casos:

  • α٨β T → α T y β T
  • α٨β F → α F o β F

→ α y β nunca son ambas C (ABS)

Ejercicio 05

Pueden pasar 2 cosas: v(α)=0 ٨ v(pi)=1 o v(α)=1 ٨ v(pi)=0 → Vale si α=¬pi

Ejercicio 06

a)

  • Reflexiva:
  • Antisimetrica:
  • Transitiva:

b)

c)

Ejercicio 07

a)

Definimos todos los conectivos en funcion a los elementos para cada conjunto:
1) {¬,٨,٧}

  • ¬p, p٨q, p٧q ya estan definidos
  • p→q = ¬p٧q


2) {¬,٨}

  • ¬p, p٨q ya estan definidos
  • p٧q = ¬(¬p ٨ ¬q)
  • p→q = ¬p٧q


3) {¬,٧}

  • ¬p, p٧q ya estan definidos
  • p٨q = ¬(¬p ٧ ¬q)
  • p→q = ¬p٧q


4) {¬,→}

  • ¬p, p→q ya estan definidos
  • p٨q = ¬(p → ¬q)
  • p٧q = ¬p → q

b)


1) {¬} Como α solo usa el ¬, α siempre sera contingencia
2) {٧,٨} Sup que lo es. Sea f | f(p)=1 para toda variable p, y vf la valuacion que extiende a f. Usando induccion en complejidad de α:

  • Si α=p → vf(α)=vf(p)=1
  • Si α=p٧q → vf(α)=vf(p٧q)=max{vf(p),vf(q)}=max{1,1}=1
  • Si α=p٨q → vf(α)=vf(p٨q)=min{vf(p),vf(q)}=min{1,1}=1

→ No es posible construir un α tq α=¬p, por lo que no hay un α | v(α)=0 → No es adecuado (ABS)
3) {٧,→} Sale muy similar a 2), si tomamos

  • Si α=p→q → vf(α)=vf(p→q)=max{1-vf(p),vf(q)}=max{0,1}=1

→ Volvemos a obtener un ABS

Ejercicio 08

a)

α β  α|β α↓β
1 1   0   0
1 0   1   0
0 1   1   0
0 0   1   1

Como se puede ver, α|β equivale a NAND y α↓β a NOR.

b)

Sabemos que {¬,٨} es un conjunto de conectivos adecuado demostrado en 7a, tratemos de armar sus equivalentes


Para {|}:

  • ¬p = p|p
  • p٨q = (p|p)|(q|q)

Por lo tanto {|} es adecuado


Para {↓}:

  • ¬p = p↓p
  • p٧q = (p↓p)↓(q↓q)

Por lo tanto {↓} es adecuado

c)

Sup. que hay otro conectivo adecuado (Sea * ese conectivo). Entonces ese conectivo no puede cumplir (1*1)=1 o (0*0)=0 (sino no podria construirse la negacion). Tomando eso en cuenta, de todas las posibilidades quedan los siguientes 4 casos:

α β  ↓ *1 *2 | 
1 1   0  0  0  0
1 0   0  0  1  1
0 1   0  1  0  1
0 0   1  1  1  1

Como se ve, entre esos conectivos estan ↓ y |, que por a) son adecuados. Vemos los otros 2:
α *1 β = (¬α٨β)٧(¬α٨¬β) = ¬α
α *2 β = (α٨¬β)٧(¬α٨¬β) = ¬β
Es decir, ambos usan el conjunto {¬} que no era adecuado, con lo cual no hay otros conectivos adecuados ademas de ↓ y | (ABS)

Ejercicio 09

a)

  • ¬p = *1(p,p,p) = (p→(¬p ٨ p)) = p→0 = ¬p
  • p→q = *1(p,¬p,q) = (p→(¬¬p ٨ q)) = (p→(p ٨ q)) = p→q
  • El resto sale ya que {¬,→} es adecuado

→ *1 es adecuado

b)

No es adecuado, ya que utiliza el conjunto {٨,→}, que tampoco lo es

Ejercicio 10

a)

  • p→q ya esta definido
  • ¬p = p→F = ¬p
  • El resto sale ya que {¬,→} es adecuado

→ {F,→} es adecuado

b)

No es adecuado. Solo se pueden dar 2 casos:

  • p→T = T
  • T→p = p

Claramente no puede construirse la negacion → {T,→} no es adecuado

Ejercicio 11

a)

Γ satisfacible Γ' satisfacible

b)


←) Con(Γ) es satisfacible y Γ Con(Γ) ( ver 12.a ) → por a) Γ es satisfacible
→) Sea v valuacion que satisface Γ → por def. de Con(), v(α)=1 α Є Con(Γ) → Con(Γ) es satisfacible

Ejercicio 12

a)

Sea α Є Γ. Si v satisface a Γ, tambien satisface a α → α Є Con(Γ). Por lo tanto Γ Con(Γ)

b)

Sea α Є Con(Γ1). Si v satisface a Γ2, tambien satisface a Γ1, luego a α → α Є Con(Γ2). Por lo tanto, Con(Γ1) Con(Γ2)

c)

Sea α Є Con(Γ1) Como Γ1 Con(Γ2) luego si v(Con(Γ2))=1 → v(Γ1)=1. Como Γ2 Con(Γ3) luego si v(Con(Γ3))=1 → v(Γ2)=1. Entonces si v(Con(Γ3)) = 1 → v(Con(Γ2)) = 1 → v(Γ1)=1. Luego v(Con(Γ3)) = 1 → v(Γ1)=1. Por lo tanto vale que Γ1 Con(Γ3)

d)


) Sea α Є Con(Con(Γ)). Si v satisface a Con(Γ), tambien satisface a α. Si w satisface a Γ, tambien satisface a Con(Γ), luego a α → α Є Con(Γ). Por lo tanto Con(Con(Γ)) Con(Γ)
) Vale usando a)
→ Con(Con(Γ))=Con(Γ)

Ejercicio 13

a)


→) supongamos que no. Vale Con({β}) Con({α}) y v(α→β)=0

Existe una v valuacion tal que v(α→β)=0. v(α)=1 y v(β)=0 entonces v(Con({α}))=1 y v(Con({β}))=0 pero esto es abusurdo.


←) importa ver que cuando v(α)=1 obliga a v(β)=1 para ser tautologia entonces cuando v(Con({α}))=1 obliga v(Con({β}))=1 entonces Con({β}) Con({α})

b)


1. F α٨β no es consecuencia de α ni de β
2. F ni α ni β son consecuencias de α٧β

    Un ejemplo, si alfa es insatisfacible, con(alfa) es FORM y sea beta = p1, con(alfa) V con(beta) es FORM, pero esto es falso por que (no p1) pertenece a FORM pero no a con(alfa V beta).


3. V Sup. que no. Entonces existe ψ tq ψ ε Con(α→β) y ¬( ψ ε Con(β) ).

  • ψ ε Con(α→β) -> (v) (¬v(α) ٧ v(β)) → v(ψ)) -> (v) (¬v(α) → v(ψ)) ٨ (v(β) → v(ψ)). En particular, (v) v(β) → v(ψ).
  • ¬( ψ ε Con(β) ) -> (v) (v(β) ٨ ¬v(ψ)), entonces (v) ¬(v(β) → v(ψ)), que es lo mismo que ¬(v) (v(β) → v(ψ)) (ABS)

Ejercicio 14


a)->b) Facil
b)->c) Esto implica que no hay valuacion que satisfaga {α1,..,αn}, por lo tanto no es satisfacible -> no es consistente -> β tq {α1,..αn}|=β y {α1,..,αn}|=¬β
c)->d) (β) β ε Con({α1,..αn}) -> (v) v({α1,..αn})=1 -> v(β)=1. Como {α1,..αn} es insatisfacible, no hay v que cumpla esto -> la implicacion siempre es verdadera
d)->a) Como (β) {α1,..αn}|=β, en particular {α1,..,αn}|=F. Entonces α1 ٨ .. ٨ αn |= F. Por teorema de la deduccion, |= α1 ٨ .. ٨ αn -> F, entonces |= ¬(α1 ٨ .. ٨ αn). Con lo cual ¬(α1 ٨ .. ٨ αn) ε Con(Ø)

Ejercicio 15

a)

Si ambas estan → Γ es inconsistente. Sup. que ninguna esta. Como Γ es MC →

  • ΓU{α} es inconsistente → Γ|-¬α
  • ΓU{¬α} es inconsistente → Γ|-α

Entonces Γ es inconsistente (ABS)

b)

Sup. que no es maximal. Entonces hay una formula α tal que al agregarla no se pierde la consistencia. Sup. que ¬α ε Γ, con lo cual Γ|=¬α. Pero entonces si tomamos ΓU{α}, se cumple que ΓU{α}|=¬α, con lo cual no es consistente -> Γ no es satisfacible (ABS)

Ejercicio 16


←) Como Γ Con(Γ), α ε Γ → α ε Con(Γ) → Γ|=α
→) Sup. ¬(α ε Γ). Como Γ es MC → ¬α ε Γ. Entonces Γ|=¬α, y por HI Γ|=α → Γ es inconsistente → Γ es insatisfacible (ABS)

Ejercicio 17


Sup. que no. Entonces α Γ y β Γ. Como Γ es MC -> ¬α Γ y ¬β Γ. Entonces debera valer (¬α٨¬β)
Por lo mismo, como α٧β Γ -> ¬(α٧β) Γ -> (¬α٨¬β) Γ. Con lo cual Γ no hace valer (¬α٨¬β) (ABS)