Fórmulas bien formadas

FBF

Los lenguajes de programación son muy estrictos en la forma en que deben escribir sus instrucciones, de lo contrario tenemos errores de sintaxis y en otras errores de semántica.

FÓRMULAS BIEN FORMADAS   (WFF, WELL FORMED FORMULES)

Una fórmula bien formada del cálculo proposicional se define mediante reglas.

        Las cadenas de símbolos que resultan por la sintaxis impuesta por estas reglas, constituyen el subconjunto de fórmulas sintácticas y semánticamente correctas, y reciben el nombre de Fórmulas Bien Formadas.

Def: Una Fórmula Bien Formada (FBF) del cálculo proposicional se define mediante reglas:

regla 1) Una variable proposicional aislada es una FBF.

regla 2) Si A es una FBF, entonces ¬A es una FBF

regla 3) Si A y B son FBF, entonces las siguientes son FBF

                        (A  ∧  B)

                        (A  ∨  B)

                        (A  →  B)

                        (A  ↔  B)

regla 4) Una cadena de símbolos es una FBF si y solo si es generada por un número finito de aplicaciones 1), 2) y 3)

OBSERVACIÓN:

Otra forma de definir el conjunto de FBF es a través de una gramática B.N.F. Backus Normal Form:

<Símbolos básicos> ::=  < | >  |  ¬  |   →   |   ↔   |  ∨   |  ∧

<Variable> ::= |  p |  q |  r |  s |  t |  u |  v |  w |  p1 | p2  | ....  |  q1 | ....

<FBF> ::= <Variable>  |  (¬<FBF>)   |  ( <FBF> ∧ <FBF> )  |  ( <FBF> ∨ <FBF> )  |  

( <FBF> → <FBF> )  | ( <FBF> ↔ <FBF> )

Una gramática está formada por:

• Alfabeto
• Conjunto de producciones que parten de un símbolo inicial y mediante reglas se van generando cadenas de símbolos hasta que termine en los símbolos terminales.
• Símbolo inicial de las producciones
• Símbolos no terminales.

Producciones: elementos que nos dan la formación de las cadenas de símbolos en el lenguaje, estas secuencias se llaman categorías sintácticas.

Categorías Sintácticas: Una gramática usa símbolos terminales y símbolos no terminales.  Se comienza una gramática con un símbolo no terminal hasta llegar a un símbolo no terminal.

Ejemplo: <dígito sin signo> ::= <dígito> |  <dígito sin signo> <dígito>

            <dígito>::=  0 |  1 |   2 |   3 |   4 |   5 |  6  |  7  | 8  |  9

Para escribir    243                                           <dígito sin signo>         raíz, nodo, símbolo inicial

[pic 1][pic 2]

                               <dígito sin signo>                            <dígito> [pic 3][pic 4][pic 5]

         [pic 6]

                <dígito sin signo>                        <dígito>                hoja, nodo, símbolo

ramas o                                                                                 terminal[pic 7][pic 8]

categorías                        <dígito>                             [pic 9][pic 10]

sintácticas                                                [pic 11]

                        árbol de derivación sintáctica

1. (p   ∧ (q ∧ p))  si es FBF.

// Cómo verificarlo?

(p   ∧ (q ∧ p))                                      // B= q ∧ p   /   A=p

( A   ∧  B )                  es una FBF por regla 3

A =  p                        es una FBF por regla 1

B =  B1  ∧  B2         es una FBF por regla 3

B1 = q                 es una FBF por regla 1

B2 = p                 es una FBF por regla 1

Por lo tanto,                es FBF por regla 4

Árbol de derivación sintáctica

// Cómo construirlo?

    <FBF>[pic 12][pic 13][pic 14][pic 15][pic 16]

(     <FBF> ∧  <FBF>   )  [pic 17][pic 18][pic 19]

<Variable>                  ( <FBF> ∧  <FBF> )  

...