Lógica algorítmica

La lógica algorítmica es un cálculo de programas que permite expresar propiedades semánticas de los programas mediante fórmulas lógicas apropiadas . Proporciona un marco que permite demostrar las fórmulas a partir de los axiomas de las construcciones de programas, como las instrucciones de asignación, iteración y composición, y a partir de los axiomas de las estructuras de datos en cuestión (véase Mirkowska y Salwicki , 1987; Banachowski et al., 1977) .

El siguiente diagrama ayuda a ubicar la lógica algorítmica entre otras lógicas . ${\displaystyle \qquad \left[{\begin{array}{l}\mathrm {Lógica proposicional} \\or\\\mathrm {Cálculo sentencial} \end{array}}\right]\subset \left[{\begin{array}{l}\mathrm {Cálculo predicativo} \\or\\\mathrm {Lógica de primer orden} \end{array}}\right]\subset \left[{\begin{array}{l}\mathrm {Cálculo de programas} \\or\\{\mbox{Lógica algorítmica}}\end{array}}\right]}$ El lenguaje formalizado de la lógica algorítmica (y de las teorías algorítmicas de diversas estructuras de datos) contiene tres tipos de expresiones bien formadas: términos (es decir, expresiones que denotan operaciones sobre elementos de estructuras de datos), fórmulas (es decir, expresiones que denotan las relaciones entre elementos de estructuras de datos) y programas (es decir, algoritmos ), que describen los cálculos. Para la semántica de términos y fórmulas, consulte las páginas sobre lógica de primer orden y la semántica de Tarski. El significado de un programa${\displaystyle K}$es el conjunto de cálculos posibles del programa.

La lógica algorítmica es una de las muchas lógicas de los programas. Otra lógica de los programas es la lógica dinámica, véase lógica dinámica , Harel, Kozen y Tiuryn ​​(2000) .

1. Mirkowska, Grażyna; Salwicki, Andrzej (1987). Lógica algorítmica (PDF) . Varsovia y Boston: PWN y D. Reidel Publ. pag.  372.ISBN​ 8301068590.]
2. [Banachowski y otros] | Banachowski, Lech; Kreczmar, Antoni; Mirkowska, Grażyna; Rasiowa, Helena; Salwicki, Andrzej (1977). Introducción a la lógica algorítmica: investigaciones metamatemáticas de la teoría de programas . Publicaciones del Centro Banach. vol. 2. Varsovia: PWN. págs. 7– 99.  
3. Harel, David ; Kozen, Dexter ; Tiuryn, Jerzy (2000). Lógica dinámica . Cambridge, Massachusetts: MIT Press. 459 págs . ISBN  978-0-262-08289-1.