Реферат: Элементы комбинаторики. Правила умножения и сложения
14. Способы построения минимальных ДНФ.
Минимизация ДНФ включает следующие этапы:
- Получение простых импликант и сокращенной ДНФ
- Получение тупиковой ДНФ
- Выбор из тупиковых ДНФ минимальной
Для реализации первого этапа алгоритма будем применять один из след методов: Метод Квайна, геометрический, карты Карно
Метод Квайна
В его основе лежат следующие равносильности:
1. Полного склеивания 
2. Поглощения 
3. Не полного склеивания 
Если в СДНФ провести все операции неполного склеивания (тем самым усложнив СДНФ), а затем провести операции поглощения, то получится сокращенная ДНФ.
Геометрический метод
Он удобен в случаях двух и трех переменных. В более сложных случаях применение метода становится громоздким.
Суть метода: 1) для функции nпеременных отмечаются вершины куба, соответств кортежам, на которых функция принимает значение 1.
2) проводят склеивание – отмечают ребра, содерж 2 отмеч вершины.
3) проводят поглощение – отмечают грани, содерж все 4 склеенные вершины.
Цель действий – накрыть множество, всех отмеченных вершин, как можно меньшим числом граней, ребер.
Карты Карно
Могут быть использованы для минимизации булевой функции любого числа переменных. Но наиболее удобно использовать его, если n=3 или n=4
Переменные кортежа разбиваются на 2 части. Первая часть является кодом столбца, вторах – строк. Таким образом, карты Карно неявно задают сами кортежи.
Например: 
| х3 | х1х2 | 00 | 01 | 11 | 10 |
| 0 | 1 | 1 | |||
| 1 | 1 | 1 | |||
Процесс минимизации СДНФ представляет собой склеивание кодов кортежей для каждого сплошного участка причем колво единиц на таком сплошном участке должно быть степенью числа 2.
15. Понятие графа. Виды графов. Изоморфизм.
Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты удобно изображать точками системы, связи между ними – дугами со стрелками(или без них). Такие системы образ графы. Объекты называют вершинами, дуги – ребрами графа.
Графом G называется совокупность 2х конечных множеств V(множество вершин) и E(множество ребер), между элементами которых определено отношение инцидентности. Каждое ребро инцидентно 2м вершинам , которое оно соединяет.
Граф, содержащий направленные ребра (дуги), называется ориентированным (орграфом). Если ребра не имеют направлений, то граф называют не ориентированным.
Ребра, инцидентные одной и той же паре вершин, называют параллельными или кратными. Граф, содержащий кратные ребра, именуется мультиграфом.
Граф называется конечным, если множество его элементов (вершин и ребер) конечно, и пустым, если множество вершин пусто.
Ребро, концевые вершины которого совпадают, называют петлей.
Граф, без петель и кратных ребер, называется полным если каждая из его вершин соединена ребром.
Степенью вершины в неориентир графе называется колво ребер, инцидентных этой вершине.