32. Теорема Поста - Яблонского

Для того, чтобы система ФАЛ была полной необходимо и достаточно, чтобы она содержала функцию:

1) не сохраняющую ноль;

2) не сохраняющую единицу;

3) нелинейную;

4) немонотонную;

5) несамодвойственную.

33. Обозначим через P₂ множество всех функций алгебры логики.

Класс функций R<P₂ называется функционально-замкнутым, если любая суперпозиция функций этого класса R принадлежит этому же классу.

1) Класс функций, сохраняющий константу 0 (К₀): f(0)=0

2) Класс функций, сохраняющий константу 1

3) Класс самодвойственных функций (К_с): Функция, f*(x₁x_2…x_n), удовлетворяющая условию f*(x₁x_2…x_n)= ¬(f(¬x₁¬x_2…¬x_n)), называется двойственной по отношению к функции f(x₁x_2…x_n). Очевидно, что (f*)*=f, т.о., если f*=g’, то g*=f, т.е. множество булевых функций разбивается на пары взаимо-двойственных функций.

4) Класс линейных функций (К_л). Функцию алгебры логики вида f(x₁x_2…x_n) называют линейной, если ее канонический полином Жигалкина имеет вид многочлена первой степени: f(x₁x_2…x_n)=k₀⊕k₁x₁⊕k₂x₂⊕…k_nx_n, аналогично обычному алгебраическому многочлену первой степени, но с коэффициентом K_i в виде 0 или 1.

5) Класс монотонных функций (К_м): Функция f(x₁x_2…x_n) называется монотонной, если для любых двух элементов α, β∈Вⁿ, сравнимых между собой, из (α₁α₂… α_n)≺(β₁ β₂… β_n) следует, что f(α₁α₂… α_n)≺f(β₁ β₂… β_n)

34. Предикаты – обширный класс высказываний, описываемый с помощью формальных теорий. Под предикатом понимают произвольную функцию P, заданную на произвольном промежутке M. Отрицанием предиката P(x….) называется предикат так же определённый на множестве D и истинный при тех значениях переменной Х, при которых P(x…) ложный.

Конъюнкция предикатов Р(х…) и Q(х….) есть новый предикат, определённый на множестве D и истинный при тех значениях переменной Х, при которых истинны одновременно оба предиката.

Дизъюнкция предикатов Р (х…) и Q(х…) называется предикат , определённый на множестве D и истинный при тех значениях переменной Х, при которых истинен хотя бы один из предикатов.

Импликация предиката Р (х…) в Q (x…) называется предикат, определённый на множестве D и ложный только при тех значениях переменной Х, при которых предикат Р(х…) истинен, а предикат Q (x…) ложен.

Эквиваленция предикатов P(x…) и Q(x…) называется предикат, определённый на множестве D и истинный при тех значениях переменной X , при которых оба предиката истины, либо ложны.

35. Формальная теория S=<A,F,P,R> называется исчислением предикатов первого порядка, если заданы алфавит, формулы, аксиомы и правила вывода.

-алфавит – предметный переменные, постоянные переменные, символы логических операций. - формулы. - аксиомы. - правило вывода – законы алгебры логики.

36. С помощью ММИ определяются сложение и умножение натуральных чисел, свойства этих операций, вводятся отношения «больше» и «меньше» и их свойства, доказываются делимость и формула для степени бинома. Смысл ММИ заключается в применении аксиомы Псано в виде некоторого алгоритма:

1. Утверждение проверяется для некоторого начального элемента, например для n=1.

2. Формулируется гипотеза о том, что утверждение справедливо для некоторого kеN.

3. Доказывается (устанавливается истинность утверждения), что если из того, что утверждение справедливо для произвольного keN следует, что оно справедливо и для любого k+1 справедливо для любого натурального числа.

37. Автомат – абстрактная модель устройства, функционирующего в дискретном времени, которая перерабатывает последовательность входных сигналов в выходные сигналы.

Автоматом принято называть устройства, выполняющие процессы приёма, преобразования и передачи энергии, материалов или информации в соответствии с заложенной в них программой, но без непосредственного участия человека.

По виду деятельности автоматы делятся на :

Информационные – справочные таблицы, информационное табло, аварийная сигнализация. Управляющие – конвейер, автоматические шлагбаумы, управление лифтом. Вычислительные – микрокалькуляторы, процессоры.

38. Аналитический – с помощью системы уравнений. Табличный – таблицы переходов автоматов Мили и Мура Графический – задание с помощью ориентированного графа – более удобная и компактная форма описания автомата. Граф содержит вершины, дуги – переходы автомата из одного состояния в другое. На дугах принято указывать пары входных и выходных сигналов – сигналов переходов.

39. Графом называется пара 2-х конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек.

Если ребро графа соединяет две его вершины, то говорят, что это ребро им инцидентно.

Две вершины графа смежные, если существует инцидентное им ребро.

Если граф имеет ребро, у которого начало и конец совпадают, то это ребро называется петлёй.

Если рёбра смежные, то они имеют общую вершину.

Граф может иметь рёбра с одинаковыми парами вершин, эти рёбра называются кратными или параллельными.

40. Количество пар одинаковых вершин называется кратностью ребра.

Число рёбер, инцидентных вершине, называется степенью этой вершины и обозначается deg (A).

Если вершине инцидентна петля, она даёт вклад в степень , равный двум, т.к. оба конца приходят в эту вершину.

Вершина графа, имеющая степень, равную нулю, называется изолированной.

Вершина графа , имеющая степень, равную 1, называется висячей.

Вершина называется чётной (нечётной), если её степень чётное (нечётное) число.

41. Граф, состоящий из изолированных вершин, называется нуль-графом.

Граф называется полным, если любые две его различные вершины соединены одним и только одним ребром.

Дополнением графа, называется граф с теми же вершинами , что и начальный, имеющий те и только те рёбра, которые необходимо добавить, чтобы он стал полным.

42. Если все пары вершин во множестве Х являются упорядоченными, то граф ориентированный или направленный.

Степенью входа (выхода) вершины ориентированного графа называется число рёбер, для которого эта вершина является концом (началом). Степень входа deg+ , а выхода deg -.

Последовательность рёбер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего , называется маршрутом.

Цикл в орграфе – путь, у которого начало и конец совпадают.

Путь – упорядоченная последовательность рёбер орграфа, в которой конец предыдущего ребра совпадает с началом следующего и все рёбра единственны.

Если ребро встречается один раз, то такой маршрут называется цепью.

Мост – это линия, соединяющая два графа при удалении которой графы становятся отдельными.

Расстояние – минимальная длина из всех возможных маршрутов между этими вершинами при условии, что существует хотя бы 1 такой маршрут.

43. Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут. Две вершины связные, если существует маршрут между ними.

Планарный граф, если существует изоморфный граф, в изображении которого на плоскости рёбра пересекаются только в вершинах. Иными словами, у планарного графа никакие два ребра не имеют общие точки, кроме общих вершин.

Изоморфные графы, если существует взаимно-однозначное соответствие между рёбрами и вершинами, причём соответствующие рёбра соединяют соответствующие вершины.

44. Объединение, пересечение, кольцевая сумма

45. Способы задания Графа:

• Табл Инцидентности

• Матрица Смежности

Табл Инцидентности B состоит из n (вершин) строк и m (Рёбер) столбцов в которой:

1)Для неориентированного графа:

Bij = 1 если вершина Vi инцидентна ребру Xj

Bij = 0 если вершина Vi не инцидентна ребру Xj

2)Для ориентированного графа:

Bij = 1 если вершина Vi начало дуги Xj

Bij = 0 если вершина Vi yt инцидентна дуге Xj

Bij = -1 если вершина Vi конц дуги Xj

Матрица смежности А состоит из (вершин)строк и (вершин) столбцов в которой:

Aij = 1 если вершины (Vi, Vj) пренадлежат ребру X

Aij = 0 если вершины (Vi, Vj) не пренадлежат ребру X

46. Деревом называется конечный связанный граф с выделеной вершиной (корни) и неимеющий циклов

Для каждой пары вершин дерева (узлов) существует единственный маршрут по этому вершины будем классифицировать по степени удалённости от корня

Расстоянием до корневой вершины Vo назовём ярусом S вершины V

S=d(Vo Vn)

Граф G является деревом только тогда гогда выполняется хотябы 1 из условий:

1)Граф G связан и несодержит циклов

2)Граф G не содержит циклов и имеет n-1 ребро

3)Граф G связан и имеет n-1 ребро

4)Граф G не содержит циклов но добавление ребра между не смежными вершинами приводит к появлению 1 и только 1 цикла

5)Граф G связный но утрачивает это свойство после удаления 1 ребра. В графе G всякая пара вершин соединена цепью и только 1.

Дерево с n вершинами имеет n-1 ребро поэтому оно будет min связным графа.

Висячие вершины дерева будем называмь листьями.

Пусть G1,G2.....Gk непересекающееся подмножество деревьев, тогда упорядоченое объединение деревьев G=......... представляют собой несвязный граф который называется лесом .

(Остовом T связного графа G назовём любой его подграф содержаший все вершины графа и вляющийся деревом.Кодеревом T' остова T графа G назовём дополнение T до G тоесть такой подграф Который содержит толькоте рёбра которые не входят в T.)

Каждая вершина дерева называется узлом, причём каждый узел имеет n поддеревьев и является деревом, тогда узел без поддеревьев называется листом и является весячей вершиной.

Узел катово яруса называется отцом к+1 яруса если они смежные.

Узел к+1 называется сыном кзла катого яруса если они смежные .

2 укзла имеющие 1 отца называются братьями.

Упорядоченым деревом называется дерево в котором поддеревья каждого узла образуют упорядоченое подмножество

Бинарное дерево- это дерево у которого либо является листом либо образуют 2 поддерева.

Строго бинарное дерево называется граф у которого каждый узел не является листом и содержит 2 и только 2 поддерева

Бинарное дерево называется полным если каждый его узел уровня n является листом a каждый узел уровня меньше n имеет непустое левое и правое поддерево.

Граф называется взвешаным или сетью если каждому его ребру поставлено в соотведствие некоторое число (вес).

47. Теория кодирования. Шифрование данных. Криптография.

48. Алгоритм метода Хаффмена. Пример.

49. Алгоритм метода Фано. Пример.

50. Алгоритм кода Хэмминга. Пример