Posterior: Cálculo proposicional formal en Arriba: Sintaxis Anterior: Sintaxis

Cálculo proposicional formal

Sea $X=\{x_1,\ldots,x_n\}$ un conjunto (finito) de variables proposicionales y sea $E=\{\rightarrow,\neg\}$ el conjunto que consta de dos símbolos conectivos, llamados implicación y negación respectivamente. $X\cup E$ es el alfabeto del CÁLCULO PROPOSICIONAL definido sobre $X$.

Definición 2.1 (Proposiciones bien formadas)   El conjunto de PROPOSICIONES BIEN FORMADAS sobre $X$ es $\mbox{\rm Pbf}_H(X)\subset (X\cup E)^*$ y está definido recursivamente como sigue:

1. Si $x$ es una variable proposicional entonces $x$ es una proposición bien formada:
   
   $$x\in X \;\Rightarrow\; x\in \mbox{\rm Pbf}_H(X)$$
   
   

2. Si $p$ es una proposición, su negación $\neg p$ también lo es:
   
   $$p\in \mbox{\rm Pbf}_H(X) \;\Rightarrow\; \neg p\in \mbox{\rm Pbf}_H(X)$$
   
   

3. Si $p$ y $q$ son dos proposiciones, la implicación $\rightarrow p q$ también lo es:
   
   $$p,q\in \mbox{\rm Pbf}_H(X) \;\Rightarrow\; \rightarrow p q\in \mbox{\rm Pbf}_H(X).$$
   
   

Es evidente de esta definición que $\mbox{\rm Pbf}_H(X)$ es un lenguaje libre de contexto, generado por la gramática siguiente:

$$\begin{array}{rcl} P &::=& x_1 \vert \cdots \vert x_n \\ P &::=& \neg P\; \vert\; \rightarrow P P \end{array}$$ (1)

y consecuentemente la revisión sintáctica de ``buena formación'' puede realizarse mediante un procedimiento basado en un dispositivo de almacenamiento del tipo ``de pila''. Si $p\in \mbox{\rm Pbf}_H(X)$ es una proposición y su primer símbolo, o sea el más a la izquierda, $s_0(p)$ no es una variable, entonces se dice que $s_0(p)$ es el CONECTIVO PRINCIPAL de $p$. Una proposición sin conectivo principal es una variable proposicional llamada también ´ATOMO.

Ejemplo 2.1   Sea $X=\{x_1,x_2,x_3\}$. Los siguientes son ejemplos de proposiciones bien formadas:

1. $\rightarrow x_1 x_1$
2. $\rightarrow \rightarrow \neg x_1 x_2 \rightarrow \rightarrow \neg x_1 \neg x_2 x_1$ En la figura 2.2 se puede ver un árbol de derivación que realiza a esta palabra como una proposición bien formada.
3. $\rightarrow x_1\rightarrow \neg x_1 x_3$

Figure 2.2: Árbol de derivación, siguiendo las reglas de ``buena formación'', para la proposición $\rightarrow \rightarrow \neg x_1 x_2 \rightarrow \rightarrow \neg x_1 \neg x_2 x_1$. Los nodos en la primera columna corresponden a los símbolos en la proposición y los restantes están etiquetados por la regla aplicada.

Las proposiciones bien formadas tienen pues la FORMA DE PREFIJO, llamada NOTACIÓN POLACA INVERSA: se dice ``polaca'' por haber sido introducida por primera vez por el lógico polaco Jan ukasiewicz (1878-1956) e ``inversa'' ya que ukasiewicz la introdujo utilizando una notación de sufijo para los conectivos, en tanto que aquí aparece como de prefijo. Aunque esta notación es suficiente con fines de presentar al cáculo proposicional, es, efectivamente, poco intuitiva. La notación polaca inversa tiene dos grandes ventajas: Se presenta de manera muy sencilla y hay univocidad en su lectura, es decir, toda proposición tiene determinada de manera única a cada una de sus componentes. Para introducir una notación más convencional, basada en una notación de enfijo, extenderemos el alfabeto actual con dos símbolos nuevos: los paréntesis izquierdo y derecho para garantizar univocidad en la representación de enfijo.
Posterior: Cálculo proposicional formal en Arriba: Sintaxis Anterior: Sintaxis