Planteamiento:
la capacidad de poderle hablar a una computadora, es sin duda lo mas cercano que hemos tenido a la magia, y como buena magia no sabemos como funciona, es decir gandalf no sabemos exactamente como funciona cada hechizo, sabe utilizarlos pero no conoce perfectamente cada principio que hay detrás, si solo te interesa programar este capitulo puede llegar a ser tedioso, pero si quieres saber como funciona una computadora esto es para ti. Al final no hay nadie vivo que entienda como funciona una computadora moderna al 100%, ya que es demasiada información, pero aspirar a saber un poquito mas, te hace llena de pasión.
Introducción:
En los capítulos anteriores vimos cómo la computadora mastica ceros y unos, y cómo usar operadores a nivel de bits y lógica booleana para controlar ese flujo, esto son temas que aunque no los entendamos perfectamente, ya los conocemos por videos de linux chad entre otras cosas.
Pero aquí entra un tema clave: cuando escribes una función, ¿cómo estás completamente seguro de que funciona para cualquier escenario y no solo para los tres casos de prueba que le pasaste? es decir como podemos demostrar que la variable P es igual que la variable Q, no vamos a entrar en axiomas matemáticos, *(pero si alguien quiere saber por que 1+1=2 es matemáticamente correcto, busque el libro de “(Principia Mathematica)”.
Como programadores (y especialmente si te gusta el bajo nivel o cacharrear con C y el hardware), no podemos depender de la fe, ya que se puede quemar algo.
Sin mas TDAH, el tema del capitulo es que escribir código es hacer una afirmación matemática: “Si me das X entrada, te garantizo Y salida”, veremos que tipos de demostraciones tenemos para saber que algo es igual que algo.
Contenido:
- Demostración Directa
- Demostración por Contraposición
- Demostración por Contradicción
Demostración Directa
La demostración directa es exactamente lo que suena: partes de un punto A (tu hipótesis), aplicas reglas lógicas, y llegas al punto B (tu conclusión). Es el equivalente a ejecutar un código línea por línea en tu cabeza sin que nada se rompa.
En matemáticas, la estructura es: P → Q (Si P es verdad, entonces Q es verdad).
Ejemplo: Demostrar que la suma de dos números pares siempre es par.
P (Hipótesis): Tenemos dos números, supongamos que a y b, que son pares. Por definición, un número par es el doble de un entero, así que a = 2r y $b = 2s.
Reglas: Sumamos ambos: a + b = 2r + 2s. Factorizamos el 2: 2(r + s).
Q (Conclusión): Como (r + s) es solo otro número entero,
el resultado tiene la forma 2k. Por lo tanto, es par.
Ahora si aplicamos esto al codigo, como de costumbre en C99…
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// Definición de nuestra propiedad
bool esPar(int n) {
return n % 2 == 0;
}
// Nuestra función basada en la demostración directa
int sumarPares(int a, int b) {
if (!esPar(a) || !esPar(b)) {
fprintf(stderr, "Error: Ambos números deben ser pares, rompes la hipótesis.\n");
exit(EXIT_FAILURE);
}
return a + b;
}
int main(void) {
int suma = sumarPares(14, 28);
printf("%d es par: %s\n", suma, esPar(suma) ? "true" : "false");
return 0;
}
Demostración por Contraposición
A veces, probar que A es igual B es un dolor de cabeza porque A no nos da suficiente información para arrancar, es decir no sabemos que tipos de variable es etc…
Aquí es donde los matemáticos y los programadores aplican un truco la contraposición*.
Ejemplo: Demostrar que “Si n^2 es par, entonces n es par”. Partir de n^2 es difícil de factorizar, solo podriamos ponerlo como n x n, y no sirve de mucho. Mejor usamos la contraposición: “Si n NO es par (es decir, es impar), entonces n^2 NO es par (es impar)”
Llevado al código: En programación, esto es muy aplicable a la ciberseguridad, ya que se usan mucho la validación de permisos o el manejo de errores (los famosos Early Returns o Guard Clauses), la verdad no es mi área, asi que si esto ya no se usa me corrigen.
En lugar de decir: “Si tiene la contraseña correcta y es administrador, entonces entra”. Aplicamos la contraposición: “Si NO entra, es porque NO tenía la contraseña o NO era administrador”. Ojo aquí con las leyes de De Morgan para negar condiciones compuestas.
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
// Función que valida requisitos
bool cumpleRequisitos(const char* clave) {
bool tieneLongitud = strlen(clave) >= 8;
// Lógica simplificada para revisar si tiene números
bool tieneDigito = strpbrk(clave, "0123456789") != NULL;
return tieneLongitud && tieneDigito;
}
int main(void) {
const char* miClave = "linuxOS";
// Si la función devuelve falso (NO Q),
// sabemos con certeza que falló al menos un requisito (NO P).
if (!cumpleRequisitos(miClave)) {
printf("Acceso denegado. Falla de longitud o falta de dígito.\n");
}
return 0;
}
Demostración por Contradicción
Esta es mi favorita, asume por un momento que es falso. Sigue las reglas de la lógica hasta que el sistema colapse y llegues a una imposibilidad absoluta, no se si es algo pretencioso este ejemplo pero es como un DDOS. (como que 1 < 0 o que un número sea par e impar al mismo tiempo). Como la lógica no permite absurdos, tu suposición inicial era basura, ergo, la afirmación original era cierta.
Como antes veamos un ejemplo matematico y luego un script…
Ejemplo: Demostrar que *“No existe un número entero máximo”.
Supongamos que sí existe, y lo llamamos M.
Por las reglas del álgebra, siempre puedo sumarle 1 a un entero.
Entonces M + 1 es un entero.
Pero M + 1 es mayor que M. Y conseguimos una contradicción. $M$ no puede ser el máximo si hay uno más grande. Así que la suposición inicial colapsa.
#include <stdio.h>
// Búsqueda Binaria basada en descartar mitades por contradicción
int busquedaBinaria(int numeros[], int longitud, int buscado) {
int izquierda = 0;
int derecha = longitud - 1;
while (izquierda <= derecha) {
int centro = izquierda + (derecha - izquierda) / 2;
if (numeros[centro] == buscado) {
return centro;
}
// Contradicción: el número no puede estar a la izquierda
if (buscado > numeros[centro]) {
izquierda = centro + 1;
}
// Contradicción: el número no puede estar a la derecha
else {
derecha = centro - 1;
}
}
return -1; // No se encontró
}
int main(void) {
int arr[] = {3, 7, 11, 15, 21, 28, 35};
int longi = sizeof(arr) / sizeof(arr[0]);
printf("El numero 21 esta en el indice: %d\n", busquedaBinaria(arr, longi, 21));
return 0;
}
Concusion:
Asi que jovenes :V
En el día a día picando código, la demostración directa te ayuda a diseñar funciones limpias donde las precondiciones garantizan la salida esperada sin tener que meter parches a ciegas. desubrimos que la rueda si gira.
