| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{Back|Lógica y Computabilidad}}
| |
|
| |
| == Ejercicio 01 == | | == Ejercicio 01 == |
| <br>a) v(α) = v(¬p1) = 1 | | <br>a) v(α) = v(¬p1) = 1 |
| Línea 10: |
Línea 8: |
| == Ejercicio 02 == | | == Ejercicio 02 == |
| ===a)=== | | ===a)=== |
| <br>1) v(α1) = 1 ↔ p1=1 ٧ p3=1 ٧ p4=1 | | <br>1) v(α1) = 1 ↔ p1=0 ٧ p3=1 ٧ p1=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 28: |
Línea 25: |
| <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 (ABS) | | *α T y β F → v(α→β)=0 |
| *α T y β C → si v(β)=0 → v(α→β)=0 (ABS) | | *α T y β C → v(α→β)=0 si v(β)=0 |
| *α C y β F → si v(α)=1 → v(α→β)=0 (ABS) | | *α C y β F → v(α→β)=0 si v(α)=1 |
| *α 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 α C y β C (ABS) |
|
| |
|
| == Ejercicio 04 == | | == Ejercicio 04 == |
| Línea 51: |
Línea 48: |
|
| |
|
| == Ejercicio 06 == | | == Ejercicio 06 == |
| ===a)===
| |
| *Reflexiva:
| |
| *Antisimetrica:
| |
| *Transitiva:
| |
| ===b)===
| |
| ===c)===
| |
|
| |
| == Ejercicio 07 == | | == Ejercicio 07 == |
| ===a)=== | | ===a)=== |
| Línea 78: |
Línea 68: |
| ===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 toda variable 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 todo 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(α)=0 → No es adecuado (ABS) | | → No es posible construir un α tq α=¬p, por lo que no hay un v | 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 98: |
Línea 88: |
| Como se puede ver, α|β equivale a NAND y α↓β a NOR. | | Como se puede ver, α|β equivale a NAND y α↓β a NOR. |
| ===b)=== | | ===b)=== |
| Sabemos que {¬,٨} es un conjunto de conectivos adecuado demostrado en 7a, tratemos de armar sus equivalentes
| | Definimos los conectivos: |
| | |
| <br>Para {|}: | | <br>Para {|}: |
| *¬p = p|p | | *¬p = p|p |
| *p٨q = (p|p)|(q|q) | | *p٨q = ¬(p|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↓p)↓(q↓q) | | *p٧q = ¬(p↓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 144: |
Línea 118: |
|
| |
|
| ===b)=== | | ===b)=== |
| No es adecuado. Solo se pueden dar 2 casos: | | No es adecuado (se prueba similar al ej. 7) |
| * p→T = T
| |
| * T→p = p
| |
| Claramente no puede construirse la negacion → {T,→} no es adecuado
| |
|
| |
|
| == Ejercicio 11 == | | == Ejercicio 11 == |
| ===a)=== | | ===a)=== |
| Γ satisfacible <math>\rightarrow (\exists v)(\forall p \in \Gamma) v(p)=1 \rightarrow (\forall p \in \Gamma') v(p)=1 \rightarrow</math> Γ' satisfacible
| | <math> |
| | | \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(Γ) → por a) Γ es satisfacible |
| <br> →) Sea v valuacion que satisface Γ → por def. de Con(), v(α)=1 <math>\forall</math> α Є Con(Γ) → Con(Γ) es satisfacible | | <br> →) Sea v valuacion que satisface Γ → por def. de Con(), v(α)=1 <math>\forall</math> α Є Con(Γ) → Con(Γ) es satisfacible |
|
| |
|
| == Ejercicio 12 == | | == Ejercicio 12 == |
| ===a)===
| |
| Sea α Є Γ. Si v satisface a Γ, tambien satisface a α → α Є Con(Γ). Por lo tanto Γ <math>\subseteq</math> Con(Γ)
| |
| ===b)===
| |
| 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)===
| |
| 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)===
| |
| <br><math>\subseteq</math>) 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(Γ)) <math>\subseteq</math> Con(Γ)
| |
| <br><math>\supseteq</math>) Vale usando a)
| |
| <br>→ Con(Con(Γ))=Con(Γ)
| |
|
| |
| == Ejercicio 13 == | | == Ejercicio 13 == |
|
| |
| ===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)===
| |
| <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 == |
| <br>a)->b) Facil
| |
| <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}|=¬β
| |
| <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
| |
| <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)===
| |
| 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 == | | == 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]]
| |
