Экзаменационные вопросы.МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВЛектор Волощук С.А.

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. 
    Элементарные частичные функции. Частично – рекурсивные функции.
    <

---

Смотрите также файлы

• Сон и бодрствование.docx

• Натурфилософия эпохи Возрождения (Н. Коперник, Дж. Бруно, Г. Галилей).docx

• Практическая работа Часть 1 Тема Особенности содержания обновленных фгос ооо, фгос соо.docx

• Междисциплинарная курсовая работа по направлению 44. 03.docx

• Докладовпрезентаций Понятия сервис для клиента.docx