VoprosyMatemat_logike2013

ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА

Федеральное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет водных коммуникаций»

Кафедра Комплексного обеспечения информационной безопасности

Дисциплина "Математическая логика и теория алгоритмов" ( ИЗ - I )

Специальность "090900.62 - Информационная безопасность" профиль "Безопасность автоматизированных систем"

Список вопросов

1. Свойства операций над множествами.

2. Отношения: инъекция, сюръекция, биекция, их свойства.

3. Отношение эквивалентности. Классы эквивалентности, их свойства.

4. Отношения частичного и линейного порядка. Теорема об изоморфизме частично упорядоч. множеств.

5. Равносильность формул. Основные свойства.

6. Основные тавтологии.

7. Правильные рассуждения. Основные схемы.

8. Двойственные формулы. Лемма. Теорема – принцип двойственности.

9. Теорема о представлении булевой функции формулой логики высказываний.

10. Полные системы связок.

11. Дизъюнктивная нормальная форма. Совершенная ДНФ. Теорема о представлении в ДНФ.

12. Теоремы о приведении к СДНФ и об единственности СДНФ.

13. Конъюнктивная нормальная форма. Совершенная КНФ. Теорема о представлении в КНФ.

14. Теорема о представимости булевых функций многочленами Жегалкина.

15. Приложение логики высказываний: к синтезу логических схем вычисл. устройств, и др.

16. Простейшие свойства выводимых формул в аксиоматических теориях (1- 8).

17. Вывод в теории Черча: .

18. Вывод в теории Черча: если , то .

19. Вывод в теории Черча: .

20. Вывод в теории Черча: .

21. Вывод в теории Черча: и .

22. Теорема о дедукции.

23. Правило силлогизма.

24. Вывод формулы: .

25. Правило перевертывания.

26. Производное правило вывода: .

27. Производное правило вывода: .

28. Производное правило вывода: .

29. Производное правило вывода: и .

30. Производное правило вывода: если , то

31. Производное правило вывода: если , то .

32. Лемма к теореме о полноте (в широком смысле).

33. Теорема о корректности АТЧ.

34. Теорема о полноте (в широком смысле).

35. Теорема о непротиворечивости.

36. Теорема о абсолютной непротиворечивости. Теорема об альтернативности АТ.

37. Частично–рекурсивные и примитивно–рекурсивные функции: ; .

38. Машина Тьюринга для простейших функций.

39. Машина Тьюринга для копирования слов.

40. Машина Тьюринга для удвоения чисел.

41. Машина Тьюринга для сложения двух чисел.