Universidad de Pamplona
Ingeniería de Sistemas
Estructuras computacionales discretas
Facilitador: MSc. Luis Armando Portilla Granados
Lógica
Material de Estudio
1. Seymour Lipschutz y Marc Lars Lipson. Matemáticas Discretas, tercera edición. Mc
Graw Hill, México 2009.
• Estudio de las secciones 4.1 a 4.8 (páginas 70-76).
• Problemas resueltos 4.1 al 4.9 (páginas 82-84)
• Ejercicios suplementarios 4.20 al 4.22 (página 86)
• Respuestas a ejercicios suplementarios 4.20 al 4.22 (página 87)
2. Richard Johnsonbaugh. Matemáticas Discretas, sexta edición. Pearson
Educación. México 2005.
• Sección 1.1. (páginas 1-7) y Ejercicios (páginas 7 y 8) – Sección 1.2. (páginas 7-
16), Ejercicios (páginas 16 y 17)
• Autoevaluación del capítulo, sección 1.1 y 1.2 (páginas 73 y 74)
• Sugerencias y soluciones a ejercicios seleccionados: Ejercicios de las secciones
1.1 y 1.2 (Página 582 y 583)
Ejercicios Propuestos
1. Identifique las proposiciones válidas y determine su valor de verdad:
1.1) New York es la capital de Estados Unidos
1.2) 2 + 2 = 5
1.3) ¿Los datos son suficientes para solucionar el problema?
1.4) Cierra la puerta
1.5) x >= 2
1.6) Formatea el disco antes de usarlo
1.7) Si x es un número impar entonces x por un número par es par
1.8) 123 es un número primo
1.9) Resuelva el problema enunciado
1.10) x>=0 y x<=5, si x = 12
2. Construya la tabla de verdad para las siguientes proposiciones compuestas:
2.1) ￢(￢ p)
2.2) ￢(￢ p v ￢ q)
2.3) p ʌ (p v q)
2.4) pv￢q
2.5) (p v q) ʌ ￢ q
2.6) (pʌq)vr
2.7) (p v q) ʌ (￢ q ʌ r)
3. Formule expresiones lógicas equivalentes para el siguiente enunciado:
Algoritmo que reciba una colección de datos y los guarde en una matriz cuadrada de tamaño
definido por el usuario, sobre los datos se debe validar que no admita datos repetidos ni entre
el rango de 10 a 20, además controlar que en la parte superior de la matriz sólo admita números
pares y en la parte inferior impares, en la diagonal no se puede ubicar ningún dato. Hay dos
opciones, una, que los datos que no cumplan lo requerido se omitan y se siga el proceso, y la otra,
que restringa la entrada de cada posición de la matriz hasta que no se cumpla las condiciones
dadas. La matriz se imprime al finalizar el proceso. Una variante del ejercicio podría ser que el
usuario defina si el orden de ingreso de datos es por filas o por columnas.
4. Escriba el algoritmo para NetBeans del problema anterior aplicando las expresiones lógicas
definidas.
5. Determinar, utilizando tablas de verdad, si las siguientes fórmulas son tautologías,
contradicciones o contingencias:
5.1) (p v¬ p)
5.2) (p ʌ¬ p)
5.3) ((¬ p v q) ↔ (p → q))
5.4) ((p v q) → p)
5.5) (¬ (p ʌ q) ↔ ( ¬ p v ¬ q))
5.6) (p → p)
5.7) ((p ʌ q) →p)
5.8) ((p → (q → r)) → ((p → q) →(p → r)))
5.9) ((p ʌ (q v r)) ↔ ((p ʌ q) v (p ʌ r)))
6. Compruebe las equivalencias lógicas de las leyes del álgebra proposicional utilizando tablas
de verdad.
6.1) Leyes idempotentes: a) (p v p) ≡ p b) (p ʌ p) ≡ p
6.2) Leyes Asociativas: a) [(p v q) V r] ≡ [p v (q v r)] b) [(p ʌ q) ʌ r] ≡ [p ʌ (q ʌ r)]
6.3) Leyes conmutativas: a) (p v q) ≡ (q v p) b) (p ʌ q) ≡ (q ʌ p) c) (p ↔ q) ≡ (q ↔ p)
6.4) Leyes distributivas: a) [p v (q ʌ r)] ≡ [(p v q) ʌ (p v r)] b) [p ʌ (q v r)] ≡ [(p ʌ q) v (p ʌ r)]
6.5) Leyes de identidad (neutro): a) (p v F) ≡ p b) (p ʌ V) ≡ p
6.6) Leyes de dominación: a) (p v V) ≡ V b) (p ʌ F) ≡ F
6.7) Leyes de la contradicción: a) (p v ￢ p) ≡ V b) (p ʌ ￢ p) ≡ F
6.8) Leyes de absorción total: a) p v (p ʌ q) ≡ p b) p ʌ (p v q) ≡ p
6.9) Leyes de absorción parcial: a) p v ( ￢ p ʌ q) ≡ (p v q) b) p ʌ (￢ p v q) ≡ (p ʌ q)
6.10) Ley de doble negación: ￢ (￢ p) ≡ p
6.11) Leyes de Morgan: a) ￢ (p v q) ≡ (￢ p ʌ ￢ q) b) ￢ (p ʌ q) ≡ (￢ p v ￢ q)
6.12) Ley del condicional: (p → q) ≡ (￢ p v q)
7. Verifique las siguientes implicaciones lógicas. a) Utilice tablas de verdad, b) y las leyes del
álgebra proposicional
7.1) p ⇒ (p v q) Adición
7.2) (p ʌ q) ⇒ p Simplificación
7.3) (p → F) ⇒ ￢ p Absurdo
7.4) [(p → q) ʌ p] ⇒ q Modus Ponens
7.5) [(p → q) ʌ ￢ q] ⇒ ￢ p Modus Tollens
7.6) [(p v q) ʌ ￢ p] ⇒ q Silogismo disyuntivo
8. Verifique las siguientes equivalencias lógicas. a) Utilice tablas de verdad, b) y las leyes del
álgebra proposicional
Variantes de la condicional
8.1) (p → q) ≡ ￢ (p ʌ ￢ q)
8.2) ￢ (p → q) ≡ (p ʌ ￢ q)
8.3) (p v q) ≡ (￢ p → q)
8.4) (p ʌ q) ≡ ￢ (p → ￢ q)
8.5) [(p → r) ʌ (q → r)] ≡ [(p v q) → r] (Demostración por casos)
8.6) [(p → q) ʌ (p → r)] ≡ [p → (q ʌ r)]
8.7) (p → q) ≡ (￢ q → ￢ p) (Contrapositiva o contrarecíproca)
8.8) (p → q) ≡ (p ʌ ￢ q) → F (Reducción al absurdo)
Variantes de la bicondicional
8.9) (p ↔ q) ≡ [(p → q) ʌ (q → p)]
8.10) (p ↔ q) ≡ [(￢ p v q) ʌ (￢ q v p)]
8.11) (p ↔ q) ≡ [(p ʌ q) v (￢ p ʌ ￢ q)]
8.12) ￢ (p ↔ q) ≡ (p ʌ ￢ q) v (q ʌ ￢ p)
8.13) (p → q) v ￢ (p → q) ≡ (p → q)
8.14) (p ≡ q) ≡ [(p → q) ʌ (q → p)
9. Usando las leyes del álgebra proposicional simplifique las siguientes formas proposicionales:
9.1) ￢ (p → q) ↔ ￢ (q → p)
9.2) {[￢ p → ￢ (p → q)] v [(p ʌ (q → p)) → p]}
9.3) [(￢ q → ￢p) ʌ ￢ (￢ p → ￢ q)] v (p → ￢ q)
9.4) (p → ￢q) ʌ [(q → ￢ p) v (q → ￢ r)
9.5) ￢ {[￢ p ʌ (q v ￢ r ) ∆ [(q ʌ ￢ p) v ￢ (p v r)]]} (∆ es la disyunción excluyente v)
Expresar la siguiente proposición en otra equivalente donde se usen los operadores negación e
implicación:
9.6) (p ʌ q) v (r v s)
Usando las leyes del álgebra proposicional demuestre:
9.7) [(p → q) ʌ (￢ p → q) ʌ (q → q)] ≡ p
9.8) ￢ [￢ (p v q) v r] v ￢ (q → r) ≡ (p v q) ʌ ￢ r
