Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по дискретной математике - файл lecture.DOC


Лекции по дискретной математике
скачать (41.6 kb.)

Доступные файлы (1):

lecture.DOC255kb.27.11.2003 22:54скачать

содержание

lecture.DOC

  1   2   3   4   5

Московский государственный институт радиотехники, электроники и автоматики (технический университет)





Лекции по



1 курс



Москва 2000

Лекция 1

Множество. Алгебра множеств.


Введем обозначения.
R – множество действительных чисел.

X e R – элемент X принадлежит множеству R.
Равные множества – множества, состоящие из одинаковых элементов.
A = B – множество А равно множеству B.
0 – пустое множество.
A<= C – Множество А является подмножеством множества С.
Если А не равно С и А <= C, то А < С. (строго).

Если A <= C и C <= А, то А = С.
Пустое множество 0 является подмножеством любого множества.
Существуют конечные и бесконечные множества. Пусть n – число элементов данного множества А. Это число называется мощностью данного множества.
У множества рациональных чисел мощность является счетной (т.е. все элементы можно пронумеровать).

У множества иррациональных чисел мощность – континиум. Обозначается (С).
^

Основное правило комбинаторики (показано на примере)

Пусть имеется палочка, разделенная на 3 части. Первую ее часть можно раскрасить n способами, вторую – m, третью – k. Всего способов раскраски палочки – n*m*k.

^

Аналогично с множествами


U = {a1,a2… an-1, an}

Пусть U = {a1, a2, a3}

Выпишем множество всех подмножеств множества U.
P(U) = {0, a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3}.
Мощность множества U равна 3, а мощность P(U) равна 8.
Методом математической индукции доказывается, что при произвольной мощности n множества U, мощность множества P(U) равна 2n.

^

Операции над множествами


  1. Объединение множеств (A U B). Элемент, принадлежащий полученному множеству, принадлежит множеству А ИЛИ множеству В.

  2. Пересечение множеств (A n B). Элемент, принадлежащий полученному множеству, принадлежит множеству А И множеству В.

  3. Дополнение множества А. (С = А ) – не А. Все элементы, принадлежащие универсальному множеству, не принадлежат множеству А.


Свойства операций над множествами.

  1. A U B = B U A – коммутативность

. A n B = B n A

  1. (A U B) U C = A U (B U C), A n (B n C) = (A n B) n C – ассоциативность.

  2. (A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) – дистрибутивность.

  3. Поглощение A U A = A, A n A = A.

  4. Существование универсальных границ.

А U 0 = A

A n 0 = 0

A u U = U

A n U = A

6. Двойное дополнение

A = A

7. A U A = U

A n A = 0

8. Законы двойственности или закон Де – Моргана

(AUB) = A n B

(AnB) = A U B











Пересечение множеств

Объединение множеств

Дополнение множества


^

Лекция 2

Теория булевых функций. Булева алгебра.


Определение.

Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры). Названия операций пока не введены.


  1. X & Y = Y&X, X V Y = Y V X – коммутативность.

  2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

  3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

  4. Поглощение – X & X = X, X V X = X.

  5. Свойства констант

X & 0 = 0

X & I = X, где I – аналог универсального множества.

  1. Инвальтивность (X*)* = X

  2. Дополнимость X V X* = I, X & X* = 0.

  3. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y


Булева алгебра всех подмножеств данного множества.

U = {a1, a2… an)

[U] = N

[P(U)] = 2n
Легко показать, что свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.

Oбъединение эквивалентно V, пересечение - &, дополнение - *, пустое множество – 0, а универсальное – I.

Все аксиомы булевой алгебры справедливы в операциях над множествами.
^ Булева алгебра характеристических векторов.
Пусть A <= U, A <- P(U) - характеристический вектор этого подмножества.
A = {, 2 ..n)
n = [P(U)]
i = 1, если ai <- A (принадлежит).

i = 0, если ai не принадлежит A.
U = {1 2 3 4 5 6 7 8 9}

A = {2 4 6 8}

B = {1 2 7}

A = {0 1 0 1 0 1 0 1 0}

B = {1 1 0 0 0 0 1 0 0}

или

A = 010101010 – скобки не нужны

A= 110000100

Характеристические векторы размерностью n называются булевыми векторами.

Они располагаются в вершинах n – мерного булева куба.

Номером булевого вектора является число в двоичном представлении, которым он является

1101 – номер.

Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (если они отличаются только одной координатой).

Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.
Б
0 1
улев куб размерности 1


Булев куб размерности 2






00

01

10

11



Булев куб размерности 3

001

011



111


101


000

010


100

110

0 – нулевой вектор.

I
Логическое умножение
– вектор из одних единиц.





Логическое сложение
XY

X&Y

X V Y

00

0

0

01

0

1

10

0

1

11

1

1


Отрицание

X = 0 Y = 0

_ _

Х = 1 Y= 1

Для размерности n операции над векторами производятся покоординатно.

Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.
Утверждение

Между множеством всех подмножеств множества U и булевым кубом Bn, где n= =[U] можно установить взаимное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.
Следствие

Множество всех характеристических векторов является булевой алгеброй.
^ Булева алгебра высказываний (алгебра логики)
Высказыванием об элементах множества U называется любое утверждение об элементах множества U, которое для каждого элемента либо истинно, либо ложно.

U = {1 2 3 4 5 6 7 8 9}
A = «число четное»

B = «число, меньшее пяти»
Множеством истинности высказывания называется совокупность всех элементов, для которых это высказывание истинно.
SA = {2 4 6 8}

SB = {1 2 3 4}
Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным.

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

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

Дизъюнкция высказываний (V, ИЛИ, OR)

Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.

Конъюнкция высказываний (&, И, AND).

Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.

Отрицание высказываний (- над буквой, НЕ, NOT).

Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.

A B

A & B

A V B

Not A

Л Л

Л

Л

И

Л И

Л

И

И

И Л

Л

И

Л

И И

И

И

Л


Л – ложно.

И – истинно.
^ Утверждение (основа всей алгебры логики)

Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения.

Следствие. Множество классов эквивалентных высказываний является булевой алгеброй.

Теорема

Существуют 3 булевых алгебры:

  1. P(U)

  2. Bn

  3. Множество классов эквивалентных высказываний.

Три булевых алгебры являются изоморфными, если между их элементами можно установить такое однозначное соответствие, при котором операции сохраняются.
Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел).
^

Лекция 3

Определение и способ задания булевых функций



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

  1. Табличный

X1 X2 X3 … XN

F(X)

0 0 0 0 0 0 0 0 0







1 1 1 1 1 1 1 1 1

n



значение функции от данных аргументов.

Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.

  1. Векторный

F = (n)

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

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

Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)
На векторах, помеченных звездочкой, функция обращается в 1.

Nf = {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.


  1. В виде формулы.

Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают.

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

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

Две булевы функции называются равными или равносильными, если одну можно получить из другой путем добавления и изъятия фиктивных переменных.
Строим таблицу функций при n = 1.


X


0


X

_

X


1

0

0

0

1

1

1

0

1

0

1



^

Таблица всех элементарных булевых функций, применяемых в записи формул




X


Y


0


&

_____

YX


X

___

XY


Y


+


V







_

Y


X Y

_X


YX


/


1

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


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

Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание.

Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры.

Суперпозиции булевых функций

Ф = {ф1…фk}
F называется элементарной суперпозицией функции из множества Ф, если она получена одним из следующих способов.

  1. Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента).

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


Ф1 = {Y…xn}

Фi = (x1 … фj(x1…xn) … xn)
Ф(1) – множество всех элементарных суперпозиций из системы Ф.

Ф(k+1) – множество всех элементарных суперпозиций из систему Фk.
Функция g называется суперпозицией функций из системы, если

 g Фn

Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции.

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

G = Fф

Суперпозиция элементарных булевых функций – формула.

Для удобства записи договоримся, что отрицание – самая сильная операция. Следующая – конъюнкция, а остальные – равносильны.

_ _

X+Y = XY V XY

_ _

X ~ Y = XY V XY

__

X  Y = X V Y

_ _

X  Y = X Y
^

Лекция 4

Дизъюнктивные нормальные формы (ДНФ)

Конъюнктивные нормальные формы (КНФ)



Введем обозначения

_

Xа = X, если а = 1 и X, если а = 0
Элементарной конъюнкцией (ЭК) называется выражение вида

X1a1 X2a2…Xnan
ЭК называется правильной, если все входящие в неё переменные различны.

Правильная ЭК называется полной относительно данного набора переменных, если в неё входят все эти переменные.

Для элементарных дизъюнкций (ЭД) – аналогичный набор определений.

ЭД – выражение вида

X1a1 V X2a2 V…V Xnan

ДНФ – дизъюнкция разных правильных элементарных конъюнкций.

__

X1 V X1X2 V X1X2X3 – ДНФ.
ДНФ называется совершенной (СДНФ), если все входящие в неё элементарные конъюнкции полны относительно данного набора переменных.
КНФ – конъюнкция разных правильных элементарных дизъюнкций.

СКНФ – совершенная КНФ. У нее все ЭД полны.
Теорема.

Любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде СДНФ по формуле:

F(x1… xn) = V(X1a1 X2a2…Xnan)
Доказательство

  1. Существование

  1. F = G

N(f)  N(G) – носители функции.

(F) F(…n) = 1

G() = G(…n) = (…nn) V (…) , где пустые скобки – оставшееся выражение.

Подставив координаты, получим:

1*1V(…) = 1 )  (G) N(F) = N(G)

2.  N(G)

G(..n) = 1 – тогда, когда хотя бы одна

…nn = 1   =  …n = n  =   N(G) = N(F)

Первая часть доказана.


  1. Единственность

Посчитаем, сколько полных ЭК может быть

Всего – 2n = N (по перестановке комбинаций)

Число СДНФ – 2N-1 – число различных формул СДНФ.

Это число совпадает с числом различных булевых функций от n переменных (за исключением константы 0).

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

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

Следствие. Любая булева функция представима формулой, в которую входит только конъюнкция, дизъюнкция и отрицание.


Принцип двойственности

F*(x1…xn) – двойственная функция,

_ _ _

F*(x1…xn) = F(x1…xn)
Например

____

_ _

(XY)* = XY = X V Y
Чтобы получить вектор двойственности функции при ее табличном задании, переворачиваем таблицу на 180 градусов и берем отрицание от получившейся функции.

Теорема. Принцип двойственности.

Если F (x1…xn) является суперпозицией функций fi (i = 1...k), то двойственная к ней функция является такой же по структуре суперпозицией, но от двойственных функций.

Доказательство следует из определения двойственной функции.

_ _ _ _ _ __

F*(x1..xn) = F(x1…xn) = f(f1…fk) = f*(f1…fk)
Следствие

f(x1..xn) = K1 V K2 V… V Kn – СДНФ

f*(x1..xn) = D1 D2 … Dn - СКНФ
Используя принцип двойственности, можно доказать следующую теорему.

Любая булева функция, тождественно не равная единице представима и притом единственным образом в виде СКНФ.

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

Задача минимизации ДНФ.

Определения:

  1. Рангом правильной ЭК называется число разных переменных, входящих в нее.

  2. Рангом ДНФ называется сумма рангов всех ЭК, входящих в ДНФ.

  3. Минимальной ДНФ или Dmin для данной функции называется ДНФ, которая равна этой функции и имеет наименьший ранг.

Задача минимизации ДНФ для данной функции состоит в нахлждении минимальной ДНФ.

Число ДНФ при фиксированном n – конечное (n - число переменных)
Тривиальный алгоритм минимизации ДНФ состоит в следующем:

  1. Выписываем все возможные ДНФ от данного числа n в порядке возрастания их рангов.

  2. Последовательно сравниваем нашу функцию с каждой из этих ДНФ. Первая ДНФ, которой равна наша функция имеет минимальный ранг.


Алгоритм представления функции в виде СДНФ.

  1. Выписываем носитель функции.

  2. Для каждого вектора из носителя выписываем конъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем с отрицанием, если единице – без отрицания). Это и будут все полные ЭК.

  3. Выписываем дизъюнкцию всех этих ЭК.


Алгоритм представления функции в виде СКНФ.

1. Выписываем носитель функции

2. Для каждого вектора из носителя выписываем дизъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем без отрицания, . если единице – с отрицанием). Это и будут все полные ЭД.

3. Выписываем конъюнкцию всех этих ЭД.
^

Лекция 5

Продолжение темы «ДНФ»


Носитель элементарной конъюнкции ранга R будем называть интервалом ранга R.

Интервал ранга R содержит 2N-R векторов.

N – количество рассматриваемых векторов.

Интервал – носитель элементарной конъюнкции.
Теорема

Носитель дизъюнкции двух функций равен объединению носителей этих функций.

Доказательство.

f V g  f() V g() = 1  f() = 1 ИЛИ g() = 1  f ИЛИ  g

ч.т.д.

Носитель ДНФ является объединением интервалов.

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

Nf = I1 V I2 V … V Ik

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

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

ЭК, N – максимальный интервал – простая импликанта.

Представление носителя в виде объединения максимальных интервалов будем называть покрытием носителя максимальными интервалами.

Дизъюнкция всех возможных простых импликант называется сокращенной ДНФ функции.

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

ДНФ, которая соответствует неприводимому покрытию, называется тупиковой ДНФ.

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

^ Минимальная ДНФ содержится среди тупиковых ДНФ.

Определение

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

Элементарная конъюнкция, соответствующая ядровому интервалу – ядровая импликанта.

Объединение всех ядровых интервалов – ядро функции.

Дизъюнкция всех ядровых импликант - ядровая ДНФ.

Ядро функции обязательно входит в любое неприводимое покрытие.
Алгоритм получения минимальной ДНФ.

  1. Выделяем носитель функции.

  2. Выделяем все возможные интервалы.

  3. Выписываем все простые импликанты.

  4. Выделяем ядровый интервал.

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

  6. Среди тупиковых ДНФ выбираем минимальную.




X1

X2

X3

F

0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

1

1

0

0

1

1

0

1

0

1

1

0

1

1

1

1

1
  1   2   3   4   5



Скачать файл (41.6 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации