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

• Название: Математическая логика и теория алгоритмов
• Дата: 26.04.2023
• Размер: 15.94 Kb.
• Имя файла: MLTA_exam_questions_VSA.docx
• Тип: Экзаменационные вопросы; #1092548

Экзаменационные вопросы.

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Лектор Волощук С.А.

1. 
   Множество и его подмножества. Способы задания. Эквивалентность множеств.
   
2. 
   Области определения и значения отображения. Виды отображений. Обратное отображение.
   
3. 
   Счетные и несчетные множества. Множество-степень. Противоречия наивной теории множеств.
   
4. 
   Булева алгебра подмножеств данного множества. Аксиомы булевой алгебры.
   
5. 
   Характеристические векторы подмножеств. Теорема о взаимно однозначном соответствии между подмножествами и их характеристическими векторами.
   
6. 
   Алгебра булевых векторов. Алгебра высказываний. Изоморфизм булевых алгебр.
   
7. 
   Определение и способы задания булевых функций.
   
8. 
   Теорема о числе булевых функций от n-переменных.
   
9. 
   Вес БФ, расстояние между БФ.
   
10. 
    Основные и элементарные булевы функции.
    
11. 
    Фиктивные и существенные переменные. Способы определения фиктивности.
    
12. 
    Суперпозиция булевых функций. Арность функций. Понятие формулы. Выражение элементарных булевых функций через основные.
    
13. 
    ДНФ.
    
14. 
    Нормальные формы. СДНФ и СКНФ. Теорема о существовании и единственности СДНФ.
    
15. 
    Алгоритмы преобразования формулы к виду СДНФ.
    
16. 
    Принцип двойственности. Следствие.
    
17. 
    Теорема о существовании и единственности СКНФ.
    
18. 
    Алгоритмы преобразования формулы к виду СКНФ.
    
19. 
    Ранг ДНФ. Минимизация ДНФ. Тривиальный алгоритм минимизации ДНФ.
    
20. 
    Определение интервала и максимального интервала для булевой функции. Сокращенная ДНФ.
    
21. 
    Теорема о неизбыточности минДНФ.
    
22. 
    Геометрический смысл задачи минимизации ДНФ. Ядровые коньюнкции и ядро булевой функции. Связь между ядром и минимальной ДНФ. Алгоритм отыскания минимальной ДНФ.
    
23. 
    Метод карт карно для отыскания минимальной ДНФ.
    
24. 
    Метод Квайна для отыскания минимальной ДНФ.
    
25. 
    Контактные схемы. Оценка Шеннона максимальной сложности КС.
    
26. 
    Теорема о существовании и единственности многочлена Жегалкина для булевой функции.
    
27. 
    Существенность переменных входящих в многочлен Жегалкина.
    
28. 
    Алгоритмы нахождения многочлена Жегалкина.
    
29. 
    Функционально полные системы функций. Две теоремы о функциональной полноте.
    
30. 
    Производная БФ.
    
31. 
    Вес производной БФ. Смешанная производная БФ.
    
32. 
    Производная БФ по набору аргументов. Ее свойства.
    
33. 
    Расширенное понятие дифференциала БФ для произвольной двуместной логиче­ской операции.
    
34. 
    Интеграл БФ. Расширенное понятие интеграла БФ.
    
35. 
    n-кратное интегрирование {0} для получения БФ f(x_1,x₂).
    
36. 
    Использование аппарата интегро-дифференциального исчисления БФ в криптографии.
    
37. 
    Понятие замкнутого класса функций. Пять важнейших замкнутых классов функций.
    
38. 
    Лемма о несамодвойственной функции.
    
39. 
    Лемма о немонотонной функции.
    
40. 
    Лемма о нелинейной функции.
    
41. 
    Теорема Поста о функциональной полноте.
    
42. 
    Высказывания. Таблицы истинности.
    
43. 
    Семантические таблицы Бета. Доказательство по Бету. Опровержение по Бету.
    
44. 
    Аксиомы логики высказываний. Правило вывода. Теорема о подстановке Эквивалентных формул.
    
45. 
    Дизъюнкты, резольвента. Резолютивный вывод из множества дизъюнктов.
    
46. 
    Метод резолюций в логике высказываний.
    
47. 
    Предикаты. Кванторы. Операции навешивания кванторов. Основные равносильности содержащие кванторы.
    
48. 
    Нормальные формы в логике предикатов.
    
49. 
    Метод семантических таблиц в логике предикатов.
    
50. 
    Метод резолюций в логике предикатов.
    
51. 
    Определение и способы задания конечных автоматов.
    
52. 
    Алгоритм задания автомата системой булевых функций.
    
53. 
    Реализация конечных автоматов схемами.
    
54. 
    Автоматы Мура. Триггеры.
    
55. 
    Основные соединения автоматов.
    
56. 
    Достаточные условия автоматной полноты.
    
57. 
    Структурный синтез автоматов.
    
58. 
    Определение и способы задания машины Тьюринга.
    
59. 
    Вычисления на машинах Тьюринга. Функции вычислимые по Тьюрингу.
    
60. 
    Вычислимость суперпозиции и разветвления на машинах Тьюринга.
    
61. 
    Частичные функции. Операции примитивной рекурсии, суперпозиции и минимизации.
    
62. 
    Элементарные частичные функции. Частично – рекурсивные функции.
    
63. 
    Геделевская нумерация
    
64. 
    Нормальный алгоритм Маркова.
    
65. 
    Понятие алгоритма и его характеристические свойства.
    
66. 
    Вычислимость по Тьюрингу частично – рекурсивных функций. Тезис Черча – Тьюринга. Примеры неразрешимых по Тьюрингу проблем.