Lógica de predicados

Considere los símbolos de función $a^{(0)}$, $b^{(0)}$, $f^{(1)}$ y $g^{(2)}$; y los de predicado $P^{(1)}$, $R^{(2)}$ y $Q^{(3)}$ ¿Son fórmulas de la lógica de predicados?

• $Q(a)$
•        No
• $P(y)$
•        Sí
• $Q(x,P(a),b)$
•        No
• $\neg R(x,a)$
•        Sí

Considere los símbolos de función $a^{(0)}$, $b^{(0)}$, $f^{(1)}$ y $g^{(2)}$; y los de predicado $P^{(1)}$, $R^{(2)}$ y $Q^{(3)}$ ¿Son fórmulas de la lógica de predicados?

• $R\big(a,g(a,f(a))\big)$
•        Sí
• $\forall x\ \neg P(x)$
•        Sí
• $\exists a\ R(a,a)$
•        No
• $\forall R(x,a)$
•        No

Considere los símbolos de función $a^{(0)}$, $b^{(0)}$, $f^{(1)}$ y $g^{(2)}$; y los de predicado $P^{(1)}$, $R^{(2)}$ y $Q^{(3)}$ ¿Son fórmulas de la lógica de predicados?

• $\exists x\ \big(Q(x,f(x),b)\rightarrow\forall x\ R(a,x)\big)$
•        Sí
• $a\rightarrow P(b)$
•        No
• $R(x,b)\vee\neg\exists y\ g(y,b)$
•        No
• $\forall x\exists y\big(R(x,y)\rightarrow R(y,x)\big)$
•        Sí

Esquemas típicos en lógica de predicados

La fórmula $\forall x (\varphi\rightarrow\psi)$ es típica en lógica de predicados porque expresa una propiedad para aquellos individuos que satisfacen cierta condición. Para aquellos que no la satisfacen, la implicación se sigue cumpliendo tengan o no la propiedad.

La fórmula $\exists x (\varphi\land\psi)$ también es típica ya que hace referencia a un objeto particular que cumple con dos propiedades a la vez.

La fórmula $\exists x (\varphi\rightarrow\psi)$ se satisface si hay un objeto que no cumple $\varphi$. Si todos cumplen $\varphi$, podríamos optar por la fórmula de arriba con el cuantificador universal. Así, $\exists x (\varphi\rightarrow\psi)$ es raro que aparezca.

Traduzca las oraciones siguientes a la lógica de predicados.

1. Todo(a) hijo(a) de mi padre es mi hermano(a).
2. Todos tienen una madre.
3. Alguien es madre de todos.
4. Cualquier persona que tenga una madre tiene un padre.
5. Ninguna abuela es el padre de todo el mundo.
6. Pablo es el cuñado de Amélie.

El vocabulario a emplear es:

Las funciones $i^{(0)}$, $a^{(0)}$ y $p^{(0)}$ representan a la primera persona del singular, a Amélie y a Pablo, respectivamente. Los predicados son:

$$\begin{array}{rl} F(x,y): & x \text{ es padre de } y\\ M(x,y): & x \text{ es madre de } y\\ H(x,y): & x \text{ es el cónyuge de } y\\ S(x,y): & x \text{ es la hermana de } y\\ B(x,y): & x \text{ es el hermano de } y \end{array}$$

Todo(a) hijo(a) de mi padre es mi hermano(a).   $f^{(1)}$ representa a la función padre.

• $\forall x\big(F(f(i),x)\rightarrow B(x,i)\vee S(x,i)\big)$

Las funciones $i^{(0)}$, $a^{(0)}$ y $p^{(0)}$ representan a la primera persona del singular, a Amélie y a Pablo, respectivamente. Los predicados son:

$$\begin{array}{rl} F(x,y): & x \text{ es padre de } y\\ M(x,y): & x \text{ es madre de } y\\ H(x,y): & x \text{ es el cónyuge de } y\\ S(x,y): & x \text{ es la hermana de } y\\ B(x,y): & x \text{ es el hermano de } y \end{array}$$

Las funciones $i^{(0)}$, $a^{(0)}$ y $p^{(0)}$ representan a la primera persona del singular, a Amélie y a Pablo, respectivamente. Los predicados son:

$$\begin{array}{rl} F(x,y): & x \text{ es padre de } y\\ M(x,y): & x \text{ es madre de } y\\ H(x,y): & x \text{ es el cónyuge de } y\\ S(x,y): & x \text{ es la hermana de } y\\ B(x,y): & x \text{ es el hermano de } y \end{array}$$

Cualquier persona que tenga una madre tiene un padre.

• $\forall x\big(\exists y M(y,x)\rightarrow \exists z F(z,x)\big)$

Las funciones $i^{(0)}$, $a^{(0)}$ y $p^{(0)}$ representan a la primera persona del singular, a Amélie y a Pablo, respectivamente. Los predicados son:

$$\begin{array}{rl} F(x,y): & x \text{ es padre de } y\\ M(x,y): & x \text{ es madre de } y\\ H(x,y): & x \text{ es el cónyuge de } y\\ S(x,y): & x \text{ es la hermana de } y\\ B(x,y): & x \text{ es el hermano de } y \end{array}$$

Ninguna abuela es el padre de todo el mundo.   $f^{(1)}$ y $m^{(1)}$ representan a las funciones padre y madre, respectivamente.

• $\forall x\Big(\neg\forall w\big(F(m(m(x)),w)\big) \land \neg\forall w\big(F(m(f(x)),w)\big) \Big)$

Las funciones $i^{(0)}$, $a^{(0)}$ y $p^{(0)}$ representan a la primera persona del singular, a Amélie y a Pablo, respectivamente. Los predicados son:

$$\begin{array}{rl} F(x,y): & x \text{ es padre de } y\\ M(x,y): & x \text{ es madre de } y\\ H(x,y): & x \text{ es el cónyuge de } y\\ S(x,y): & x \text{ es la hermana de } y\\ B(x,y): & x \text{ es el hermano de } y \end{array}$$

Pablo es el cuñado de Amélie.

• $\exists x\big(S(x,a)\wedge H(p,x)\big)\vee \exists y\big(H(y,a)\wedge B(p,y)\big)$

¿Cuál es la formalización más adecuada para la oración Todas las mujeres son rockeras, con la posible excepción de Adela, dado el diccionario  $a$: Adela,  $M(x)$: $x$ es mujer,  y $D(x)$: $x$ es rockera?

a) $\forall x(M(x) \rightarrow D(x))\wedge \neg D(a)$

b) $\forall x(M(x) \wedge a\neq x \rightarrow D(x))$

c) $\forall x(D(x)\rightarrow M(x) \wedge \,a\neq x)\wedge \neg D(a)$

d) $\forall x((M(x) \wedge a\neq x) \equiv D(x))$

e) $\forall x(D(x) \rightarrow M(x) \wedge a\neq x)$

¿Cuál es la formalización más adecuada para la oración: Todas las mujeres son rockeras, con la posible excepción de Adela, dado el diccionario  $a$: Adela,  $M(x)$: $x$ es mujer,  y $D(x)$: $x$ es rockera?

a) $\forall x(M(x) \rightarrow D(x))\wedge \neg D(a)$⇦¡¡Se tiene $D(a)$ y $\neg D(a)$!!

b) $\forall x(M(x) \wedge a\neq x \rightarrow D(x))$⇦ Respuesta

c) $\forall x(D(x)\rightarrow M(x) \wedge \,a\neq x)\wedge \neg D(a)$

d) $\forall x((M(x) \wedge a\neq x) \equiv D(x))$

e) $\forall x(D(x) \rightarrow M(x) \wedge a\neq x)$

La formalización para Todas las mujeres son rockeras, con la certera excepción de Adela, es la siguiente

$$\forall x(M(x) \wedge a\neq x \rightarrow D(x))\wedge\neg D(a)$$

Variables libres y ligadas

Una presencia de $x$ en $\varphi$ es libre si es un nodo hoja del árbol de análisis sintáctico de $\varphi$ tal que no hay trayectoria ascendente de ese nodo $x$ a un nodo $\forall x$ o $\exists x$. De otro modo, esa presencia de $x$ está ligada.

El alcance de $\forall x$ en $\forall x \varphi$ es $\varphi$ —a excepción de cualquier subfórmula de $\varphi$ que esté cuantificando a $x$ por su cuenta propia. Análogamente se define el alcance de $\exists x$ en $\exists x \varphi$.

Árbol de análisis sintáctico de
$\forall x\ \big(\neg\forall yQ(x,y)\land R(x,y)\big)$

¿Cuáles variables son
ligadas y cuáles libres?

Árbol de análisis sintáctico de
$\forall x\ \big(Q(x,f(x),y)\rightarrow\exists x\ R(z,x)\big)$

¿Cuáles variables son
ligadas y cuáles libres?

Predicados para tipos

La oración Existe un entero que es más pequeño que cualquier natural se traduce como $\exists x\forall y\,(x<y)$; sin embargo, se prefiere

$$\exists x\,\big(Int(x)\wedge \forall y\,(Nat(y)\rightarrow x<y)\big)$$

Introducimos abreviaturas para ahorrarnos algunos conectivos:

$$\begin{array}{c} \forall x:\mathsf{A}.P(x) \text{ significa } \forall x\,(A(x)\rightarrow P(x)), \\[0.65em] \exists x:\mathsf{A}.P(x) \text{ significa } \exists x\,(A(x)\wedge P(x)). \end{array}$$

La traducción anterior se expresa como $\exists x:\mathsf{Int}\ \forall y:\mathsf{Nat}\, (x<y)$.

Usando la notación para tipos y el vocabulario en la siguiente diapositiva, especifique en lógica de predicados los enunciados que aparecen a continuación:

1. Hay un libro más extenso que "El Quijote de la Mancha"
2. "La construcción lógica del mundo" está escrito por un filósofo y no es más extenso que "Alicia en el país de las maravillas"
3. Si "Alicia en el país de las maravillas" está escrito por un matemático, entonces está escrito por un filósofo
4. No es el caso que todo libro está escrito por un filósofo.
5. Hay alguien que es filósofo y matemático y ha escrito un libro más extenso que "Alicia en el país de las maravillas"

$$\begin{array}{rl} L(x,y): & x \text{ es más extenso que }y\\ E(x,y): & x \text{ está escrito por }y\\ M(x): & x \text{ es matemático}\\ F(x): & x \text{ es filósofo}\\ B(x): & x \text{ es un libro}\\ q: & \text{``El Quijote de la Mancha''}\\ c: & \text{``La construcción lógica del mundo''}\\ a: & \text{``Alicia en el país de las maravillas''} \end{array}$$

Hay un libro más extenso que "El Quijote de la Mancha"

• $\exists x:\mathsf{B}.L(x,q)$

$$\begin{array}{rl} L(x,y): & x \text{ es más extenso que }y\\ E(x,y): & x \text{ está escrito por }y\\ M(x): & x \text{ es matemático}\\ F(x): & x \text{ es filósofo}\\ B(x): & x \text{ es un libro}\\ q: & \text{``El Quijote de la Mancha''}\\ c: & \text{``La construcción lógica del mundo''}\\ a: & \text{``Alicia en el país de las maravillas''} \end{array}$$

"La construcción lógica del mundo" está escrito por un filósofo y no es más extenso que "Alicia en el país de las maravillas"

• $\big(\exists x:\mathsf{F}.E(c,x)\big)\wedge\neg L(c,a)$

$$\begin{array}{rl} L(x,y): & x \text{ es más extenso que }y\\ E(x,y): & x \text{ está escrito por }y\\ M(x): & x \text{ es matemático}\\ F(x): & x \text{ es filósofo}\\ B(x): & x \text{ es un libro}\\ q: & \text{``El Quijote de la Mancha''}\\ c: & \text{``La construcción lógica del mundo''}\\ a: & \text{``Alicia en el país de las maravillas''} \end{array}$$

Si "Alicia en el país de las maravillas" está escrito por un matemático, entonces está escrito por un filósofo

• $\big(\exists x:\mathsf{M}.E(a,x)\big)\rightarrow\big(\exists y:\mathsf{F}.E(a,y)\big)$

$$\begin{array}{rl} L(x,y): & x \text{ es más extenso que }y\\ E(x,y): & x \text{ está escrito por }y\\ M(x): & x \text{ es matemático}\\ F(x): & x \text{ es filósofo}\\ B(x): & x \text{ es un libro}\\ q: & \text{``El Quijote de la Mancha''}\\ c: & \text{``La construcción lógica del mundo''}\\ a: & \text{``Alicia en el país de las maravillas''} \end{array}$$

No es el caso que todo libro está escrito por un filósofo.

• $\neg\forall x:\mathsf{B}.\exists y:\mathsf{F}.E(x,y)$

No es el caso que todo libro está escrito por un filósofo, se puede expresar de forma equivalente como:

• Hay un libro que no está escrito por un filósofo.

$$\exists x:\mathsf{B}.\neg \exists y:\mathsf{F}. E(x,y)$$

• Hay un libro que los filósofos no escribieron.

$$\exists x:\mathsf{B}. \forall y:\mathsf{F}. \neg E(x,y)$$

$$\begin{array}{rl} L(x,y): & x \text{ es más extenso que }y\\ E(x,y): & x \text{ está escrito por }y\\ M(x): & x \text{ es matemático}\\ F(x): & x \text{ es filósofo}\\ B(x): & x \text{ es un libro}\\ q: & \text{``El Quijote de la Mancha''}\\ c: & \text{``La construcción lógica del mundo''}\\ a: & \text{``Alicia en el país de las maravillas''} \end{array}$$

Hay alguien que es filósofo y matemático y ha escrito un libro más extenso que "Alicia en el país de las maravillas"

• $\exists x\big(F(x)\wedge M(x)\wedge\exists y:\mathsf{B}. (E(y,x)\wedge L(y,a))\big)$

Especificación de listas

Dado un tipo de datos $A$ se define el tipo de datos de listas con elementos de $A$ ($L_A$) como sigue:

• La lista vacía, $nil$, es un miembro de $L_A$.
• Si $a$ es un elemento de $A$ y $\ell$ es una lista de $L_A$, entonces $a:\ell$ es un miembro de $L_A$.
• Son todos.

Especificación de listas

Consideraremos a $nil$ constante para la lista vacía; $\ :^{(2)}$ función que construye una lista; y los símbolos de predicado $A^{(1)}$ y $L_A^{(1)}$ que denotan el tipo $A$ y listas $L_A$. La formalización es la siguiente:

• $L_A(nil)$,
• $\forall x:\mathsf{A}.\forall \ell:\mathsf{L_A}.\ L_A(x:\ell)$.

Especificación de listas

Realice la especificación formal de las siguientes propiedades de las relaciones concatenación y reversa :

1. La operación de concatenación es asociativa.
2. Si la concatenación de dos listas es vacía, entonces ambas listas son vacías.
3. Si la concatenación de dos listas es una lista unitaria, entonces una de tales listas es vacía y la otra es la misma lista unitaria.
4. La reversa de la reversa de una lista es la misma lista.

Especificación de listas

$$nil^{(0)} \text{ y } :^{(2)}$$

$$A(x): x \in A \qquad L_A(\ell) : \ell\in L_A$$

$$C(x,y,z): z \text{ es la concatenación de $x$ y $y$}$$

1. La operación de concatenación es asociativa.

• $\forall \ell:\mathsf{L_A}.\forall m:\mathsf{L_A}.\forall n:\mathsf{L_A}\forall u:\mathsf{L_A}.\forall v:\mathsf{L_A}.\forall w:\mathsf{L_A}\ \big(C(\ell,m,u)\wedge C(u,n,\pmb{v})\wedge C(m,n,w)\rightarrow C(\ell,w,\pmb{v})\big)$

Especificación de listas

$$nil^{(0)} \text{ y } :^{(2)}$$

$$A(x): x \in A \qquad L_A(\ell) : \ell\in L_A$$

$$C(x,y,z): z \text{ es la concatenación de $x$ y $y$}$$

2. Si la concatenación de dos listas es vacía, entonces ambas listas son vacías.

• $\forall \ell:\mathsf{L_A}.\forall m:\mathsf{L_A}.\ \big(C(\ell,m,nil) \rightarrow \ell=nil \wedge m=nil\big)$.

Especificación de listas

$$nil^{(0)} \text{ y } :^{(2)}$$

$$A(x): x \in A \qquad L_A(\ell) : \ell\in L_A$$

$$C(x,y,z): z \text{ es la concatenación de $x$ y $y$}$$

3. Si la concatenación de dos listas es una lista unitaria, entonces una de tales listas es vacía y la otra es la misma lista unitaria.

• $\forall \ell:\mathsf{L_A}.\forall m:\mathsf{L_A}.\forall x:\mathsf{A}\ \big(C(\ell,m,x:nil) \rightarrow (\ell=x:nil\wedge m=nil) \vee (\ell=nil\wedge m=x:nil)\big)$.

Especificación de listas

$$nil^{(0)} \text{ y } :^{(2)}$$

$$A(x): x \in A \qquad L_A(\ell) : \ell\in L_A$$

$$R(x,y): y \text{ es la reversa de $x$}$$

4. La reversa de la reversa de una lista es la misma lista.

• $\forall \ell:\mathsf{L_A}.\forall \ell':\mathsf{L_A}.\ \big(R(\ell,\ell')\rightarrow R(\ell',\ell)\big)$

• Hasta cierto punto se codifican estas propiedades en Prolog.