- •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.Способы представления деревьев
38. Класс функций, сохраняющих значение 0.
Т0 – класс бул. ф-ций сохраняющих 0:
fT0 <=> f(0,…,0)=0.
входят: 0, x, x&y, xy.
невходят: 1, x, xy, , , .
Число ф-ций входящих в класс Т0 равно 2(2^n)-1
Класс Т0 – замкнут: [T0]=T0.
Для док-ва класса Т0 достаточно показать, что элементарная суперпозиция ф-ций из класса Т0 также принадлежат Т0:
Ф(x1,x2,…xn)=f0(f1(…),…fk(…))T0, т.е.
Ф(0,…,0)=f0(0,…,0)=0, что верно.
Поэтому [T0]=T0.
39. Класс функций, сохраняющих значение 1.
Т1 – класс бул. ф-ций сохраняющих 1:
fT1 <=> f(1,…,1)=1.
входят: 1, x, x&y, xy, xy, xy.
невходят: x, xy, xy, xy.
Класс Т1 – замклут: [T1]=T1.
Для выполнения этого достаточно показать, что элементарная суперпозиция ф-ций из Т1 также принадлежит Т1.
Ф(x1,x2,…xn)=f0(f1(…),…fk(…)), f0, f1,…,fkT1.
Ф(1,…,1)=f0(f1(1),…,fk(1))=f0(1,…,1)=1, т.е. ФТ1.
40. Принцип двойственности. Класс самодвойственных функций.
Класс самодвойст. ф-ций: f*=f
fS <=> f*=f.
входят: x, x.
невходят: 0, 1, , &, , , .
Из определения самодвойственной ф-ции следует, что для ее задания достаточно определить значения f только для половины наборов, поэтому: |S|=2(2^n)/2.
Класс самодвойст. ф-ций замкнут: [S]=S.
Ф(x1,x2,…xn)=f0(f1(…),…fk(…))
Ф*(x1,x2,…xn)=f0*(f1*(…),…fk*(…))
по принципу двойственности.
Ф*(x1,x2,…xn)=f0(f1(…),…fk(…))=Ф(x1,x2,…xn). T.к. fi (i=1,k) – самодв.: fi*=fi.
Лема о несамодвойственных ф-ях: Если ф-ция f не самодв., то из нее путем подстановки вместо переменных тождественных ф-ций и отрицания можно получить константу.
Док-во: Пусть f*f, т.е. f*=f(x1,…xn)f(x1,…xn) или набор (1,…,n): f*(1,…,n)f(1,…,n), f(1,…,n)=f(1,…,n)
Построем ф-цию (x)=f(x1,x2,…,xn). Ф-ция получена из f в результате подстановки вместо аргументов тождественной ф-ции или отрицания
(1)=f(f1,f2,…,fn), 1i={(1, если i=1), (0, если i=0)} т.е. 1i=i, тогда (1)=f(1,2,…,n)=f(1,2,…,n) =f(01,02,…,0n)=(0) т.е. – константа. ч.т.д.
41. Класс монотонных функций.
М – класс монотонных ф-ций.
Пусть =(1,…,n) и =(1,…, n).
Набор меньше набора (<), {(< – такой треугольничек)} если 11, 22,…,nn. Например: (1001)<(1011).
< – рефликсивно, транзитивно, антисиметрично, т.е. это отношение частичного порядка, но в общем случае не линейного порядка. Ф-ция f наз. монотонной, или всегда из того, что < следует f()f().
входят: 0, 1, x, &, .
невходят: x, , , .
Для проверки ф-ции на монотонность необходимо проверить, что f()f() для всевозможных пар сравнимых наборов.
Класс мон. ф-ций замкнут: [M]=M.
Соотношение < индуцирует это же соотношение на всевозможных поднаборов и .
(j1, j2, …,jij)<(j1, j2, …,jij).
Пусть i=fj(j1, j2, …,jij), i=fj(j1, j2, …,jij) тогда из того, что fjM, ij (j=1,k), т.е. < но f0M т.е. f0()f0(), а, значит Ф()Ф(). ч.т.д.
Лема о немонотонных ф-циях: Если ф-ция f немонотонна, то из нее путем подстановки вместо переменных констант и тождественной ф-ции можно подставить отрицание.
Пусть fM т.е. <: f()<f(), поэтому f()=1, f()=0. Покажем, что найдутся два соседних набора (по некоторой переменной) и такие, что <, а f()>f(). Предположим обратное: пусть < и они отличаются, например, по первым t переменным.
=(0, 0, …, 0, t+1,…,n)
=(1, 1, …, 1, t+1,…, n)
По и построим последовательность наборов (0)=, (1) – соседний с (0) по 1-й переменной, (2) – по 2-й переменной и т.д., (t)=.
=(0)<(1)<…<(t)=, причем f((0))>f((t)), поэтому в этой последовательности найдутся два соседних набора (i)<(i+1), а f((0))>f((i+1)).
Поэтому будем предпологать, что и – два соседних набора, для которых нарушается монотонность. Эти наборы можно найти по таблице истинности. Построим ф-цию (x)=( 1,…,i-1,x,i+1,…,n) (наборы и соседние по х).
(0)=( 1,…,i-1,0,i+1,…,n)=f()=1
(1)=( 1,…,i-1,1,i+1,…,n)=f()=0
т.е. (x)=x ч.т.д.