- •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.6 Критерий полноты в класее двоичных функций относительно суперпозиций функций.
Для того, чтобы система была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти классов: T0, T1 , S, M, L.
Проблема полноты : по заданной системе функции ответить на вопрос, является ли эта система полной, т.е. можно ли с помошью всевозможных суперпозиций данных функций получить любую булевую функцию.
Проверим вначале критерий Поста на известных примерах, а затем докажем его справедливость в общем случае.
Пример: .
По теореме о представлении любой булевой функции в виде СДНФ данная система полна. И в тоже время система не содержится ни в одном из классов T0, T1 , S, M, L, поэтому критерий Поста справедлив для данной системы.
Пример:
Полнота данной системы следует из теоремы о представлении любой булевой функции в виде полинома Жегалкина, и вновь критерий Поста справедлив для данной системы, т.к. система не принадлежит ни одному из пяти классов.
Пример: не полная, так как
и критерий Поста справедлив для данной системы, т.к. L.
Доказательство:
Необходимость : пусть система K полна.
Покажем, что она не принадлежит ни одному из пяти классов. Допустим противное : система принадлежит одному из пяти классов. Пусть K T0 .Т.е. все функции K сохраняют 0. Но тогда и любая суперпозиция функций из K будет сохранять 0. Но тогда [K] , и K неполная. Пусть K T1, тогда любая суперпозиция из K сохраняет 1, тогда [K]. Пусть K S, тогда суперпозиция любых функций будет самодвовойственна, тогда [K].
Пусть K M, тогда [K]. Пусть K L, тогда [K]. Получаем противоречие (система не является полной, в силу замкнутости классов T0, T1, S, M, L относительно суперпозиций).
Достаточность : пусть система K не содержится ни в одном из пяти классов, т.е.
Построим заведомо полную систему .
I этап :
II этап :
I этап: и , и переименуем все их переменные в : и :
-
X
f0
f1
0
1
1,0
1
1,0
0
Теперь имеем четыре возможных случая в зависимости от значений функций и в 1 и в 0 соответственно.
1)
2)
3)
4)
Простейшими окажутся 1) и 4).
Рассмотрим 1) и 4) случаи.
1 случай :
-
X
f0
f1
0
1
1
1
1
0
т.е .
4 случай :
-
X
f0
f1
0
1
0
1
0
0
т.е .
Остались 2) и 3)
2 случай :
-
X
f0
f1
0
1
0
1
1
0
т.е .
Построим вывод :
.
M , следовательно по определению существует пара наборов (нижний строго больше верхнего), а значение функции наоборот :
Разобьем множество переменных на два множества и .
- переменные, которые не изменяются в двух данных наборах, а - все остальные переменные:
И теперь все переменные множества переименнуем в x , а во все переменные множества подставим соответствующие константы :
.
Тогда полученная функция одного аргумента в нуле будет равна значению первоначальной функции на верхнем наборе, т.е. единице, а в единице равна значению первоначальной функции на нижнем наборе, т.е. нулю. Это и есть . .
Например, пусть наборы были:
-
X1
x2
X3
x4
x5
fM
0
1
0
1
0
1
1
1
0
1
1
0
3 случай :
-
X
f0
f1
0
1
1
1
0
0
т.е .
Построим вывод :
Пусть и пара противоположных наборов, на которых значение функции одно и то же, и равно, для определенности нулю: .
Разобьем множество всех переменных на две группы. В первую отнесем все переменные, которые равны нулю в первом наборе, во вторую , которые равны единице в первом наборе:
Теперь в переменные подставим x, а в подставим : .
Нетрудно видеть, что полученная функция есть константа 0, т.к. данная функция в нуле равна значению первоначальной функции на первом наборе, т.е. нулю, а в единице равна значению первоначальной функции на втором наборе, т.е. нулю. Константу 1 получим подстановкой 0 в функцию .
Например, пусть пара противоположных наборов, на которых равна нулю, имеют вид :
-
X1
x2
X3
x4
x5
f
0
1
1
0
1
0
1
0
0
1
0
0
Тогда .
Iый этап завершен.