Лекции - Дискретная математика - файл n2.doc

Лекции - Дискретная математика
скачать (55.8 kb.)
Доступные файлы (1):
n2.doc255kb.17.10.2008 16:40скачать

n2.doc

1   2   3   4   5   6

Лекция 9


Доказательство леммы 3
F(x1…xn) = x1x2 (f1(x1…xn)) + x1f2(x1…xn) + x2f3(x1…xn) + f4(x1…xn)
Вместо x1…xn ставим константы 1…n, такие, что

f1(1…n) = 1


  1. A = B = 0

F(x1x2…3…n) = x1x2 + C = {x1x2, если с = 0 и NOT(x1x2, если с = 1)

Аналогично получаем дизъюнкцию и ее отрицание.
Теорема Поста.

Система функций полна тогда и только тогда, когда она не находится ни в одном из пяти важнейших замкнутых классов, а именно S, M, L, T0, T1.

  1. Необходимо.

Дана полная система функций. Отсюда следует, что она не принадлежит никакому замкнутому классу (см. выше).

Доказательство следует из того факта, что по определению и по тому, что мы доказали, что все важнейшие классы замкнуты. Если предположить, что система целиком входит в один из замкнутых классов, то
[] = [B] = B
Но множество всех булевых функций, а B – не всех.

Получили противоречие.
Доказательство дано в виде алгоритма получения из системы основных элементарных булевых функций, образующих полную систему, значит и эта система будет полна.

Дано

{S, M, L, T0, T1}
Каждая функция (f с индексами 1…5) не принадлежит каждому соответствующему ей важнейшему замкнутому классу.

  1. Получение констант.

F1(00…0) = 1

  1. F(111) = 1

  2. F(111) = 0

F(xxxx) = 1

F2(111) = 0

  1. Получение отрицаний

Из F4 по лемме 2 мы можем получить отрицание.

  1. Используя F5 по лемме 3 получаем xy, x V y, not(xy), not(x V y)



Лекция 10

Функциональные элементы. Схемы


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

.

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

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

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

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


&

V
- Конъюнктор



- Ин
__
вертор

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

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

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

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


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

Y = YnYn-1…Y1

Z = x+y = Zn+1Zn…Z1

X+Y – сумма чисел.
Для решения такой задачи вводим qi – единица переноса из одного разряда в другой.
Формулы сумматора

Zi = Xi + Yi + Qi – сумма по модулю 2

Qi+1 = XiYi V XiQi V QiYi

Лекция 11

Графы



Графом (G) будем называть тройку объектов (V, X, )
V – множество n вершин.

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

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

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

Vk – его конец
xi) = (Vj, Vk) – ребро инцидентно в вершине Vj и в вершине Vk.
Если одной и той же паре вершин инцидентно несколько ребер, то ребра называются кратными.

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

(x0) = (Vj0, Vj0),

то ребро называется петлей.
Способы задания графов

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

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

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

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

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

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

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



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

A(m*n)

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

n = [X}- число ребер
а) Неориентированные графы

Aij = {0, если Vi не инцидентно xj, 1, если Vi инцидентно xj)
б) Орграфы

Aij = {0, если Vi не инцидентно xj, -1, если Vi - начало xj, 1, если Vi - конец xj)
Для петель нужны дополнительные предположения.


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


B(m*m) m = [V]
Bij равно числу ребер, инцидентных паре вершин (oi, oj)

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

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

Дальше все о неориентированных графах.
K1 – полный граф с одной вершиной


K2 – с двумя






K3 – с тремя




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


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
















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

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

















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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Лекция 9
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации