Геометрическое представление логических функций. Минимизация булевых функций. Карты Карно

 

Логические функции строятся при помощи определенного набора операций, называемого базисом.

Базис называется полным, если он позволяет представить любую логическую функцию.

Минимальным называется базис, который нельзя свести к базису из меньшего количества операций.

Примеры полных базисов: {и, или, не}; {и, не}; {или, не}; {функция Шеффера}; {функция Пирса}.

Геометрическое представление логических функций

Каждый набор х 1, х 2… х n может рассматриваться как n-мерный вектор, определяющий точку n-мерного пространства.

Все множество наборов, на которых определена функция n-переменных f(х 1, х 2,.., х n), представляется в виде вершин n-мерного куба.

Отмечая точками вершины, где функция равна 1, получаем ее геометрическое представление.

Функцию 2-х переменных можно представить на плоскости в декартовой системе координат.

Две вершины, принадлежащие одному и тому же ребру, называются соседними и «склеиваются» по переменной, меняющейся вдоль этого ребра. («склеивание» по х ).

Функцию 3-х переменных можно представить в 3-мерном пространстве декартовой системы координат в виде 3-мерного куба.

Минимизация логических функций

 

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

Термы максимального ранга называют 0-кубами (точки) и обозначают К0.

Если 2 0-куба из комплекта К0 отличаются только по 1-й координате, то они образуют путем «склеивания» 1-куб К1 (отрезок).

Если 2 1-куба из комплекта К1 отличаются только по 1-й координате, то они образуют путем «склеивания» 2-куб К2 (плоскость).

И т.д.

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

Карта заполняется также как таблица истинности: в клетке ставится 1, если эта клетка соответствует набору, на котором функция равна 1.

 

 

х1	х2	х3	f (x1, x2, x3)	x1	K^0 {010; 100; 101; 110; 111}
				K^1 { *10; 10*; 1*0; 1*1; 11*}
				K^2 { 1** }
				K^0 {000; 001; 011}
				K^1 {00*; 0*1}

 

6. Теория графов. Основные определения. Инварианты графа. Изоморфизм графов. Способы представления графов.

ГрафомG(V, E) называется совокупность множеств V (точек) и Е (линий), между которыми определено отношение инцидентности, причем каждый элемент е ÎЕинцедентен ровно двум вершинам u’, u’’ ÎV.

Степень вершины равна числу ребер, инцидентных ей.

Ребро S и вершина V (U) называются инцидентными, если ребро S = <U, V>соединяет вершины U и V.

 

 

Sи U – инциденты

S и V – инциденты

Вершины U и Vназываются смежными, если ребро S = <U, V>соединяет вершины Uи V.

Ребра, инцидентные одной и той же вершине, называются смежными.

Множество вершин, смежных с вершиной V,называется множеством смежности вершины V.

 

G(V, E) = <V; E>, V ¹ Æ, E = { e= { a,b } | a,b Î V&a ¹ b&e ƹ &"e Î E|e|=2 }

 

Вершины, которые не принадлежат ни одному ребру называются изолированными.

Ребро можно обозначить

не только как множество { v1, v2 },

но и какпару (v1, v2).

Граф изображают диаграммой: вершины - точками (или кружками),ребра - линиями.

На рис.4 диаграмма графа, имеющего 4 вершины и 5 ребер.

Множества смежности вершины v1:

Г+(v1) = {v2, v4} Г*(v1) = {v1, v2, v4}

Множество смежности множества вершин А={ v1, v2 }:

Г (А) = {v1, v2, v3, v4}

Виды графов:

- Граф, состоящий из одной вершины, называется тривиальным.

- Граф, состоящий из одних изолированных вершин, называется нуль-графом (Op).

- Граф, в котором каждая пара вершин соединена ребром, называется полным (Kp).

Полный граф с p вершинами имеет максимально возможное число ребер: q(Kp) = p (p - 1) / 2

- Ориентированный граф содержит направленные ребра (направления ребер отмечаются стрелками).

- Пустой граф – если множество вершин V пусто, то пусто и E.

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

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

-

Выражение "граф G (V, E)" означает неориентированный непомеченный граф без петель и кратных ребер с множеством вершин V и множеством ребер Е.

Инварианты графа

Инвариант графа в теории графов — некоторое обычно числовое значение или упорядоченный набор значений (хэш-функция), характеризующее структуру графа и не зависящее от способа обозначения вершин или графического изображения графа.

Количество ребер, инцидентных вершине v, называется степенью (валентностью) вершины V.

(Если не оговаривается особо, то петля учитывается дважды при подсчете d(v))

Степень изолированной вершины равна нулю (то есть d(v) = 0).

Если степень вершины равна единице (то есть d(v) = 1), то вершина называется концевой или висячей.

Обозначим минимальную степень вершины графа G – d(G), а максимальную –через D(G):

d(G(V, E)) =min d(v),D(G(V, E)) = max d(v).

Если степени всех вершин графаравны k, то граф называется регулярным графом степени k:

d(G) = D(G) = k.

Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.

Пример:

На рис.6. приведены диаграммы двух регулярных, но неизоморфных графов степени 3.

На рис.7. приведена диаграмма регулярного графа степени 3.

Изоморфизм графов

Это отношение эквивалентности на множестве графов. Изоморфным отображением одного неориентированного графа на другой называется взаимно однозначное отображение вершин и ребер одного графа соответственно на вершины и ребра другого графа, при котором сохраняется отношение инцидентности. Два графа называются изоморфными, если существует изоморфное отображение одного из этих графов на другой. Графы G₁ и G₂, представленные на рис., не изоморфны, a G₁ и G₃ изоморфны.