Inicio · Parte 04 — Matemática discreta para computación
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q)Una tabla de verdad decide cualquier equivalencia proposicional por fuerza bruta: se evalúan las dos fórmulas en las 2ⁿ asignaciones posibles y se comparan. Es un método completo —siempre da respuesta— y de coste exponencial, lo que anticipa por qué SAT es un problema difícil (clase 097).
Las leyes de De Morgan son las que más se usan sin nombrarlas. Al negar una condición compuesta, la conjunción se convierte en disyunción y viceversa, y cada término se niega. En código: la negación de edad >= 18 and tiene_permiso es edad < 18 or not tiene_permiso, no edad < 18 and not tiene_permiso. Ese error produce condiciones que parecen razonables y filtran mal.
Una tautología es verdadera bajo toda asignación; una contradicción, falsa bajo todas. Detectarlas importa porque señalan código muerto: una condición tautológica siempre se cumple y su rama alternativa nunca se ejecuta.
El XOR merece mención aparte: es verdadero cuando los operandos difieren, y tiene la propiedad de ser su propia inversa, (a ⊕ b) ⊕ b = a. Esa propiedad lo hace omnipresente en criptografía, en sumas de comprobación y en el intercambio de variables sin memoria auxiliar.
Verificar De Morgan exhaustivamente.
4 casos evaluados (2² asignaciones)
p q | ¬(p∧q) ¬p∨¬q | ¬(p∨q) ¬p∧¬q
V V | F F | F F
V F | V V | F F
F V | V V | F F
F F | V V | V V
Ambas leyes: columnas idénticas ✓
Tautología: p ∨ ¬p → V en las 4 filas
Contradicción: p ∧ ¬p → F en las 4 filas
XOR: (V,V)→F (V,F)→V (F,V)→V (F,F)→FLeyes de De Morgan verificadas exhaustivamente.
python classes/part-04-matematica-discreta-para-computacion/082-tablas-de-verdad-y-equivalencias/lab.py
compmath run 082casos_evaluados¬(p∧q) ≡ ¬p∨¬q¬(p∨q) ≡ ¬p∧¬qtautologia_p∨¬pcontradiccion_p∧¬pxor{
"casos_evaluados": 4,
"¬(p∧q) ≡ ¬p∨¬q": true,
"¬(p∨q) ≡ ¬p∧¬q": true,
"tautologia_p∨¬p": true,
"contradiccion_p∧¬p": true,
"xor": [
[
true,
true,
false
],
[
true,
false,
true
],
[
false,
true,
true
],
[
false,
false,
false
]
]
}Simplificación de condiciones, optimización de consultas SQL, diseño de circuitos digitales y refactorización de código con lógica compleja.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.