Programación Estructurada

Lógica


“Si buscas resultados distintos, no hagas siempre lo mismo”
“Quien nunca ha cometido un error nunca ha probado algo nuevo”

Albert Einstein

La lógica proposicional y la teoría de conjuntos…
“lenguaje de la matemática”

Lógica

La lógica estudia la forma del razonamiento, es una disciplina que por medio de reglas y técnicas determina si un teorema es falso o verdadero, además de que es ampliamente aplicada en filosofía, matemáticas, computación y física.

En filosofía la lógica se utiliza para establecer si un razonamiento es valido o no, en matemáticas la lógica es una herramienta útil para demostrar teoremas e inferir resultados, así como para resolver problemas, en la computación la lógica se aplica en la elaboración y revisión de programas, en el estudio de lenguajes formales y la relación existente entre ellos, así como en la obtención de resultados en forma recursiva, con el apoyo de la lógica, en el área de la inteligencia artificial se logra que una maquina tome decisiones precisas, y en la física, la lógica se necesita tanto para establecer el procedimiento para llevar a cabo un experimento como para interpretar los resultados obtenidos.

Proposiciones

Una proposición o enunciado es una oración, frase o expresión matemática que puede ser falsa o verdadera, pero no ambas a la vez. La proposición es un elemento fundamental de la lógica matemática.  También se les llama proposiciones válidas.

Ejemplos:

  • "Pamplona es una ciudad mitrada"
  • “2 + 3 = 4”
  • “Si x = 2 entonces x2 = 4”

Los predicados son las freses a las que no es posible determinar un valor de verdad, también conocidas como proposiciones no válidas, en el lenguaje natural se incluye las frases interrogativas o imperativas, por ejemplo:

  • “x > 0 y x < 1”
  • "Esta información es falsa"
  • "¿qué hora es?
  • "¡Silencio!"

Conectivos Lógicos

Los conectivos lógicos son operadores entre proposiciones para la construcción de nuevas proposiciones que se denominan proposiciones compuestas o expresiones lógicas compuestas y su valor de verdad será el resultado de la aplicación de los conectivos lógicos a los valores de verdad de las proposiciones simples que la conforman.

Sean las proposiciones p1, p2, p3, … pn se combinan para formar una nueva proposición p = p(p1, p2, p3, … pn), serán relacionadas con los conectivos:

  • Conjunción   p ∧ q    (p & q,  p · q   ó   pq) 
  • Disyunción   p ∨ q    (p + q)
  • Disyunción excluyente  p v q   (p ∆ q)
  • Negación    ￢p    (p’, pˉ  ó  ∼ p)
  • Condicional  p → q
  • Bicondicional  p ↔ q

En la construcción de tablas de verdada se requiere para n variables 2n filas, ejemlpo, para 2 variables se requieren 4 filas; para 3 variables se necesitan 8 filas.

Operaciones Lógicas

Conjunción Y

La conjunción de dos preposiciones p y q es verdadera cuando el valor de verdad de las dos proposiciones son verdaderas, en caso contrario es falso. Se lee p y q.

Si p y q son verdaderas, entonces p ∧ q es verdadera; en otro caso, p ∧ q es falsa

p q p ∧ q
V V V
V F F
F V F
F F F

Disyunción O

La disyunción de dos preposiciones p y q es falsa cuando el valor de verdad de las dos proposiciones son falsas, en caso contrario es verdadera.  Se lee p ó q.

Si p y q son falsas, entonces p ∨ q es falsa; en otro caso , p ∨ q es verdadera

p q p ∨ q
V V V
V F V
F V V
F F F

Disyunción Exclusiva

La disyunción excluyente (o disyunción fuerte) es un caso especial de la disyunción en la que se establece que si uno de los dos sucesos se realiza, el otro queda excluido.

Si p y q son falsas o verdaderas, entonces p v q es falsa; en otro caso , p v q es verdadera

p q p v q
V V F
V F V
F V V
F F F

Negación NO

La negación de una preposición p es falsa cuando el valor de verdad de p es verdadero y es verdadero si el valor de verdad de p es falso.  “No es verdad que…”, “No es cierto que…”.  Se lee NO p.

Si p es verdadera, entonces ￢p es falsa; y si p es falsa, entonces ￢p es verdadera

p ￢p
V F
F V

Condicional →

La disyunción de dos preposiciones p y q, en las que p es la hipótesis o antecedente y q es la conclusión o consecuente, p → q es falsa cuando la conclusión es falsa, para los demás casos es verdadera.  Se lee p entonces q, p sólo si q, p implica q, p es una condición suficiente para q, q es una condición necesaria para p.

p q p → q
V V V
V F F
F V V
F F V

Bicondicional ↔

La bicondicional de dos preposiciones p y q, p ↔ q es verdadera cuando p y q coinciden y cumple (p → q) ∧ (p → q).  Se lee “p si y sólo si q”   ó  “p es una condición necesaria y suficiente para q”

p q p ↔ q
V V V
V F F
F V F
F F V

Construcción de Tablas de Verdad

Se construye la tabla en número de filas de acuerdo al número de variables lógicas, es decir 2n filas, en este caso 4 columnas, y se crea tantas columnas como operaciones se tenga

Ejemplos:

1. Construya la tabla de verdad para la proposición ￢(p ∧ ￢ q).

Por descomposición

p q ￢ q p ∧ ￢ q ￢(p ∧ ￢ q)
V V F F V
V F V V F
F V F F V
F F V F V

Por asignación directa (enumeración)

p q ￢ (p ∧ ￢ q)
V V V V F F V
V F F V V V F
F V V F F F V
F F V F F V F


4 1 3 2 1

Tautologías, Contradicciones y Contingencias

Tautologías

Una proposición compuesta p = p(p1, p2, p3, … pn) es una tautología si p es verdadera para todos los valores de verdad que se asignen a p1, p2, p3, … pn

Contradicciónes

Una proposición compuesta p = p(p1, p2, p3, … pn) es una contradicción si p es  falsa para todos los valores de verdad que se asignen a p1, p2, p3, … pn

Contingencias

Si la proposición compuesta no es Tautología ni Contradicción se dice que es una contingencia, por ejemplo:   p  ʌ  (q  v  r)

Álgebra Proposicional

Las proposiciones cumplen las siguientes leyes:

  • Leyes idempotentes:   a) (p ∨ p) ≡ p   b) (p ʌ p) ≡ p
  • Leyes Asociativas:   a) [(p ∨ q) V r] ≡ [p ∨  (q ∨ r)]   b) [(p ʌ q) ʌ r] ≡ [p ʌ  (q ʌ r)]
  • Leyes conmutativas:  a) (p ∨ q) ≡ (q ∨ p)   b) (p ʌ q) ≡ (q ʌ p)   c) (p ↔ q) ≡ (q ↔ p)
  • Leyes distributivas:   a) [p ∨ (q ʌ r)] ≡ [(p ∨ q) ʌ (p ∨ r)]   b) [p ʌ (q ∨ r)] ≡ [(p ʌ q) ∨ (p ʌ r)]
  • Leyes de identidad (neutro):   a) (p ∨  F) ≡ p   b) (p ʌ V) ≡ p
  • Leyes de dominación:   a) (p ∨ V) ≡ V   b) (p ʌ  F) ≡ F
  • Leyes de la contradicción:  a) (p ∨ ￢ p) ≡ V   b) (p ʌ ￢ p) ≡ F
  • Leyes de absorción total:   a) p ∨ (p ʌ q) ≡ p   b) p ʌ (p ∨ q) ≡ p
  • Leyes de absorción parcial:   a) p ∨ ( ￢ p ʌ q) ≡ (p ∨ q)   b) p ʌ (￢ p ∨ q) ≡ (p ʌ q)
  • Ley de doble negación:   ￢ (￢ p) ≡ p
  • Leyes de Morgan:   a) ￢ (p v q) ≡  (￢ p ʌ ￢ q)   b) ￢ (p ʌ q) ≡  (￢ p v ￢ q)
  • Ley del condicional: (p → q) ≡ (￢ p ∨ q)

Implicación Lógica

Se dice que “p Implica Lógicamente a q” si p → q es una tautología.  Se escribe p => q

Ejemplo:

  • Compruebe que la simplificación (p ʌ q) => p es una implicación lógica.  Como ejercicio haga la comprobación utilizando el método de descomposición.
p q (p ʌ q) => p
V V V V V V V
V F V F F V V
F V F F V V F
F F F F F V F
    1 2 1 3 1

Equivalencia Lógica

Se dice que dos proposiciones p y q son Lógicamente Equivalentes si p ↔ q es una tautología.  Se escribe p ≡ q

Ejemplo:

  • Compruebe la ley de Morgan  ￢(p v q) ≡  ￢p ʌ ￢ q es lógicamente equivalente. Como ejercicio haga la comprobación utilizando el método de descomposición.
p q ￢ (p v q) ≡ ￢ p ʌ
￢ q
V V F V V V V F V F F V
V F F V V F V F V F V F
F V F F V V V V F F F V
F F V F F F V V F V V F
    3 1 2 1 4 2 1 3 2 1

Actividades Complementarias

  1. Seymour Lipschutz y Marc Lars Lipson. Matemáticas Discretas, tercera edición. Mc Graw Hill, México 2009.  Estudio secciones 4.1 a 4.8 páginas 70-76.  Problemas resueltos páginas 82-84, suplementarios página 86
  2. Richard Johnsonbaugh.  Matemáticas Discretas, sexta edición. Pearson Educación.  México 2005.  Estudio secciones 1.1. Proposiciones y 1.2. Proposiciones condicionales y equivalencia lógica.   Contenido y ejercicios páginas 1-17.  Autoevaluación secciones 1.1 y 1.2 páginas 73 y 74.
  3. Utilice el siguiente material para ampliar información [Ir al sitio]
  4. Consulte sobre las siguientes operaciones: Pierce (↓) y Sheffer (↑)

 

Regresar