- •Множества. Операции над множествами.
- •Законы алгебры множеств.
- •Мощность множества. Теорема о числе подмножеств конечного множества.
- •Бинарные отношения и их типы
- •Отношение эквивалентности. Теорема о разбиении множества на классы.
- •Перестановки и сочетания
- •Формулы о подсчете числа подстановок из сочетаний с повторениями и без повторений.
- •Высказывания. Операции над высказываниями.
- •Булевы функции
- •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. Разделимый код. Теорема Маркова (без доказательства).
59. Операция примитивной рекурсии. Примитивно-рекурсивные функции. Примеры.
Будем говорить, что (n+1) – местная функция f получается из n – местной функции g и (n+2) – местной функции h с помощью операции примитивной рекурсии, если при любых значениях x1, x2,…, xn выполняются равенства:
f(x1, x2,…, xn, 0) = g (x1, x2,…, xn)
f(x1, x2,…, xn, 1) = h(x1, x2,…, xn , 0, f(x1, x2,…, xn, 0))
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
f(x1, x2,…, xn, y+1 ) =h(x1, x2,…, xn, y, f(x1, x2,…, xn,y))
Эти равенства называют схемой примитивной рекурсии. И тот факт, что функция f получается из функций g, h c помощью операции примитивной рекурсии, записывается следующим образом: f=R(g,h).
Функция f называется примитивно рекурсивной функцией, если она получается из простейших функций с помощью операций суперпозиции и примитивной рекурсии, взятых конечное число раз в любой последовательности.
Из данного определения следует, что любая примитивно рекурсивная функция является числовой функцией.
Множество всех примитивно рекурсивных функций обозначим через Pn.p.
Пример . Доказать, что функция f(x,y)= x+y примитивно рекурсивна.
Действительно. Справедливы следующие тождества
f(x,0) =x+0 = x = g( x)
f(x,y+1) = x+(y+1) = (x+y)+1 = f(x,y)+1
Отсюда следует, что x+y = R(g(x) = x, h(x,y,z) = z+1). Так как функции g, h – простейшие функции, то x + y Pn.p.
60. Операция минимизации. Рекурсивные функции.
Будем говорить, что n-местная функция g(x1,x2,…,xn) полученная из (n+1)-местной функции f(x1,x2,…,xn,y) с помощью операции минимизации или оператора наименьшего числа, если для любых x1, x2,…, xn, y равенство g(x1,x2,…,xn) = y выполняется тогда и только тогда, когда:
f(x1,x2,…,xn,t) определено и f(x1,x2,…,xn,t) > 0 для любых 0 ≤ t < y;
f(x1,x2,…,xn,y) = 0.
Если какое-либо из условий 1), 2) будет невыполнено, то функция g(x1,x2,…,xn) не определена при наборе x1, x2,…, xn.. Короче говоря, величина g(x1,x2,…,xn) равна наименьшему значению аргумента y, при котором выполняется последнее равенство.
Используется следующее обозначение:
g(x1,x2,…,xn) = My [f(x1,x2,…,xn,y)=0].
Про функцию g говорят, что она получена из функции f при помощи операции минимизации.
Функция f называется частично рекурсивной функцией, если она может быть получена из простейших функций с помощью операции суперпозиции, примитивной рекурсии и минимизации, взятых конечное число раз в любой последовательности.
Класс частично рекурсивных функций обозначим Prp.
Обозначим через Pp – класс рекурсивных функций, т.е. всех числовых функций из Prp.
61. Тезисы Тьюринга и Черча. Теорема о связи между рекурсивными функциями и функциями вычислимыми по Тьюрингу (без доказательства).
Тезис Тьюринга: для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция является вычислимой по Тьюрингу, т.е. когда она может вычисляться на подходящей машине Тьюринга.
Тезис Чёрча: числовая функция тогда и только тогда алгоритмически вычислима, когда она рекурсивна.
Теорема: следующие классы функций (заданные на натуральных числах и принимающие натуральное значение) совпадают:
1) Класс всех функций вычислимых по Тьюрингу;
2) Класс всех рекурсивных функций.