Propiedades de 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
  
  

Absorción:

• not (p and q) = (not p) or (not q)
  
  
• not (p or q) = (not p) and (not 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.