- •Множества. Операции над множествами.
- •Законы алгебры множеств.
- •Мощность множества. Теорема о числе подмножеств конечного множества.
- •Бинарные отношения и их типы
- •Отношение эквивалентности. Теорема о разбиении множества на классы.
- •Перестановки и сочетания
- •Формулы о подсчете числа подстановок из сочетаний с повторениями и без повторений.
- •Высказывания. Операции над высказываниями.
- •Булевы функции
- •12. Законы равносильности. Доказать законы Де Моргана.
- •13. Формулы алгебры логики, их классификация и примеры.
- •14. Алгоритмы определения типа формулы.
- •15. Двойственные формулы. Принцип двойственности.
- •20. Сднф и алгоритмы ее построения.
- •21. Скнф и алгоритмы ее построения.
- •22. Теорема о разложении.
- •23. Контактные схемы.
- •24. Логические схемы.
- •26.Область истенности булевой фун-ции. Покрытие обл. Заданной в днф.
- •27.Метод Блейка,Нельсона, графический метод.
- •28. Минимальная днф. Метод инпликантных матриц.
- •29.Сокращенная днф. Теорема о связи сднф и мднф.
- •30. Тупиковая днф. Теорема о связи тднф и мднф
- •31.Алгоритмпостроения тупиковой днф
- •41. Квантор общности. Теорема о применении квантора общности для предиката определенном на конечном множестве.
- •42. Квантор существования. Теорема о применении квантора существования для предиката определенного на конечном множестве.
- •43. Законы алгебры логики предикатов.
- •44. Тождественно истинные предикаты, примеры. Теорема о тождественно истинных предикатах.
- •45. Тождественно ложные предикаты и теорема о тождественно ложных предикатах.
- •46. Понятие следствия и равносильности предикатов, примеры.
- •47. Формулы алгебры логики предикатов и их классификация.
- •48. Законы Де Моргана для алгебры логики предикатов.
- •49. Закон пронесения квантора общности через конъюнкцию.
- •50. Закон пронесения квантора существования через дизъюнкцию.
- •51.Закон пронесения квантора общности и существования через импликацию.
- •53. Детерминированные функции и графическое изображение (примеры).
- •54. Ограничено-детерминированные функции.
- •55. Диаграммы Мура.
- •56. Канонические уравнения ограничено-детерминированных функций.
- •57. Машины Тьюринга.
- •58. Простейшие функции. Теорема о простейших функциях.
- •59. Операция примитивной рекурсии. Примитивно-рекурсивные функции. Примеры.
- •60. Операция минимизации. Рекурсивные функции.
- •61. Тезисы Тьюринга и Черча. Теорема о связи между рекурсивными функциями и функциями вычислимыми по Тьюрингу (без доказательства).
- •62. Графы. Способы задания графов.
- •63. Формула Эйлера.
- •64. Графы к3,3 и к5,5. Теорема.
- •65. Плоские графы. Теорема о плоских графах (без доказательства).
- •66. Эйлеровые графы. Теорема о Эйлеровых графах. Гамильтоновы графы.
- •67. Деревья. Теорема о деревьях (без доказательства).
- •68. Предмет теории кодирования, алфавитное кодирование.
- •69. Префиксный код. Теорема о префиксном коде.
- •70. Разделимый код. Теорема Маркова (без доказательства).
Перестановки и сочетания
Если в некотором множестве А переставлять местами элементы, оставляя неизменным их количество, то каждая полученная таким образом комбинация называется перестановкой. Общее число перестановок из m элементов обозначается Pm и вычисляется по формуле:
Если из т элементов составлять группы по п элементов в каждой, не обращая внимания на порядок элементов в группе, то получившиеся при этом комбинации называются сочетаниями из т элементов по п. Общее число сочетаний находится по формуле:
Формулы о подсчете числа подстановок из сочетаний с повторениями и без повторений.
Число размещений с повторениями
Теорема: Число размещений с повторениями A’nr = nr.
Доказательство: В r-размещении (а1, a2,…,ar) элемент а1 в n-элементном множестве M можно выбрать n способами, элемент a2 – тоже n способами, наконец, элемент ar – n способами. По правилу произведения A’nr.
Следствие: Число перестановок с повторениями Cnr = n!/(r!(n-r)!).
Число сочетаний без повторений
Теорема: Число сочетаний без повторений Cnr = n!/(r! (n-r)!).
Доказательство: Каждому r-сочетанию (а1, a2,…, ar) n-элементного множества соответствует r! перестановок. Тогда число размещений A’nr = Cnrr! откуда и следует требуемая формула.
Число сочетаний с повторениями
Теорема: Число сочетаний с повторениями C’nr = C’n+1-r.
Доказательство: Каждому r-сочетанию из n-элементного множества M сопоставим набор (k1, k2,…, kn) из натуральных чисел, указывающих число повторов каждого элемента из M в выбранном сочетании. При этом k1 +k2 +…+ kn = r. Например, если M = {a,b,c,d,e}, то сочетанию (a,a,c,c,c,e,e) сопоставим набор (2,0,3,0,2), то есть элементы a,b,c,d,e множества M встречаются в сочетании (а,а,с,с,с,е,е) соответственно 2,0,3,0,2 раз. Каждому полученному набору (k1, k2, …, kn) сопоставим набор (l1, l2,…,ln), где li = k1 +1, i = 1,2,…, n. Тогда l1+l2+…+ln = k1+k2 +…+kn +n = r+n. Каждый полученный набор (l1, l2, …, ln) взаимнооднозначно соответствует числу n+r ненулевых слагаемых l1, l2,…,ln. Разделим n+r последовательно записанных звездочек вертикальными разделительными черточками на n непустых частей, состоящих соответственно из l1, l2,…,ln звездочек. Для нашего примера получим следующее разбиение:
* * * | * | * * * * | * | * * *
l1 =3 l2 =1 l3 =4 l4 =1 l5=3
k1 =2 k2 =0 k3 =3 k4 =0 k5=2
Каждому разбиению числа n+r на n ненулевых слагаемых взаимнооднозначно соответствует распределение n-1 разделителей, которые можно расставить в n+r-1 пробелах между звездочками Cn+r-1n-1 способами. Следовательно, число сочетаний с повторениями C’nr = Cn+r-1.
Высказывания. Операции над высказываниями.
Понятие «высказывание» является первичным, оно не определяется, а поясняется. Под высказыванием понимают предложение, о котором можно сказать одно из двух: истинно оно или ложно. Высказывания обозначаются малыми латинскими буквами x, y, z,…, а их значения, т.е. истину и ложь, соответственно 1 и 0. Все логические операции являются высказываниями. Логическая операция, соответствующая связке «и», называется конъюнкцией. Данное высказывание истинно тогда и только тогда, когда истинны оба высказывания x и y истинны Логическая операция, соответствующая связке «или», называется дизъюнкцией.
Данное высказывание истинно тогда и только тогда, когда хотя бы одно из высказываний x и y истинно. Логическая операция, соответствующая связке «не», называется отрицанием. Логическая операция, соответствующая связке «если … то», называется импликацией. Импликация двух высказываний x и y задается следующей таблицей истинности:
x |
y |
x_y |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
|
Логическая операция, соответствующая связке «тогда и только тогда, когда …» называется эквивалентностью и обозначается символом n. Данное высказывание истинно тогда и только тогда, когда оба
высказывания x и y или истинны или ложны.