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

Cálculo proposicional formal en enfijo

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

1. Si $x$ es una variable proposicional entonces $x$ es una proposición bien formada y su conectivo principal es vacío:
   
   $$x\in X \;\Rightarrow\; x\in \mbox{\rm Pbf}(X) \;\&\; \mbox{\it ConPrinc}(x)=\mbox{\it nil}.$$
   
   

2. Si $p$ es una proposición, sea $q=\neg (p)$ si el conectivo principal de $p$ es $\rightarrow$ y sea $q=\neg p$ en otro caso. $q$ es la negación de $p$ y es también una proposición:
   
   $$\begin{array}{ll} p\in \mbox{\rm Pbf}(X) \;\&\; q=\left\{\be... ...box{\rm Pbf}(X) \;\&\; \mbox{\it ConPrinc}(q)=\neg \end{array}$$
   
   

3. Si $p$ y $q$ son dos proposiciones, definamos
   
   $$r=\left\{\begin{array}{ll} (p) \rightarrow (q) & \mbox{\rm s... ...mbox{\it ConPrinc}(q)\not=\rightarrow %%\\ \end{array}\right.$$
   
   
   $r$ es la implicación de $p$ a $q$ y es también una proposición:
   
   $$p,q\in \mbox{\rm Pbf}(X) \;\Rightarrow\; r\in \mbox{\rm Pbf}(X) \;\&\; \mbox{\it ConPrinc}(r)=\rightarrow.$$
   
   

El lenguaje de proposiciones $\mbox{\rm Pbf}(X)$ también es libre de contexto y está generado, por ejemplo, por la gramática, con símbolo inicial $P$, siguiente:

$$\begin{array}{rcl} P &::=& Q\; \vert\; I \\ Q &::=& A\; ... ...\; (I)\rightarrow Q \; \vert\; Q\rightarrow Q % \end{array}$$ (2)

Ejemplo 2.2   En notación de enfijo, las proposiciones del ejemplo 2.2.1 quedan escritas equivalentemente como sigue:

1. $x_1 \rightarrow x_1$
2. $\left(\neg x_1 \rightarrow x_2\right) \rightarrow \left(\left(\neg x_1 \rightarrow \neg x_2\right) \rightarrow x_1\right)$
3. $x_1\rightarrow \left(\neg x_1 \rightarrow x_3\right)$

Intuitivamente resulta claro que ambas definiciones 2.2.1 y 2.2.2 son equivalentes, en el sentido de que toda proposición bien formada en el sentido de la definición 2.2.1 puede transformarse en otra bien formada en el sentido de la definición 2.2.2 y viceversa. Más aun, dichas transformaciones ``preservan'' la estructura sintáctica de cada proposición. Bien que la intuición es sumamente motivante, debemos aun precisar estas propiedades. Sea $X$ una colección finita de variables proposicionales. Definamos una primera transformación $\Phi:\mbox{\rm Pbf}_H(X) \to \mbox{\rm Pbf}(X)$ recursivamente como sigue:

$$\begin{eqnarray*} \Phi(x) &=& x \\ \Phi(\neg p) &=& \left\{\begin{array}{ll} ... ...box{\it ConPrinc}(q)\not=\rightarrow %%\\ \end{array}\right. \end{eqnarray*}$$

y una segunda $\Psi:\mbox{\rm Pbf}(X) \to \mbox{\rm Pbf}_H(X)$ como sigue:

$$\begin{eqnarray*} \Psi(x) &=& x \\ \Psi(\neg (p)) &=& \neg \Psi(p) \\ \Psi(... ... \Psi( p \rightarrow q ) &=& \rightarrow \Psi(p) \Psi(q) %%\\ \end{eqnarray*}$$

(en ambas definiciones $x$ es un átomo y $p , q$ son proposiciones cualesquiera). Razonando por inducción en la construcción de la proposición $p$, se puede demostrar que

$$\forall p\in \mbox{\rm Pbf}_H(X):\ \ \Psi\circ\Phi(p) = p$$ (3)

$$\forall p\in \mbox{\rm Pbf} (X):\ \ \Phi\circ\Psi(p) = p%%\\$$ (4)

En consecuencia, las transformaciones $\Phi$ y $\Psi$ son inversas una de la otra y son sendas biyecciones. $\forall p\in \mbox{\rm Pbf}_H(X)$ se dice que $p'=\Phi(p)$ es la forma de enfijo equivalente a $p$ y, en sentido inverso, $\forall p\in \mbox{\rm Pbf}(X)$ se dice que $p'=\Psi(p)$ es la forma en notación polaca inversa equivalente a $p$.
Posterior: Cálculo proposicional booleano Arriba: Sintaxis Anterior: Cálculo proposicional formal