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 ٧ 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)=== |
Línea 78: |
Línea 76: |
| ===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 108: |
Línea 106: |
| <br>Para {↓}: | | <br>Para {↓}: |
| *¬p = p↓p | | *¬p = p↓p |
| *p٧q = (p↓p)↓(q↓q) | | *p٧q = (p↓p)(q↓q) |
|
| |
|
| Por lo tanto {↓} es adecuado | | Por lo tanto {↓} es adecuado |
Línea 151: |
Línea 149: |
| == 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(Γ) ( ver 12.a ) → por a) Γ es satisfacible |
Línea 176: |
Línea 175: |
|
| |
|
| == 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 == |
| <br>a)->b) Facil
| | ===a)=== |
| <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}|=¬β
| | ===b)=== |
| <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
| | ===c)=== |
| <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(Ø)
| | ===d)=== |
|
| |
|
| == 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]] | | |
| | [[Category:Lógica y Computabilidad]] |