Фрагмент (логика)
В математической логике фрагмент на логического языка или теории — это подмножество этого логического языка, полученное путем наложения синтаксических ограничений. язык [1] Следовательно, правильно построенные формулы фрагмента являются подмножеством формул исходной логики. Однако семантика формул во фрагменте и в логике совпадают, и любая формула фрагмента может быть выражена в исходной логике.
Вычислительная сложность задач типа выполнимости или проверки модели для логического фрагмента не может быть выше аналогичных задач в исходной логике, так как происходит редукция от первой задачи к другой. Важной проблемой вычислительной логики является определение фрагментов известных логик, таких как логика первого порядка , которые являются максимально выразительными, но при этом разрешимы или, что более важно, имеют низкую вычислительную сложность. [1] Область описательной теории сложности направлена на установление связи между логикой и теорией вычислительной сложности путем выявления логических фрагментов, которые точно охватывают определенные классы сложности . [2]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Брэдли, Аарон Р.; Манна, Зохар (2007), Вычислительный анализ: процедуры принятия решений с применением к проверке , Springer, стр. 70, ISBN 9783540741138 .
- ^ Эббингауз, Хайнц-Дитер; Флум, Йорг (2005), «Глава 7. Описательная теория сложности», Теория конечных моделей , Перспективы математической логики, Springer, стр. 119–164, ISBN 9783540287889 .
 | Эта логике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |