5.7: Variables libres y oraciones

Última actualización
Guardar como PDF

Page ID: 103690

$ \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

Definición$\PageIndex{1}$: Free occurrences of a variable

Las ocurrencias libres de una variable en una fórmula se definen inductivamente de la siguiente manera:

$\indcaseA{A}{$A$ is atomic}$todas las ocurrencias de variables en$\indfrm$ son libres.
$\indcase{A}{\lnot B}$las ocurrencias de variables libres de$\indfrm$ son exactamente las de$B$.
$\indcase{A}{(B \ast C)}$las ocurrencias variables libres de$\indfrm$ son las que están$B$ junto con las de$C$.
$\indcase{A}{\lforall{x}{B}}$las ocurrencias de variables libres en$\indfrm$ son todas aquellas en$B$ excepto las ocurrencias de$x$.
$\indcase{A}{\lexists{x}{B}}$las ocurrencias de variables libres en$\indfrm$ son todas aquellas en$B$ excepto las ocurrencias de$x$.

Definición$\PageIndex{2}$: Bound Variables

Una ocurrencia de una variable en una fórmula$A$ está ligada si no es libre.

Problema$\PageIndex{1}$

Dar una definición inductiva de las ocurrencias de variables enlazadas a lo largo de las líneas de Definición$\PageIndex{1}$.

Definición$\PageIndex{3}$: Scope

Si$\lforall{x}{B}$ es una ocurrencia de una subfórmula en una fórmula$A$, entonces la ocurrencia correspondiente de$B$ in$A$ se llama el alcance de la ocurrencia correspondiente de$\lforall{x}{}$. De manera similar para$\lexists{x}{}$.

Si$B$ es el alcance de una ocurrencia cuantificador$\lforall{x}{}$ o$\lexists{x}{}$ en$A$, entonces las ocurrencias libres de$x$ in$B$ están enlazadas en$\lforall{x}{B}$ y$\lexists{x}{B}$. Decimos que estas ocurrencias están ligadas por la ocurrencia cuantificadora mencionada.

Ejemplo$\PageIndex{1}$

Considera la siguiente fórmula:\[\lexists{\Obj v_0}{\underbrace{\Atom{\Obj A^2_0}{\Obj v_0,\Obj v_1}}_{B}}\nonumber\]$B$ representa el alcance de$\lexists{\Obj v_0}{}$. El cuantificador se une a la ocurrencia de$\Obj v_0$ in$B$, pero no se une a la ocurrencia de$\Obj v_1$. Así$\Obj v_1$ es una variable libre en este caso.

Ahora podemos ver cómo esto podría funcionar en una fórmula más complicada$A$:\[\lforall{\Obj v_0}{\underbrace{(\Atom{\Obj A^1_0}{\Obj v_0} \lif \Atom{\Obj A^2_0}{\Obj v_0, \Obj v_1})}_{B}} \lif \lexists{\Obj v_1}{\underbrace{(\Atom{\Obj A^2_1}{\Obj v_0, \Obj v_1} \lor \lforall{\Obj v_0}{\overbrace{\lnot \Atom{\Obj A^1_1}{\Obj v_0}}^{D}})}_{C}}\nonumber\]$B$ es el alcance de la primera$\lforall{\Obj v_0}{}$,$C$ es el alcance de$\lexists{\Obj v_1}{}$, y$D$ es el alcance de la segunda $\lforall{\Obj v_0}{}$. El primero$\lforall{\Obj v_0}{}$ se une a las ocurrencias de$\Obj v_0$ in$B$,$\lexists{\Obj v_1}{}$ la ocurrencia de$\Obj v_1$ in$C$, y el segundo$\lforall{\Obj v_0}{}$ se une a la ocurrencia de$\Obj v_0$ in $D$. La primera ocurrencia$\Obj v_1$ y la cuarta ocurrencia de$\Obj v_0$ son libres en$A$. La última ocurrencia de$\Obj v_0$ es libre en$D$, pero atado en$C$ y$A$.

Definición$\PageIndex{4}$: Sentence

Una fórmula$A$ es una oración iff que no contiene ocurrencias libres de variables.