💻 computer science

Fully Evaluated Left-Sequential Logics

Este artículo introduce una jerarquía de lógicas totalmente evaluadas y secuenciales a la izquierda que van desde FEL Libre hasta FEL Estático, proporcionando axiomatizaciones completas para sus versiones de dos y tres valores utilizando árboles de evaluación como base semántica.

Autores originales: Alban Ponse, Daan J. C. Staudt

Publicado 2026-05-14

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Alban Ponse, Daan J. C. Staudt

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un chef preparando un plato complejo. En el mundo de la lógica informática, los «ingredientes» son hechos (verdaderos o falsos) y las «recetas» son instrucciones sobre cómo combinarlos. Este artículo introduce una familia de estilos culinarios denominados Lógicas Completamente Evaluadas de Secuencia Izquierda (FEL).

La idea central es simple: Debes probar cada ingrediente individualmente en orden, de izquierda a derecha, antes de decidir si el plato está listo. No puedes saltarte un paso, ni detenerte a mitad de camino solo porque el primer ingrediente supiera mal.

A continuación se presenta un desglose de los diferentes «estilos culinarios» (lógicas) que los autores exploran, utilizando analogías cotidianas.

1. La regla básica: «Secuencia Izquierda»

En estas lógicas, el orden importa. Si tienes una receta A luego B, debes probar A primero.

El punto: Los autores utilizan un punto especial (como ∧•) para mostrar esto. Significa «Prueba el lado izquierdo primero. Una vez hecho eso, prueba el lado derecho».
La diferencia: En la lógica normal (como una tabla de verdad estándar), si la primera parte es «Falsa», podrías detenerte allí porque todo el conjunto ya es falso. En estas lógicas, sigues adelante. Pruebas la segunda parte de todos modos. Esto se denomina «Evaluación Completa».

2. Los cuatro niveles de «estilos culinarios»

El artículo presenta una jerarquía de cuatro lógicas, que van desde la más caótica hasta la más rígida. Piensa en ellas como diferentes niveles de disciplina en la cocina.

Nivel 1: FEL Libre (FFEL) – El «Degustador Caótico»

El ambiente: Este es el estilo más básico y «libre».
La regla: Pruebas todo en orden. Sin embargo, si pruebas el mismo ingrediente dos veces (por ejemplo, A y luego A de nuevo), la segunda vez podría saber diferente porque la primera vez cambió la cocina.
La analogía: Imagina probar un limón. La primera vez, es ácido. Pero si lo pruebas de nuevo inmediatamente después de exprimirlo, quizás ahora sea solo una cáscara húmeda. En FFEL, A y A no son necesariamente iguales porque el primer A podría haber tenido un «efecto secundario» (como cambiar el entorno).
Característica clave: Es inmune a los efectos secundarios solo si prometes que los ingredientes no cambian. Es la lógica «más débil» porque permite la mayor imprevisibilidad.

Nivel 2: FEL Memorizante (MFEL) – El «Chef que toma notas»

El ambiente: Este chef está organizado.
La regla: Si pruebas un ingrediente (digamos, A), lo anotas en un cuaderno. Si encuentras A de nuevo más adelante en la receta, simplemente miras tu cuaderno. No lo pruebas de nuevo.
La analogía: Imagina a un guardia de seguridad revisando identificaciones. Si revisa tu identificación en la puerta, no necesita volver a revisarla en la entrada trasera; recuerda quién eres.
Característica clave: Esto elimina los «efectos secundarios». Una vez que un átomo (ingrediente) es evaluado, su valor se fija para el resto del proceso. Esto hace que la lógica sea más fuerte y predecible.

Nivel 3: FEL Condicional (CℓFEL) – El «Equipo Flexible»

El ambiente: Este equipo puede intercambiar lugares.
La regla: Es como MFEL (recuerdas lo que probaste), pero ahora puedes intercambiar el orden de los ingredientes si son diferentes. A luego B se trata igual que B luego A.
La analogía: Imagina a un grupo de amigos decidiendo dónde comer. Si Alice y Bob deciden entre Pizza y Sushi, no importa quién hable primero; la decisión final es la misma.
Característica clave: Esta lógica es equivalente a una famosa lógica de tres valores llamada Lógica de Bochvar. Maneja los ingredientes «no definidos» (como un huevo roto) tratando todo el plato como «roto» (no definido) inmediatamente.

Nivel 4: FEL Estática (SFEL) – El «Contador Estricto»

El ambiente: El estilo más rígido y tradicional.
La regla: Esto es simplemente la lógica proposicional estándar (como las matemáticas de la escuela secundaria), pero con la regla de que aún debes probar todo en orden.
La analogía: Este es el «Estándar de Oro». Si tienes una receta que dice «Si el huevo está malo, el pastel está malo», esta lógica está de acuerdo. Absorbe todo el caos.
Característica clave: Es tan estricta que no puede manejar ingredientes «no definidos». Si intentas mezclar «No definido» con «Falso», las matemáticas se rompen (porque No definido se convierte en Falso, lo cual es una contradicción).

3. El ingrediente «No definido» (U)

Los autores también exploran qué sucede si un ingrediente es No definido (U).

En los estilos «Libre» y «Memorizante»: Si pruebas un ingrediente no definido, todo el proceso se detiene o se vuelve no definido. Es como intentar hornear un pastel con «polvo misterioso». El resultado es un «pastel misterioso».
La regla «Absorbente»: En la versión más fuerte de tres valores (FEL Condicional), el ingrediente no definido es «absorbente». Si mezclas No definido con cualquier cosa, el resultado es No definido. Es como un agujero negro en tu receta.

4. Los «árboles» de la lógica

Para demostrar que sus reglas funcionan, los autores utilizan Árboles de Evaluación.

Imagina un árbol genealógico:
- La parte superior es la pregunta principal.
- Las ramas son los caminos «Izquierdo» (Verdadero) y «Derecho» (Falso).
- Las hojas en la parte inferior son las respuestas finales (Verdadero o Falso).
La innovación: En estas lógicas, el árbol muestra el camino exacto que tomaste. Si probaste A y luego B, el árbol muestra ese viaje específico. En la lógica «Memorizante», el árbol es más limpio porque no muestra que probaste el mismo ingrediente dos veces.

Resumen del logro del artículo

Los autores no solo describieron estos estilos culinarios; escribieron los Reglamentos (Axiomas) para cada uno.

Definieron exactamente cómo combinar ingredientes (ecuaciones).
Demostraron que estos reglamentos son Completos (cubren cada escenario posible) e Independientes (ninguna regla es redundante; no puedes eliminar ninguna sin romper el sistema).
Utilizaron herramientas informáticas (Prover9 y Mace4) para verificar sus matemáticas, asegurando que ningún error humano se colara.

En resumen: Este artículo traza un espectro de sistemas lógicos donde se te obliga a probar cada ingrediente individualmente en orden. Comienza con un sistema caótico donde los ingredientes podrían cambiar, pasa a un sistema donde recuerdas lo que probaste, luego a un sistema donde el orden no importa, y finalmente a un sistema rígido que se comporta como las matemáticas estándar. Proporcionan las leyes matemáticas exactas para cada estilo.

Resumen Técnico: Lógicas Left-Sequential Completamente Evaluadas

Enunciado del Problema
Este artículo aborda la formalización y axiomatización de las "Lógicas Left-Sequential Completamente Evaluadas" (FELs). A diferencia de las lógicas de cortocircuito (SCLs), donde la evaluación se detiene una vez determinado el resultado de una expresión compuesta, las FELs prescriben una estrategia de evaluación "completa" o "estricta": cada proposición atómica dentro de un término se evalúa independientemente de si su valor es estrictamente necesario para el resultado final. Esta estrategia está motivada por contextos de programación donde deben garantizarse efectos secundarios (por ejemplo, cambios de estado) para todos los átomos en una expresión. Los autores tienen como objetivo definir una jerarquía de tales lógicas, que va desde la más débil (FEL Libre), que es inmune a efectos secundarios atómicos, hasta la más fuerte (FEL Estática), que se comporta como una versión secuencial de la lógica proposicional clásica. Además, el artículo extiende estas lógicas a un contexto de tres valores para manejar la "indefinición" ( $U$ ), una característica común en programación y lógica (por ejemplo, división por cero).

Metodología
Los autores emplean un marco semántico basado en árboles de evaluación, un concepto introducido en su trabajo anterior [19].

Semántica: Los árboles de evaluación son árboles binarios donde los nodos internos representan átomos y las hojas representan valores de verdad ( $T$ $T$ , $F$ $F$ o $U$ $U$ ). Un camino desde la raíz hasta una hoja modela una secuencia de evaluación.
- En FEL Libre (FFEL), la estructura del árbol preserva estrictamente el orden de evaluación y permite ocurrencias repetidas del mismo átomo, modelando posibles efectos secundarios.
- En FEL Memorizante (MFEL), la semántica se refina de modo que ningún camino en el árbol contiene múltiples ocurrencias del mismo átomo; la evaluación de un átomo se "memoriza" si se encuentra nuevamente.
- En FEL Condicional (CℓFEL), la lógica incorpora la conmutatividad de los átomos, tratando efectivamente el orden de los átomos independientes como irrelevante.
- En FEL Estática (SFEL), la lógica colapsa en una versión secuencial de la lógica proposicional donde se cumplen las leyes de absorción.
Extensión a Tres Valores: Para todas las lógicas excepto SFEL, los autores introducen una constante $U$ (indefinido). La semántica se extiende a árboles con hojas en $\{T, F, U\}$ , donde $U$ actúa como un elemento absorbente (por ejemplo, $U \land_r x = U$ ).
Axiomatización: La contribución metodológica principal es la derivación de axiomatizaciones equacionales completas para cada lógica. Los autores definen formas normales (por ejemplo, Forma Normal FEL, formas $\sigma$ -normales) para probar la completitud. Utilizan el demostrador de teoremas Prover9 para verificar derivaciones y Mace4 para generar contra-modelos finitos que prueben la independencia de los axiomas.

Contribuciones y Resultados Clave

Jerarquía de FELs de Dos Valores:
- FEL Libre (FFEL): La lógica más débil, axiomatizada por el conjunto $EqFFEL$. Refuta la idempotencia ( $x \land_r x \neq x$ ) pero satisface la asociatividad. Es la lógica de la evaluación completa sin restricciones de efectos secundarios.
- FEL Memorizante (MFEL): Axiomatizada añadiendo un axioma a FFEL (específicamente, $(x \lor_r y) \land_r z = (\neg x \land_r (y \land_r z)) \lor_r (x \land_r z)$ ). Exige que los átomos repetidos se traten como idénticos, eliminando los efectos secundarios.
- FEL Condicional (CℓFEL $_2$ ): Axiomatizada añadiendo la conmutatividad ( $x \land_r y = y \land_r x$ ) a MFEL. Esta lógica es equivalente a la sublógica de dos valores de la Lógica Condicional (Guzmán y Squier [12]).
- FEL Estática (SFEL): La lógica más fuerte, obtenida añadiendo $x \land_r F = F$ a CℓFEL $_2$ . Es equivalente a la Lógica de Cortocircuito Estática (SSCL) y a la lógica proposicional estándar bajo evaluación secuencial.
Extensiones a Tres Valores (FELU):
- Los autores definen versiones de tres valores (FFELU, MFELU, CℓFEL) añadiendo los axiomas $\neg U = U$ y $U \land_r x = U$ .
- CℓFEL (la FEL Condicional de tres valores) se demuestra equivalente a la lógica estricta de Bochvar [8].
- SFEL no puede extenderse con $U$ porque la ley de absorción $F = U \land_r F = U$ conduce a un colapso de los valores de verdad.
Completitud e Independencia:
- Se proporcionan axiomatizaciones equacionales completas para todas las lógicas definidas.
- Los autores presentan conjuntos alternativos y más concisos de axiomas independientes para cada lógica (por ejemplo, el conjunto $MF$ para MFEL), verificados mediante herramientas automatizadas.
- Se construyen formas normales para demostrar que la igualdad sintáctica de las formas normales corresponde a la igualdad semántica de los árboles de evaluación.

Significado y Afirmaciones
El artículo afirma proporcionar un marco unificado para comprender la evaluación left-sequential completa, cerrando la brecha entre las lógicas de cortocircuito y la lógica proposicional clásica.

Previsibilidad: Los autores argumentan que las FELs ofrecen mayor previsibilidad respecto al estado del entorno (efectos secundarios) después de la evaluación en comparación con las SCLs, ya que se garantiza que todos los átomos sean evaluados.
Expresividad: El artículo demuestra que, mientras que FFEL no puede expresar ciertos árboles de evaluación uniformes (por ejemplo, árboles donde un átomo aparece en diferentes ramas con resultados diferentes), MFEL y las lógicas más fuertes sí pueden expresarlos, aumentando así el poder expresivo de la lógica.
Relación con Trabajos Existentes: El trabajo sitúa a CℓFEL dentro de la jerarquía de lógicas, mostrando que es equivalente a la lógica de Bochvar y una sublógica de la Lógica Condicional. También aclara la relación entre las FELs y las Lógicas de Cortocircuito (SCLs), señalando que los conectivos FEL pueden definirse dentro de marcos SCL (y viceversa bajo condiciones específicas), aunque las FELs imponen una disciplina de evaluación más estricta.

El artículo concluye que estas lógicas proporcionan una base teórica robusta para el razonamiento sobre expresiones donde se requiere una evaluación completa, ofreciendo axiomatizaciones completas e independientes que facilitan el razonamiento y la verificación automatizados.