Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2001

Práctica 1

Fecha sugerida de finalización: 5/4/2001

Primera Parte: Lógica Proposicional

Alfabeto

•       Variables proposicionales: p, q, r, s, ...

•       Conectivos lógicos: Ø (negación), Ù (conjunción), ú (disyunción), Þ (implicación), º (equivalencia).

•       Símbolos auxiliares: ( (paréntesis abierto), ) (paréntesis cerrado).

Expresión

Lista finita de símbolos del alfabeto.

Expresiones bien formadas

Una expresión a es una expresión bien formada, a la que podemos llamar también fórmula bien formada o fórmula, si se cumple que:

•       a es una variable proposicional; o

•       a es de la forma Øb, y b es una fórmula; o

•       a es de la forma (b Ù g), o de la forma (b ú g), o de la forma (b Þ g), o de la forma (b º g), y b y g son fórmulas.

Ejercicio 1

Utilizando las definiciones anteriores: ¿Cuáles de la siguientes expresiones son fórmulas? (p, q son variables proposicionales)

i.                     Øp

ii.                    Ø(p)

iii.                  (Øp)

iv.                  p ú q

v.                   p ú q)

vi.                  (p ú q)

vii.                Øp Ù

viii.               Øp Ù q

ix.                   (Øp Ù q)

x.                    p q

xi.                   (p Û q)

xii.                 p + q

Convenciones de notación

Las convenciones de notación son reglas que se utilizan, simplemente, por una cuestión de comodidad. Ellas son:

•       No es necesario escribir paréntesis exteriores. Ejemplo: escribir p Þ (q Þ r) en lugar de (p Þ (q Þ r)).

•       Sea * el conectivo para la disyunción, conjunción o implicación. La expresión a₁ * a₂ * ... * a_n representa la fórmula (a₁ * (a₂ * (... * a_n))).

Precedencias

Teniendo en cuenta que el orden de precedencias entre los símbolos es:

Ø (negación)

Ù (conjunción) ú (disyunción)

Þ (implicación)

º (equivalencia)

se pueden omitir paréntesis cuando no haya ambigüedades.

Ejemplos:

•       p Þ q Ù r representa (p Þ (q Ù r))

•       p Þ q º r representa ((p Þ q) º r)

•       p ú q Ù r no representa una fórmula porque no hay precedencia entre Ù y ú. En este caso se presenta una ambigüedad.

Ejercicio 2

¿Cuáles de las expresiones del ejercicio 1 son fórmulas teniendo en cuenta las convenciones de notación?

Valuación

Una valuación es una asignación de valores de verdad a las variables proposicionales. La podemos ver como una función que recibe un nombre de variable y devuelve un valor de verdad. Una vez fijada una valuación, se puede determinar el valor de verdad de una fórmula aplicando las tablas de verdad de los conectivos.

Ejercicio 3

Dada una valuación m tal que m(a), m(b) y m(c) son verdaderas, y m(x) y m(y) son falsas, determinar el valor de verdad de las siguientes proposiciones para dicha valuación:

i.                     Øa ú b

ii.                    (c ú y) Ù (x ú b)

iii.                  c ú (y Ù x) ú b

iv.                  (c ú y) Ù (x ú b) º c ú (y Ù x) ú b

v.                   Ø(c ú y)

vi.                  Øc Ù Øy

vii.                Ø (c ú y) º Øc Ù Øy

Tautología

Una fórmula b es una tautología si y sólo si b es verdadera para toda posible asignación de valores de verdad a las variables proposicionales que aparecen en b.

Contradicción

Una fórmula b es una contradicción si y sólo si b es falsa para toda posible asignación de valores de verdad a las variables proposicionales que aparecen en b.

Contingencia

Una fórmula b es una contingencia si y sólo si b no es una tautología ni una contradicción, es decir, su valor de verdad depende de los valores de verdad que tomen sus variables proposicionales.

Ejercicio 4

Determinar, utilizando tablas de verdad, si las siguientes fórmulas son tautologías, contradicciones o contin­gen­cias.

i.                     Øp

ii.                    p ú Øp

iii.                  p Ù Øp

iv.                  p Þ p

v.                   Øp ú q º p Þ q

vi.                  p Ù q Þ p

vii.                p ú q Þ p

viii.               (p Þ (q Þ r)) Þ ((p Þ q) Þ (p Þ r))

Simplificación

Introduciremos dos símbolos, F y T, que representan una fórmula que es una contradicción y una fórmula que es una tautología, respectivamente. En la bibliografía también se los puede encontrar como 0 y 1.

La equivalencia entre fórmulas puede verse como una regla de simplificación de fórmulas. Por ejemplo, la fórmula (p ú F) Ù (p ú Øp), sabiendo que (p ú F) º p y que (p ú Øp) º T, es equivalente a p Ù T, que finalmente es equivalente a p. Luego, (p ú F) Ù (p ú Øp) º p.

En realidad, cualquier tautología de la forma b º g puede utilizarse como regla de simplificación, teniendo en cuenta que se busca obtener, en algún sentido, fórmulas más simples. Una fórmula con menos símbolos puede considerarse más simple, pero también una fórmula con menos conectivos lógicos puede considerarse más simple.

Reglas útiles de simplificación

•       p Ù F º F F es absorbente para Ù

•       p Ù T º p Identidad de Ù

•       p ú F º p Identidad de ú

•       p ú T º T T es absorbente para ú

•       p Ù p º p Idempotencia para Ù

•       p ú p º p Idempotencia para ú

•       p ú Øp º T Tautología

•       p Ù Øp º F Ley de contradicción

•       Ø Ø p º p Ley de doble negación

•       p Ù q º q Ù p Conmutatividad de Ù

•       p ú q º q ú p Conmutatividad de ú

•       r Ù (p ú q) º (r Ù p) ú (r Ù q) Distributividad

•       r ú (p Ù q) º (r ú p) Ù (r ú q) Distributividad

•       Ø(p Ù q) º Øp ú Øq Ley de De Morgan

•       Ø(p ú q) º Øp Ù Øq Ley de De Morgan

•       p Þ q º Øp ú q Equivalencia del Þ

Ejercicio 5

Simplificar las siguientes fórmulas. Puede suceder que para reducir algunas expresiones sea necesario utilizar una tautología del tipo b º g que no figure entre las reglas de simplificación propuestas. En ese caso, la validez de la tautología debe ser probada mediante tablas de verdad.

i.                     p Ù p Ù p Ù p Ù p Ù p Ù p Ù p Ù p

ii.                    (p Ù (Øp ú q )) ú q ú (p Ù (p ú q))

iii.                  Øp Þ Ø(p Þ Øq)

iv.                  Ø ((Ø (p Ù q ) ú p ú q) Þ (ØØp ú Øp))

v.                   ((p Þ q) Ù (p Ù Øq)) Þ q

Relación de Fuerza

Dadas las proposiciones lógicas b y g, se dice que b es más fuerte que g si y sólo si b Þ g es una tautología. También decimos que g es más débil que b. Entonces, dos fórmulas pueden ser equivalentes, una más fuerte que la otra o no comparables (si ni b Þ g ni g Þ b son tautologías).

Ejercicio 6

Determinar la relación de fuerza de los siguientes pares de fórmulas:

i.                     T, F

ii.                    T, T

iii.                  F, F

iv.                  p, q

v.                   p Ù q, p ú q

vi.                  p, p Ù q

vii.                p, p ú q

viii.               p, p Þ q

¿Cuál es la proposición más fuerte y cuál la más débil de las que aparecen en este ejercicio?

Equivalencia entre conectivos

Decimos que un conectivo es expresable mediantre otros si es posible escribir una fórmula utilizando exclusiva­mente estos últimos y que tenga la misma tabla de verdad que el primero. Por ejemplo, la conjunción es expresable mediante la disyunción mas la negación, ya que la siguiente equivalencia es una tautología:

p Ù q º Ø(Øp ú Øq)

Ejercicio 7

i.                     Mostrar que la la disyunción es expresable mediante la conjunción más la negación.

ii.                    Mostrar que la implicación es expresable mediante la conjunción más la negación.

Los símbolos ï y ¯

Los símbolos ï (barra de Sheffer) y ¯ (barra de Nicod) son dos conectivos lógicos, también conocidos como NAND y NOR, respectivamente. Tienen las siguientes tablas de verdad:

Ejercicio 8

i.                     Mostrar que la negación es expresable mediante el símbolo ï y la negación. Mostrar la equivalencia usando tablas de verdad.

ii.                    Mostrar que la conjunción es expresable mediante el símbolo ï y la negación. Mostrar la equivalencia usando tablas de verdad.

iii.                  Del mismo modo, mostrar que la negación y la disyunción son expresables mediante el símbolo ¯. Mostrar las equivalencias usando tablas de verdad.

iv.                  ¿Podría utilizarse solamente el símbolo ï como reemplazo de los otros conectivos lógicos ? ¿Y solamente el símbolo ¯?

Ejercicio 9

Siendo a, b y g fórmulas, escribir una fórmula que sea verdadera cuando:

i.                     Al menos una es verdadera.

ii.                    Ninguna es verdadera.

iii.                  Todas son verdaderas.

iv.                  Exactamente una de las tres es verdadera.

v.                   No todas al mismo tiempo son verdaderas.

vi.                  a es verdadera.

Segunda Parte: Lógica de Predicados

Alfabeto

•       Variables: x₁, x₂, x₃, ...

•       Constantes: c₁, c₂, c₃, ...

•       Funciones: F₁, F₂, F₃, ...

•       Predicados: P₁, P₂, P₃, ...

•       Conectivos lógicos: Ø (negación), Ù (conjunción), ú (disyunción), Þ (implicación), º (equivalencia).

•       Cuantificadores: " (universal) y $ (existencial).

•       Símbolos auxiliares: ( (paréntesis abierto), ) (paréntesis cerrado).

Las variables van a poder tomar cualquier valor de un universo de elementos U. Las constantes representarán algunos elementos de U.

Por ejemplo, si tomamos como universo el conjunto de los números naturales, las variables podrían tomar el valor de cualquier natural y cada constante representaría un natural particular. Las funciones representarían la suma, la resta, el producto, el máximo común divisor, etc., y el hecho de llamarle funciones no nos obliga a usar la notación suma(x₁, x₂) sino que podemos escribir x₁ + x₂ y hablar del símbolo funcional + de aridad dos. Los predicados podrían ser Par(x₁), Menor(x₁, x₂), Divisor (x₁, x₂). Notar que cada función y cada predicado tiene asociado una aridad.

Términos

•       Las variables son términos.

•       Las constantes son términos.

•       Si F_i es un símbolo de función n-ario y t₁, t₂, t₃,..., t_n son términos, entonces F_i(t₁, t₂, t₃,..., t_n) es un término.

Ejemplos

Son términos: x₁, 3, 3 + x₁, MCM(8, 12) + 3.

("MCM" es el mínimo común múltiplo entre dos números.)

No son términos: Par(x₁), Mayor(3, x), Coprimos(MCM(8, 12), 3).

Fórmulas atómicas

•       Si P_i es un símbolo de predicado n-ario y t₁, t₂, t₃,..., t_n son términos entonces P_i(t₁, t₂, t₃,..., t_n) es una fórmula atómica.

Ejemplos

Son fórmulas atómicas: Par(x₁), Primo(3), Primo(3 + x₁), Menor(mcd(8, 12) + 3, 8).

("mcd" es el máximo común divisor entre dos números.)

No son fórmulas atómicas: x₁, 3 + x₁, mcd(8, 12).

Fórmulas

a es una fórmula bien formada, o simplemente fórmula, si se cumple que:

•       es una fórmula atómica; o

•       es de la forma Øb y b es una fórmula bien formada; o

•       es de la forma (b Ù g) o de la forma (b ú g) o de la forma (b Þ g) o de la forma (b º g) y se cumple que b y g son fórmulas; o

•       es de la forma ("x₁) b o ($x₁) b, y b es una fórmula bien formada.

Ejemplos

Son fórmulas bien formadas: Par(x₁), (Primo(3) Þ Par(x₁)), (ØPar(x₁) ú Primo(1 + x₁)),

("x₁) Menor(mcd(8, 12) + 3, x₁), ("x₁) (Par(x₁) Þ Par(x₁+1)).

Ejercicio 10

[ATENCION: Este ejercicio es más importante de lo que parece.]

¿Cuáles de la siguientes expresiones son fórmulas?

i.                     Ø3

ii.                    Ø(Par(3))

iii.                  Ø(Par(3)

iv.                  3 + x₁ ú Impar(3)

v.                   Impar(3) ú Par(3)

vi.                  (Menor(x₁ * 5, 8)ú Impar(3))

vii.                "x₁

viii.               ("x₁) Menor(x₁ * 5, 8)

ix.                   ("x₁) (Menor(x_1­, 3) Þ Par Ù Primo(x₁))

x.                    ("x₁) (Menor(x₁ * 5, 8) ú ("x₂) Impar(3))

xi.                   "x₁ (Menor(x₁ * 5, 8) ú ("x₂) Impar(3))

xii.                 ("x₁) ("x₂) Divisor(x₂, x₂ * x₁)

xiii.                ("x₁) ("x₂) x₁ < x₂

xiv.               ("x₁) ("x₂) x₁ < 3

xv.                 ("x₁) x₁ < 3 ú ("x₂) x₂ < 3

xvi.               Par(Primo(x₁))

Convenciones de notación

La cuestión es más compleja que en el cálculo proposicional, ya que intervienen también las convenciones de notación del dominio sobre el que estamos trabajando.

Tomemos como ejemplo el universo de los números naturales. Cuando escribimos términos en dicho universo usamos normalmente convenciones de notación y escribimos 3 + 4 + 1, y entendemos que hay que resolver primero un + y luego el otro. Aceptaremos las convenciones comunes para expresiones entre naturales.

De la misma manera, cuando escribimos fórmulas atómicas en ese universo usamos normalmente convenciones de notación y escribimos 3 + 4 < 1 y entendemos que hay que resolver primero el + y luego el <. Aceptaremos también las convenciones comunes para predicados sobre naturales.

Sí nos interesa aplicar convenciones a la escritura de fórmulas:

•       No es necesario escribir paréntesis exteriores. Ejemplo: escribir b Þ (g Þ a) en lugar de (b Þ (g Þ a)).

•       Sea * el conectivo para la disyunción, conjunción o implicación. La expresión a₁ * a₂ * ... * a_n representa la fórmula (a₁ * (a₂ * (... * a_n))).

Precedencias

Teniendo en cuenta que el orden de precedencias entre los símbolos es:

" (Cuantificador universal) y $ (Cuantificador existencial)

Ø (negación)

Ù (conjunción) ú (disyunción)

Þ (implicación)

º (equivalencia)

se pueden omitir paréntesis cuando no haya ambigüedades. Ejemplos:

•       ("x₁) a Þ b Ù g representa (("x₁) a Þ (b Ù g))

•       a Þ b º g representa ((a Þ b) º g)

•       a ú b Ù g no representa una fórmula porque no hay precedencia entre Ù, ú.

Ejercicio 11

¿Cuáles de las expresiones del ejercicio 10 son fórmulas teniendo en cuenta las convenciones de notación?

Ejercicio 12

i.                     Escribir el predicado Suma(x₁, x₂, x₃), que verifica si x₃ es la suma entre x₁ y x₂.

ii.                    Escribir el predicado Divide_a(x₁, x₂), que verifica si x₁ divide a x₂.

iii.                  Escribir el predicado Primo(x₁), que verifica si x₁ es primo.

iv.                  Escribir el predicado MayorPrimo(x₁, x₂), que verifica si x₁ es el mayor primo que divide a x₂.

v.                   Escribir el predicado Coprimos(x₁, x₂), que verifica si x₁ y x₂ son coprimos.

vi.                  Escribir el predicado MCM(x₁, x₂, x₃), que verifica si x₃ es el MCM entre x₁ y x₂.

Tautología (generalización)

Una fórmula b es una tautología si y sólo si b es verdadera para toda posible valuación de las variables libres que aparecen en b.

Contradicción (generalización)

Una fórmula b es una contradicción si y sólo si b es falsa para toda posible valuación de las variables libres que aparecen en b.

Ejercicio 13

Dar la relación de fuerzas entre A y B en los siguientes casos:

i.                     A º ("x) ( P(x) Ù Q(x) )

B º ("x) ( P(x) Þ Q(x) )

ii.                    A º ($x) P(x) Ù ($y) Q(y)
B º ($x) (P(x) Ù Q(x))

iii.                  A º ("x) P(x) ú ("y) Q(y)
B º ("x) (P(x) ú Q(x))

iv.                  A º ("x) ( P(x) Ù ($y) Q(y) )

B º ($x) ( P(x) Ù ("y) (Q(y))

Ejercicio 14

Las siguientes fórmulas pueden ser verdaderas o falsas. Determinarlo y explicar.

i.                     ("x₁) ($x₂) x₁ < x₂

ii.                    ("x₁) ($x₂) x₁ > x₂

iii.                  ("x₁) ("x₂) x₁ < x₂

iv.                  ("x₁) ("x₂) x₁ > x₂

v.                   ("x₁) ("x₂) (x₁ > x₂ ú x₁ < x₂ ú x₁ = x₂)

vi.                  ("x₁) ("x₂) ($x₃) x₁ * x₃ > x₂

Ejercicio 15

a)                   En las siguientes expresiones indicar cuáles de las apariciones de x, y, y z son ligadas y cuáles son libres:

i.                     Par(x)

ii.                    ("y) Par(x)

iii.                  ("x) Par(x)

iv.                  Par(y) ú ($y) Par(y)

v.                   ($x) Par(x) Þ Par(x)

vi.                  Par(x) Þ ("x) Par(x)

vii.                Divide_a(x, y)

viii.               ("x) ("y) Divide_a(x, y)

ix.                   ("x) ($y) Divide_a(x, y)

x.                     ("z) (Par(z) Þ ($x) (Par(x) Ù Divide_a(x, z)))

xi.                   ("z) (Par(z) Þ ($x) (Par(x) Ù Divide_a(x, y)))

b) Usando la lógica de predicados sobre los naturales y dada la valuación m definida por m(x) = 2, m(y) = 3,
m(z) = 5, aplicar m y calcular el valor de verdad de las fórmulas del punto a).

(El predicado Par(x) es verdadero cuando x es par; el predicado Divide_a(x, y) es verdadero cuando x es un divisor de y.)

Ejercicio 16

Decidir si son verdaderas o falsas las siguientes fórmulas para la valuación m, siendo m(x_i) = 2 * i.

i.                     ("x₁) ($x₂) x₁=x₂

ii.                    ($x) (x ¹ x₁ Ù x ¹ x₃ Ù (x₃ + x₁) = x)

iii.                  x₁ + 1 = x₁ + x₂

iv.                  (x₁ = 5) ï (x₀ = x₁ - 2 ¯ Par(x₁))

Ejercicio 17

Determinar cuáles de los siguientes esquemas de fórmulas son tautologías:

i.                     b Þ ("x₁) b (sabiendo que x₁ no aparece en b)

ii.                    b Þ ("x₁) b (sabiendo que x₁ aparece libre en b)

iii.                  b Þ ($x₁) b (sabiendo que x₁ no aparece en b)

iv.                  b Þ ($x₁) b (sabiendo que x₁ aparece libre en b)

v.                   ("x₁) b Þ ($x₁) b

Ejercicio 18

Utilizando el universo de personas, y asumiendo el predicado Padre(x, y) que significa que x es la madre o el padre de y, definir los siguientes predicados:

i.                     Hermano(x, y)

ii.                    Hijo(x, y)

iii.                  Nieto(x, y)

iv.                  Abuelo(x, y)

v.                   Primo(x, y)

Ejercicio 19

Expresar en lógica de predicados los siguientes enunciados:

i.                     Para todo natural existe un natural mayor que él.

ii.                    Para cualquier natural hay algún natural igual a él.

iii.                  El predicado Raíz_Cuadrada(x, y), que es verdadero cuando x es la raíz cuadrada de y.

iv.                  Para cualquier natural siempre es posible encontrar un primo mayor.

v.                   El predicado Mayor(a, b), que es verdadero cuando a es mayor que b.

vi.                  El predicado Contenido_en(x, a, b), que es verdadero cuando x está entre a y b y es distinto de ambos.

vii.                El predicado Dígito(x), que es verdadero cuando x es un dígito.

viii.               El predicado Dígito_Par(x), que es verdadero cuando x es un dígito par.

ix.                   El predicado Múltiplo_de(x, y), que es verdadero cuando x es un múltiplo de y.

Ejercicio 20

Dados los predicados Real, Natural, Entero, Múltiplo, >, <, =, con los siguientes significados: Real(x), "x es un número real"; Natural(x), "x es un número natural"; Entero(x), "x es un número entero"; Múltiplo_de(x, y), "x es múltiplo de y"; x > y, "x es mayor que y"; x < y, "x es menor que y"; x = y, "x es igual a y"; traducir a lógica de predicados los siguientes enunciados:

i.                     Todo número natural es real.

ii.                    Algún número real es natural.

iii.                  Algún entero no es natural.

iv.                  El 1,2 no es natural.

v.                   El cero es entero.

vi.                  p no es entero.

vii.                Si un número es múltiplo de 4, también es múltiplo de 2.

viii.               Un número mayor que 4 es mayor que 0.

ix.                   El cuadrado de cualquier número es mayor o igual a cero.

x.                    Cualquier número x tal que su cuadrado es mayor que cero, es distinto de cero.

Conjuntos

En los ejercicios siguientes vamos a trabajar con conjuntos de naturales. Las variables en mayúsculas (X, Y, Z) se utilizarán para conjuntos y las variables en minúsculas (r, s, t) para naturales.

Ejercicio 21

Utilizando el predicado Î, que devuelve verdadero cuando un natural pertenece a un conjunto, escribir predicados para:

i.                     Vacío(X), que es verdadero cuando X no tiene elementos.

ii.                    Unión(X, Y, Z), que es verdadero cuando Z es la unión entre X e Y.

iii.                  Diferencia(X, Y, Z), que es verdadero cuando Z es la diferencia entre X e Y.

iv.                  Diferencia_Simétrica(X, Y, Z), que es verdadero cuando Z es la diferencia simétrica entre X e Y.

v.                   Contiene(X, Y), que es verdadero cuando X contiene a Y.

vi.                  Intersección(X, Y, Z), que es verdadero cuando Z es la intersección entre X e Y.

vii.                Algún_Divisor(r, X), que es verdadero cuando algún divisor de r está en X.

viii.               Divisores(r, X), que es verdadero cuando todos los divisores de r están en X.

ix.                   Mayor_Divisor(r, X), que es verdadero cuando el mayor divisor propio de r está en X. (Se dice que n es un divisor propio de m sii n es divide a m y n es distinto de m.)

Listas

En los ejercicios siguientes vamos a trabajar con listas de naturales. Las listas son sucesiones finitas de elementos. Cada elemento tiene una posición asignada en la lista. Debido a está propiedad en las listas pueden coexistir elementos con el mismo valor ya que su posición en la misma será diferente.

Notación de Listas

Las variables que representan listas van a ser las letras mayúsculas (L, M, etc.). Una lista tiene asociada una longitud, que es la cantidad de elementos. Por ejemplo, si la lista L es 1,3,5,2, su longitud será long(L) = 4. Para referirnos a un elemento en particular dentro de una lista, vamos a escribir el nombre de la lista seguido de una expresión numérica entre corchetes, cuyo valor va a estar entre 0 y la longitud de la lista menos uno, contando los elementos de izquierda a derecha. Por ejemplo, en la lista L anterior , L[0] = 1, L[1] = 3, etc. Para evitar indefiniciones, la expresión numérica debe estar obligatoriamente entre 0 y la longitud de la lista menos uno.

Notar que con la definición previa, no tenemos medios para definir una lista por extensión (con una notación del estilo L=[4,6,2] ), sólo podemos describir la longitud de una lista L mediante long(L) y referirnos al i-ésimo elemento con L[ i ].

Ejercicio 22

Escribir los siguientes predicados

i.                     Pertenece(L, r), que es verdadero sólo cuando el elemento r pertenece a la lista L.

ii.                    Todos_Distintos(L), que es verdadero sólo cuando todos los elementos de la lista L son distintos.

iii.                  Todos_Iguales(L), que es verdadero sólo cuando todos los elementos de la lista L son iguales.

iv.                  Ordenada_Ascendentemente(L), que es verdadero sólo cuando los elementos de L están ordenados ascendentemente.

v.                   Mismos_Elementos(C, L), que es verdadero cuando la lista L tiene exactamente los mismos elementos que el conjunto C en algún orden, sin importar si aparecen repetidos o no.

Ejercicio 23

Escribir predicados para:

i.                     Menores(r, L), que es verdadero cuando exactamente todos los naturales menores que r están en la lista L.

ii.                    Rango(r, s, L), que es verdadero cuando exactamente todos los naturales de [r, s] están en la lista L.

iii.                  Cuadrados(r, L), que es verdadero cuando exactamente todos los cuadrados menores que r están en la lista L.

iv.                  Divisores_Comunes(r, s, L), que es verdadero cuando exactamente todos los divisores propios de r y s están en la lista L.

v.                   Primos_Menores(r, L), que es verdadero cuando exactamente todos los primos menores a r están en la lista L.

Ejercicios adicionales

Ejercicio A1

Mostrar que cualquier fórmula de la lógica proposicional que utilice los conectivos Ø (negación), Ù (conjunción), ú (disyunción), Þ (implicación), º (equivalencia) puede reescribirse utilizando sólo los conectivos Ø (negación), ú (disyunción).

Ejercicio A2

Dado el predicado Maximo(a, b, c), que es verdadero cuando c es el máximo entre a y b y falso en caso contrario, decidir si es verdadera la siguiente equivalencia. Justificar

Maximo(a, b, c) º ( b ³ a Ù c = b ) ú ( c = a )

Ejercicio A3

Expresar en lógica de predicados sobre naturales:

i.                     El predicado de aridad 1 tiene_dos_divisores(x), que sólo es verdadero cuando x tiene exactamente dos divisores.

ii.                    Un número primo elevado al cubo tiene exactamente dos divisores.

iii.                  Cualquier número con exactamente dos divisores no es primo.

iv.                  Si a un número se le suma uno, el resultado no tiene exactamente dos divisores.

v.                   Un número divisible por dos tiene exactamente dos divisores.

Ejercicio A4

Expresar en lógica de predicados sobre naturales:

i.                     El predicado de aridad 1 UnoDos(x) que sólo es verdadero cuando x es 1 o x es 2.

ii.                    Todos los números son 1 o 2 (usar el predicado UnoDos).

iii.                  El cuadrado de un número cualquiera verifica UnoDos si dicho número verifica UnoDos.

iv.                  Todos los números mayores que 2 no verifican UnoDos.

v.                   La suma de dos números cualesquiera que verifican UnoDos, no verifica UnoDos.

Ejercicio A5

Definimos la propiedad se puede reemplazar de la siguiente manera:

1)       Una variable x se puede reemplazar por z en un término t si z no aparece en t.

2)       Una variable x se puede reemplazar por z en una fórmula atómica P(t1, ...., tn) si x se puede reemplazar por z en t1, x se puede reemplazar por z en t2, . . . y x se puede reemplazar por z en tn.

3)       Una variable x se puede reemplazar por z en una fórmula de la forma Øa si x se puede reemplazar por z en a.

4)       Una variable x se puede reemplazar por z en una fórmula de la forma (a Ù b), o de la forma (a ú b), o de la forma (a Þ b), o de la forma (a º b) si x se puede reemplazar por z en a y x se puede reemplazar por z en b.

5)       Una variable x se puede reemplazar por z en una fórmula de la forma ("z) a, o de la forma ($z) a, si x no aparece en a.

6)       Una variable x se puede reemplazar por z en una fórmula de la forma ("x) a, o de la forma ($x) a, si z no aparece en a.

Determinar si x₁ se puede reemplazar por x₂ en las siguientes fórmulas. En cada caso indicar qué reglas se han aplicado:

i)                     x₂

ii)                   x₂ + x₁

iii)                  Par(x₁) Ù Par(x₂)

iv)                 ($x₂) x1 + x₂ = 3

v)                   ($x₁) x₁ = 3

Ejercicio A6

Dado el tipo Jugador de Futbol que cuenta con la funciones Goles, Infracciones y Partidos que reciben como parámetro un Jugador de Futbol y devuelven un natural que representa la cantidad de goles, infracciones que tuvo y partidos en los cuales jugó respectivamente, se pide definir los siguientes predicados:

a)       EsBuenJugador (x) que es verdadero si x hizo al menos 10 goles y tuvo menos de 5 infracciones y falso en caso contrario

b)       EsFigura(x) que es verdadero cuando x es el más goleador entre todos los "buenos jugadores" y falso en caso contrario

c)       Todos los jugadores que hicieron goles y jugaron más de 2 partidos, cometieron alguna infracción

d)       Algún jugador tiene un promedio de al menos un gol por partido

Nota: En los items c y d, dar un nombre a los predicados.

Ejercicio A7

Sabiendo que el predicado Multiplo(x, y) º ($k) (x = y * k) decidir el valor de verdad del predicado Multiplo (x, y) para las siguientes valuaciones. Justificar

	X	Y	K
u1	1	0	2
u2	0	2	1
u3	2	1	0

Nota: interpretar la tabla como u₁(x)=1, ..