Siguiente: Tercetas de igual longitud Un nivel arriba: Ejemplos de gramáticas Anterior: Ejemplos de gramáticas

Proposiciones bien formadas

En el Cálculo Proposicional, las proposiciones se construyen a partir de un conjunto de variables proposicionales siguiendo un conjunto de reglas gramaticales:

i)

Una variable proposicional es una proposición.

ii)

La negación de una proposición es una proposición también.

iii)

La conjunción, la disyunción, la implicación y la equivalencia de dos proposiciones es también una proposición.

iv)

Las proposiciones se obtienen sólo mediante la aplicación sucesiva de las reglas anteriores.

Para describir esta construcción mediante una gramática formal, podemos considerar como conjunto de símbolos terminales al conjunto unión de los siguientes:

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

Como es convencional, los conectivos tienen asociada una prioridad:

$$\begin{array}{\vert\vert c\vert l\vert\vert}\hline \hline \m... ...3 & \rightarrow,\leftrightarrow \\ \hline \hline \end{array}$$

donde un valor menor de Prior significa que el correspondiente conectivo se aplica más rápido, y, en igualdad de prioridades, el orden de izquierda a derecha determina el de aplicación de los conectivos. Así,

$$\neg x_0\lor x_2\land x_3\lor x_5\rightarrow x_6\leftrightarrow x_7$$

se ha de interpretar como

$$\left[\left(\left(\neg x_0\lor x_2\right)\land x_3\right)\lor x_5\rightarrow x_6\right]\leftrightarrow x_7.$$

Introduzcamos entonces los siguientes símbolos variables para la gramática formal:

$\langle\mbox{\it VarsProp\/}\rangle$	: variables proposicionales,
$\langle\mbox{\it Prop\/}\rangle$	: proposiciones bien formadas,
$\langle\mbox{\it PropNeg\/}\rangle$	: proposiciones cuyo conectivo principal es la negación,
$\langle\mbox{\it PropCon\/}\rangle$	: proposiciones cuyo conectivo principal es la conjunción,
$\langle\mbox{\it PropDis\/}\rangle$	: proposiciones cuyo conectivo principal es la disyunción,
$\langle\mbox{\it PropImp\/}\rangle$	: proposiciones cuyo conectivo principal es la implicación,
$\langle\mbox{\it PropEqu\/}\rangle$	: proposiciones cuyo conectivo principal es la equivalencia.
$\langle\mbox{\it Prop1\/}\rangle$	: proposiciones cuyo conectivo principal tiene prioridad 1,
$\langle\mbox{\it Prop2\/}\rangle$	: proposiciones cuyo conectivo principal tiene prioridad 2,
$\langle\mbox{\it Prop3\/}\rangle$	: proposiciones cuyo conectivo principal tiene prioridad 3,

En la tabla (2.1) presentamos las producciones de la gramática PBF (de Proposiciones Bien Formadas).

  

Table 2.1: Gramática de proposiciones bien formadas.

El lenguaje generado pr PBF consta de todas las proposiciones bien formadas a partir de las variables proposicionales $x_1,\ldots, x_n$.


En la presentación de las siguientes gramáticas, utilizaremos símbolos mayúsculos para denotar a los símbolos variables y minúsculos para los terminales.
Siguiente: Tercetas de igual longitud Un nivel arriba: Ejemplos de gramáticas Anterior: Ejemplos de gramáticas