Referencias

Cap´
ıtulo 1

Inducci´n y recursividad
o

1.1.

Proposiciones

´
Definicion 1 (Proposici´n)
o
Una proposici´n es una colecci´n de s´
o
o
ımbolos sint´cticos a la cual se le puede asiga
nar uno y solo un valor de verdad: verdadero (V) o falso (F). Las proposiciones,
generalmente se denotan con letras en may´scula.
u
Recordatorio
Sean P y Q dos proposiciones, las conectivasl´gicas conjunci´n (∧),
o
o
disyunci´n (∨), implicaci´n (⇒), y doble implicaci´n (⇔) generan nueo
o
o
vas proposiciones definidas cuyos valores de verdad se define a continuaci´n:
o
P

Q

P ∧Q

P

Q

P ∨Q

P

Q

P ⇒Q

P

Q

P ⇔Q

V
V
F
F

V
F
V
F

V
F
F
F

V
V
F
F

V
F
V
F

V
V
V
F

V
V
F
F

V
F
V
F

V
F
V
V

V
V
F
F

V
FV
F

V
F
F
V

´
Definicion 2 (Proposici´n abierta)
o
Una proposici´n abierta es una colecci´n de proposiciones indexadas a trav´s de uno
o
o
e
o varios par´metros. El conjunto m´s grande de posibles valores para los par´metros,
a
a
a
se denomina universo de discurso o dominio.
Ejemplo 1
Considere la proposici´n abierta:
o
Pn : n2 + 1 es un n´mero par. Donde n ∈ IN
u
noteque para diferentes valores de n la proposici´n Pn puede ser falsa o verdadera,
o
es importante entender que Pn no es una sola proposici´n, sino una familia de proo
posiciones. Donde P1 , P2 , P3 , etc, son miembros particulares de dicha familia. Para
1

2

1.2. Inducci´n matem´tica.
o
a

este caso, se puede observar que: P1 ≡ V , P2 ≡ F , P3 ≡ V , P4 ≡ F .
Demostraci´n de unaimplicaci´n
o
o
Demostrar P ⇒ Q consiste en demostrar que la proposici´n
o
P ⇒Q≡V
esto es que no es posible la combinaci´n P ≡ V y Q ≡ F .
o
Para demostrar P ⇒ Q se puede hacer de dos posibles formas:
Demostraci´n directa: Consiste en suponer que P ≡ V y demostrar
o
que bajo esa suposici´n se llega a concluir que Q ≡ V .
o
Demostraci´n por contradicci´n: Consiste en suponer verdadero
o
ola proposici´n: P ∧¬Q y demostrar que bajo dicha suposici´n, se puede
o
o
concluir una contradicci´n (Una proposici´n evidentemente falsa). De
o
o
esta manera, de donde se parti´ tiene que ser falso y como P no puede
o
ser falso, pues es la premisa o hip´tesis ¬Q tiene que serlo. As´ se tiene
o
ı
que P ⇒ Q ≡ V

1.2.

Inducci´n matem´tica.
o
a

La inducci´n matem´tica es unat´cnica de demostraci´n que se basa en el principio
o
a
e
o
del bueno orden, dicho principio se menciona a continuaci´n:
o

Principio del buen orden.
Todo subconjunto de los n´meros naturales posee primer elemento.
u

El m´todo de inducci´n matem´tica sirve para probar que una proposici´n abierta
e
o
a
o
es verdadera para todo n es su dominio, siempre que ´ste sea de la forma {p, p +e
1, p + 2, p + 3, . . .}, donde p ≥ 0. Para el caso de que el dominio sea IN se tiene que:
M´todo de inducci´n matem´tica.
e
o
a
Para demostrar (∀n ∈ IN)[Pn ] ≡ V . Basta probar que:
P0 ≡ V .
Pn ⇒ Pn+1 ≡ V .

Si el dominio no es IN se deber´ probar que Pp ≡ V , donde p es el primer elemento
a
del dominio, y posteriormente probar que Pn ⇒ Pn+1 ≡ V para n arbitrario. Posteriormente seconcluye que (∀n ∈ D)[Pn ] ≡ V , donde D = {p, p + 1, p + 2, p + 3, . . .}.

1. Inducci´n y recursividad
o

1.2.1.

3

¿Por qu´ funciona el m´todo de inducci´n matem´tica?
e
e
o
a

El objetivo de la t´cnica de inducci´n matem´tica, es poder garantizar que una
e
o
a
proposici´n abierta Pn es verdadera para todo n ∈ IN, n ≥ p. Por comodidad suponga
o
que p = 0.
Si se tieneque P0 ≡ V y Pn ⇒ Pn+1 ≡ V para todo n, entonces se puede hacer el
siguiente an´lisis:
a
P0 ≡ V
Para n = 0 se tiene que: P0 ⇒ P1 , por lo que P1 ≡ V
Para n = 1 se tiene que: P1 ⇒ P2 , por lo que P2 ≡ V
Para n = 2 se tiene que: P2 ⇒ P3 , por lo que P3 ≡ V
Para n = 3 se tiene que: P3 ⇒ P4 , por lo que P4 ≡ V
Para n = 4 se tiene que: P4 ⇒ P5 , por lo que P5 ≡ V
.
.≡.
.
.
.
por lo que...