Математическая логика и теория алгоритмов

§ 18. Вопросы и темы для самопроверки 1. Эффективные и полуэффективные методы. 2. Дедуктивные теории, их классификация. 3. Свойства дедуктивных теорий: непротиворечивость, полнота, независимость аксиом, разрешимость. 4. Полуформальные аксиоматические теории. Пример такой теории - геометрия. В чем отличие геометрии Евклида от геометрии Лобачевского-Бойяи-Гаусса? 5. Формальные аксиоматические теории. Их задание, понятие вывода, теоремы, следствия. 6. Какие свойства выводимости знаете? 7. Исчисление высказываний. Задание. Конечно или бесконечно множество аксиом этой теории? 8. Является ли формула а=>а теоремой исчисления высказыва­ ний? 9. Указките, какие из следующих формул являются теоремами исчисления высказываний: a)1l5=>5; 6)fi=>ll5; в) 1у4=>(1^=>15); Г )1 Я =>Б; д) Ы=>(^=>Я); е) ж) (а =>В )=>(1 Я=>1 а); з) а-=^(\ 5 =>1 (а=:>в)); и) a=>b)=i>b); к) в. 10. Производные (доказуемые) правила вывода в исчислении высказываний. 11. Эквивалентность двух определений непротиворечивости для теорий, содержащих исчисление высказываний. 12. Непротиворечивость исчисления высказываний. 13. Полнота исчисления высказываний. 14. Независимость схем аксиом исчисления высказываний. 15. Разрешимость исчисления высказываний. 16. Другие аксиоматизации исчисления высказываний. 183