Práctica 3: Cuantificadores (Algoritmos I)

Ejercicio 1

Determinar cuales de las variables que aparecen en las siguientes expresiones aparecen libres y cuales ligadas.

1. ($\forall x\in [0..n))x+y==z$
2. ($\forall x\in [0..n),y\in [0..m))x+y==z$
3. ($\forall j\in [0..|s|))s_{j}==0$
4. ($\forall j\in [0..|s|))s_{j}==x$
5. ($\exists x\in r,x\ mod\ 2==0)(\forall j\in [0..|s|))s_{j}==x$
6. $(|s|>5\land a<b-1\land (\forall j\in [a..b))2*s_{j}==s_{j+1})$

Respuestas: Recordemos que las variables ligadas son aquellas que son variables de selector y están al alcance del mismo.

1. x.
2. x e y.
3. j
4. j
5. x y j
6. j

Ejercicio 2

Escriba los siguientes predicados en lenguaje de especificación:

a) aux suc$(x:\mathbb {Z} ):\mathbb {Z}$, que corresponde al sucesor de x.

b) aux suma$(x,y:\mathbb {R} ):\mathbb {R}$, que corresponda a la suma entre x e y.

c) aux producto$(x,y:\mathbb {R} ):\mathbb {R}$, que corresponde al producto entre x e y.

d) aux cuadrado$(x:\mathbb {Z} )$: Bool, que sea verdadero sii x es un número cuadrado.

e) aux primo$(x:\mathbb {Z} )$: Bool, que sea verdadero sii x es primo.

f) aux coprimos$(x,y:\mathbb {Z} )$: Bool, que sea verdadero sii x e y son coprimos.

g) aux divisoresGrandes$(x,y:\mathbb {Z} )$: Bool, que sea verdadero sii todos los divisores de x, sin contar el uno, son mayores que y.

h) aux mayorPrimo$(x:\mathbb {Z} ):\mathbb {Z}$, que represente el mayor primo que divide a x.

i) aux mcm$(x,y:\mathbb {Z} ):\mathbb {Z}$, que represente el mínimo común múltiplo entre x e y.

j) aux mcd$(x,y:\mathbb {Z} ):\mathbb {Z}$, que represente el máximo común divisor entre x e y.

Respuestas:

a) aux suc $(x:\mathbb {Z} ):\mathbb {Z}$ = x + 1;

b) aux suma $(x,y:\mathbb {R} ):\mathbb {R}$ = x + y;

c) aux producto$(x,y:\mathbb {R} ):\mathbb {R}$ = x * y;

d) aux cuadrado$(x:\mathbb {Z} )$: Bool = (x $\geq$ 0 $\wedge$($\exists$ y $\leftarrow$ [0..x]) y*y == x);

e)aux primo$(x:\mathbb {Z} )$: Bool = |[ y | y $\leftarrow$[1..|x|], x mod y == 0]| == 2 (Recordemos que un número es primo si tiene exactamente dos divisores positivos: el 1 y su valor absoluto)

f) aux coprimos$(x,y:\mathbb {Z} )$: Bool == |[ z | z $\leftarrow$ [1..x], x mod z==0, y mod z == 0]| == 1 (Dos números son coprimos si tienen un único divisor positivo en común: el uno)

g) aux divisoresGrandes$(x,y:\mathbb {Z} )$: Bool = ($\forall$ z $\leftarrow$ [ t | t $\leftarrow$ [2..|x|], x mod t == 0]) z > y

h) aux mayorPrimo$(x:\mathbb {Z} ):\mathbb {Z}$ = $[y|y\leftarrow [0..|x|],primo(y),x\ mod\ y==0]_{|[y|y\leftarrow [0..|x|],\ primo(y),x\ mod\ y==0]|-1}$ otras formas: -utilizar un aux ultimo que sea algo asi como cabeza(invertir(l:[T]))

i) aux mcm$(x,y:\mathbb {Z} ):\mathbb {Z}$ = cab([ z | z $\leftarrow$ [0..|x*y|], z \ mod \ x == 0, z \ mod \ y == 0])

j) aux mcd$(x,y:\mathbb {Z} ):\mathbb {Z}$ = $[z|z\leftarrow [0..|x|],x\ mod\ z==0,y\ mod\ z==0]_{[z|z\leftarrow [0..|x|],x\ mod\ z==0,y\ mod\ z==0]-1}$

Ejercicio 3

Escriba las siguientes funciones auxiliares sobre secuencias de enteros, aclarando los tipos de los parámetros que recibe y devuelve:

1. capicua, que determina si una secuencia es capicúa. (Por ejemplo, [0,2,1,2,0] es capicúa y [0,2,1,4,0] no).

capicua(x: [T]): Bool = ($\forall$i $\leftarrow$ [0..|x|) ) $x_{i}==x_{|x|-i-1}$

2. esPrefijo, que determina si una secuencia es prefijo de otra.

esPrefijo(x,y: [T]): Bool = ($\exists$ i $\leftarrow$ [0..|y|-1]) x==[$y_{i}$| j $\leftarrow$ [0..i] ]

otra forma: (|b| > |a| $\wedge$ ($\forall i\leftarrow$ [0..|a|) ) $a_{i}==b_{i}$);

3. estaOrdenada, que determina si la secuencia está ordenada de menor a mayor.

estaOrdenada(x: [Int]): Bool = ($\forall$ i,j $\leftarrow$ [0..|x|-1], i<j) $x_{i}<x_{j}$

4. todosPrimos, que determina si todos los elementos de la secuencia son números primos.

todosPrimos(x: [$\mathbb {Z}$]): Bool = ($\forall$ t $\leftarrow$ x) primo(t)

(primos la definimos en el ejercicio 2.5)

5. todosIguales, que determina si todos los elementos de la secuencia son iguales.

todosIguales(x: [T]): Bool = ($\forall$ a, b $\leftarrow$ x) a==b

6. hayUnoParQueDivideAlResto, que determina si hay un elemento par en la secuencia que divide al resto.

hayUnoParQueDivideAlResto(x: [$\mathbb {Z}$]): Bool = ($\exists$ a $\leftarrow$ x, a mod 2 == 0) ($\forall$ b $\leftarrow$ x) b mod a == 0

7. hayUnoEnPosicionParQueDivideAlResto, que determina si hay un elemento en una posición par de la secuencia que divide al resto.

hayUnoEnPosicionParQueDivideAlResto(x: [$\mathbb {Z}$]): Bool =
($\exists$ i $\leftarrow$ [0..|x|-1], i mod 2 == 0)($\forall$ a $\leftarrow$ x) $amodx_{i}==0$

8. sinRepetidos, que determina si la secuencia no tiene repetidos.

sinRepetidos(x: [T]): Bool = ($\forall$ i,j $\leftarrow$ [0..|x|-1], i $\neq$j) $x_{i}\neq x_{j}$ otra forma: ($\forall$ i $\leftarrow$ [0..|x|-1]), $x_{i}\not \in x_{[0..i)})$ otra más: ($\forall$ e $\leftarrow$ x, cuenta(e, x) == 1)

9. sinMasDeNApariciones, que determina si en la secuencia, ningún elemento aparece más de n veces.

sinMasDeNApariciones(x: [T]): Bool = ($\forall$ a $\leftarrow$ x) | [ b | b $\leftarrow$ x, b==a ] | $\leq$ n

10. otroMayorADerecha, que determina si todo elemento de la secuencia, salvo el último, tiene otro mayor a su derecha.

otroMayorADerecha(x: [$\mathbb {Z}$]): Bool = ($\forall$ i $\leftarrow$ [0..|x|-2]) $x_{i}<x_{i+1}$

11. todoEsMultiplo, que determina si todo elemento de la secuencia es múltiplo de alg¶un otro.

todoEsMultiplo(x: [$\mathbb {Z}$]): Bool = ($\exists$ a $\leftarrow$ x)($\forall$ b $\leftarrow$ x) b mod a == 0

12. enTresPartes, que determina si en la secuencia aparecen (de izquierda a derecha) primero 0s, después 1s y por último 2s. Por ejemplo [0; 0; 1; 1; 1; 1; 2] cumple con enTresPartes, pero [0; 1; 3; 0] o [0; 0; 0; 1; 1] no. ¿Cómo modificaría la expresión para que se admitan cero apariciones de 0s, 1s y 2s (es decir, para que por ejemplo [0; 0; 0; 1; 1] o [ ] sí cumplan nTresPartes?

enTresPartes(x: [$\mathbb {Z} ]$): Bool = ( estaOrdenada(x) $\land x_{0}==0\ \land \ x_{|x|-1}==2\ \land \ 1\in x$ )

Pero si queremos que no sea estrictamente necesaria la pertenencia de al menos un 0, un 1 y un 2, podemos modificarlo de la siguiente manera:

enTresPartesPrima(x: [$\mathbb {Z} ]$): Bool = ( estaOrdenada(x) $\land (\forall$ a $\leftarrow$ x) $(0\geq a\ \land \ a\leq 2$ ) )

Ejercicio 4

1- "Todos los naturales menores a 10 que cumplen P, cumplen Q":

aux a: Bool ($\forall x\in$ [0..10)) ($P(x)\wedge Q(x)$)

Esta mal porque no queremos que para todos, todos cumplan P y Q, sino que cuando P sea verdadero, Q tambien lo sea:

aux a: Bool ($\forall x\in$ [0..10))($P(x)\Rightarrow Q(x)$)

2- "No hay ningún natural menor a 10 que cumpla P y Q":

aux c: Bool = $(\neg (\exists x\in [0..10)P(x)\wedge \neg (\exists x\in [0..10)Q(x))$

Pero esto diría que ninguno en s cumple P y ninguno en s cumple Q. En su lugar deberíamos poner:

aux c: Bool = $\neg (\exists x\in [0..10))P(x)\wedge Q(x)$;