Complejidad de Expresiones Lógicas

Las expresiones lógicas pueden ser simples o complejas en diferentes niveles. Para medir la complejidad, usamos varios aspectos, como la longitud de la fórmula, su profundidad y estructura.

Longitud

La longitud muestra de cuántos símbolos consta una expresión. Cuantos más operadores lógicos y variables, más larga es la fórmula.

Esta expresión tiene 5 símbolos: p, ∨, q, ∧, r.

Profundidad

La profundidad indica el anidamiento de paréntesis. Un simple p ∧ q tiene profundidad 1, mientras que (p ∧ (q ∨ r)) tiene profundidad 2.

Simplificación

A menudo, las fórmulas complejas se pueden simplificar usando identidades lógicas (p. ej., leyes de De Morgan, idempotencia, distributividad). Esto reduce tanto la longitud como la profundidad.

Ejemplo: ¬(p ∧ q) ↔ (¬p ∨ ¬q). La expresión original parece más larga y profunda, pero la identidad la transforma en una forma más simple.

¿Por Qué es Importante la Complejidad?

• Los circuitos lógicos de las computadoras son más eficientes con fórmulas más simples.
• Desde el punto de vista de la comprensibilidad, es importante que la expresión sea lo más corta y clara posible.
• La dificultad de resolver problemas lógicos a menudo depende de la complejidad de las expresiones.

Resumen

La complejidad lógica consta de tres factores principales: longitud, profundidad y simplificabilidad. Con estos, podemos entender y manejar mejor las fórmulas lógicas.

Ejercicio de Práctica