- •1. Множества, их способы задания. Подмножество, булеан. Операции над множествами.
- •2.Свойства оперций над множествами. Разбиения и покрытия множеств.
- •4. Основные свойства матриц бинарных отношений. Свойства бинарных отношений (рефлексивность, симметричность, антисимметричность, транзитивность).
- •5. Отношение эквивалентности. Классы эквивалентности. Фактор-множество
- •6. Отношение порядка. Лексикографический порядок.
- •7. Функциональные отношения (функции). Инъекция, сюръекция, биекция. Понятие о мощности.
- •8. Основные понятия логики высказываний. Высказывание, основные логические операции.
- •9. Логические переменные и формулы. Таблицы истинности логических операций и формул. Соглашение о приоритетах логических операций.
- •11 Эквивалентность формул. Основные эквивалентные соотношения алгебры логики
- •13. Сднф и скнф
- •14. Минимизация в классе днф.
- •15. Коммутационные схемы
- •16. Двойственность. Булева алгебра и теория множеств.
- •17. Основные понятия и определения теории графов.
- •18. Способы задания графов (пара множеств, рисунок, матрица инцидентности, матрица смежности, список ребер (дуг)).
- •19. Связь между графами и бинарными отношениями. Изоморфизм графов. Подграфы. Операции над графами.
- •20. Маршруты, цепи, пути, циклы, контуры. Связность, сильная связность, компоненты связности.
- •21. Определение связных и сильно связных компонент. Матрица достижимости.
- •22. Исследование маршрутов графа (определение маршрутов фиксированной длины и их количество)
- •24. Расстояния в графах (эксцентриситет, диаметр, радиус, центр)
- •25. Взвешенные графы. Матрица весов. Взвешенное расстояние. Нахождение кратчайших маршрутов(алгоритм Дейкстры).
- •27. Деревья, лес. Корневые деревья. Остов графа. Цикломатическое число. Число остовых деревьев в графе (теорема Кирхгофа).
- •23. Эйлеров и Гамельтонов граф.
- •29. Раскраска графов. Планарность.
13. Сднф и скнф
ДНФ и КНФ имеют тот недостаток, что они не обладают свойством единственности, т.е. одна и та же формула имеет несколько ДНФ и КНФ. Этим недостатком не обладают совершенные нормальные формы.
Опр. СДНФ - ДНФ, в кот. в каждую элементарную конъюнкцию каждая переменная входит ровно один раз, причём, входит либо сама переменная, либо её отрицание, и среди элементарных конъюнкций не должно быть одинаковых.
Опр. СКНФ - КНФ, в кот. в каждую элементарную дизъюнкцию каждая переменная входит ровно один раз, причём, входит либо сама переменная, либо её отрицание, и среди элементарных дизъюнкций не должно быть одинаковых.
Т. (Сущ. и единственность СДНФ и СКНФ). Всякая логическая формула единственным образом (с точностью до порядка следования элементарных конъюнкций (дизъюнкций)) может быть представлена в СДНФ (СКНФ).
Приведение к СДНФ:
І метод: а) приводим формулу к ДНФ; б) если какая-то элементарная конъюнкция не содержит некоторой переменной у, то добавляем её, используя закон расщепления в) убираем одинаковые элементарные конъюнкции, используя закон идемпотентности .
ІІ
метод:
для данной формулы строим таблицу
истинности, потом применяем правило,
основанное на теореме Шеннона: СДНФ
функции
содержит столько элементарных конъюнкций,
сколько единиц в столбце значений ;
каждому единичному набору нулей и единиц
соответствует элементарная конъюнкция
всех переменных, в которой xi
взята с отрицанием, если
и без отрицания, если
.
Приведение формулы к СКНФ аналогично приведению к СДНФ. Также существует два метода: а) метод элементарных преобразований; б) СКНФ находят по таблице истинности: СКНФ функции содержит столько элементарных дизъюнкций, сколько нулей в столбце значений ; каждому нулевому набору нулей и единиц соответствует элементарная дизъюнкция всех переменных, в которой xi взята с отрицанием, если и без отрицания, если .
14. Минимизация в классе днф.
Под вхождением переменной понимается место, которое переменная занимает в формуле.
МДНФ - ДНФ с наименьшим числом вхождений переменных.
Карты Карно (КК)
К
К
– это таблица, каждая клетка (ячейка)
которой соответствует некоторой
элементарной конъюнкции всех переменных.
Для функции n переменных х1,х2,...,хn
существует 2n
возможных комбинаций их значений,
состоящих из 0 и 1. То есть, например, для
n=2 имеем 22 = 4
элементарные конъюнкции
,
которым соответствуют следующие наборы
0 и 1: (1,1), (1,0), (0,1), (0,0).
КК строятся в виде таблицы размером 2n-k x 2k, так, что её столбцы соответствуют значениям переменных х1,х2,...,хk, строки – хk+1,хk+2,...,хn (или наоборот).
Для определения МДНФ сначала надо найти её СДНФ, затем каждую элементарную конъюнкцию СДНФ отметить единицей в соответствующей ячейке КК. Если в КК две, четыре, восемь (для функции четырёх переменных) соседних ячеек по вертикали или по горизонтали содержат 1, то эти ячейки объединяют в блоки (на картах их отмечают овалами), и соответствующие этим блокам дизъюнкции элементарных конъюнкций можно упростить.
П
ример
- СДНФ. Здесь блок из двух ячеек. Этому
блоку соответствует одна переменная
х,
а именно та переменная, которая полностью
«покрывает» этот блок. Формула упростилась
φ1=х.
