Practica matematica discreta y logica 2

Matem´tica Discreta y L´gica 2 a o Pr´ctico 2 a 1) Escribir alfabetos para los lenguajes de los tipos dados en el ejercicio 1). 2) Escribir cinco t´rminos de los lenguajes que pertenecen al ejercicio1, partes e 3) y 7). Escribir cuatro f´rmulas at´micas del lenguaje 7) del ejercicio 1) y tres o o ´tomos cerrados del ejercicio 1 parte 3). a 3) Escribir un alfabeto para lenguajes de tipos (3; 1,1, 2; 0) (−; 2; 0) y (1; −; 3) 4) Demostrar el principio de inducci´n para F ORM . o 5) Considere el conjunto N de los n´meros naturales. u 1. definalo inductivamente 2. enuncie el principio deinducci´n primitiva para N o 3. demuestre el principio de inducci´n primitiva definido en la parte anterior o

6) Considere el conjunto T de los naturales potencia de 2. 1. definalo inducivamente 2. enuncie elprincipio de inducci´n primitiva para T o 3. demuestre el principio de inducci´n primitiva definido en la parte anterior o

7) Definir por recursi´n en TERM la funci´n nro f unciones(t) que cuenta lao o cantidad de funciones que aparecen en un t´rmino t. e 8) Definir por recursi´n en FORM la funci´n nro conectivos(φ) que cuenta la o o cantidad de conectivos que aparecen en una f´rmula φ. o 9)Definir por recursi´n en FORM la funci´n nro f orall(φ) que cuenta la cano o tidad de conectivos ∀ que aparecen en una f´rmula φ. o 10) Demostrar por inducci´n en T ERM que nro f unciones(t) ≥ 0 para todo ot.

1

11) Demostrar por inducci´n en F ORM que nro f orall(φ) ≤ nro conectivos(φ). o

12) Determine F V (t) para los siguientes t´rminos t: e 1. t = x0 2. t = f (x1 , x2 ) 3. t = f (y, y) 4.t = f (g(x2 , y), x1 )

13) Determine F V (φ) para las siguientes f´rmulas φ: o 1. x0 = x2 2. f (x2 ) = x1 3. ∀x(x > 0) 4. (∀x∃y(x < y)) ∧ (z < x) 5. ∃x(¬(x = y) ∧ P (x, x))

14) Chequear quet´rminos est´n libres en los siguientes casos y lleve adelante e a la sustituci´n: o 1. x para x en x = x 2. y para x en x = x 3. x + y para y en z = 0 4. 0 + y para y en ∃x(y = x) 5. x + y para z en...