p02

Departamento de Ciencias e Ingenier´ıa de la Computaci´on

´ matas
Lenguajes Formales y Auto
Segundo Cuatrimestre de 2013
Trabajo Pr´actico N◦ 2
´ gica proposicional
Lo
1. Escriba la versi´on parentizada de cada una de las siguientes expresiones. Indique previamente la precedencia utilizada.
a) ¬P ∧ Q → P ∨ R
b) P ∨ ¬Q ∨ R → P ∨ R → ¬Q
c) A → B ∨ ¬C ∨ D ∨ E → F
2. Eliminar tantos par´entesis comosea posible de cada una de las siguientes f´ormulas bien
formadas. (fbf ).
a) (((P ∨ Q) → (¬R)) ∨ (((¬Q) ∧ R) ∧ P ))
b) ((A → (B ∨ C)) → (A ∨ (¬(¬B))))
3. Mostrar que A → (B → C) no es equivalente a (A → B) → C.
4. Definir tautolog´ıa, contingencia y contradicci´
on. Luego, determinar si cada una de estas
fbf es tautolog´ıa, contingencia, o contradicci´on.
a) A ∧ B → A
b) A ∨ B → B
c) (A → B) ∨((C → ¬B) ∧ ¬C)
d ) A ∧ ¬(B → A)
5. Mostrar que las siguientes sentencias no son tautolog´ıas encontrando una asignaci´on de
valores de verdad que haga falsa la sentencia. Para ello, busque en cada caso, una manera
de hacer verdadera la premisa y falsa la conclusi´on.
a) (A ∨ B) → (C ∨ A) ∧ (¬C ∨ B)
b) (A → B) ∧ (B → ¬A) → A
c) (A → B) ∧ (B → C) → (C → A)
d ) (A ∨ B → C) ∧ A → (C → B)
Observe que,de alguna manera, lo que est´a haciendo en este ejercicio es probar que una
sentencia es falsa por medio de un contraejemplo (ya hab´ıamos hecho este tipo de pruebas
en el pr´actico anterior). El contraejemplo en este caso, es esa asignaci´on de valores de
verdad, que hace que la sentencia no sea verdadera.
6. Verifique cada una de las siguientes equivalencias a trav´es de una prueba deequivalencia1 .
a) (A → B) ∧ (A ∨ B) ≡ B
b) A ∧ B → C ≡ (A → C) ∨ (B → C)
1

Utilice las equivalencias/leyes/conversiones dadas en la tabla 6.3, pag 314 de [1]

c) A ∧ B → C ≡ A → (B → C)
d ) A ∨ B → C ≡ (A → C) ∧ (B → C)
e) A → B ∧ C ≡ (A → B) ∧ (A → C)
f ) A → B ∨ C ≡ (A → B) ∨ (A → C)
7. Hallar, para cada una de las siguientes sentencias, una fbf equivalente en forma normal
conjuntiva y una fbfequivalente en forma normal disyuntiva.
a) Q ∧ ¬P → P
b) (P ∨ Q) ∧ R
c) (A ∧ B) ∨ E ∨ F
d ) (A ∧ B) ∨ (C ∧ D) ∨ (E → F )
8. ¿Qu´e significa que una f´ormula en forma normal sea completa? Explicar claramente y dar
ejemplos.
9. Para cada una de las siguientes funciones booleanas, escribir una f´ormula en forma normal
disyuntiva completa y una f´ormula en forma normal conjuntiva completa.
a) f (P, Q) = true,si y solo si P es true.
b) g(P, Q, R) = true, si y solo si Q es true o R es false.
10. Joaqu´ın es bastante desordenado con las comidas, y el otro d´ıa coment´o que no siempre
desayuna. Explic´o a sus amigos que esto depende de tres factores: si se levanta temprano o
tarde, si tiene o no comida para preparar el desayuno, y si tiene hambre o no al levantarse.
Coment´o que en caso de levantarse yno tener hambre, no desayuna. Pero, si tiene comida
y hambre, no importa si se levant´o temprano o se le hace tarde, desayuna s´ı o s´ı. En caso
que se haya levantado temprano y tenga hambre, siempre desayuna. Pues no importa si no
tiene comida porque -como se levant´o temprano- tiene tiempo para cruzarse al mercado
a buscar algo para desayunar. Pero si se levanta tarde y encima no tiene comida,tenga
hambre o no, nunca desayuna.
Describa -a trav´es de una tabla de verdad- una funci´on booleana desayuno que describa
la situaci´on descripta. ¿Cu´antos argumentos tiene esta funci´on? ¿Qu´e representan cada
uno de estos argumentos? Encuentre una fbf equivalente a esa funci´on booleana.
11. ¿Qu´e significa que un conjunto de conectivos sea completo?.
12. Mostrar que cada uno de los siguientesconjuntos de conectivos (operadores booleanos)
es un conjunto completo de conectivos para el c´alculo proposicional
a) {¬, ∧}
b) {¬, ∨}
c) {¬, →}
d ) { false, → }
e) { NAND }
f ) { NOR }

13. Sistemas de Razonamiento Formal
a) ¿Cu´ales son los tres elementos que componen una Teor´ıa Formal o Sistema de Razonamiento Formal?
b) ¿Qu´e es una regla de inferencia y para qu´e sirve?
c) ¿Qu´e es una...