Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
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. Определение NP-полной задачи. Примеры.
27. NP-полнота задачи 3-ВЫП.
28. NP-полнота задачи проверки совместности системы линейных неравенств в целых и 0-1 числах.
29. NP-полнота задачи проверки совместности системы полиномов Жегалкина.
30. Полиномиально быстрое решение сравнения с нулём полинома Жегалкина.
31. Определение P-SPACE-полной задачи. Примеры.
32. Определение элементарных по Кальмару функций (программ).
33. Определение примитивно-рекурсивных программ.
34. Определение паскалевидной функции. Примеры.
35. Нормальные алгоритмы. Примеры.
36. Алгоритмы Маркова-Поста. Примеры.
37. Рекурсивные алгоритмы Маркова-Поста. Примеры.
38. Простейшие теоремы о невозможности алгоритмов.
39. Алгоритмическая неразрешимость простейших массовых проблем.
40. Теорема о непродолжимости универсального алгоритма до всюду применимого.
41. Алгоритмическая неразрешимость проблемы применимости.
42. Алгоритмическая неразрешимость проблемы равенства слов в полугруппе.
43. Теорема Райса об инвариантных свойствах алгоритмов.
44. Неразрешимость исчисления предикатов.
45. Определение конструктивных вещественных чисел и операций над ними.
46. Правила сведения утверждения корректности программ.
47. Смешанные и конечнозначные логики.
48. Неполнота исчисления для доказательства применимости и неприменимости универсального алгоритма.