ПРИЛОЖЕНИЕ № 1. Перечень вопросов для проверки практических

навыков студентов по дисциплине «Математическая логика и теория алгоритмов»

1. Распознавание формул алгебры высказываний.
2. Метод истинностных таблиц в логике высказываний: построение таблиц истинности формул алгебры высказываний, доказательство эквивалентности формул, выяснение тождественной истинности (ложности), выполнимости (опровержимости) формулы.
3. Распознавание формул алгебры логики.
4. Метод истинностных таблиц в алгебре логики: построение таблиц истинности булевых функций, доказательство эквивалентности формул, выяснение тождественной истинности (ложности), выполнимости (опровержимости) формулы.
5. Основные эквивалентные формулы алгебры логики. Доказательство эквивалентности, упрощение формул алгебры логики, выяснение тождественной истинности (ложности), выполнимости (опровержимости) формулы методом эквивалентных преобразований.
6. Приведение булевой функции к ДНФ.
7. Приведение булевой функции к СДНФ по таблице истинности и алгебраически.
8. Приведение булевой функции к КНФ.
9. Приведение булевой функции к СКНФ по таблице истинности и алгебраически.
10. Приведение булевой функции к полиному Жегалкина методом неопределённых коэффициентов и с помощью эквивалентных преобразований.
11. Построение двойственных функций по определению и с помощью принципа двойственности.
12. Реализация булевой функции релейно-контактной схемой. Параллельно-последовательные схемы.
13. Реализация булевой функции релейно-контактной схемой методом каскадов.
14. Нахождение по релейно-контактной схеме булевой функции, которую она реализует.
15. Построение интерпретаций формул логики предикатов.
16. Доказательство и опровержение общезначимости формул в частных случаях.
17. Эквивалентные формулы логики предикатов.
18. Эквивалентные преобразования формул логики предикатов.
19. Доказательство производных правил вывода и теорем теории исчисления высказываний.
20. Доказательство теорем других теорий исчисления высказываний (Россера, Гильберта-Аккермана, исчисления секвенций, интуиционистской).
21. Доказательство производных правил вывода и теорем теории исчислений предикатов.
22. Доказательство теорем исчисления предикатов методом резолюций.
23. Доказательство примитивной рекурсивности, частичной рекурсивности и общерекурсивности некоторых арифметических функций.
24. Восстановление явного вида функции по схеме примитивной рекурсии.
25. Нахождение конечных конфигураций машин Тьюринга при заданных начальных конфигурациях.
26. Распознавание применимости машины Тьюринга к начальному слову.
27. Определение вычисляемой функции по программе машины Тьюринга.
28. Построение машин Тьюринга, вычисляющих заданные функции и осуществляющих определённые преобразования начальных слов.