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