Copia - 4.1 Modelo Progr Lógica

2025

UNIDAD 4 Modelo de Programación Lógica

Introducción

• En la ingeniería de software, una de las áreas más activas es el desarrollo de conceptos y herramientas para el prototipado automático. Su importancia es ampliamente reconocida, y se considera que puede lograrse de manera efectiva mediante el uso de técnicas de especificación formal.

• La lógica matemática subyacente aporta s u sintaxis, su semántica y su mecanismo de deducción, que debe ser correcto y completo. Se puede así definir el significado de la especificación en términos de modelos y su ejecución en términos de deducción, lo cual permite considerar la propia especificación (ejecutable) como un prototipo (de muy alto nivel) del sistema.
• El estilo lógico o declarativo se sitúa en ese punto en el que la frontera entre especificación y programa parece desdibujarse.

Semántica de los Lenguajes de Programación

• Uno de los principales requisitos de u n buen lenguaje de programación es el de disponer de una semántica definida de un modo sencillo, flexible y con un buen soporte formal. La tendencia actual es asociar a los lenguajes de especificación una semántica formal definida en un estilo ya estándar, semántica declarativa y semántica operacional, con resultados de equivalencia entre ambas.
• De esta forma, las especificaciones pueden ser consideradas como teorías que se pueden animar para verificar el hecho de que su modelo se corresponde con las intenciones del programador, para verificar su corrección (y otras propiedades) respecto de la funcionalidadesperada.

A) Semántica Declarativa

• El término "declarativa" indica un tipo de semántica que especifica el significado de los objetos sintácticos por medio de su traducción en elementos y estructuras de un dominio matemático conocido. Se han propuesto muchos métodos que se basan en este principio.

1. Algunos de los más interesantes que examinaremos a continuación, son:
2. La semántica por teoría de modelos "a la Tarski",
3. La semántica algebraica,
4. La semántica por punto fijo y
5. La semántica denotacional.

1. Semántica por Teoría de Modelos

• La semántica por teoría de modelos se basa en los conceptos de interpretación y modelo.

Una interpretación define un dominio y asigna a los símbolos del lenguaje (constantes, funciones y predicados) elementos, funciones y relaciones de ese dominio, mientras que las conectivas lógicas tienen un significado fijo.

• Un modelo de un conjunto de axiomas es toda interpretación en la que dichos axiomas son verdaderos. Así, el significado de un programa se entiende como el conjunto de sus consecuencias lógicas, es decir, las fórmulas que son verdaderas en todos los modelos posibles del programa.

La teoría de modelos ha generado resultados clave en lógica:

• Teorema de Löwenheim-Skolem: toda teoría consistente tiene al menos un modelo numerable.

• Teorema de completitud de Gödel: existe equivalencia entre derivabilidad e implicación semántica.

• Teorema de indecidibilidad de Gödel: todas las teorías suficientemente potentes (como la aritmética) son indecidibles.

En los programas de cláusulas de Horn definidas, se cumple el teorema del modelo mínimo de Herbrand, el cual representa a toda la clase de modelos respecto a la verdad de ciertas fórmulas. Por ello, se utiliza para caracterizar el significado de este tipo de programas.

2. Semántica Algebraica

• El método algebraico se utiliza para especificar tipos de datos y definir la semántica de lenguajes ecuacionales de primer orden. Se apoya en conceptos de la teoría de categorías y el álgebra universal.
• Un resultado central en este enfoque es el teorema de completitud de Birkhoff, considerado la versión algebraica del teorema de completitud de Gödel.

• En esta aproximación, la semántica de un programa se define usando una clase de álgebras que cumplen las ecuaciones del programa según un criterio de satisfacción. Según el tipo de programa, se pueden emplear distintas variantes: álgebras finitamente generadas, parciales, de error, ordenadas, continuas, entre otras.
• La técnica más común consiste en elegir un objeto inicial (semántica inicial) o un objeto final (semántica final) dentro de la categoría de álgebras que sirven como modelos de dichas ecuaciones.

• Un álgebra inicial se caracteriza por la hipótesis de mundo cerrado: solo lo demostrable es verdadero y lo demás es falso. Esto implica ausencia de basura (no hay entidades innecesarias) y de confusión (no existen elementos distintos que no puedan distinguirse).
• En cambio, la semántica final varía esta idea: considera verdadero todo aquello que no puede demostrarse como falso a partir de las observaciones realizadas en los modelos de la especificación.

3. Semántica por Punto Fijo

• La aproximación por punto fijo define el significado de un programa recursivo o iterativo como el punto fijo mínimo de una transformación continua asociada al programa. Gracias a la continuidad, este punto fijo puede construirse de forma iterativa, aplicando la transformación repetidamente desde el elemento más pequeño del dominio, lo que garantiza una interpretación computacional directa.

• En general, la semántica por punto fijo es solo una abstracción de un proceso computacional y no define directamente una semántica declarativa.

Sin embargo, en los programas lógicos con cláusulas de Horn definidas, adquiere un papel especial: describe cómo construir inductivamente un modelo aplicando las reglas a los hechos de forma ascendente, generando nuevos hechos hasta llegar a un punto donde no se puedan producir más.

4. Semántica Denotacional

• La aproximación denotacional, que tiene sus orígenes en los trabajos de Scott, Strachey y de Bakker, se articula en las siguientes fases:

• 1. Subdivisión de los objetos linguísticos en varios conjuntos (categorías sintácticas o dominios sintácticos) y clasificación de los operadores linguisticos (i.e., de las construcciones que permiten componer objetos linguísticos para obtener otros objetos).

2. Definición de los oportunos dominios semánticos, algunos de los cuales corresponden a las categorías sintácticas mientras que otros son auxiliares. Esta definición viene dada constructivamente, partiendo de los dominios de base y especificando dominios cada vez más complejos por medio de operadores de dominio. 3. Definición de algunas funciones de valuación semántica, que asocian a cada objeto linguistico un elemento del correspondiente dominio semántico y a cada operador un elemento del espacio funcional sobre los correspondientes dominios semánticos.

B) Semántica Operacional

• La semántica operacional es la forma más antigua de definir el significado de un programa. Se basa en describir las acciones que ejecutaría una máquina abstracta previamente definida. En la práctica, equivale a especificar un intérprete del lenguaje, independiente de su implementación real.

• Una implementación de un lenguaje puede usar mecanismos distintos a los de su definición semántica, pero siempre debe producir los mismos resultados.
• La semántica de las construcciones se define mediante inducción estructural y reglas de inferencia, lo que facilita demostrar propiedades de los programas, combinando la inducción estructural con la inducción sobre secuencias de transición.

Lenguajes Lógicos

• Un lenguaje lógico es aquel donde los programas se consideran teorías en una lógica, y son equivalentes tres conceptos: computación en la máquina, deducción lógica y satisfacción en un modelo.
• Además, para diferenciar la programación lógica de la simple demostración de teoremas, se requiere eficiencia y un mecanismo efectivo de obtención de respuestas.

• Un ejemplo importante en lógica de primer orden es el lenguaje de cláusulas de Horn definidas (HCL), cuyas fórmulas son disyunciones de literales con un único literal positivo. Esta restricción limita la representación de todas las fórmulas de primer orden.

• Para manejar información negativa en programas HCL se utiliza la regla de negación como fallo, ya que sus consecuencias lógicas son siempre positivas.

Característicasde los lenguajes lógicos

• El estilo lógico se distingue por el uso de variables lógicas (unificación) y el no determinismo (búsqueda).

• La unificación bidireccional, a diferencia del pattern-matching unidireccional, permite trabajar con definiciones inversibles y estructuras de datos parciales, lo que hace la programación más compacta y flexible.

¡GRACIAS!

2025