Posterior: Reglas convencionales de buena Arriba: Sintaxis Anterior: Cálculo proposicional formal en

Cálculo proposicional booleano

Extendamos el alfabeto de $\mbox{\rm Pbf}(X)$ para incluir los conectivos booleanos de disyunción, de conjunción y de equivalencia. Consideremos pues el alfabeto $X_B=X\cup E\cup \{(,)\}\cup \{\lor,\land,\leftrightarrow\}$.

Definición 2.3 (Proposiciones booleanas bien formadas)   El conjunto de PROPOSICIONES BOOLEANAS bien formadas, $\mbox{\rm Pbf}_B(X)$ consta de $\mbox{\rm Pbf}(X)$ más las proposiciones resultantes de los siguientes esquemas de abreviación:

$$\begin{eqnarray*} \mbox{\rm disyunci\'on} &:& p \lor q := \neg p \rightarrow q ... ...:= \neg (p \rightarrow q) \rightarrow \neg (q \rightarrow p). \end{eqnarray*}$$

Evidentemente, es necesario introducir paréntesis de manera convencional para la interpretación única de proposiciones en $\mbox{\rm Pbf}_B(X)$. Dejamos pues al lector la tarea de formalizar en una gramática libre de contexto sobre el alfabeto terminal $X_B$ al lenguaje $\mbox{\rm Pbf}_B(X)$. Veamos una construcción alternativa de $\mbox{\rm Pbf}_B(X)$. En el cálculo proposicional booleano, las proposiciones se construyen a partir de un conjunto de variables proposicionales siguiendo un conjunto de reglas de buena formación de proposiciones:

1. Una variable proposicional es una proposición.
2. La negación de una proposición es una proposición también.
3. La conjunción, la disyunción, la implicación y la equivalencia de dos proposiciones es también una proposición.
4. Las proposiciones se obtienen sólo mediante la aplicación sucesiva de las reglas anteriores.

Es posible describir esta construcción mediante una gramática formal. El alfabeto (de símbolos terminales) de la gramática es la unión de los siguientes dos conjuntos:

$$\begin{array}{lclcl} \mbox{\it VarsProp} &=&\{x_a,x_1,x_2,\l... ...arrow,\leftrightarrow\} &:& \mbox{\rm especiales}. \end{array}$$

Posterior: Reglas convencionales de buena Arriba: Sintaxis Anterior: Cálculo proposicional formal en