Articulos de interes



Curso online gratuito - POO y Java - Click Aquí

Propiedades en Programación

En lógica proposicional, a veces es necesario transformar una fórmula en otra equivalente. Las transformaciones se hacen de acuerdo a una serie de leyes o reglas:

Complemento

  • not 0 = 1
  • not 1 = 0
  • p and (not p) = 0
  • p or (not p) = 1

Idempotencia

  • p and p = p
  • p or p = p

Identidad

  • p and 1 = p
  • p and 0 = 0
  • p or 1 = 1
  • p or 0 = p

Doble negación

  • not (not p) = p

Asociación

  • (p and q) and r = p and (q and r)
  • (p or q) or r = p or (q or r)

Distribución

  • p and (q or r) = (p and q) or (p and r)
  • (q or r) and p = (q and p) or (r and p)
  • p or (q and r) = (p or q) and (p or r)
  • (q and r) or p = (q or p) and (r or p)

Absorción

  • p and (p or q) = p
  • p or (p and q) = p

Leyes de Morgan

  • not (p and q) = (not p) or (not q)
  • not (p or q) = (not p) and (not q)

Conmutación

  • p and q = q and p
  • p or q = q or p

Por definición

  • p and q = not ((not p) or (not q))
  • p -> q = (not p) or q


Utilizando estas leyes podemos demostrar que 2 fórmulas son equivalentes. Por ejemplo, not (p -> q) y p and (not q) son fórmulas equivalentes. Es decir, partiendo de una fórmula y aplicándole las reglas de transformación, llegamos a la otra fómula. La demostración, utilizando las reglas anteriores, sería:

Definición: not (p -> q) = not ((not p) or q) =
Morgan: = (not (not p)) and (not q) =
Doble Negación: = p and (not q)
        

Vemos que a partir de una fórmula hemos llegado a la otra aplicándole las reglas de transformación. Queda como ejercicio para el alumno desarrollar las tablas de verdad de ambas fórmulas y comprobar que son equivalentes.

Tautología: Fórmula o proposición siempre cierta (su tabla de verdad es siempre 1). Por ejemplo: p or (not p) = 1

p not p p or (not p)
0 1 1
1 0 1

Contradicción: Fórmula o proposición siempre falsa (su tabla de verdad es siempre 0). Por ejemplo: p and (not p) = 0

p not p p and (not p)
0 1 0
1 0 0

 



Nombre:

Email:

Comentario: