Ejercicios 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í

¿Cuál es la formalización más adecuada para la oración Todas la 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 la 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 la 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)$$

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.

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)$.

$$\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 cualquier libro es escrito por un filósofo.

• $\neg\forall x:\mathsf{B}.\exists y:\mathsf{F}.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

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