- •Основные понятия теории множеств. Способы задания множеств. Мощность множества. Примеры.
- •Операции с множествами. Свойства операций.
- •Подмножества. Булеан. Мощность булеана. Разбиение, покрытие и дизъюнктивный класс. Примеры.
- •Прямое произведение множеств. Мощность прямого произведения множеств.
- •Соответствие двух множеств. Виды соответствий. Равномощные множества. Примеры.
- •Многоместные отношения. Способы задания бинарных отношений. Композиция отношения. Примеры.
- •Виды отношений. Ядро отношения. Примеры.
- •Свойства отношений. Примеры. Теорема о свойствах отношений.
- •R рефлексивно I r
- •R транзитивно rr r
- •R антисимметрично rr-1I
- •Замыкание отношения. Примеры.
- •Отношение эквивалентности. Примеры. Классы эквивалентности.
- •Отношение порядка. Примеры.
- •Две теоремы о матрицах отношений.
- •Алгебра. Свойства алгебраических операций.
- •Морфизмы алгебр. Виды морфизмов.
- •Функция. Виды функций. Формулы.
- •Способы задания функций.
- •Основные понятия теории графов. Классификация вершин и дуг графа. Отношения связности и инцидентности в графе. Виды графов: полный, безреберный, орграф, мультиграф, двудольный граф.
- •Изоморфные графы. Примеры.
- •Способы задания графов. Матрицы и диаграмма графа. Примеры.
- •Части графа: подграф, суграф, дополнительный граф. Операции с частями графа. Примеры.
- •Маршрут, цепь, цикл. Отношение связности в графе. Компоненты связности. Примеры.
- •Разрезы и разделяющие множества графа. Примеры.
- •Дерево и лес. Свойства деревьев. Диаметр и радиус дерева. Примеры.
- •Остов графа. Примеры.
- •Центральные и бицентральные деревья. Радиус и диаметр дерева. Примеры.
- •Эйлеровы цепи и циклы. Эйлеровы графы. Теорема Эйлера. Примеры.
- •Гамильтоновы цепи и циклы. Гамильтоновы графы. Примеры.
- •Раскраски графа. Хроматические характеристики: хроматическое число, хроматический индекс, тотальный минимум. Примеры.
- •Укладка графа на плоскости. Планарность графа. Примеры.
- •Критерии планарности графов.
- •Булева алгебра. Переключательные функции (пф). Примеры. Количество наборов и пф от n переменных. Фиктивные переменные.
- •Способы задания пф. Таблица истинности. Формулы и суперпозиции. Равносильные формулы. Семантические деревья.
- •Пф от одной и двух переменных. Сигнатура булевой алгебры. Выражение функций от двух переменных через дизъюнкцию, конъюнкцию и отрицание.
- •Свойства пф.
- •Двойственность функций. Принцип двойственности. Принцип двойственности для алгебры логики.
- •Разложение пф по переменным.
- •Дизъюнктивная и конъюнктивная нормальные формы. Совершенные формы. Получение скнф из сднф.
- •Минимизация функций в классе днф. Пример минимизации методами Квайна и сочетания индексов.
- •Функционально полные системы (фпс) пф. Замыкание фпс пф. Примеры базисов.
- •Замкнутые классы пф. Классификация замкнутых классов.
- •Теорема Поста о функциональной полноте систем пф.
Двойственность функций. Принцип двойственности. Принцип двойственности для алгебры логики.
Д ля функции f(x1 …xn) можно задать двойственную: f ' (x1 …xn) - двойственная, если f(x1 …xn)= f ' (x1 …xn).
Заметим, что отношение двойственности симметрично.
Любая функция имеет двойственную. Пример: законы де Моргана.
У равных функций двойственные равны.
Функция, двойственная сама себе, называется самодвойственной. Пример: инволютивность, т.е. инверсия самодвойственная.
Принцип двойственности: Если в формуле F, представляющей функцию f, все знаки заменить на знаки двойственных функций, а переменные на их отрицания, то получим формулу F', описывающую функцию f ', двойственную к f.
Для булевой алгебры: конъюнкцию меняем на дизъюнкцию, дизъюнкцию меняем на конъюнкцию, 1 на 0, 0 на 1.
Разложение пф по переменным.
Лемма: (о дизъюнктивном разложении). Любая булева функция f(x1 …xn) может быть представлена в виде дизъюнкции:
f(x1 …xi…xn)= not(xi)f (x1 …,0,…xn) or xif (x1 …,1,…xn).
Док-во: 1) xi=0, f(x1 …xi…xn)= not(0)f (x1 …,0,…xn) or 0f (x1 …,1,…xn)= 1 and f (x1 …,0,…xn) or 0 and f (x1 …,1,…xn)=f (x1 …,0,…xn).
2) xi=1, f(x1 …xi…xn)= not(1)f (x1 …,0,…xn) or 1f (x1 …,1,…xn)= 0 and f (x1 …,0,…xn) or 1 and f (x1 …,1,…xn)=f (x1 …,1,…xn).
Такое представление называется разложением функции по одной переменной.
Существует общий вид разложения функции по m переменным (док-во по индукции)
f(x1 …xi, xi+1 …xn)= or (x1а1 …xiаi f (а1…аi…xn)), где а1…аi=1 or 0.
Пример: f(a b c d).
По переменной а
По переменным а, b
По переменным а, b, c
По переменным а, b,c,d.
Последний расклад - разложение по всем переменным – называется ДНФ.
Дизъюнктивная и конъюнктивная нормальные формы. Совершенные формы. Получение скнф из сднф.
Опр-е: разложение функции по всем переменным, где каждая переменная или ее отрицание входят в каждую конъюнкту (слагаемое в дизъюнкции), называется СДНФ.
Любая ПФ (кроме тождественного нуля) допускает разложение в СДНФ, причем такое разложение единственно. Из этого следует, что такое разложение позволяет проверять функции на равносильность.
По принципу двойственности формируется понятие КНФ и СКНФ.
Любая ПФ (кроме тождественной единицы) допускает разложение в СКНФ, причем такое разложение единственно.
Если функция задана таблицей истинности, то СДНФ строится по единичному множеству, СКНФ по нулевому.
Из ДНФ СДНФ получается добавлением к каждой неполной конъюнкте единицы (х or (not x)).
ДНФ=not(not(КНФ)) и наоборот.
Минимизация функций в классе днф. Пример минимизации методами Квайна и сочетания индексов.
Однако, СхНФ часто слишком громоздка и неудобна в пользовании, поэтому функцию минимизируют, приводя к МхНФ.
Методы минимизации:
метод простых преобразований (метод Квайна). Построен на многократном применении свойств ПФ, чаще всего склеивания и добавления констант.
карта Карно: все переменные накладываем на таблицу, применяя закон склеивания две соседние конституенты объединяем в одну, исключив при этом переменную, в которой расходятся оба слагаемых. Краевые ячейки карты считаются соседними. Используя закон идемпотентности, одну и ту же ячейку можно задействовать несколько раз. Склеивать можно только четное число ячеек.
метод сочетания индексов. Оформляется в виде таблицы:
список переменных | сочетания переменных | значение функции
В сочетаниях переменных вычеркиваем в каждом столбце сочетания, не соответствующие нужному значению функции. Далее собираются оставшиеся импликанты, выбираются минимальные в каждой строке и из них составляется МНФ - минимальная нормальная форма.
П ример:f=x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 .
Минимизируем в классе ДНФ.
сочетание индексов (табл. 4.1):
Таблица 4.1
-
x1
x2
x3
x1 x2
x1 x3
x2 x3
x1 x2 x3
f
0
0
0
00
00
00
000
1
0
0
1
00
01
01
001
0
0
1
0
01
00
10
010
0
0
1
1
01
01
11
011
1
1
0
0
10
10
00
100
1
1
0
1
10
11
01
101
0
1
1
0
11
10
10
110
1
1
1
1
11
11
11
111
0
Из первой строки выбираем 00, из четвертой - 011, из пятой - 10.
В итоге имеем: . f= x2 x3 x1 x2 x3 x1 x3 – МДНФ.
2) карта Карно (табл. 4.2):
Таблица 4.2
|
Х1 |
Х1 |
|
|
Х3 |
111 |
101 |
011 |
001 |
|
100 |
110 |
010 |
000 |
|
|
Х2 |
Х2 |
|
И меем: -00, 1-0, 011, т.е. f= x2 x3 x1 x2 x3 x1 x3 – МДНФ
МКНФ строится по принципу двойственности.