Все выпуски

В данной работе представлен новый подход к интерпретации логических формул для синтеза алгоритмов и программ. Предложенный метод сочетает в себе черты реализации Клини и интерпретации Гёделя «диалектика», но не опирается на них непосредственно. Рассматривается простой вариант позитивного языка логики предикатов без функций, с конъюнкцией, дизъюнкцией, импликацией и кванторами всеобщности и существования. Описана новая реализационная семантика формул и секвенций, в которой рассматривается не просто реализация формулы, а реализация с дополнительной поддержкой. Реализация примерно соответствует реализации Клини. Поддержка предоставляет дополнительные данные в пользу того, что реализация корректна. Поддержка должна подтвердить, что реализация работает корректно для формулы в любых корректных условиях применения. Представлен язык доказательств, для которого доказана теорема о корректности, показывающая, что любая выводимая секвенция имеет реализацию и поддержку, подтверждающую, что эта реализация работает правильно для этой формулы в любых корректных условиях при подходящем интерпретаторе используемых программ.

В статье определяются и исследуются основные конструкции и семантика языка описания действий (action description language), предназначенного для описания и анализа преобразований отношений моделей ситуаций (реляционных преобразований).
Основное отличие описываемого языка KSL (Knowledge Specification Language) от традиционных (STRIPS, ADL, PDDL и т. п.) - использование кроме традиционных (STRIPS-like) правил их теоретико-множественных композиций. Это существенно повышает выразительность языка.
Точная характеризация основных свойств реляционных преобразований на языке логики предикатов первого порядка (FOL), но без использования дополнительных конструкций ситуационного исчисления, дает возможность сформулировать и доказать естественный критерий реализуемости (непротиворечивости) системы правил реляционных преобразований и, соответственно, явно описывать и исправлять логические противоречия рассматриваемой системы преобразований.