- •4.3 Методы анализа графа. Поиск в ширину. Нахождение кратчайших путей в графе……………………………………………………………………………..…….………88
- •Введение
- •1.Элементы функциональной полноты в классе двоичных функций.
- •1.1 Основные двоичные функции и их своства. Булевой функцией f(x1 … xn) называют функцию, аргументы которой принимают значения из множества , и значение функции также из множества {0;1}.
- •Бинарная операция ассоциативна, если тождественно выполняется: ;
- •1.2 Утверждение о числе функций от n переменных.
- •1.3 Представление функции в виде совершенной дизъюнктивной и совершенной конъюнктивной формах. Разложение функции по начальному множеству переменных.
- •1.4 Утверждение о представлении двоичной функции в виде полинома Жегалкина .
- •1.5 Основные замкнутые классы двоичных функций относительно суперпозиций функций.
- •1.6 Критерий полноты в класее двоичных функций относительно суперпозиций функций.
- •I этап :
- •II этап :
- •II этап :
- •1.7 Предполные классы двоичных функций.
- •Все полные системы для классов t0, t1, s, m, l в утверждениях выше являются базисами для этих систем.
- •2 .Минимизация днф заданной функции.
- •2.1 Геометрическая интерпретация двоичных функций.
- •2.2 Утверждение о максимальных интервалах и тупиковых покрытиях.
- •1 Этап:
- •2 Этап:
- •2.3 Метод поиска всех максимальных интервалов заданной функции с помощью операции склеивания и сокращения.
- •2.4 Метод нахождения всех тупиковых покрытий максимальными интервалами.
- •Достаточно ясна связь задачи нахождения тупиковых покрытий и минимизации функции покрытия.
- •2.5 Метод построения сокращённой д.Н.Ф. С помощью обобщенного склеивания
- •3. Элементы математической логики. Исчисление высказываний, его полнота.
- •Семь теорем.
- •2) . Запишем аксиому а3 в следующем виде: вместо в подставим формулу а, а вместо а подставим
- •Доказательство полноты исчисления высказываний.
- •4 Графы
- •4.1 Неориентированные, ориентированные графы. Способы задания графов.
- •Представление графов
- •1. Задание графа с помощью матрицы смежности.
- •2. Задание графа с помощью матрицы инцидентности.
- •3. Задание графа с помощью списка смежности.
- •4.2 Азбука теории графов. Маршрут, путь, простой путь. Цикл. Простой цикл. Связность в графе.
- •Связные графы
- •4.3 Методы анализа графа. Поиск в ширину. Нахождение кратчайших путей в графе.
- •4.4 Поиск в глубину. Нахождение остовного дерева с помощью поиска в глубину.
- •4.5 Укладки графов. Планарные графы.
- •Теорема Эйлера
- •4.6 Критерий Понтрягина-Куратовского планарности графа.
- •4.7 Хроматическое число графа.
- •5 Элементы комбинаторики.
- •5.1 Упорядоченные наборы с повторением и без повторений.
- •Упорядоченные наборы а элементов n данных с возможными повторениями.
- •5.2 Неупорядоченные наборы элементов из данных без повторений.
- •5.3 Неупорядоченные наборы элементов из п данных с возможными повторениями.
- •5.4 Метод включения-исключения.
- •Упражнения.
- •5.5 Основы метода производящих функций.
- •5.6 Основы теории перечисления Пойа. Лемма Бернсайда.
- •Упражнения.
- •6 Основы схем из функциональных элементов. Проблема минимизации
- •6.1 Сложность мультиплексора порядка .
- •1) Мультиплексор порядка
- •6.2 Сложность дешифратора порядка n.
- •2) Дешифратор порядка .
- •6.3 Сложность универсального многополюсника.
- •3) Универсальный многополюсник.
- •6.4 Оценка сложности функций n переменных .
- •7. Элементы теории конечных автоматов.
- •7.1 Ограниченно- детерминированные функции и автоматные языки. Эквивалентность.
- •8. Элементы теории кодирования.
- •Теория кодирования.
- •8.1 Критерий однозначности кодирования.
- •8.2 Критерий префиксного кодирования Мак-Миллана.
1.5 Основные замкнутые классы двоичных функций относительно суперпозиций функций.
Функции сохраняющие ноль -T0 и функции
сохраняющие единицу- T1 .
T0 : T1:
T0 , T1
T0 , T1
T0 , T1
T0 , T1
T0 , T1
T0 , T1
T0 , T1
T0 , T1
Самодвойственные функции S .
Определение: называется самодвойственной, если совпадает с двойственной к ней функцией.
.
Очевидно эквивалентное определение самодвойственной функции:
Определение: S, если принимает противоположные значения на противоположных наборах.
x1 |
x2 |
x3 |
f(x1x2x3) S |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
Пример:
S S
S S
S S
S S
Монотонные функции M .
Определение: набор , если ;
Например:
наборы 0101 и 1001 не сравнимы.
Определение: M, если :
.
y
x1
x2
x
-
x1
x2
x3
f(x1x2x3) M
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
Метод определения монотонности функции f :
Рассматриваем все наборы, на которых значение . Для этих наборов рассматриваем наборы большие, и если среди больших наборов нет нуля функции, тогда функция монотонна. В противном случае она не монотонная. Корректность этого метода следует непосредственно из определения монотонной функции.
-
x1
x2
x3
f(x1x2x3) M
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
Для данной функции для единицы 001 большие наборы есть 101, 011, 111. Среди них есть ноль, набор 011. Поэтому функция немонотонная.
M M
M M
M M
M M
Линейные функции L .
Определение: линейные функции – функции, степень полинома Жегалкина которых не больше единицы .
Определение: степенью полинома Жегалкина называется максимальное число переменных в слагаемых этого полинома.
Степень равна 3.
Степень равна 1.
Степень 1 равна 0 ; степень 0 равна 0.
-
x1
x2
x3
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
0
1
1
1
1
0
1
Методы определения линейности функции f :
1.Способ Находим полином Жегалкина функции f и определяем его степень. Если степень , то функция линейная. В противном случае функция нелинейная.
2. Способ. Определяем существенные переменные функции f и рассматриваем две возможные линейные функции : сумма найденных существенных переменных и сумма существенных переменных плюс 1. Если исходная функция совпадает с одной из данных двух, то функция линейна. В противном случае функция нелинейная.
Корректность данного метода следует из факта, что у линейной функции все переменные существенные и других существенных нет.
1) x1 существенная (по 1-ому и 5- ому) ,x2 существенная (по 3- ему и по 1-ому набору), x3 не существенная . Если функция линейная, то она имеет вид либо x1+x2, либо x1+x2+1; подходит первое выражение, поэтому первая функция линейная.
-
0
0
0
1
0
1
1
0
1
0
1
0
1
1
0
1
вторая функция нелинейная
2) x1 существенная (по 4-ому и 8-ому),x2 существенная (по 6-ому и 8-ому), x3 не существенная :
-
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
вторая функция нелинейная
Утверждение: все перечисленные пять классов являются замкнутыми, то есть суперпозиция любых двух функций из каждого класса является функцией тогоже класса.
Доказательство :
1) T0
Рассмотрим T0
T0
Рассмотрим суперпозицию
и покажем, что полученная T0. Для этого найдем значение на нулевом наборе :
2) T1
Рассмотрим T1
T1
Рассмотрим :
3) S
Рассмотрим S
S
Рассмотрим :
4) М
Рассмотрим М
М
Рассмотрим суперпозицию
: и
рассмотрим произвольную пару сравнимых наборов и : и покажем, что выполнено : .
Нетрудно видеть, что из того, что следует, что и .
В силу того, что :
5) L
Рассмотрим L
L
, где α и β некоторые константы.
Рассмотрим .
.
Используя ассоциативность и коммутативность операции , преобразуем к виду :
.
Степень не превосходит 1, следовательно L.
Замечание Приведенные выше рассуждения будут справедливы, если множества переменных подставляемых функций пересекаются.
Упражнение Покажите, что переименование переменных не выводит функции из классов
.