Cálculo proposicional: enunciado y demostración del teorema único de legibilidad en notación polaca

Question

La lengua $\mathcal{L_0}$ : Dejemos que $\mathcal{L_0}$ sea el conjunto más pequeño $L$ de secuencias finitas de $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ y $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ para $n \in \mathbb{N}$ que satisface las siguientes propiedades:

(1) Para cada símbolo proposicional $A_n$ con $n\in\mathbb{N}$ , \begin{multline} A_n \in L. \end{multline}

(2) Para cada par de secuencias finitas $s$ y $t$ Si $s$ y $t$ pertenecen a $L$ entonces \begin{multline} (\neg s) \in L \end{multline} y \begin{multline} (s \to t) \in L. \end{multline}

Legibilidad para $\mathcal{L_0}$ : Supongamos que $\phi$ es una fórmula en $\mathcal{L_0}$ . Entonces se da exactamente una de las siguientes condiciones.
(1) Hay un $n$ tal que $\phi = A_n.$
(2) Existe una $\psi \in \mathcal{L_0}$ tal que $\phi = (\neg\psi)$ .
(3) Hay $\psi_1$ y $\psi_2$ en $\mathcal{L_0}$ tal que $\phi = (\psi_1 \to \psi_2)$

Legibilidad única para $\mathcal{L_0}$ : Las mismas condiciones de legibilidad, pero en (2) y (3), las fórmulas $\psi$ , $\psi_1$ y $\psi_2$ son únicos, respectivamente.

Problema (notación polaca): Dejemos que $\mathcal{P_0}$ sea el conjunto más pequeño de secuencias $P$ de manera que se cumplan las siguientes condiciones.
a) Para cada $n$ , $A_n \in P$ .
b) Si $\psi_1$ y $\psi_2$ pertenecen a $P$ entonces también $\neg\psi_1$ y $\to\psi_1\psi_2 = \langle \to \rangle + \psi_1 + \psi_2$ .

Indique y demuestre el teorema de legibilidad única para $\mathcal{P_0}$

Answer 1

Supongamos que $\phi$ es una fórmula en $\mathcal{P_0}$ . Entonces $\phi$ es una y sólo una de estas formas:
(1) Hay un $n$ tal que $\phi =A_n$ .
(2) Existe una $\psi$ en $\mathcal{P_0}$ tal que $\phi = \neg\psi$ .
(3) Hay $\psi_1$ y $\psi_2$ en $\mathcal{P_0}$ tal que $\phi = \to\psi_1\psi_2$ .
Además, el $\psi_i$ en (2) y (3) están determinados de forma única.

Está absolutamente claro que son mutuamente excluyentes en la notación polaca. Todo lo que queda es mostrar que en (2) y (3), estos $\psi_i$ son únicas:

Para (2), supongamos $\neg\psi_a$ = $\neg\psi_b \implies \psi_a=\psi_b \implies$ la singularidad.
Para (3), supongamos $\to\psi_1\psi_2=\to\psi_3\psi_4 \implies \psi_1\psi_2=\psi_3\psi_4 \implies$ uno de $\psi_1,\psi_3$ es un segmento inicial de otro, lo que sabemos que no es posible:

Dejemos que $w$ sea el peso de los símbolos:
$w(A_n) = 1, w(\neg)=0, w(\to) = -1$ .

Entonces, para cualquier fórmula de pulido $\psi = s_1\dots s_n$ de longitud $n$ La suma de los pesos de sus símbolos, $\sum_{i=1}^{n}w(s_i) =1$ por inducción.

Cualquier segmento terminal de una fórmula de pulido es una concatenación de fórmulas de pulido. Supongamos, pues, que $\psi'$ es una fórmula de pulido de segmento inicial adecuada de la fórmula de pulido $\psi$ y $\psi''$ es el segmento terminal de $\psi$ que hace que $\psi=\psi'\psi''$ .

Si $\psi=\psi'\psi''$ entonces $w(\psi) = w(\psi')+w(\psi'')$ . Pero $\psi''$ es un segmento de terminación de una fórmula de pulido por lo que su peso es mayor o igual a $1$ . Contradicción.