5.15: Resumen

Última actualización
Guardar como PDF

Page ID: 103696

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Template:MathJaxZach

Un lenguaje de primer orden consiste en símbolos constantes, de función y predicados. Los símbolos de función y constante toman un número específico de argumentos. En el lenguaje de la aritmética, por ejemplo, tenemos un solo símbolo de constante\(\Obj 0\), un símbolo de función de 1 lugar\(\prime\), dos símbolos de función de 2 lugares\(+\) y\(\times\), y un símbolo de predicado de 2 lugares\(<\). A partir de variables y símbolos constantes y de función formamos los términos de un lenguaje. A partir de los términos de un lenguaje junto con su símbolo predicado, así como el símbolo de identidad\(\eq[][]\), formamos las fórmulas atómicas. Y a su vez a partir de ellos, usando las conectivas lógicas\(\lnot\)\(\lor\),\(\land\),\(\lif\),,\(\liff\) y los cuantificadores\(\lforall{}{}\) y\(\lexists{}{}\) formamos sus fórmulas. Dado que tenemos cuidado de incluir siempre los paréntesis necesarios en el proceso de formación de términos y fórmulas, siempre hay exactamente una manera de leer una fórmula. Esto permite definir las cosas por inducción sobre la estructura de las fórmulas.

Las ocurrencias de variables en fórmulas a veces se rigen por un cuantificador correspondiente: si una variable ocurre en el alcance de un cuantificador se considera vinculada, de lo contrario libre. Todos estos conceptos tienen definiciones inductivas, y también definimos inductivamente la operación de sustitución de un término por una variable en una fórmula. Las fórmulas sin ocurrencias de variables libres se llaman oraciones.

La semántica para un lenguaje de primer orden viene dada por una estructura para ese lenguaje. Consiste en un dominio y se asignan elementos de ese dominio a cada símbolo constante. Los símbolos de función son interpretados por funciones y símbolos de relación por relación en el dominio. Una función del conjunto de variables al dominio es una asignación de variables. La relación de satisfacción relaciona estructuras, asignaciones variables y fórmulas;\(\Sat[,s]{M}{A}\) se define por inducción sobre la estructura de\(A\). \(\Sat[,s]{M}{A}\)sólo depende de la interpretación de los símbolos que realmente ocurren en\(A\), y en particular no depende de\(s\) si no\(A\) contiene variables libres. Entonces si\(A\) es una oración,\(\Sat{M}{A}\) si\(\Sat[,s]{M}{A}\) para alguna (o para todas)\(s\).

La relación de satisfacción es la base de todas las nociones semánticas. Una oración es válida,\(\Sat{ {} }{A}\), si se satisface en cada estructura. Una sentencia\(A\) está implicada por conjunto de oraciones\(\Gamma\),\(\Gamma \Entails A\), iff\(\Sat{M}{A}\) para todos los\(\Struct{M}\) que satisfacen cada oración en\(\Gamma\). Un conjunto\(\Gamma\) es satisfacible si hay alguna estructura que satisfaga cada oración en\(\Gamma\), por lo demás insatisfactorio. Estas nociones están interrelacionadas, por ejemplo,\(\Gamma \Entails A\) iff\(\Gamma \cup \{\lnot A\}\) es insatisfactorio.