Práctica 4 (LyC Verano)
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=0 ٧ p3=1 ٧ p1=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 todo 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 | 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)
Definimos los conectivos:
Para {|}:
- ¬p = p|p
- p٨q = ¬(p|q)
- El resto sale ya que {¬,٨} es adecuado
Para {↓}:
- ¬p = p↓p
- p٧q = ¬(p↓q)
- El resto sale ya que {¬,٧} 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 (se prueba similar al ej. 7)
Ejercicio 11
a)
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)
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(Γ)