Unidad 2 Mates Discretas

http://cesimo.ing.ula.ve

A
i

Universidad de Los Andes

1/40

Unidad 2: MAtematicas discretas


LO ´ GI C

< >

Centro de Simulaci´n y Modelos (CESIMO) o

UL

A

?

P


L´gica U2 (v1.0) 2 o

A
A diferencia de las otras unidades, en esta tocamos mas de un tema separable: 1. Inducci´n matem´tica: Deducci´n en matem´ticas. o a o a 2. Nociones elementales de latises yalgebras y su relaci´n con las estructuras o de “significados” en l´gica. o 3. Elementos de la teor´ de grafos en l´gica. ıa o

2/40

LO ´ GI C

< >

UL

A

i P

?

A
i

Inducci´n matem´tica o a

3/40

El m´todo de inducci´n matem´tica se aplica cuando: e o a 1. sabemos la respuesta al principio.

2. sabemos c´mo determinar la respuesta en una etapa a partir de larespuesta o en la etapa anterior, y 3. tenemos una expectativa (una idea) de la respuesta general.
< >

UL

A

LO ´ GI C

?

P

J. D´vila < jacinto@ula.ve > a

L´gica U2 (v1.0) 4 o

Versi´n elemental del principio de inducci´n matem´tica o o a
Consideremos una lista p(1), p(2), ... de proposiciones con ´ ındices en P. Todas estas proposiciones son ciertas si: • B) p(1).

A

4/40• I) (∀N ∈ P)(p(N + 1) ← p(N ))

Observe que el principio de inducci´n NO es una prueba de que p(N) sea cierta o para toda N. El principio dice que si B) e I) son verdaderas, entonces las p(N) lo son. Precisamente la deducci´n que todas las p(N) son ciertas es lo que uno obtiene al o aplicar el principio.

LO ´ GI C

< >

UL

A

i P

?

J. D´vila < jacinto@ula.ve > a

L´gica U2(v1.0) 5 o

El principio de inducci´n matem´tica es deductivo!! o a
p(1) ∀N (p(N + 1) ← p(N )) ∀N (p(N ))

A

5/40

Esta conclusi´n es deducida, no inducida!!. o

As´ termina una demostraci´n por el principio de inducci´n matem´tica: ı o o a ... entonces p(N+1) es verdadera siempre que p(N) lo sea. As´ que, por el ı principio de inducci´n matem´tica podemos concluir p(N) es verdadera parao a toda N.

LO ´ GI C

< >

UL

A

i P

?

J. D´vila < jacinto@ula.ve > a

L´gica U2 (v1.0) 6 o

Primer forma del principio de inducci´n matem´tica o a
(B) p(m)

A

6/40

(I) (∀N ≥ m)(p(N + 1) ← p(N )) (∀N ≥ m)(p(N ))

Segunda forma del principio de inducci´n matem´tica o a
< >

(B) p(m), ..., p(m + l)

(∀N ≥ m)(p(N ))

UL

A

(I) (∀N ≥ m)(p(N ) ← p(m) ∧... ∧ p(N − 1))

LO ´ GI C

i P

?

J. D´vila < jacinto@ula.ve > a

L´gica U2 (v1.0) 7 o

Principio del buen orden

A
i

7/40

Principio del buen orden: todo subconjunto no vac´ de los naturales N ıo tiene elemento m´ ınimo. Esta propiedad no es una consecuencia de las reglas aritm´ticas de N. e El principio del buen orden implica que:

Dado m ∈ Z, todo subconjunto no vac´ de{n ∈ Z : n ≥ m} tiene elemento ıo m´ ınimo. El principio del buen orden es usado para probar la validez de los principios de inducci´n matem´tica. o a

LO ´ GI C

< >

UL

A

?

P

Un ejemplo de inducci´n matem´tica o a
Teorema LM2-1: Todo n´mero entero mayor o igual que 2 (N ≥ 2) puede u escribirse como el producto de otros numeros primos. Prueba: Sea p(N) la proposici´n: “N es elproducto de primos”. o B) Dado que el 2 es primo tenemos p(2) (puesto que 2 = 2 ∗ 1). I) Veamos que ocurre con N > 2. Supongamos que p(K) es cierto para todo K mayor o igual que 2 y menor que N. Con esta suposici´n tratemos de probar que o p(N) es verdadero. Si N es primo, p(N) es directamente cierta de la misma forma que B). Si N no es primo, se le puede escribir como el producto de dos n´meros,J y W, u mayores que 1. Pero esto implica que J y W son ambos mayores o iguales que 2 y estrictamente menores que N. Es decir que, en virtud de la suposici´n que o hicimos en esta parte, ambos son productos de primos. Pero entonces, N que es igual a J*W, es tambi´n producto de primos (Fin de la e prueba).
< >

A

8/40

UL

A

LO ´ GI C

i P

?

A

Conjuntos parcialmente...