Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

1/^1 1/^2 • • • ^^1 ^^2 • • • \/Xi 1/^2 • • • ^У\ ^У2 ^^1 ^^2 • • • ^^ra- Эти классы удобнее записывать аббревиатурами V^3^, V^3V^, V^33V^ соответственно. Так как выяснение выполнимости двойственно выяснению логически об­ щезначимости, то имеем следующее. Следствие 2.1. Проблема выяснения выполнимости формул логики преди­ катов разрешима для класса чистых формул, которые в предваренной нормаль­ ной форме имеют префикс одного из следующих видов: 3^ \/3^\ 3^ VV3^ Теорема 2.13. Класс чистых формул, которые в предваренной нормальной форме имеют префиксы 333V или 3V3 не имеют общей разрешающей проце­ дуры для выяснения логической общезначимости, даже если в матрице форму­ лы содержатся не более чем двухместные предикатные буквы. Вопросы и темы для самопроверки 1. Понятие предиката. 2. Кванторы. Использование кванторов и предикатов для символизации языка. 3. Термы, элементарные формулы и формулы логики предикатов. 4. Свободные и связанные переменные. Замкнутые формулы. Замыкание формулы. 5. Интерпретация, выполнимые, истинные и ложные в данной интерпрета­ ции формулы. 6. Модель. 7. Свойства формул в данной интерпретации. 8. Логически общезначимые формулы. Выполнимые формулы. 9. Логическое следствие в логике предикатов. Равносильные формулы. 10. Правила перенесения отрицания через кванторы. 11. Можно ли переставлять рядом стоящие одноименные кванторы? 12. Можно ли переставлять рядом стоящие разноименные кванторы? 13. Определение предваренных нормальных форм. Для каждой ли форму­ лы логики предикатов существует предваренная нормальная форма? 14. Алгоритмы нахождения предваренных нормальных форм. 15. Формулировка проблемы разрешимости логики предикатов. 16. Существует ли метод позволяющий для любой формулы А логики пре­ дикатов за конечное число шагов выяснить А логически общезначима или нет? 17. Для каких подмножеств формул проблема разрешимости логики пре­ дикатов имеет решение? Упражнения 1. Какие из следующих выражений являются предикатами: а) число X - простое число; 51