title: Lenguaje proposicional
text: # Lenguaje proposicional
  
      Este artículo está orientado a proporcionar un tratamiento riguroso y abstracto del lenguaje proposicional. Para una introducción más accesible véase lógica proposicional
  Dentro de la lógica formal, el lenguaje proposicional estudia las propiedades de los conectivos proposicionales como y, o, no, si y solo si y entonces entre otros, usados en el desarrollo de sistemas lógicos en la lógica matemática.
  Para sintetizar gramaticalmente el modelo matemático de lenguaje será necesario introducir unos símbolos para denominar las frases atómicas y otros símbolos, distintos, para denominar los conectivos.
  
  # Lenguaje proposicional
  ## Las fórmulas proposicionales
  
  En este apartado se definirá lo que serán estructuralmente las fórmulas proposicionales a escala sintáctica sin importar el significado de dichas fórmulas.
  
  # Lenguaje proposicional
  ## Nota histórica
  
  Aristóteles estableció un primer sistema de leyes para la lógica sugerido por Platón, luego Teofrasto y Eudemo enriquecieron la obra lógica y desarrollaron la lógica proposicional.
  Debido a Leibniz se desarrolla un nuevo punto de vista del lenguaje lógico, consiguiendo desvincular las proposiciones de su semántica, simplificando las reglas de deducción como simples reglas de cálculo.
  
  # Lenguaje proposicional
  ## Lenguaje de orden cero
  
  Se llama lenguaje de orden cero al que, precisamente, utiliza dos tipos de símbolos, uno para designar las letras, átomos o fórmulas atómicas y otro para los símbolos lógicos o conectivos que tienen su propia anidad o ariedad(expresiones a las que afecta y enlaza).
  Las elecciones primigenias de los símbolos lógicos no son únicas, pero dichas elecciones de símbolos son equivalentes entre ellas, es decir, que a partir de un par de símbolos lógicos se puede incluir las propiedades de otros símbolos lógicos y viceversa.
  
  # Lenguaje proposicional
  ## Definición de símbolos lógicos
  
  Sea $X_^$ el conjunto de letras o fórmulas atómicas.
  Sea el objeto $\neg _^$ el símbolo lógico de negación.
  Sea el objeto $\to _^$ el símbolo lógico de implicación.
  Sean los objetos ( y ) los paréntesis encargados de los símbolos de puntuación.
  
  # Lenguaje proposicional
  ## Definiciones secundarias
  
  Sea $S:=X\cup \{\neg ,\;\to \}\cup \{(,\;)\}$ el conjunto de símbolos del lenguaje o alfabeto.
      Se considera, dentro de $S_^$, que los objetos no son sucesiones infinitas de otros objetos. Consecuentemente se tiene que la longitud de una sucesión es constante.
  Sea $E:=S^{\ast }$ el conjunto de expresiones del lenguaje, que es el conjunto de palabras sobre el alfabeto.
  Para todo elemento $a\in E$ existe un único valor $n>0$ de modo que a es de $S_^{n}$, a n se le llama longitud de a.
  Ejemplo:
      Dado $X_^=\{f,g\}$ se tiene que una expresión del tipo $f\neg \to )g\to \;\in S_^{6}\subset E$
  Observación:
      En E están todas las expresiones del lenguaje que se pueden hacer a partir del alfabeto S. Para separar las expresiones, que por un lado no tienen sentido de las que por otro lado están bien formadas o son sintácticamente correctas, se ha de establecer unas normas y reglas para usar los símbolos de puntuación.
  
  # Lenguaje proposicional
  ## Operación negación e implicación
  
  A cada símbolo lógico se le asocia una operación interna sobre el conjunto de expresiones, así se formalizan las expresiones bien formadas mediante su construcción.
  Negación: Operación unaria definida por la aplicación:
  ${\begin{matrix}E&\longrightarrow &E&\\a&\longmapsto &(\neg a)&:=<(>\circ <\neg >\circ <a>\circ <)>.\end{matrix}}$
  Implicación: Operación binaria definida por la aplicación:
  ${\begin{matrix}E\times E&\longrightarrow &E&\\<a,\;b>&\longmapsto &(a\to b)&:=<(>\circ <a>\circ <\to >\circ <b>\circ <)>.\end{matrix}}$
  Ejemplo:
      Dado $X_^=\{f,g\}$ tenemos que:
         La negación de $fg\to ($ es $(\neg fg\to$.
         La implicación de $)\to \to g$ a $f\neg$ es $\to \to g\to f\neg )$.
  Si se desea ver un trabajo equivalente con notación polaca, ahorrando los paréntesis, consúltese Pla J., posteriormente se podrá probar que las dos notaciones son equivalentes, de hecho no son necesarios los paréntesis en la definición polaca, y que por tanto se podrían haber ahorrado dichos paréntesis.
  Con estas dos operaciones ya se puede construir y formalizar el conjunto de expresiones bien formadas conocidas como conjunto de fórmulas proposicionales:
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  
  El conjunto de fórmulas proposicionales es el conjunto $Prop(X):=\bigcup _{n\geq 0}X_{n}$ donde:
  ${\begin{matrix}{X_{0}^\;\;}&{=}&{X,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}\\{X_{n+1}^}&{=}&{X_{n}\cup \{(\neg \varphi ):\varphi \in X_{n}\}\cup \{(\varphi \to \psi ):\varphi ,\psi \in X_{n}\}}.\end{matrix}}$
  Ejemplos:
      Dado $X_^=\{f,g\}$ tenemos que:
         $f\in X_{0}^\subset Prop(X)$
         $(\neg f)\in X_{1}^\subset Prop(X)$
         $(g\to f)\in X_{1}^\subset Prop(X)$ con $g\in X_{0}^$
         $((g\to f)\to (\neg f))\in X_{2}^\subset Prop(X)$.
  Comentarios:
  * A las fórmulas proposicionales, las llamaremos simplemente fórmulas. Evitemos llamarlas simplemente proposiciones pues técnicamente dicho término ya está cogido en matemáticas.
  * Se usará letras griegas minúsculas para nombrar cada fórmula arbitraria.
  * Se usará letras griegas mayúsculas para nombrar cada conjunto arbitrario de fórmulas.
  * Se ahorrará los paréntesis al escribir fórmulas atómicas y los paréntesis más exteriores de las fórmulas.
  * Las fórmulas son sucesiones finitas.
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Rango de una fórmula
  
  Se llamará rango de una fórmula al valor:
  $n=min\{i:\varphi \in X_{i}\}.$
  Observación:
      El rango será útil para demostrar propiedades por inducción.
      Si $r<n\Rightarrow X_{r}\subset X_{n}.$
      Si $\varphi \in X_{r},\;r<n\Rightarrow \varphi \in X_{n}.$
      $\{\neg \psi :\psi \in Prop(X)\}\cap \{\gamma \to \xi :\gamma ,\xi \in Prop(X)\}=\emptyset$ ya que el primer conjunto tiene globalmente una operación unaria y el segundo una binaria, es decir, que de la raíz del árbol de $\neg \psi _^$ sale solo una rama y de la raíz de $\gamma \to \xi _^$ parten dos ramas.
      Si $rang(\neg \psi )=n\Rightarrow rang(\psi )=n-1.$
      Si $rang(\gamma \to \xi )=n\Rightarrow rang(\gamma )=n-1\;o\;\;rang(\xi )=n-1.$
  En la siguiente proposición la definición del conjunto $Prop(X)_^$ los elementos están definidos de forma única:
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Proposición
  
  Toda fórmula
     $\varphi \in Prop(X)$
  cumple una única condición de las siguientes:
  1) $\varphi =x\in X.$
  2) $\varphi =\neg \psi$ para una única fórmula $\psi \in Prop(X).$
  3) $\varphi =\psi \to \xi$ para dos únicas fórmulas $\psi ,\xi \in Prop(X).$
  * Demostración
  * Si $\varphi \in Prop(X)\Rightarrow$ $\exists n:rang(\varphi )=n\;\;y\;\varphi \in X_{n},$ veamos todos los casos de n por inducción:
  * Si $n=0_^\Rightarrow$ $X_{0}^=X\Rightarrow$ $\varphi =a\in X$ por tanto únicamente el caso 1).
  * Si $n>0_^,$ supongamos probado hasta el caso $rang(\varphi )=n-1,$ entonces demostrémoslo para n, así de $\varphi \in X_{n}=X_{n-1}\cup \{\neg \varphi :\varphi \in X_{n-1}\}\cup \{\gamma \to \xi :\gamma ,\xi \in X_{n-1}$ parten únicamente 3 casos:
  * $rang(\varphi )=n\Rightarrow \varphi \notin X_{n-1}.$
  * Si $\varphi =\neg \psi :\psi \in X_{n-1}\Rightarrow$ $rang(\psi )\leq n-1\Rightarrow$ $\psi _^$ es único por hipótesis y por tanto cumple 2).
  * Si $\varphi =\gamma \to \xi :\gamma ,\xi \in X_{n-1}\Rightarrow$ $rang(\gamma )\leq n-1\;\;y\;\;rang(\xi )\leq n-1\Rightarrow$ $\gamma \;\;y\;\;\xi$ son únicos por hipótesis y por tanto cumple 3).
  Las dos operaciones no generan un conjunto diferente de $Prop(X)_^$ a partir de $X_^.$
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Teorema
  
  $Prop(X)_^$ es el conjunto más pequeño que contiene a $X_^,$ y a su vez cerrado para las operaciones negación e implicación.
  * Demostración
  * Directamente $X=X_{0}\subseteq Prop(X).$
  * Veamos que $Prop(X)$ es cerrado para las operaciones $\neg$ y $\to :$
  * Si $\varphi \in Prop(X)\Rightarrow$ $\exists n:\varphi \in X_{n}\Rightarrow$ $\neg \varphi \in X_{n+1}\subset Prop(X).$
  * Si $\varphi ,\psi \in Prop(X)\Rightarrow$ $\varphi \in X_{n}$ y $\psi \in X_{m}\Rightarrow$ $\varphi \to \psi \in X_{n+m+1}\subset Prop(X).$
  * Veamos finalmente por inducción sobre n que es el conjunto más pequeño:
  * Sea $Z\subset E:X\subset Z\varsubsetneq Prop(X)$ y cerrado para las dos operaciones, entonces:
  * Si n=0, tenemos $X_{0}=X\subseteq Z.$
  * Supongamos que $X_{n}\subseteq Z\Rightarrow$ $X_{n}\cup \{(\neg \varphi ):\varphi \in X_{n}\}\cup \{(\varphi \to \psi ):\varphi ,\psi \in X_{n}\}\subseteq Z\Rightarrow$ $X_{n+1}\subseteq Z$ por ser $Z_^$ cerrado por las dos operaciones.
  * Por tanto quiere decir que $Prop(X)\subseteq Z$ contradiciendo la hipótesis, es decir, rechazando la existencia de dicha $Z_^.$
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Teorema
  
  El álgebra $<Prop(X),\;\neg ,\;\to >$ es el álgebra absolutamente libre del tipo (1,2) generado por el conjunto X.
  Observación
  * Se llama tipo (de similitud) de una estructura algebraica a la que nos indica la anidad de sus operaciones.
  * Se nota que un álgebra es del tipo (1, 2) si tiene dos operaciones, una unaria indicada por el uno($\neg$ que actúa sobre un elemento) y otra binaria indicada por el dos($\to$ que actúa sobre dos elementos).
  * Se dice que un álgebra está generado por $X$ si es el álgebra más pequeño que contiene el conjunto $X$ y es cerrado por las operaciones.
  * Se dice que un álgebra es absolutamente libre si para cada álgebra $<A,\;$╖$,\;\Rightarrow >$ del mismo tipo (1, 2), tenemos que toda función $f:X\to A$ se puede extender de manera única a un homomorfismo ${\bar {f}}:Prop(X)\to A.$
      Véase también: Álgebra universal
         Véase también: Objeto libre
  * Demostración
  * Por construcción $<Prop(X),\;\neg ,\;\to >$ es un álgebra del tipo (1,2).
  * Por el teorema anterior $<Prop(X),\;\neg ,\;\to >$ está generado por $X_^.$
  * Finalmente para ver que es absolutamente libre:
  * Sea $<A,\;$╖$,\;\Rightarrow >$ un álgebra del tipo (1,2), veamos que toda ${\begin{matrix}f:&X&\longrightarrow &A&\\&a&\longmapsto &f(a)\end{matrix}}$ puede extenderse de forma única a ${\begin{matrix}{\bar {f}}:&Prop(X)&\longrightarrow &A&\\&\varphi &\longmapsto &{\bar {f}}(\varphi )\end{matrix}}$, definida recursivamente o mejor por libertad sobre $X_{n}^.$
  * Se sabe que ${\begin{matrix}{\bar {f}}_{|X_{0}}:&X&\longrightarrow &A&\\&a&\longmapsto &{\bar {f}}_{|X_{0}}(a)&:=f(a)\end{matrix}}$ ya que $X_{0}^=X.$
  * Suponiendo que está bien definida para $X_{n}$, entonces para $\varphi \in X_{n+1}$ solo queda definir $\alpha \in X_{n+1}\backslash X_{n}=\{(\neg \varphi ):\varphi \in X_{n}\}\cup \{(\varphi \to \psi ):\varphi ,\psi \in X_{n}\}$, es decir, cuando $\alpha =\neg \varphi$ y $\alpha =\varphi \to \psi$ tenemos inevitablemente que para ser homomorfismo se tienen que cumplir:
  * ${\bar {f}}(\neg \varphi )=$ ╖${\bar {f}}(\varphi )$
  * ${\bar {f}}(\varphi \to \psi )={\bar {f}}(\varphi )\Rightarrow {\bar {f}}(\psi )$
  * Queda bien definido para todo n y, es decir, para $Prop(X)_^.$
  * Por tanto ${\bar {f}}$ es el único homomorfismo de este tipo.
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Teorema
  #### Corolario
  
  Para cada álgebra $<A,\;$╖$,\;\Rightarrow >$ del tipo (1,2) hay una biyección entre las funciones de $X\to A$ y los homomorfismos $Prop(X)\to A.$
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Conjunto de subfórmulas
  
  El conjunto de subfórmulas de una fórmula $\varphi$ es el conjunto $Sb(\varphi )_^$ definido por recursión con:
         $Sb(x)=\{x\}\;si\;x\in X$
         $Sb(\neg \varphi )=Sb(\varphi )\cup \{\neg \varphi \}$
         $Sb(\varphi \to \psi )=Sb(\varphi )\cup Sb(\psi )\cup \{\varphi \to \psi \}.$
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Conjunto de letras
  
  El conjunto de letras de una fórmula $\varphi \in Prop(X)$ es el conjunto $X_{\varphi }^$ definido por recursión con:
         $X_{x}=\{x\}\;si\;x\in X$
         $X_{\neg \varphi }=X_{\varphi }$
         $X_{\varphi \to \psi }=X_{\varphi }\cup X_{\psi }.$
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Conjunto de letras
  #### Proposición
  
  Para cada fórmula $\varphi$, el conjunto $X_{\varphi }^$ es finito y además es el conjunto más pequeño contenido en $X_^$ tal que $\varphi \in Prop(X_{\varphi }).$
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Conjunto de letras
  #### Proposición
  
  La imagen de toda fórmula solo depende de las imágenes de sus letras.
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Conjunto de letras
  #### Proposición
  ##### Lema
  
  Dada un álgebra $<A,\;\sim ,\;\Rightarrow >$ de tipo (1,2) y $Z\subset X$, si $f:X\to A_^$ entonces ${\bar {f}}_{|Prop(Z)}={\overline {f_{|Z}}}$
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Abreviaciones
  
  Las abreviaciones comunes son las siguientes:
  * La disjunción (...o...): $\varphi \lor \psi :=(\neg \varphi )\to \psi .$
  * La conjunción (...i...): $\varphi \land \psi :=\neg (\varphi \to (\neg \psi )).$
  * La equivalència (...si i solo sí...): $\varphi \leftrightarrow \psi :=(\varphi \to \psi )\land (\psi \to \varphi ).$
  
  # Lenguaje proposicional
  ## Conjunto de fórmulas proposicionales
  ### Eliminación de paréntesis
  
  Los convenios de eliminación de paréntesis se hacen necesarios para reducir la proliferación de paréntesis, para ello y mantener la estructura original de las fórmulas es necesario estos tres:
  1) $\neg$ solo afecta a fórmulas inmediatas.
  2) $\lor ,\land$ solo afectan a las fórmulas inmediatas y toma como una fórmula las de tipo 1), $\neg \varphi$, sin necesidad de paréntesis.
  3) $\to ,\leftrightarrow$ afectan de modo global, es decir, toman como una fórmula las de tipo 1) y 2) sin necesidad de paréntesis.
  Ejemplo:
  * $\neg \varphi \lor \psi \to \xi$ es la misma que $((\neg \varphi )\lor \psi )\to \xi .$
  Observación:
      Para restaurar los paréntesis se hace en el mismo modo primero 1) luego 2) y finalmente 3) como se observa en el ejemplo anterior.
  
  # Lenguaje proposicional
  ## Semántica bivalorada
  
  Sin significado todas las fórmulas proposicionales son sintácticamente diferentes unas de otras, excepto si son la misma cadena de símbolos. La introducción de la semántica bivalorada a la gramática proposicional consiste en reducir todas las situaciones posibles a dos: cierto o verdadero y falso. Aparece entonces una relación de equivalencia entre fórmulas que permiten identificar fórmulas equivalentes.
  
  # Lenguaje proposicional
  ## Nota histórica
  
  Aristóteles desarrolló la parte más importante y sólida de la lógica, pero su semántica tiene un desarrollo embrionario.
  Boole desarrolló el primer cálculo lógico sugerido por Leibniz, construyendo cálculos puramente algebraicos mediante símbolos y operaciones. Boole consigue reactivar con su teoría algebraica la lógica proposicional.
  Observación intuitiva
  Si $\alpha _^$ es verdadera, entonces $\sim \alpha _^$ es falsa.
      Igualmente si $\alpha _^$ es falsa, entonces $\sim \alpha _^$ es verdadera.
  Supongamos que $\alpha \Rightarrow \beta$ es verdadero si, siempre que $\alpha _^$ es verdad entonces exige que $\beta _^$ sea verdad.
  Fácilmente:
      Si $\alpha _^$ es verdad y $\beta _^$ es falsa, contradice la afirmación anterior y por tanto sería falsa.
      Si $\alpha _^$ es falsa y $\beta _^$ es verdad, no contradice la afirmación anterior y por tanto sería verdadera.
      Si $\alpha _^$ es falsa y $\beta _^$ es falsa, no contradice la afirmación anterior y por tanto sería verdadera.
  
  # Lenguaje proposicional
  ## Definiciones básicas
  
  Sean 1 (verdad) y 0 (falso) los dos valores de verdad.
  Sea $A=\{1,0\}_^$.
  Sea $\mathbb {A} =<A,\sim ,\Rightarrow >$ el álgebra del tipo (1,2) sobre el conjunto base $A_^$ y las operación de negación, $\sim _^$, e implicación, $\Rightarrow$.
  Observación
      La observación anterior quedaría descrita como:
         ${\underline {\sim 1=0}}\;\;\;\;\;\;\;\sim 0=1_^$
         ${\underline {1\Rightarrow 1=1}}\;\;\;\;\;1\Rightarrow 0=0$
         $0\Rightarrow 1=1\;\;\;\;\;0\Rightarrow 0=1$
      presentado en tablas por:
  ${\begin{array}{c|cc}&\sim \\\hline 0&1\\1&0\\\end{array}}\;\;\;\;\;\;\;\;\;\;\;\;{\begin{array}{c|cc}\Rightarrow &0&1\\\hline 0&1&1\\1&0&1\\\end{array}}$
  
  # Lenguaje proposicional
  ## Definición de valoración
  
  Llamaremos valoración a cualquier morfismo entre $<Prop(X),\lnot ,\to >$ y A.
  Sea $v_^$ una valoración, entonces para cada fórmula $\xi _^$ podemos definir su valor recursivamente mediante las ecuaciones
      $v(\lnot \varphi )=\sim v(\varphi )$
      $v(\varphi \to \psi )=v(\varphi )\Rightarrow v(\psi )$
  a partir de cada letra o fórmula atómica de $\xi _^$ podemos hallar $v(\xi _^)$.
  Ejemplo
      Dada $\xi _^=\neg \varphi \to \psi$ y una sola valoración al azar $v(\varphi )=1,\;v(\psi )=0$, véase que:
         $v(\xi _^)=v(\neg \varphi \to \psi )=v(\neg \varphi )\Rightarrow v(\psi )=\sim v(\varphi )\Rightarrow v(\psi )=$ $\sim 1\Rightarrow 0=0\Rightarrow 0=1.$
  Para acelerar el proceso de cálculo de fórmulas proposicionales se ha generalizado el uso de tablas de la verdad: