5.2: Idiomas de primer orden
- Page ID
- 103721
Las expresiones de lógica de primer orden se construyen a partir de un vocabulario básico que contiene variables, símbolos constantes, símbolos predicados y, a veces, símbolos de función. A partir de ellos, junto con las conectivas lógicas, cuantificadores y símbolos de puntuación como paréntesis y comas, se forman términos y fórmulas.
Informalmente, los símbolos de predicado son nombres para propiedades y relaciones, los símbolos constantes son nombres para objetos individuales y los símbolos de función son nombres para asignaciones. Estos, a excepción del predicado de identidad\(\eq[][]\), son los símbolos no lógicos y juntos conforman un lenguaje. Cualquier lenguaje de primer orden\(\Lang L\) está determinado por sus símbolos no lógicos. En el caso más general,\(\Lang L\) contiene infinitamente muchos símbolos de cada tipo.
En el caso general, hacemos uso de los siguientes símbolos en la lógica de primer orden:
-
Símbolos lógicos
-
Conectivos lógicos:\(\lnot\) (negation),\(\land\) (conjunction),\(\lor\) (disjunction),\(\lif\) (conditional),\(\lforall{}{}\) (universal quantifier),\(\lexists{}{}\) (existential quantifier).
-
La constante proposicional para la falsedad\(\lfalse\).
-
El predicado de identidad de dos lugares\(\eq[][]\).
-
Un conjunto contablemente infinito de variables:\(\Obj v_0\),\(\Obj v_1\),\(\Obj v_2\),...
-
-
Símbolos no lógicos, que constituyen el lenguaje estándar de la lógica de primer orden
-
Un conjunto contablemente infinito de símbolos de predicado\(n\) -place para cada\(n>0\):\(\Obj A^n_0\),\(\Obj A^n_1\),\(\Obj A^n_2\),...
-
Un conjunto contablemente infinito de símbolos constantes:\(\Obj c_0\),\(\Obj c_1\),\(\Obj c_2\),...
-
Un conjunto contablemente infinito de símbolos de función\(n\) -place para cada\(n>0\):\(\Obj f^n_0\),\(\Obj f^n_1\),\(\Obj f^n_2\),...
-
-
Signos de puntuación: (,), y la coma.
La mayoría de nuestras definiciones y resultados se formularán para el lenguaje estándar completo de la lógica de primer orden. Sin embargo, dependiendo de la aplicación, también podemos restringir el lenguaje a solo unos pocos símbolos predicados, símbolos constantes y símbolos de función.
Ejemplo\(\PageIndex{1}\)
El lenguaje\(\Lang L_A\) de la aritmética contiene un solo símbolo de predicado de dos posiciones\(<\), un solo símbolo de constante\(\Obj 0\), un símbolo\(\prime\) de función de un solo lugar y dos símbolos de función de dos posiciones\(+\) y \(\times\).
Ejemplo\(\PageIndex{2}\)
El lenguaje de la teoría de conjuntos\(\Lang L_Z\) contiene solo el símbolo de predicado de dos lugares\(\in\).
Ejemplo\(\PageIndex{3}\)
El lenguaje de las órdenes\(\Lang L_\le\) contiene sólo el símbolo predicado de dos lugares\(\le\).
Nuevamente, estas son convenciones: oficialmente, estos son solo alias, por ejemplo\(<\),\(\in\),, y\(\le\) son alias para\(\Obj A^2_0\),\(\Obj 0\) para\(\Obj c_0\),\(\prime\) para\(\Obj f^1_0\), \(+\)para\(\Obj f^2_0\),\(\times\) para\(\Obj f^2_1\).
Además de los conectivos primitivos y cuantificadores introducidos anteriormente, también utilizamos los siguientes símbolos definidos:\(\liff\) (biconditional), truth \(\ltrue\).
Un símbolo definido no forma parte oficialmente del lenguaje, sino que se introduce como una abreviatura informal: nos permite abreviar fórmulas que, si solo usáramos símbolos primitivos, se alargarían bastante. Esto es obviamente una ventaja. La mayor ventaja, sin embargo, es que las pruebas se vuelven más cortas. Si un símbolo es primitivo, tiene que ser tratado por separado en pruebas. Los símbolos más primitivos, por lo tanto, más largas son nuestras pruebas.
Es posible que esté familiarizado con terminología y símbolos diferentes a los que usamos anteriormente. Los textos de lógica (y los maestros) comúnmente usan cualquiera\(\sim\),\(\neg\), y! por “negación”,\(\wedge\),\(\cdot\), y\(\&\) para “conjunción”. Los símbolos comúnmente utilizados para el “condicional” o “implicación” son\(\rightarrow\),\(\Rightarrow\), y\(\supset\). Los símbolos para “bicondicional”, “bi-implicación” o “equivalencia (material)” son\(\leftrightarrow\), \(\Leftrightarrow\), and \(\equiv\).\(\lfalse\) symbol is variously called “falsity,” “falsum,” “absurdity,” or “bottom.” El\(\ltrue\) symbol is variously called “truth,” “verum,” or “top.”
Es convencional usar letras minúsculas (por ejemplo,,\(a\)\(b\),\(c\)) desde el principio del alfabeto latino para símbolos constantes (a veces llamados nombres), y letras minúsculas desde el final (por ejemplo,\(x\),\(y\), \(z\)) para variables. Los cuantificadores se combinan con variables, por ejemplo,\(x\); las variaciones notacionales incluyen\(\forall x\)\((\forall x)\)\((x)\),\(\Pi x\),,,\(\bigwedge_x\) para el cuantificador universal y\(\exists x\), \((\exists x)\),\((Ex)\),\(\Sigma x\),\(\bigvee_x\) para el cuantificador existencial.
Podríamos tratar a todos los operadores proposicionales y a ambos cuantificadores como símbolos primitivos del lenguaje. En su lugar, podríamos elegir un stock más pequeño de símbolos primitivos y tratar a los otros operadores lógicos como se definen. Los conjuntos de operadores booleanos “Truth funcionalmente completos” incluyen\(\{ \lnot, \lor \}\)\(\{ \lnot, \land \}\), y\(\{ \lnot, \lif\}\) —estos se pueden combinar con cualquier cuantificador para un lenguaje de primer orden expresivamente completo.
Quizás estés familiarizado con otros dos operadores lógicos: el trazo de Sheffer\(|\) (llamado así por Henry Sheffer), y la flecha de Peirce\(\downarrow\), también conocida como daga de Quine. Cuando se les dan sus lecturas habituales de “nand” y “nor” (respectivamente), estos operadores son verdad funcionalmente completos por sí mismos.