Satisfacibilidad y contradicciones en lógica

Satisfacibilidad y contradicciones en lógica

En el ámbito de la informática y la lógica formal, comprender los conceptos de satisfacibilidad, tautología, contradicción y contingencia es fundamental para diseñar sistemas correctos y evitar errores de diseño. Este curso está estructurado a partir de una serie de preguntas tipo test que permiten profundizar en cada uno de estos conceptos, ofreciendo definiciones claras, ejemplos prácticos y buenas prácticas para su aplicación.

1. ¿Qué significa que una fórmula sea satisfacible?

Una fórmula lógica es satisfacible cuando existe al menos una valuación (asignación de valores de verdad a sus variables) que la hace verdadera. No es necesario que sea verdadera en todas las valuaciones, basta con una sola que la satisfaga.

• Condición necesaria: Existe al menos una valuación que la hace verdadera.
• Ejemplo: la proposición a ∨ ¬a es siempre verdadera (tautología) y, por tanto, también es satisfacible. En cambio, a ∧ ¬a nunca puede ser verdadera; es una contradicción y no es satisfacible.

2. Contradicciones directas en requisitos de sistemas

En la especificación de un sistema, una contradicción ocurre cuando dos afirmaciones se excluyen mutuamente. Analicemos el siguiente caso:

• "La sección B mostrará información actualizada para usuarios no registrados"
• "Los usuarios no registrados no pueden acceder a la sección B"

La primera afirmación genera una contradicción directa con la segunda, pues ambas no pueden ser verdaderas al mismo tiempo. Detectar estas inconsistencias es clave para garantizar la coherencia lógica del sistema.

3. Identificando fórmulas insatisfacibles

Una fórmula es insatisfacible (o contradicción) cuando ninguna valuación la hace verdadera. Veamos un ejemplo concreto:

• a ∧ r ∧ ¬r – Aquí la conjunción incluye r y su negación ¬r. No importa el valor de a; la presencia simultánea de r y ¬r hace que la fórmula sea siempre falsa.

Las demás proposiciones (s ⇒ b, ¬r ⇒ ¬b, r ⇒ s) pueden ser verdaderas bajo alguna valuación, por lo que no son insatisfacibles.

4. De la insatisfacibilidad a la contradicción

Cuando una fórmula es no satisfacible, se clasifica como una contradicción. En contraste:

• Una tautología es verdadera en todas las valuaciones.
• Una contingencia es verdadera bajo algunas valuaciones y falsa bajo otras.

Reconocer estas categorías ayuda a simplificar expresiones lógicas y a detectar errores en algoritmos de verificación.

5. Interpretando la tabla de verdad: la columna ‘V’

En una tabla de verdad, la columna marcada con ‘V’ indica que la proposición evaluada es verdadera bajo esa combinación específica de valores de las variables. Por ejemplo, para s ⇒ b:

• Si s es falso, la implicación es verdadera sin importar b (regla de la implicación).
• Si s es verdadero y b también es verdadero, la implicación sigue siendo verdadera.

Solo cuando s es verdadero y b es falso la implicación sería falsa.

6. Diferencia esencial entre satisfacibilidad y tautología

Es importante no confundir estos dos conceptos:

• Satisfacibilidad: la fórmula es verdadera al menos en una valuación.
• Tautología: la fórmula es verdadera en todas las valuaciones.

Una tautología es siempre satisfacible, pero una fórmula satisfacible no necesariamente es una tautología. Por ejemplo, a ∨ b es satisfacible (basta con que a o b sea verdadero) pero no es tautología, pues puede ser falsa cuando ambos son falsos.

7. Reglas lógicas en requisitos de acceso

En el diseño de sistemas, la regla de exclusión de acceso basada en registro establece que ciertos recursos deben estar disponibles exclusivamente para usuarios registrados o no registrados, pero no simultáneamente para ambos. Violaciones de esta regla generan inconsistencias lógicas que pueden traducirse en fallos de seguridad o en comportamientos inesperados.

Ejemplo:

• Afirmación correcta: "La sección B está disponible solo para usuarios registrados".
• Afirmación conflictiva: "La sección B debe estar disponible para usuarios registrados y no registrados simultáneamente" – rompe la regla de exclusión.

8. ¿Qué es una contingencia?

Una contingencia es una fórmula que no es ni tautología ni contradicción. Es decir, es verdadera bajo algunas valuaciones y falsa bajo otras. Este tipo de fórmulas son comunes en la práctica, ya que la mayoría de los enunciados del mundo real dependen del contexto.

• Ejemplo: a ∧ b es verdadera solo cuando ambas variables son verdaderas; en cualquier otro caso es falsa.

Entender la naturaleza de una fórmula (tautología, contradicción o contingencia) permite elegir la estrategia adecuada para su simplificación y para la verificación automática de requisitos.

9. Resumen de conceptos clave

• Satisfacible: al menos una valuación la hace verdadera.
• Contradicción: ninguna valuación la hace verdadera.
• Tautología: todas las valuaciones la hacen verdadera.
• Contingencia: verdadera en algunas valuaciones y falsa en otras.
• Regla de exclusión de acceso: evita que un recurso sea simultáneamente accesible para usuarios con y sin registro.

10. Buenas prácticas para evitar contradicciones en sistemas

Aplicar los siguientes pasos ayuda a garantizar la consistencia lógica:

1. Identificar todas las condiciones de acceso y expresarlas formalmente.
2. Construir tablas de verdad para cada regla y verificar que no existan filas donde una proposición y su negación sean simultáneamente verdaderas.
3. Utilizar herramientas de modelado lógico (por ejemplo, SAT solvers) para comprobar la satisfacibilidad del conjunto completo de requisitos.
4. Revisar las reglas de exclusión y asegurarse de que no haya solapamientos que generen contradicciones.
5. Documentar claramente las decisiones de diseño y los supuestos lógicos subyacentes.

Al seguir estas prácticas, los equipos de desarrollo pueden detectar y corregir inconsistencias antes de que se conviertan en fallos críticos en producción.