Лекция 10: «Функциональные элементы. Логические схемы»

 

F

Функциональный элемент с n упорядоченными входами и одним выходом

.

 

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

Каждый вход – аргумент функции.

Выход – булева функция от аргументов.

 

Из функциональных элементов можно строить по правилам их соединения схемы (логические сети).

 

Два и более входов можно отождествлять.

 

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

 

Полный набор булевых функций, который мы будем использовать для построения логических сетей (схем) в какой-нибудь задаче, мы назовем базисом из функциональных элементов.

Число функциональных переменных считаем сколь угодно большим.

 

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

 

Очевидно, чтобы базис был полным, необходимо и достаточно, чтобы система функций, реализуемых элементами базиса, была полной.

 

Пример полного базиса.

	&

- Конъюнктор

 

 

	V

- Дизъюнктор

 

- Инвертор

Чтобы построить минимальную функциональную схему для функции на конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию, нужно

1. Найти минимальную ДНФ.

2. Для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя.

Сумматор n-разрядных двоичных чисел

Составить элементы с 2n входами и n+1 выходом, реализующих сложение n-разрядных двоичных чисел вида

X = X_nX_n-1…X₁

Y = Y_nY_n-1…Y₁

Z = x+y = Z_n+1Z_n…Z₁

X+Y – сумма чисел.

Для решения такой задачи вводим q_i – единица переноса из одного разряда в другой.

Формулы сумматора

Z_i = X_i + Y_i + Q_i – сумма по модулю 2

Q_i+1 = X_iY_i V X_iQ_i V Q_iY_i

Лекция 11: «Графы»

 

Графом (G) будем называть тройку объектов (V, X, q)

 

V – множество n вершин.

X – конечное множество ребер.

q - функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.

 

q задана на множестве X.

 

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

V_j – начало ребра

V_k – его конец

 

q(x_i) = (V_j, V_k) – ребро инцидентно в вершине Vj и в вершине Vk.

 

Если одной и той же паре вершин инцидентно несколько ребер, то ребра называются кратными.

Если на ребре x_i0

q(x₀) = (V_j0, V_j0),

то ребро называется петлей.

 

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

1. Аналитический

Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной.

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

В конце выписываются все изолированные вершины.

2. Геометрический

Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин – кривой.

Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.

 

 

3. С помощью матрицы инцидентности

A(m*n)

m = [V] – число вершин

n = [X}- число ребер

 

а) Неориентированные графы

A_ij = {0, если V_i не инцидентно x_j, 1, если V_i инцидентно x_j)

 

б) Орграфы

A_ij = {0, если V_i не инцидентно x_j, -1, если V_i - начало x_j, 1, если V_i - конец x_j)

 

Для петель нужны дополнительные предположения.

 

4. Матрица смежности (задается одинаково для всех графов)

 

B(m*m) m = [V]

 

Bij равно числу ребер, инцидентных паре вершин (oi, oj)

Если граф не ориентирован, то матрица симметрична.

 

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

Простой граф называется полным, если любой паре его вершин инцидентно одно ребро.

Дальше все о неориентированных графах.

 

K1 – полный граф с одной вершиной

 

 

K2 – с двумя

 

 

K3 – с тремя

 

 

 

K4 – полный граф с четырьмя вершинами

 

 

 

K5 – полный пятивершинник

 

 

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

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

 

 

 

Полный двудольный граф.

 

 

Маршруты, циклы, связности.

 

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

Будем говорить, что этот маршрут соединяет первую и последнюю вершину. Если существует маршрут, то последняя вершина называется достижимой из первой вершины.

Маршрут, в котором нет повторяющихся ребер, называется цепью.

Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью.

Если в простой цепи первая и последняя вершины совпадают, то она называется циклом.

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

Эти части называются компонентами связности.

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

 

Утверждение.

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

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

Несвязный граф, компонентами связности которого являются деревья, лесом.

Свойства деревьев.

1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.