Este post es "continuación" de los siguientes:
Duda sobre definiciones y conjuntos inductivosEsquema de recursión primitiva para PROPSecuencias de formación y subfórmulasLos ejercicios anteriores eran más bien para introducirnos en el lenguaje de la lógica proposicional, o sea, para entender bien qué elementos están el lenguaje \( \text{PROP} \) y cuáles no, qué son las subfórmulas, cómo probar propiedades sobre los elementos de \( \text{PROP} \), etc.
Los ejercicios que vienen ahora corresponden a la
semántica de la lógica proposicional. Una vez que está definido el lenguaje, interesa saber para qué lo definimos, es decir, qué significado le vamos a dar a estas "tiras" de símbolos y qué se puede representar con ellas.
Para ello, lo primero es la siguiente definición.
Definición 4Una
valuación es una función \( v:\text{PROP}\rightarrow \{0,1\} \) que satisface:
i) \( v(\varphi\wedge \psi)=\min\{v(\varphi),\ v(\psi)\} \)
ii) \( v(\varphi\vee \psi)=\max\{v(\varphi),\ v(\psi)\\} \)
iii) \( v(\varphi\rightarrow \psi)=\max\{1-v(\varphi),\ v(\psi)\} \)
iv) \( v(\varphi\leftrightarrow \psi)=1 \Longleftrightarrow v(\varphi)=v(\psi) \)
v) \( v(\lnot \varphi)=1-v(\varphi) \)
vi) \( v(\bot)=0 \)
Estas reglas nos dicen claramente cómo se transmite el valor de verdad a partir de las letras proposicionales. Y son exactamente las mismas que las famosas "tablas de verdad" que hay para cada uno de los conectivos.
Luego en el libro aparecen algunos teoremas (o metateoremas) sobre las valuaciones, por ejemplo, si una función \( v':\{p_0,p_1,\dots, \bot\}\rightarrow \{0,1\} \) satisface \( v(\bot)=0 \) entonces hay una única valuación \( v \) tal que \( v(\varphi)=v'(\varphi) \) para toda \( \varphi\in \text{PROP} \). O sea, fijado el valor de verdad de cada uno de los átomos, queda fijo también el valor de verdad de cualquier otra fórmula del lenguaje. Otro teorema dice que el valor de verdad de una fórmula depende únicamente del valor de sus letras de proposición. Y así más resultados similares...
Definición 5i) \( \varphi\in \text{PROP} \) es una
tautología si y sólo si, para cualquier valuación \( v \), se cumple que \( v(\varphi)=1 \).
ii) Dadas \( \Gamma\subseteq \text{PROP} \) y \( \alpha\in \text{PROP} \), \( \alpha \) es
consecuencia lógica de \( \Gamma \) si y sólo si, para cualquier valuación \( v \) que verifique \( v(\gamma)=1,\;\forall \gamma\in \Gamma \), se cumple que \( v(\alpha)=1 \).
Notación- \( \Gamma \models \alpha \) se lee \( \text{``$\alpha$ es consecuencia l\'ogica de $\Gamma$''} \).
- \( \gamma_1,\gamma_2,\dots, \gamma_n\models \alpha \) se usará en vez de \( \{\gamma_1,\dots,\gamma_n\}\models\alpha \).
- Asimismo, \( \models \alpha \) representará \( \emptyset\models \alpha \), y se lee \( \text{``$\alpha$ es tautolog\'ia''} \).
Una cosa que no dije antes es que la notación usada para las fórmulas de \( \text{PROP} \) (de acuerdo a la definición inductiva) se flexibilizará para disminuir la cantidad de paréntesis. Por norma, se eliminarán siempre los paréntesis exteriores y no se usarán en el caso de la negación. Asimismo se adopta la convención de que \( \vee \) y \( \wedge \) tienen mayor prioridad respecto a las flechas (algo así como si las flechas correspondieran a los símbolos de suma y resta, y la conunción y la disjunción fueran los de multiplicación y división). El símbolo de negación \( \lnot \) será el que tiene mayor prioridad de todos. En el libro a las expresiones resultantes de aplicar estas reglas, se les llama
abbreviations y se aclara que estrictamente hablando, no son fórmulas proposicionales. Dicho todo ésto, pongo algunos ejemplos triviales:
1) \( \models \varphi\rightarrow \varphi \)
2) \( \models \varphi\vee \lnot\varphi \)
3) \( \varphi,\psi\models \varphi\wedge \psi \)
Bueno, me faltan ahora dos conceptos más para que se pueda entender el ejercicio que voy a plantear.
Definición 6Dos fórmulas \( \alpha \) y \( \beta \) se dicen
equivalentes sii \( \models\alpha\leftrightarrow\beta \). Se simbolizará \( \alpha \approx \beta \).
Ejemplo: \( \alpha\leftrightarrow \beta\approx (\alpha\rightarrow \beta)\wedge (\beta\rightarrow\alpha) \)
Después hay un teorema de sustitución muy importante (por eso lo menciono si bien no es estrictamente indispensable para entender el ejercicio que voy a plantear), que dice que en una fórmula uno puede sustituir subfórmulas por otras equivalentes sin que eso altere el valor de verdad.
Definición 7Un conjunto de conectivos \( C \) es funcionalmente completo si para cada conectivo
n-ario \( \$ \) (donde \( n>0 \)) definido por su correspondiente tabla de verdad, existe una fórmula \( \sigma \) que contiene sólo a las letras proposicionales \( p_{1},p_{2},\dots, p_{n} \) y a los conectivos de \( C \), tal que \( \sigma \approx \$(p_{1},p_{2},\dots, p_{n}) \).
Si entendí bien la definición, un conjunto de conectivos es completo si cualquier otro conectivo puede expresarse en términos de los conectivos de \( C \).
En el libro, para demostrar que \( \{\lnot,\ \vee\} \) es completo hace una prueba por inducción sobre \( n \), considerando
todos los conectivos posibles. Pero en el teórico, se hizo el siguiente ejemplo: probar que \( \{\bot,\ \rightarrow\} \) es completo. Y el profesor hizo algo así. Considere el conjunto \( \text{PROP}_{\bot,\rightarrow} \) definido inductivamente como:
\( \begin{array}{ll} \mbox{ I } & p_i\in \text{PROP}_{\bot,\rightarrow}(i\in \mathbb{N}), \\ \mbox{ II }& \bot\in \text{PROP}_{\bot,\rightarrow}, \\ \mbox{ III }& \mbox{Si $\varphi,\psi\in \text{PROP}_{\bot,\rightarrow}$, entonces $(\varphi\rightarrow \psi)\in \text{PROP}_{\bot,\rightarrow}$} \end{array} \)
Después de eso, lo que hizo fue probar que para toda \( \alpha\in \text{PROP} \) existe \( \beta\in \text{PROP}_{\bot,\rightarrow} \) tal que \( \alpha\approx \beta \). Para eso definió una función de "traducción" de un lenguaje a otro, que a cada fórmula proposicional de \( \text{PROP} \) le asigne su equivalente en \( \text{PROP}_{\bot,\rightarrow} \). Define tal función \( f:\text{PROP}\rightarrow \text{PROP}_{\bot,\rightarrow} \) por recursión primitiva:
\( \left\{\begin{array}{rll} f(p_i) &=& p_i,\;\forall i\in \mathbb{N}\\ f(\bot) &=& \bot\\ f((\lnot\varphi))} &=& (f(\varphi)\rightarrow \bot)\\ f((\varphi\vee \psi))&=&((f(\varphi)\rightarrow \bot)\rightarrow f(\psi))\\ f((\varphi\rightarrow \psi))&=&(f(\varphi)\rightarrow f(\psi))\\ &\vdots& \end{array}\right. \)
Por último, prueba por inducción sobre \( \phi \) que \( \phi\approx f(\phi) \). ¿Por qué ésa es una demostración válida de que \( \{\bot,\ \rightarrow\} \) es completo? Pues en realidad no está mostrando que
todos los conectivos posibles pueden ponerse en términos de \( \bot \) y de \( \rightarrow \) sino sólamente los de \( \text{PROP} \). ¿Es suficiente? En caso de serlo, requeriría una demostración también... ¿o no?
Bueno, ahora sí el ejercicio que me piden resolver. Dice así:
Denotamos por \( \text{``$|$''} \) la barra de Sheffer cuya función de valuación es la siguiente:
\( v(\alpha|\beta)=0\Longleftrightarrow v(\alpha)=v(\beta)=1 \) (se lee \( \alpha \) y \( \beta \) son incompatibles, es decir, no ocurren ambos a la vez)
Demuestre que el conjunto \( \{|\} \) es funcionalmente completo.
No sé como hacer la demostración. Lo más fácil es hacer algo parecido a lo que hizo mi profesor, aunque algunos conectivos quedan muy largos usando sólo la barra de Sheffer; no sé cuál sería la forma más simple.
Muchas gracias.
Saludos