Parcial Lógica 13/10/06 (Lógica y Computabilidad)

• 1. Demostraciones por Induccion y Conectivos Adecuados

a. Sea $\alpha$ perteneciente a Form, tal que los conectivos de \alpha no aparece el conectivo unario ¬.

1. Definir inductivamente $\alpha _{R}$, la f'ormula asociada a $\alpha$ que se obtiene leyendo los s'imbolos de $\alpha$ en orden inverso, cambiando el sentido de los par'entesis cuando corresponda. Por ejemplo, si $\alpha =((p_{1}\lor p_{2})\to (p_{4}\lor p_{3}))$, entonces $\alpha _{R}=((p_{3}\lor p_{4})\to (p_{2}\lor p_{1})).$

2. Si adem'as en la f'ormula no aparece el conectivo binario $\to$, mostrar que para toda valuaci'on vale $v(\alpha )\equiv v(\alpha _{R})$. Dar un ejemplo que muestre que esta afirmaci'on no es v'alida cuando $\to$ es un conectivo de $\alpha$

• Consecuencia L'ogica y 'Algebras de Boole

a. Dado Γ ⊂ Form definimos