Formulas Proposicionales

2.1.2 Fórmulas Proposicionales

En las ciencias de la Computación, el término expresión es usado para denotar la construcción de un valor complejo de valores elementarios. En el cálculo proposicional, el término formula proposicional (llamada Formula bien formada FBF en un contexto más corto y claro)es utilizado en lugar del otro. las formulas sintácticamente correctas son descritas dando una gramática libre de contexto similar a la gramática BNF usada para describir lenguajes de programación.

El cálculo proposicional estudia fórmulas proposicionales simples o compuestas.

Una fórmula bien formada (fbf) es una expresión que representa una proposición simple o compuesta, la cual esta bien escrita de acuerdo con determinada sintaxis.

En el cálculo proposicional las terminales son los operadores booleanos y un ilimitado conjunto de símbolos arbitrarios P llamados letras proposicionales o proposiciones atómicas (las llamaremos átomos). Los átomos serán denotados por las letras minúsculas en el conjunto (p, q, r,…),posiblemente con subíndices.

Definición:Una FBF en cálculo proposicional es una palabra que puede ser derivada de la siguiente gramática, comenzando del nodo terminal formula:

1. <formula> ::= p

para cualquier p ∈ P

2. <formula> ::= ¬(<formula>)

3. <formula> ::= ((<formula>) ∨ (<formula>))

4. <formula> ::= ((<formula>) ∧ (<formula>))

5. <formula> ::= ((<formula>) → (<formula>))

6. <formula> ::= ((<formula>) ↔ (<formula>))

Podemos utilizar una definición más corta:

1. <formula> ::= p

para cualquier p ∈ P

2. <formula> ::= ¬(<formula>)

3. <formula> ::= ((<formula>) <OP> (<formula>))

4. ‹OP> ::= ∨ | ∧ | → | ↔

El conjunto de fórmulas que pueden ser derivadas de estas reglas de gramática es denotado por F cada derivación de una fórmula puede ser representada por una derivación de árbol que muestra la aplicación de la gramática a los nodos terminales.

Ejemplo: derivación de ((p → q) ↔ ((¬ (p)) → (¬(q))))

     1.  <formula>                                     nodo terminal inicial
     2. ((<formula>) ↔ (<formula>))                            Regla 6 
     3. (((<formula>) → (<formula>)) ↔ (<formula>))            Regla 5 
     4. ((p → (<formula>)) ↔ (<formula>))                      Regla 1 
     5. ((p → q) ↔ (<formula>))                                Regla 1 
     6. ((p → q) ↔ ((<formula>) → (<formula>)))                Regla 5 
     7. ((p → q) ↔ ((¬(<formula>)) → (<formula>)))             Regla 2 
     8. ((p → q) ↔ ((¬(p)) → (<formula>)))                     Regla 1 
     9. ((p → q) ↔ ((¬(p)) → (¬(<formula>))))                  Regla 2 
    10. ((p → q) ↔ ((¬(p)) → (¬(q))))                          Regla 1 

Derivación de Árbol:

Attach:proposiciones_fig1.jpg Δ

Formación de Árbol:

Attach:Proposicionesfigura2.jpg Δ

En ocaciones es tedioso escribir tantos paréntesis para una fórmula proposicional, esto es con el fin de evitarnos ambigüedades, la fórmula anterior puede escribirse también de la siguiente manera:

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