Lenguaje proposicional


Lenguaje proposicional
ArbolProposicional.PNG

Dentro de la lógica formal, el lenguaje proposicional estudia las propiedades de los conectivos proposicionales cono y, o, no, si y solo si y entonces entre otros, usados en el desarrollo de las matemáticas.

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.

Para una presentación resumida e informal véase lógica proposicional.

Contenido

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.

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.[1]

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.[2]

Lenguaje de orden cero

Llamaremos 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).

Veremos que las elecciones primigenias de los símbolos lógicos no serán únicas, pero dichas elecciones de símbolos sí serán equivalentes entre ellas, es decir, veremos que a partir de un par de símbolos lógicos podemos incluir las propiedades de otros símbolos lógicos y viceversa.

Definiciones

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.

Sea S:= X \cup \{ \neg ,\; \to \} \cup \{ ( ,\; ) \} el conjunto de símbolos del lenguaje o alfabeto.

Consideremos, dentro de S_{}^{}, que los objetos no son sucesiones finitas de otros objetos. Consecuentemente tenemos 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 lo llamaremos longitud de a.

Ejemplo:

Dado X_{}^{}=\{f,g\} tenemos 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.

Operación negación e implicación

Operación n-aria

Al par de símbolos lógicos le asociaremos dos operaciones internas sobre el conjunto de expresiones, y así formalizar las expresiones bien formadas y construir otras nuevas.

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  f g \to ( es  ( \neg f g \to ( ).
La implicación de  ) \to \to g a  f \neg es  ( ) \to \to g \to f \neg ).

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 esta cogido en matemáticas.
  • Usaremos letras griegas minúsculas para nombrar cada fórmula arbitraria.
  • Usaremos letras griegas mayúsculas para nombrar cada conjunto arbitrario de fórmulas.
  • Ahorraremos 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.

Rango de una fórmula

Llamaremos 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 raiz del árbol de  \neg \psi_{}^{} sale solo una rama y de la raiz 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.

Veamos en la siguiente proposición que en la definición del conjunto Prop(X)_{}^{} tenemos que sus elementos están definidos de forma única:

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(φ) = 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).

Veamos que las dos operaciones no generan un conjunto diferente de Prop(X)_{}^{} a partir de X_{}^{}.

Teorema

Prop(X)_{}^{} es el conjunto más pequeño que contiene a X_{}^{} , y a su vez cerrado para las operaciones negación y 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_{}^{}.

Teorema

El álgebra  < Prop(X) ,\; \neg ,\; \to > es el álgebra absolutamente libre del tipo (1,2) generado por el conjunto X.

Observación

  • Llamaremos tipo (de similaridad) de una estructura algebraica a la que nos indica la anidad de sus operaciones.
  • Notaremos a 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).
  • Diremos 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.
  • Diremos que un álgebra es absolutamente libre si para cada álgebra  < A ,\; \sim ,\; \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.

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 ,\; \sim ,\; \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 Xn.
Sabemos que \begin{matrix}\bar{f}_{|X_0} & X & \longrightarrow & A & \\ a & \longmapsto & \bar{f}_{|X_0}( a ):=f(a) \end{matrix} ya que X0 = X.
Supongamos que está bien definida para Xn, 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 ) = \sim \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.

Corolario

Para cada álgebra  < A ,\; \sim ,\; \Rightarrow > del tipo (1,2) hay una biyección entre las funciones de  X \to A y los homomorfismos  Prop(X) \to A.

Conjunto de subfórmulas

El conjunto de subfórmulas de una fórmula  \varphi es el conjunto Sb(φ) 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 \}.

Conjunto de letras

El conjunto de letras de una fórmula  \varphi \in Prop(X) es el conjunto Xφ 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}.

Proposición

Para cada fórmula  \varphi , el conjunto Xφ es finito y además es el conjunto más pequeño contenido en X tal que  \varphi \in Prop( X_{\varphi}).

Proposición

La imagen de toda fórmula solo depende de las imágenes de sus letras.

Lema

Dada un álgebra  < A ,\; \sim ,\; \Rightarrow > de tipo (1,2) y Z..X, si f : X \to A_{}^{} entonces ---

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).

Eliminación de paréntesis

Los convenios de eliminación de paréntesis se hacen necesários para reducir la proliferación de paréntesis, para ello y mantener la estructura original de las fórmulas es necesário 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 parentesis se hace en el mismo modo primero 1) luego 2) y finalmente 3) como se observa en el ejemplo anterior.

Sin significado todas las formulas proposicionales son sintacticamente 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.

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.[3]

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.[4]

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.

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, \lnot, e implicación,  \Rightarrow .

Observación

La observación anterior quedaría descrita como:
\sim 0 = 1_{}^{}
\sim 1 = 0_{}^{}
1 \Rightarrow 1 = 1
1 \Rightarrow 0 = 0
0 \Rightarrow 1 = 1
0 \Rightarrow 0 = 1

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.

Enderton, H.B., A Mathemátical introduction to Logic, Academic Press, 1972.

Hamilton, A.G., Lógica para matemáticos, Paraninfo, 1981.

Mendelson, E., Introduction to Mathematical Logic, 3ª. ed.,Wadworth an Brook/Cole, 1987, 4ª ed.,Chapman and Hall, 1997.

Pla, J., Lliçons de lógica matemática, P.P.U., 1991.

Referencias

  1. Evandro Agazzi. 3ªedición 1979, pg. 72-73.
  2. Evandro Agazzi. 3ªedición 1979, pg. 75-77.
  3. Evandro Agazzi. 3ªedición 1979, pg. 67.
  4. Evandro Agazzi. 3ªedición 1979, pg.87-90.

Bibliografía complementaria

Badesa, C., Jané, I., Jansana, R., Elementos de lógica formal, Ariel, 1998.

Barnes, D.W., Mack, J.M., Una introducción algebraica a la lógica matemática, Eunibar, 1978.

Bridge, J., Beginning Model Theory, Oxford University Press, 1977.

Ershov, Y., Paliutin. E., Lógica matemática, Mir, 1990.

Hofstadter, D., Gödel, Escher, Bach: un Eterno y Grácil Bucle, Tusquets Editores, Barcelona, 1987.

Jané, I., Álgebras de Boole y lógica, Publs. U.B., 1989.

Monk, J.D., Mathematical Logic, Springer-Verlag, 1976.

Nidditch, P.H., El desarrollo de la lógica matemática. Ediciones Cátedra, 1978.

Van Dalen, D., Logic and Structure, 2nd ed., Universitext, Springer-Verlag, 1983.

Bibliografía de contexto

Evandro Agazzi, la lógica simbólica,Ed Herder, 1967.

Nino B. Cocchiarella and Max A. Freund, Modal Lógica An Introduction to Its Syntax and Semantics , Oxford 2008


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Lenguaje Fril — Saltar a navegación, búsqueda Fril es un lenguaje de programación para el cálculo de predicados de primer orden. Trabaja con un subconjunto de la semántica del lenguaje Prolog pero no del estándar ISO PROLOG, sino con la sintaxis de micro Prolog …   Wikipedia Español

  • Lenguaje formalizado — El lenguaje formalizado es un lenguaje sometido a unas «reglas fijas de formación de expresiones y significados». Es una de las características esenciales del lenguaje científico. Incluso hay autores que llegan a opinar que la ciencia en sí misma …   Wikipedia Español

  • Lenguaje y pensamiento — La Teoria del language y pensamiento, o mentalés es una teoría, principalmente del filósofo EE.UU. Jerry Fodor, lo que supone una especie de lenguaje para ser utilizado por los procesos mentales, que permiten el desarrollo de pensamientos… …   Wikipedia Español

  • Lógica proposicional — En lógica, la lógica proposicional es un sistema formal diseñado para analizar ciertos tipos de argumentos. En lógica proposicional, las fórmulas representan proposiciones y las conectivas lógicas son operaciones sobre dichas fórmulas, capaces de …   Wikipedia Español

  • Lógica modal — Una lógica modal es un sistema formal que intenta capturar el comportamiento deductivo de algún grupo de operadores modales.[1] Los operadores modales son expresiones que califican la verdad de los juicios.[1] Por ejemplo, en la oración es… …   Wikipedia Español

  • Álgebra de las palabras — El álgebra de las palabras estudia la formalización gramatical de las construcciones de palabras sobre un alfabeto para un lenguaje, desde una perspectiva matemática que nos permita, de un modo firme, afirmar o rechazar diversos resultados… …   Wikipedia Español

  • Sucesión matemática — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Cálculo lógico — Saltar a navegación, búsqueda El cálculo lógico, o derivación lógica, es un algoritmo que permite cómoda y fácilmente inferir o deducir un enunciado verdadero a partir de otro u otros que se tienen como válidamente verdaderos. La inferencia o… …   Wikipedia Español

  • Lógica de primer orden — La lógica de primer orden, también llamada lógica de predicados o cálculo de predicados, es un sistema formal diseñado para estudiar la inferencia en los lenguajes de primer orden.[1] Los lenguajes de primer orden son, a su vez, lenguajes… …   Wikipedia Español

  • Lógica — La lógica es una ciencia formal y una rama de la filosofía que estudia los principios de la demostración e inferencia válida. La palabra deriva del griego antiguo λογική (logike), que significa «dotado de razón, intelectual, dialéctico,… …   Wikipedia Español