Lógica y técnicas de demostración

Para qué sirve esto

Hasta ahora has calculado: resolver ecuaciones, derivar, integrar. Pero las matemáticas de verdad consisten en demostrar: probar que algo es cierto siempre, sin excepción. ¿Cómo sabemos que hay infinitos números primos? Por más que pruebes ejemplos nunca lo verás; se demuestra.

La lógica te da:

El lenguaje preciso ("si… entonces", "para todo", "existe").
Las reglas para razonar sin errores.
Un poder de análisis que sirve para programar, argumentar y detectar falacias en la vida diaria.

No necesitas más que sentido común y los capítulos anteriores como fuente de ejemplos (conjuntos en N0, números primos, pares e impares…).

Proposiciones y conectivos

Una proposición es una afirmación que es verdadera (V) o falsa (F), y no ambas: " $7$ es primo" (V), " $2 + 2 = 5$ " (F). ("¿Qué hora es?" no lo es.)

Se combinan con conectivos:

Conectivo	Símbolo	Se lee	Es verdadera si…
Negación	$\neg p$	"no $p$ "	$p$ es falsa
Conjunción	$p \land q$	" $p$ y $q$ "	ambas son verdaderas
Disyunción	$p \lor q$	" $p$ o $q$ "	al menos una es verdadera
Implicación	$p \Rightarrow q$	"si $p$ , entonces $q$ "	no ocurre ( $p$ V y $q$ F)
Equivalencia	$p \Leftrightarrow q$	" $p$ si y solo si $q$ "	$p$ y $q$ tienen el mismo valor

Tabla de verdad de los conectivos:

$p$	$q$	$\neg p$	$p \land q$	$p \lor q$	$p \Rightarrow q$	$p \Leftrightarrow q$
V	V	F	V	V	V	V
V	F	F	F	V	F	F
F	V	V	F	V	V	F
F	F	V	F	F	V	V

Equivalencias importantes

Dos expresiones son equivalentes si tienen la misma tabla de verdad.

Leyes de De Morgan: $\neg(p \land q) \equiv \neg p \lor \neg q$ y $\neg(p \lor q) \equiv \neg p \land \neg q$ .
Doble negación: $\neg(\neg p) \equiv p$ .
Implicación como disyunción: $p \Rightarrow q \equiv \neg p \lor q$ .
Contrarrecíproco: $p \Rightarrow q \equiv \neg q \Rightarrow \neg p$ .

Dada la implicación $p \Rightarrow q$ :

Recíproca: $q \Rightarrow p$ — no es equivalente a la original.
Contrarrecíproca: $\neg q \Rightarrow \neg p$ — sí es equivalente.

Cuantificadores

$\forall x$ ("para todo $x$ "): la propiedad vale siempre.
$\exists x$ ("existe un $x$ "): vale al menos una vez.

Negar un cuantificador intercambia $\forall$ y $\exists$ y niega la propiedad: $\neg(\forall x,\ P(x)) \equiv \exists x,\ \neg P(x) \qquad\qquad \neg(\exists x,\ P(x)) \equiv \forall x,\ \neg P(x)$

Cómo demostrar

Demostración directa

Se parte de la hipótesis y se llega a la tesis con pasos lógicos.

Por contrarrecíproco

Para probar $p \Rightarrow q$ , se prueba $\neg q \Rightarrow \neg p$ (equivalente), que a veces es más fácil.

Por reducción al absurdo

Se supone lo contrario de lo que se quiere probar y se llega a una contradicción.

Por inducción

Sirve para probar propiedades de todos los naturales $n$ . Es como una fila de fichas de dominó: