Matematica Discreta

[pic 1][pic 2][pic 3][pic 4]

Contenido

Práctico 5:        2

Ejercicio 1 (completo):        2

Ejercicio 4 (parte a, b):        3

Práctico 6:        4

Ejercicio 1 (parte e):        4

Ejercicio 2 (parte d):        5

Ejercicio 4 (parte b):        5

Practico 7:        7

Ejercicio 3 (parte d, e, f):        7

Ejercicio 5 (parte e):        8

Ejercicio 6 (parte d):        9

Práctico 5:

Ejercicio 1 (completo):

Considere la siguiente estructura M con tipo de similaridad < 1, 2; 2, 2, 1; 3 >:
M = < N ; Par, Mayor ; Sum, Prod, Cuad ; 0,1,2 >
- N es el conjunto de los números naturales.
- Par = { x ∈N | x es múltiplo de 2 } es la relación “ser par”.
- Mayor = { (x,y) ∈ NxN | x > y } es la relación “mayor”.
- Sum : NxN → N / Sum (x,y) = x + y es la función suma de naturales.
- Prod : NxN → N / Prod (x,y) = x * y es la función producto de naturales.
- Cuad : N → N / Cuad (x) = x2 es la función cuadrado de un número natural.

Se define el siguiente alfabeto de símbolos para el tipo de similaridad presentado:

- Símbolos de Relación: P (unario), M (binario).
- Símbolos de Función: s (binario), p (binario), c (unario).
- Símbolos de Constante: c1, c2, c3.

Utilizando solamente los símbolos presentados, traduzca a fórmulas bien formadas de FORM las siguientes afirmaciones sobre el universo de discurso dado por la estructura M.

a) Existe algún natural que no es par.
b) No todos los naturales son pares.
c) No hay ningún natural que sea par e impar a la vez.
d) Hay por lo menos dos naturales tales que su suma es mayor que cero.
e) Cualquier natural mayor que cero cumple que su cuadrado también lo es.
f) La suma de dos naturales pares también es par.
g) Existen dos naturales tales que su suma es mayor que su producto.
h) Si el cuadrado de un natural cualquiera es par y mayor que cero, entonces el natural
también es par y mayor que cero.

(Respuesta)

a) ∃x (¬ P(x))

b) ¬ (∀x (P(x)))

c) ¬ (∃x (P(x) ∧ ¬P(x) ))

d) ∃x∃y( M(s(x, y), c1)) (siendo c1 = 0)

e) ∀x(M(x, c1) → M(c(x), c1)) (siendo c1 = 0)

f) ∀x∀y(P(x) ∧ P(y) → P(s(x, y)))

g) ∃x∃y( M(s(x, y), p(x, y)))

h) ∀x( P(c(x)) ∧ M(c(x), c1)) → (P(x) ∧ M(x, c1))) (siendo c1 = 0)

Ejercicio 4 (parte a, b):

Considere la siguiente estructura M con tipo de similaridad < 1, 1, 2; – ; 3 >:
M = < Z* ; Positivo, Negativo, Mayor ; – ; 1,2,3 > donde:
- Z* es el conjunto de los números enteros excluido el cero.
- Positivo = { x ∈ Z* | x > 0 } es la relación “ser positivo”.
- Negativo = { x ∈ Z* | x < 0 } es la relación “ser negativo”.
- Mayor = { (x,y) ∈ Z*x Z* | x > y } es la relación “mayor”.

Se define el siguiente alfabeto de símbolos para el tipo de similaridad presentado:

- Símbolos de Relación: P (unario), N (unario), M (binario).
- Símbolos de Constante: c1, c2, c3.

Demuestre o refute cada una de las siguientes afirmaciones, justificando su respuesta en todos los casos en forma detallada:

a) M |=∀x (P(x) → M(x, c2))                                        Afirmación INCORRECTA
b) M |=∀x∃yM(y,x)                                                Afirmación CORRECTA

(Respuesta)

a)

M |=∀x (P(x) → M(x, c2))                                        ssi (por def. de modelo)

vM(∀x (P(x) → M(x, c2)))=1                                        ssi (por def. valuación caso ∀)

Para todo a ∈ Z*/ vM(P(a) → M(a, c2))=1                        ssi (por def. valuación caso →)

Para todo a ∈ Z*/ 1− vM (P(a))=1 ∨ vM(M(a, c2))=1                ssi (por def. valuación caso base)

• 1− vM (P(a))=1 → vM (P(a))=0
• vM(M(a, c2))=1

Para todo a ∈ Z*, (a no es positivo) ∨ (a > 2 (c2=2)).

Esto no es cierto para todo elemento del conjunto Z*, y como contraejemplo tomemos el valor a=1. El valor 1 ∈ Z* y es positivo, pero no es mayor a 2.

b)

M |=∀x∃yM(y,x)                                                ssi (por def. de modelo)

vM(∀x∃yM(y,x))=1                                                ssi (por def. valuación ∀)

Para todo a ∈ Z* / vM(∃yM(y,a))=1                                ssi (por def. valuación ∃)

Para todo a ∈ Z*, ∃ b ∈ Z* /vM(M(b,a))=1                        ssi (por def. caso base)

Para todo a ∈ Z*, ∃ b ∈ Z* / b > a.

Esto es cierto para cualquier elemento del conjunto Z*.

Práctico 6:

Ejercicio 1 (parte e):

Considere el tipo de similaridad < 1, 2; 1 ; 2 > con símbolos de relación P (unario) y R (binario), símbolo de función f (unario) y símbolos de constante c1, c2. Construya derivaciones que demuestren las siguientes consecuencias sintácticas. Justifique cuando corresponda que las restricciones sobre las variables se cumplen al aplicar las reglas:

...