SCI Библиотека

Задание базовых правил вывода имеет фундаментальное значение для логики. Наиболее общим вариантом возможных правил вывода являются допустимые правила вывода: в логике

Изучается нетранзитивная временная мультиагентная логика с мультиозначиваниями агентов для переменных и формул. Ранее время и знания моделировались с помощью моделей Крипке, структура которых выглядела как простой единый временной кластер с множеством отношений достижимости для агентов. Здесь мы развиваем этот подход и используем модели Крипке, которые представляют собой линейное нетранзитивное время и состояния, представленные произвольными временными кластерами для мультиотношений достижимости агентов. Эта логика определяется семантически как множество формул, истинных на линейных моделях с мультиозначиваниями переменными и кластерами состояний. Мы предлагаем обоснование такого подхода и методику вычисления истинностных значений формул. Основные результаты касаются проблемы разрешимости. Мы доказываем, что полученная логика разрешима и финитно аппроксимируема.

Общее понятие алгоритма первично и не определяемо, а может бытьь только понято через его свойства, подобно понятию множества. Через вычислительные модели (машина Тьюринга, Колмогорова, нормальные алгоритмы Маркова) оно уточняется. То же относится к понятию исчисления, которое уточняется в конкретных дедуктивных системах (логические исчисления, формальная арифметика). Между алгоритмами и исчислениями существует тесная связь Для каждого алгоритма существует исчисление, порождающее область определения этого алгоритма, более того, можно указать исчисление, порождающее те и только те пары (x, y), для которых Ψ(x) = y. С другой стороны, для каждого исчисления существует алгоритм, область определения которого совпадает с множеством, порождаемым исходным исчислением. Каждый алгоритм задает функцию на своей области применимости, ее значения равны результату алгоритма Ψ(x). Применительно к исчислению можно говорить о породимых, разрешимых и перечислимых множествах. Тезисы Черча и Поста формулируются, соответственно, для вычислимой модели алгоритма и порождающей модели исчисления. С помощью общего понятия исчисления можно глубже осмыслить многие фундаментальные понятия математической логики. В частности, знаменитую теорему Геделя о полноте, утверждающую, что все истинные формулы логики предикатов 1-го порядка могут быть порождены некоторым исчислением. Другая знаменитая теорема Геделя о неполноте утверждает, что множество всех истинных формул арифметики (а, значит, и множество всех общезначимых формул логики предикатов 2-го порядка) не может быть порождено никаким исчислением. На базе понятия исчисления можно изложить всю дескриптивную теорию алгоритмов (наличие или отсутствие алгоритма без оценки затрат на достижение этой цели). Вычислимая функция - это функция, вычислимая каким-либо алгоритмом: при применении к какому-нибудь входу вычисляющий алгоритм должен не только давать результат, совпадающий со значением функции на этом входе, если такое значение существует, но; и не давать никакого результата, если функция не определена на данном входе. Породимое множество - это множество, порождаемое какимлибо исчислением. Перечислимое множество - это либо множество значений всюду определенной вычислимой функции натурального аргумента, либо пустое множество. Обе теоремы Геделя можно сформулировать в терминах перечислимости и неперечи-слимости соответствующих множеств. Множество называется разрешимым, или распознаваемым, если оно содержится в некотором породимом множестве X и для него существует разрешающий алгоритм. Алгоритм Ψ называется разрешающим алгоритмом для подмножества A множества X, если множество допустимых входов для Ψ совпадает с X и Ψ отвечает на все вопросы типа “x∈X & x∈A”. Проблема отыскания такого алгоритма называется проблемой разрешения для множества A.;

Генерические алгоритмы решают проблемы на множествах почти всех входов, выдавая неопределённый ответ для остальных редких входов. В статье доказывается, что проблема равенства генерически разрешима в конечно порождённых полугруппах S, для которых существует такая конгруэнция θ, что полугруппа S/θ является бесконечным финитно аппроксимируемым моноидом с сокращениями и с разрешимой проблемой равенства. Это обобщает ранее полученный результат автора о генерической разрешимости проблемы равенства в конечно определённых полугруппах, которые остаются бесконечными при добавлении свойств коммутативности и сокращения. Отметим, что примерами таких полугрупп служат полугруппы с одним определяющим соотношением, а также так называемые сбалансированные полугруппы, для которых Вон доказал генерическую разрешимость проблемы равенства. В частности, сбалансированными являются классические полугруппы Цейтина и Маканина с неразрешимой проблемой равенства.

Ранее К. Дошен и М. Божич ввели четыре независимые интуиционистские модальные логики - по одной для каждого из четырёх типов модальных операторов: необходимости N, возможности P, невозможности Im и не-необходимости Un. Эти логики обозначаются HKM, где M∈{N,P,Un,Im}. Интерес к тому, чтобы рассматривать четыре типа модальных операторов по отдельности, связан именно с тем, что над интуиционистской логикой они не могут быть сведены друг к другу. Здесь изучаются расширения логик HKM, у которых есть нормальные напарники. Оказывается, что нормальные напарники есть у всех расширений логик HKN и HKUn. Для расширений HKP и HKIm получен критерий существования нормальных напарников, который заключается в присутствии некоторого модального закона двойного отрицания. Также показывается, как добавление этого закона влияет на выразительные возможности логики. Особый интерес представляет результат о том, что расширения HKP и HKIm имеют нормальных напарников, только если они дефинициально эквивалентны расширениям HKN и HKUn соответственно. Этот результат является ещё одним примером различия в поведении четырёх типов модальных операторов над интуиционистской логикой.