- •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. Примеры логических функций.
- •29. Представление булевых функций формулами.
- •30. Представление булевых функций формулами. Примеры.
- •31. Разложение булевых функций по переменным. Теорема.
- •32. Совершенная дизъюнктивная нормальная форма
- •33. Эквивалентные преобразования. Доказательство.
- •34. Правила подстановки, замены.
- •35. Некоторые эквивалентные преобразования.
- •36. Приведение дизъюнктивной нормальной формы к совершенной дизъюнктивной нормальной форме.
- •37. Замкнутые классы. Свойства замыкания.
- •38. Класс функций, сохраняющих значение 0.
- •39. Класс функций, сохраняющих значение 1.
- •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. Операции с частями графа.
- •67. Маршруты, цепи, циклы.
- •68. Связные компоненты графа.
- •69. Расстояния в графе.
- •70. Диаметр, радиус, центр графа.
- •71. Произведение графов.
- •72. Прямое произведение графов.
- •73. Эйлеровы циклы.
- •74. Теорема Эйлера.
- •75. Эйлеровы цепи.
- •76. Гамильтоновы циклы.
- •77. Некоторые классы графов и их частей. Дерево и лес.
- •78. Концевые вершины и ребра.
- •82. Цикломатическое число графа.
- •83. Ориентированные графы. Пути и циклы в ориентированном графе.
- •86.Деревья
- •49.Функциональная полнота. Теорема Поста
- •94. Блок-схемы алгоритмов
- •95.Машины Тьюринга. Основные определения.Машина
- •96.Машины Тьюринга.Сложение
- •96.Машины Тьюринга.Копирование
- •80.Типы вершин
- •84.Начальные и конечные вершины. Ранги вершин
- •90. Бінарне дерево
- •79. Дерево с корнем. Ветви.
- •81. Центры деревьев. Теорема.
- •85. Отношение достижимости. Базисный граф
- •88.Способы представления деревьев
29. Представление булевых функций формулами.
Функции называются выражением, описывающие суперпозицию элементарных функций.
Суперпозицией будем называть функцию f, полученную в результате подстановок функций друг в друга и переименования переменных. Переменные, от которых зависит функция называют формулами имеющими глубину 0.
f(x1x2). Функция зависящая от переменных формулой глубины 1. Соответственно функция f(f1,f2..fn) будет иметь глубину k если она зависит от функций глубины k-1.
Для записи формул используют знаки операций(конъюнкция, сложение по модулю 2, Стрелка Пирса, импликация и тд).
Обычно для булевых функций используется инфиксная запись.
Функция каждому набору аргументов ставит в соответствие значение и следовательно может служить способом описания функции. Табличное представление функции является единственным способом. Для задания функции формулой можно использовать различные записи.
30. Представление булевых функций формулами. Примеры.
Функции называются выражением, описывающие суперпозицию элементарных функций.
Суперпозицией будем называть функцию f, полученную в результате подстановок функций друг в друга и переименования переменных. Переменные, от которых зависит функция называют формулами имеющими глубину 0.
f(x1x2). Функция зависящая от переменных формулой глубины 1. Соответственно функция f(f1,f2..fn) будет иметь глубину k если она зависит от функций глубины k-1.
Для записи формул используют знаки операций(конъюнкция, сложение по модулю 2, Стрелка Пирса, импликация и тд).
Обычно для булевых функций используется инфиксная запись.
Функция каждому набору аргументов ставит в соответствие значение и следовательно может служить способом описания функции. Табличное представление функции является единственным способом. Для задания функции формулой можно использовать различные записи.
31. Разложение булевых функций по переменным. Теорема.
Пусть x={x, если =0; x, если =1;}.
Ф-и вида хi1i1 хi2i2 …хikik=K наз. элементарной коньюнкцией. Сумма элеменнтарных коньюнкций наз. дизъюктивной нормальной формой: ti=1Ki.
Ф-ции вида хi1i1 хi2i2 …хikik=D наз. элементарной дизъюнкцией. Произведение эл. дизъюнкций наз. коньюктивной нормальной формой: &ti=1 Di.
Теорема о разложении бул. ф-ций по переменным: Любую бул. ф-цию можно представить в виде: f(x1, x2, …xn)= f(1, …k ,xk+1, …,xn) (1). (Разложение функции по первым к переменным).
Док-во: f(1, 2, …n)=f(1, …k ,xk+1, …,xn)=f(1, 2, …n). В правой части (1) коэф. при ф-и f будет равен 1 только в единственном случае, когда i=i =xi (i=1,k).
Часные случаи:
1)Разложение по одной переменной:
f=(x1, x2, …xn)=1х11 f(1,x2, …,xn)=х10f(0,x2, …,xn) х11f(1,x2, …,xn)= х1f(0,x2, …,xn) х1f(1,x2, …,xn).
2)Разложение по всем переменным:
f=(x1, x2, …xn)=(1, 2,…, n) х11х12…х1n f(1, 2,…,n)=(1,…, n)(f(1,…, n)=1) х11х12…х1n (2).
Такое представление наз. совершенной дизъюктивной нормальной формой (СДНФ). Представление ф-ции в виде СДНФ конструктивно и его можно построить по таблице истинности: выделяются строки, в которых строки принимают единичное значение и по каждой из них строится элементарная коньюнкция, которые затем складываются.
Если f=(x1, x2, …xn)0, то ее также можно представить в виде ДНФ: f=(x1, x2, …xn)=х1х1. Любую бул. ф-цию можно представить в виде ф-лы над мн-вом ф-ций D={&,,}, например, в виде ДНФ.