Univ. Nacional de Colombia, Medellın – Escuela de MatematicasMatematicas Discretas – Febrero 28, 2010

Soluciones Taller 1

1. Si p → q es una forma proposicional falsa, determine el valor de verdad de

(a) ¬(¬p ↔ q) → (p → ¬q)

(b) ¬(¬p ∨ q) ↔ ¬(p ↔ ¬q)

(c) (¬p → q) ∧ ¬(p ∨ q)

Solucion: Si p → q es F entonces p es V y q es F (la unica asignacionque hace la implicacion F). Ası que solo es suficiente evaluar las formas paraesta asignacion.

(a)

p q ¬ (¬p ↔ q) → (p → ¬q)

V F F F V F V V V V

(b)

p q ¬ (¬p ∨ q) ↔ ¬ (p ↔ ¬q)

V F V F F F F F V V V

(c) Se tiene la siguiente equivalencia independientemente de la asignaciona p y q:

(¬p → q) ∧ ¬(p ∨ q) ⇔ (p ∨ q) ∧ ¬(p ∨ q) ⇔ F

2. Verifique las siguientes equivalencias usando propiedades conocidas. Tambienusando tablas de verdad.

(a) p → (q ∨ r) ⇔ (p → q) ∨ r

Solucion:

p → (q ∨ r) ⇔ ¬p ∨ (q ∨ r) equivalencia de →⇔ (¬p ∨ q) ∨ r asociatividad de ∨⇔ (p → q) ∨ r equivalencia de →1

(b) (p ∨ q) → r ⇔ (p → r) ∧ (q → r)

Solucion:

(p ∨ q) → r ⇔ ¬(p ∨ q) ∨ r equivalencia de →⇔ (¬p ∧ ¬q) ∨ r ley de de Morgan⇔ (¬p ∨ r) ∧ (¬q ∨ r) distributividad⇔ (p → r) ∧ (q → r) equivalencia de →3. Verifique las siguientes equivalencias usando equivalencias ya conocidas (equiv-

alencia de la implicacion en terminos de ¬ y ∨, asociatividad, leyes de deMorgan, etc; no use tablas de verdad):

(a) (p ∧ q) → r ⇔ p → (q → r)

Solucion:

(p ∧ q) → r ⇔ ¬(p ∧ q) ∨ r equiv. implicacion⇔ (¬p ∨ ¬q) ∨ r de Morgan⇔ ¬p ∨ (¬q ∨ r) asociatividad⇔ ¬p ∨ (q → r) equiv. implicacion⇔ p → (q → r) equiv. implicacion

(b) p ∧ (q → r) ⇔ (p → q) → (p ∧ r)

Solucion:

p ∧ (q → r) ⇔ p ∧ (¬q ∨ r) equiv. implicacion⇔ (p ∧ ¬q) ∨ (p ∧ r) distributividad⇔ ¬¬(p ∧ ¬q) ∨ (p ∧ r) doble negacion⇔ ¬(¬p ∨ ¬¬q) ∨ (p ∧ r) de Morgan⇔ ¬(¬p ∨ q) ∨ (p ∧ r) doble negacion⇔ ¬(p → q) ∨ (p ∧ r) equiv. implicacion⇔ (p → q) → (p ∧ r) equiv. implicacion

4. Muestre que cualquier conectivo binario se puede implementar usando soloel conectivo ↑ (no-y) y solo el conectivo ↓ (no-o). Indique por que no esposible implementar cualquier conectivo binario usando solo los conectivos∧ y ∨.

Solucion:

Todos los conectivos posibles se pueden implementar usando ∧, ∨ y ¬ pormedio de la forma normal disyuntiva, o de la forma normal conjuntiva. Oincluso usando solo ∧ y ¬, o solo ∨ y ¬ por medio de las leyes de de Morgan:

p ∧ q = ¬(¬p ∨ ¬q), y p ∨ q = ¬(¬p ∧ ¬q).

2

Veamos que ∧, ∨ y ¬ se pueden implementar usando solo ↑:

¬p = ¬(p ∧ p) = p ↑ p

p ∧ q = ¬(¬(p ∧ q)) = ¬(p ↑ q) = (p ↑ q) ↑ (p ↑ q)

p ∨ q = ¬(¬(p ∨ q)) = ¬(¬p ∧ ¬q) = ¬((p ↑ p) ∧ (q ↑ q)) = (p ↑ p) ↑ (q ↑ q)

donde se ha usado la expresion para ¬p en las otras dos. Y usando solo ↓:

¬p = ¬(p ∨ p) = p ↓ p

p ∨ q = ¬(¬(p ∨ q)) = ¬(p ↓ q) = (p ↓ q) ↓ (p ↓ q)

p ∧ q = ¬(¬(p ∧ q)) = ¬(¬p ∨ ¬q) = ¬((p ↓ p) ∨ (q ↓ q)) = (p ↓ p) ↓ (q ↓ q)

En cuanto a la segunda pregunta, observe que el resultado de ∧ y ∨ cuandolos valores de las variables son V y V es tambien V . Por lo tanto, unconectivo binario cuyo valor es F cuando sus variables son V y V no puedeser implementado por alguna combinacion de ∧ y ∨.

5. Verifique la siguiente implicacion logica

p → q, (p ∧ q) → r ⇒ p → r

(a) por medio de una tabla de verdad: la implicacion debe ser una tau-tologıa

Solucion: Verificamos que la tabla de verdad de la implicacioncorrespondiente es una tautologıa. En particular, se debe tener quesiempre que las premisas son V , la conclusion es V (esto ocurre en laslıneas 1, 5, 6, 7, 8):

p q r ((p → q) ∧ ((p ∧ q) → r)) → (p → r)

V V V V V V V V V

V V F V F V F V F

V F V F F F V V V

V F F F F F V V F

F V V V V F V V V

F V F V V F V V V

F F V V V F V V V

F F F V V F V V V

(b) usando la equivalencia (definicion) de la implicacion: p → r ⇔ ¬p ∨ r

Solucion:

3

1. p → q premisa2. (p ∧ q) → r premisa3. ¬p ∨ q equivalencia de 1 (implicacion)4. ¬(p ∧ q) ∨ r equivalencia de 2 (implicacion)5. (¬p ∨ ¬q) ∨ r equivalencia de 4 (de Morgan)6. ¬p ∨ (¬q ∨ r) equivalencia de 5 (asociatividad)7. ¬p ∨ (r ∨ ¬q) equivalencia de 6 (conmutatividad)8. (¬p ∨ r) ∨ ¬q equivalencia de 7 (asociatividad)9. ¬p ∨ (¬p ∨ r) resolucion de 3 y 810. (¬p ∨ ¬p) ∨ r equivalencia de 9 (asociatividad)11. ¬p ∨ r equivalencia de 10 (idempotencia)12. p → r equivalencia de 11 (implicacion)

(c) con el metodo de prueba condicional

Solucion:1. p → q premisa2. (p ∧ q) → r premisa3. p premisa PC (prueba condicional)4. q MP 1,35. p ∧ q Conj. 3,46. r MP 5,27. p → r PC 3,6

6. (a) Verifique que la siguiente regla de inferencia es incorrecta:

p → (q ∨ r), q → ¬r, p ⇒ q ∧ ¬r

Como se puede modificar la conclusion para que sea correcta ? Justi-fique.

Solucion: [Una regla es correcta si siempre que las premisas son todasV, la conclusion es tambien V. Para determinar si la regla es correcta sepuede dar una deduccion usando otras reglas (correctas) o se puede verificarpor medio de una tabla de verdad que siempre que las premisas son todasV, la conclusion es tambien V. Para determinar que la regla es incorrectaes suficiente mostrar una asignacion de valores V o F a las variables talque todas las premisas son V pero la conclusion es F; esto se puede hacer“ensayando” valores, o “propagando restricciones” desde la conclusion (quedebe ser F), o simplemente escribiendo la tabla completa y verificando que almenos una lınea resulta en valores V para las premisas y F para la conclusion.Tratar de dar una deduccion y fallar en llegar a la conclusion deseada noconstituye una prueba de que la regla no es correcta. NO es cierto que si nose puede concluir algo (q∧¬r aquı), entonces se debe concluir su negacion.]

La regla de inferencia dada es incorrecta porque la asignacion “valorde p es V , valor de q es F y valor de r es V” resulta en valores V paratodos los precedentes y en valor F para el consecuente.

4

No hay una forma unica de “reparar” la regla. Una forma trivial esconcluir una premisa o una equivalencia de ella, por ejemplo (de lasegunda en este caso):

p → (q ∨ r), q → ¬r, p ⇒ ¬q ∨ ¬r

Mas interesante, por ejemplo, aplicando modus ponens a p y p →(q ∨ r) se infiere q ∨ r, y no parece haber otra deduccion mas “corta”.Ası se tiene:

p → (q ∨ r), q → ¬r, p ⇒ q ∨ r

Por otra parte examinando q ∨ r y ¬q ∨ ¬r (equivalente a la segundapremisa), se observa que entre q y r una debe ser V y la otra debe serF, lo cual es una conclusion mas “larga” pero quizas mas “interesante”:

p → (q ∨ r), q → ¬r, p ⇒ (q ∨ r) ∧ (¬q ∨ ¬r)

que es la conjuncion de las dos anteriores:

1. p → (q ∨ r) premisa2. q → ¬r premisa3. p premisa4. q ∨ r modus tollens 1,35. ¬q ∨ ¬r equivalencia de 26. (q ∨ r) ∧ (¬q ∨ ¬r) conjuncion 4,5

(b) Justifique que el siguiente argumento no es valido:

p ∧ ¬q premisap → (q → r) premisa

∴ ¬r conclusion

Solucion: Si p, q y r tienen valores de verdad V , F y V respectiva-mente, entonces la dos premisas son V pero la conclusion es F. Por lotanto el argumento no es valido.

Si se intercambian q y r en la segunda premisa se obtiene otra regla.Justifique que esta es valida usando reglas de inferencia basicas.

Solucion:

1. p ∧ ¬q premisa2. p → (r → q) premisa3. p simplificacion de 14. r → q modus ponens 2,35. ¬q simplificacion de 16. ¬r modus tollens 4,5.

7. Dar una prueba de la validez de la siguiente forma de argumento (indiqueen cada paso si es una premisa o que regla de inferencia o equivalencia seha aplicado).

5

(a)

p → q premisar ∨ s premisa¬s → ¬t premisa¬q ∨ s premisa¬s premisa¬p ∧ r → u premisaw ∨ t premisa

∴ u ∧ w conclusion

Solucion:1. p → q premisa2. r ∨ s premisa3. ¬s → ¬t premisa4. ¬q ∨ s premisa5. ¬s premisa6. ¬p ∧ r → u premisa7. w ∨ t premisa8. s ∨ r conmut. 29. r SD 5,810 s ∨ ¬q conmut. 411. ¬q SD 5,1012. ¬p MT 11,113 ¬p ∧ r conj. 12, 914. u MP 13,615. ¬t MP 5,316. t ∨ w conmut. 717. w SD 15,1618. u ∧ w conj. 14,17

Note que por ejemplo en 8 usamos conmutatividad antes de aplicarSD porque estrictamente SD requiere las variables en ese orden. Esedetalle por supuesto no es muy importante.

(b)

¬p → (r ∧ ¬s) premisat → s premisau → ¬p premisa¬w premisau ∨ w premisa

∴ ¬t ∨ w conclusion

Solucion:

6

1. ¬p → (r ∧ ¬s) premisa2. t → s premisa3. u → ¬p premisa4. ¬w premisa5. u ∨ w premisa6. w ∨ u conmutatividad 57. u silogismo disyuntivo 4,68. ¬p modus ponens 3,79. r ∧ ¬s modus ponens 1,810. ¬s simplificacion 911. ¬t modus tollens 2,1012. ¬t ∨ w disyuncion 11

8. Para los siguientes argumentos, escriba la correspondiente forma de argu-mento y una prueba de la validez.

(a) Si no llueve, entonces voy de compras. Si voy de comprasentonces, si no llevo la sombrilla entonces va a llover. Si voyen el carro entonces no llevare la sombrilla. Por lo tanto, vaa llover o no llevare el carro.

Solucion: Simbolizamos las proposiciones:

L: Llueve

C: Voy de compras

K: Voy en el carro

S: Llevo la sombrilla

La conclusion que se busca es L ∨ ¬K. Usamos las correspondientes le-tras minusculas para denotar variables (esto no es importante, podrıamostrabajar con las mayusculas) y escribir la forma de argumento:

¬` → c premisac → (¬s → `) premisak → ¬s premisa

∴ ` ∨ ¬k conclusion

Y la prueba de la validez del argumento:

1. ¬` → c premisa2. c → (¬s → `) premisa3. k → ¬s premisa4. ¬` → (¬s → `) SH 1,25. ` ∨ s equivalencia de 46. ¬k ∨ ¬s equivalencia de 37. ` ∨ ¬k resolucion de 5 y 6

La equivalencia en la lınea 5 se deberıa en principio detallar en terminosde equivalencias mas basicas, pero se ha omitido aquı porque resulta

7

muy largo:

¬` → (¬s → `) ⇔ ¬¬` ∨ (¬s → `)⇔ ` ∨ (¬s → `)⇔ ` ∨ (¬¬s ∨ `)⇔ ` ∨ (s ∨ `)⇔ ` ∨ (` ∨ s)⇔ (` ∨ `) ∨ s⇔ ` ∨ s.

En la lınea 7, en lugar de resolucion se podrıa hacer conjuncion de 5 y6 y luego simplificar usando equivalencias.

(b) Si el verano es muy caliente entonces no viajo de vacaciones.O viajo de vacaciones o compro un computador nuevo (posi-blemente ambos). Por lo tanto, si el verano es muy calienteentonces voy a comprar un computador nuevo.

Solucion: Simbolizamos las proposiciones:

M: El verano es muy caliente

V : Viajo de vacaciones

C: Compro un computador nuevo

Con estos sımbolos el argumento es:

M → ¬V premisaV ∨ C premisa

∴ M → C conclusion

Usamos las correspondientes letras minusculas para denotar variablesy escribir la forma de argumento (realmente no es importante estepaso y obviamente se puede continuar todo con las mayusculas, perolo hacemos para ser consistente con la pregunta de que pide la formade argumento, la cual maneja variables, no proposiciones):

m → ¬v premisav ∨ c premisa

∴ m → c conclusion

Y la prueba de la validez del argumento:

1. m → ¬v premisa2. v ∨ c premisa3. m premisa prueba condicional4. ¬v modus ponens 1,35. c silogismo disyuntivo 2,46. m → c prueba condicional 3,5

8