Элементы комбинаторики. Правила умножения и сложения (стр. 3 из 5)

Другим, более распространенным способом нахождения полинома Жегалкина явл метод неопределенных коэффициентов, который основан на выше указанной теореме

12. Классы Поста. Теорема о функциональной полноте.

Под классом функций будем понимать множество функций, замкнутых относительно операций взятия суперпозиции.

Существуют 5 классов перекл функций. Это классы Поста (Пост – Америк логик 20 века.

1.Класс

линейных функций

Перекл функция назыв линейной, если она представима полиномом Жегалкина первой степени:

Число линейных функций рано

например при n=2 число линейных функций равно 8:

2. Класс

функций, сохраняющих 0

Если перекл функция на кортеже 00…0 равна нулю, то говорят, что функция сохран нуль

Т.о. функция

принадлежит классу функций, сохраняющих 0, если

Для 2х переменных таких функций 8.

3. Класс

функций, сохраняющих 1

Если перекл функция на кортеже 11…1 равна 1, то говорят, что функция сохран единицу

Т.о. функция

принадлежит классу функций, сохраняющих 1, если

Для 2х переменных таких функций 8

4.Класс

монотонных функций

- монотонная функция

Таких функций 6

5. Класс

самодвойственных функций.

Переключательная функция называется самодвойственной, если на каждой паре противоположных кортежей значения функции противоположны.

На кортежах 00 и 11,01,10 противоположные значения могут иметь функции

Теорема Поста о функциональной полноте. Для того чтобы система булевых функций была полной необходимо и достаточно, чтобы она содержала:
-хотя бы одну функцию, не сохраняющую 0

-хотя бы одну функцию, не сохраняющую 1

-хотя бы одну функцию, не явл линейной

-хотя бы одну функцию, не явл монотонной

-хотя бы одну функцию, не явл самодвойственной.

Каждый базис содержит не более 4х булевых функций.

13. Минимизация переключательных функций. Основные понятия,

14. Способы построения минимальных ДНФ.

Минимизация ДНФ включает следующие этапы:

1. Получение простых импликант и сокращенной ДНФ
2. Получение тупиковой ДНФ
3. Выбор из тупиковых ДНФ минимальной

Для реализации первого этапа алгоритма будем применять один из след методов: Метод Квайна, геометрический, карты Карно

Метод Квайна

В его основе лежат следующие равносильности:

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м вершинам , которое оно соединяет.

Граф, содержащий направленные ребра (дуги), называется ориентированным (орграфом). Если ребра не имеют направлений, то граф называют не ориентированным.

Ребра, инцидентные одной и той же паре вершин, называют параллельными или кратными. Граф, содержащий кратные ребра, именуется мультиграфом.

Граф называется конечным, если множество его элементов (вершин и ребер) конечно, и пустым, если множество вершин пусто.

Ребро, концевые вершины которого совпадают, называют петлей.

Граф, без петель и кратных ребер, называется полным если каждая из его вершин соединена ребром.

Степенью вершины в неориентир графе называется колво ребер, инцидентных этой вершине.

Графы отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Изоморфные графы имеют одинаковое число вершин, ребер, степени соответствующих вершин равны.

16. Способы задания графов.

В общем виде «задать граф» означает: описать множество его вершин и ребер, а также отношение инцидентности.

Способы задания графа:

1. Графический

2. Перечислением вершин и ребер.

3. Задание графа матрицей инцидентности. Строки матрицы характеризуют вершины графа, столбцы – ребра графа.