Tema 2: Métodos de Demostración
Métodos de Demostración
Predicados
Predicado: Proposición que alude a elementos de un conjunto. Denotaremos por P(x) a un predicado que haga referencia a un objeto variable x. La misma álgebra de conectores que actúa sobre las proposiciones, actúa sobre los predicados.
Por ejemplo:
- P (n): n es un número entero.
- Q (m, n): m es divisible por n.
Podemos usar conectores para formar predicados nuevos. Por ejemplo:
- Ejemplo 1:
- ¬ P (n): n no es un número entero.
- P (n) ∧ Q (m, n): n es un número entero, y m es divisible por n.
- Q (m, 2) ∧ Q (m, 3) → Q (m, 6): Si m es divisible por 2, y m es divisible por 3, entonces m es divisible por 6.
- Q (2, 3): 2 es divisible por 3.
- Ejemplo 2:
- P (x): Al estudiante x le gusta el álgebra.
- ∀ xP (x): A todo estudiante le gusta el álgebra.
Cuantificadores
Son operadores que determinan a cuántos elementos de un conjunto hace referencia una proposición.
- Cuantificador universal: Para todo. Se escribe: ∀.
- Cuantificador existencial: Existe. Se escribe: ∃.
Por ejemplo:
- f (x) = sin^2(x)
- P (x): f (x) ≥ 0
- ∀ x P (x)
- Q (x): f (x) = 0
- ∃ x Q (x)
Por ejemplo, consideremos la función lineal f(x):
- P(x): f(x) > 0
- N(x): f(x) < 0
- C(x): f(x) = 0
- ∃ xP(x) ∧ yN(y) → ∃ zC(z)
Demostración
Definición: Argumento válido que establece la veracidad de una proposición matemática a partir de:
- Axiomas: Afirmaciones que se asumen como ciertas.
- Otras afirmaciones demostradas.
- Hipótesis adicionales.
Teorema (Bolzano)
- Sea \(f: [a, b] \mapsto \mathbb{R}\) una función continua. Supongamos que \(f(a)
\cdot f(b) < 0\). Entonces \(\exists x_0\in(a, b)\) tal que \(f(x) = 0\):
- H_1: Existe una función \(f\) definida en el intervalo cerrado [a, b]
- H_2: \(f(a) \cdot f(b) < 0\). ¿Qué significa?
- \(\(f(a) < 0 \wedge f(b) > 0\) \vee \(f(a) > 0 \wedge f(b) < 0\)\)
- H_3: \(f\) es continua
- T: La función \(f\) se anula en algún punto x_0.
Demostración Directa
La demostración por método directo demuestra que una condicional \(P \rightarrow Q\) asumiendo que P es cierta y utilizando reglas de inferencia hasta llegar a que Q también es cierta.
Por ejemplo: si n es par, n^2 también es par:
- \(P(n)\): es par
- \(Q(n)\): n^2 es par
- \(\forall n P(n) \rightarrow Q(n)\)
- Suponemos que \(P(n)\) es cierta: \(\exists k\) entero, tal que \(n = 2k\)
- \(n^2 = n \cdot n = 2k \cdot 2k = 2 \cdot (2 \cdot k^2) = 2k_2\)
- ¿\(Q(n)\)? Sí, k_2 es un número entero, tal que \(n^2 = 2k_2\)
Prueba Indirecta
Muestra que la condicional \(P \rightarrow Q\) es cierta, sin tomar P como hipótesis.
Contraposición
\(P \rightarrow Q\) es equivalente a \(\not Q \rightarrow \not P\). Podemos tomar \(\not Q\) como hipótesis y demostrar que \(\not P\) es cierta.
Por ejemplo:
- \(\not Q(n): n^2\) impar, \(\not P(n): n\) impar
- \(n^2 = (2k + 1)\)
- \(n = \frac{2k + 1}{n}\)
- Como \(n\) es un número entero, \(2k + 1\) es divisible por \(n\). Un número impar nunca es divisible por 2. Nunca es divisible por un número par. \(n\) divide a \(2k + 1\) es impar.
Reducción al Absurdo
Asumir que \(\not P\) es verdadero. Al demostrar \(\not P \rightarrow Q\) llegamos a una contradicción.
- \(\not P\): Not existen enteros tal que: \(2x + 4y = 1\)
- \(\not P\): Existen enteros tales que: \(2x + 4y = 1\)
- Dividimos ambos lados por 2: \(x + 2y = \frac{1}{2}\)
- Si \(x\), \(y\) son enteros \(x + 2y\) es un entero
- \(Q(x)\): \(\frac{1}{2}\) es un entero (afirmación falsa)
- \(\not P\) es falsa. P es cierta.
Contraejemplo
Demostrar que \(\forall x P(x)\) es falsa, demostrando \(\exists x P(x)\) es falsa.
Inducción
Técnica para demostrar proposiciones sobre un conjunto de números naturales: \(\forall n \in \mathbb{N}: P(n)\).
Consta de dos pasos:
- Paso base: Se demuestra \(P(n)\) para un número natural, por ejemplo, \(P(1)\)
- Paso inductivo: Se desmuestra \(\forall k \in \mathbb{N} \rightarrow P(k + 1)\). Se supone que \(P(k)\) es cierta, y se demuestra \(P(k + 1)\).
Por ejemplo: La suma de los primeros \(n\) números naturales. Demostramos que:
\(1 + 2 + 3 + \cdots + n = \frac{n (n + 1)}{2}\)
- Paso base: \(P(1)\) es trivial
- Paso inductivo: Suponemos que \(P(k)\) es cierto. Demostremos \(P(k + 1)\):
- \(1 + 2 + 3 + \cdots + k + (k + 1) = \frac{k (k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2}\)
Principio de Buena Organización: Toda colección de números naturales posee un elemento mínimo.
Recursión
En ocasiones es dificil (tal vez imposible) definir un objeto de forma explícita. Podemos usar la misma idea que en la inducción.
- Paso base: Especificar un valor (o valores) iniciales.
- Paso recursivo: Especificar una regla para encontrar el objeto etiquetado por un entero grande. Se calcula a partir de valores menores.
Por ejemplo: Definimos una sucesión de números enteros llamada \(\{F_k\}k\): \(\{F_k\}_k = \{F_1, F_2, F_3, \cdots, \}\)
- Paso base: \(F_1 = 1\), \(F_2 = 1\)
- Paso recursivo: \(F_k = F_{k - 1} + F_{k - 2}\)
