Lenguaje proposicional. ¿No entiende la definición?

Question

Estoy tomando una clase de lógica matemática, y no entiendo esta definición del $propositional$ $language$ como se indica en mi libro:

"El lenguaje proposicional $\mathscr{L}_0$ es el conjunto más pequeño $L$ de secuencias finitas de los símbolos anteriores que satisfacen las siguientes propiedades.

(1) Para cada símbolo proposicional $A_n$ con $n\in$ $0, 1, 2, ... $ tenemos

$A_n \in L$

(2) Para cada par de secuencias finitas $s$ y $t$ , si $s$ y $t$ pertenecen a $L$ entonces

$(\neg s) \in L$

y

$(s \implies t) \in L$ .

He intentado encontrar otras fuentes en Internet, pero la notación es tan variada... Agradecería mucho que me ayudaran a entender lo que significa.

Answer 1

Estoy seguro de que $(1)$ y $(2)$ se explican con suficiente claridad en las respuestas siguientes. También tienes que entender bien la primera frase de la definición. Asumo que ya has definido $\{A_n\}$ el conjunto de símbolos proposicionales.

La definición dice primero que todos los elementos de $ \mathscr L_{\circ} $ son cadenas de símbolos de $\{A_n\}$ o $ \{ \lnot, \implies , (, )\} $ . Así que el alfabeto de su idioma se ha especificado.

A continuación dice que sólo se pueden considerar cadenas finitas. Esto es muy importante a la hora de construir fórmulas. Así que las cadenas infinitas no son "palabras" en el Lenguaje de las Proposiciones.

Finalmente dice que este es el conjunto más pequeño $L$ tal que $(1)$ y $(2)$ retener. Esto también es muy importante. Dice que ninguna otra cadena que contenga letras de $\{A_n , \lnot, \implies , (, )\} $ es una palabra gramatical en $ \mathscr L_{\circ} $ a menos que sea necesario por las condiciones $(1)$ y $(2)$ . Es decir, si $\alpha \in \mathscr L_{\circ} $ entonces $\alpha$ es un símbolo proposicional O $\alpha $ es idéntica a $ (\lnot \beta) $ donde $ \beta \in \mathscr L_{\circ} $ O $\alpha$ es idéntica a $ \beta \implies \gamma $ donde $ \beta, \gamma \in \mathscr L_{\circ} $

Estas definiciones deben entenderse correctamente. La frase "conjunto más pequeño" puede interpretarse como

• La intersección de todos los conjuntos para los que $(1)$ y $(2)$ están satisfechos O
• Como el conjunto de todas las palabras construidas de los símbolos proposicionales (y sólo ellos) mediante las operaciones $\lnot$ y $\implies$ .

Ver Introducción matemática a la lógica por Enderton para demostrar que los dos conjuntos son realmente iguales. Espero que esto haya servido de ayuda.

Answer 2

Bueno, sería bueno tener algún contexto adicional para esta pregunta, pero déjame tratar de responder (lo que entendí de tu versión corta):

Aparentemente el ejemplo trata de construir un lenguaje que imite la negación lógica $\neg$ y la implicación $\Rightarrow$ .

Así que en su idioma hay algunos símbolos $A_n$ ( $n=1,2,3,4,\ldots$ ) que son como variables y luego hay dos "operaciones" entre esos símbolos. La primera es la "negación" $\neg$ que es un operador unitario, es decir, que toma una sola variable o cadena y se pone delante de ella (para negar lo que sigue). El segundo es un operador binario $\Rightarrow$ lo que suele significar que si la cadena de la izquierda es verdadera, la de la derecha también tiene que serlo.

Este parece ser el "sentido" (la intención) del ejemplo de este lenguaje. Sin embargo lo que el lenguaje realmente hace es formar todas las cadenas finitas que corresponden a fórmulas lógicas en las variables y esos dos operadores. Lo que describes es sólo una manera formal de construir un conjunto de todas las cadenas a partir de esos símbolos y operadores de "conexión". No estoy seguro de lo que tú (o el libro) pretende hacer con esto después.

Si buscas más ejemplos de este tipo, intenta construir un lenguaje a partir de símbolos $A_n$ y operadores como $\mathsf C$ , $\cap$ y $\cup$ (que podría interpretarse como complemento, intersección y unión en teoría de conjuntos) o de $\neg$ , $\wedge$ , $\vee$ (que correspondería a la negación, al AND lógico y al OR lógico), etc. Intenta escribir los axiomas (reglas) de esos lenguajes para ver si has entendido de qué trata el concepto formal.

Answer 3

Aquí hay una presentación de diapositivas sobre estos lenguajes con algunos antecedentes adicionales y algunos ejemplos/ejercicios:

http://www3.cs.stonybrook.edu/~pfodor/courses/CSE371/slides03/3slides.pdf