Размещено на http://www.allbest.ru/

1

Вопрос 1. Многоместные отношения. Композиция отношений. Степень и ядро отношений. [c.46,2]

Многоместные отношения

Естественным обобщением понятия бинарного отношения является понятие n-арного (n-местного) отношения, определяемого как подмножество декартова произведения п множеств. [1, c. 16]

Определение: Пусть X₁,X₂,…,X_n - непустые множества; n-местным отношением, заданным на X₁ЧX₂Ч…ЧX_n называют подмножество S декартова произведения X₁ЧX₂Ч…ЧX_n. Об n-ке (x₁;x₂;…;x_n) говорят, что она связана отношением S, если (x₁;x₂;…;x_n)?S, или не связана отношением S, если (x₁;x₂;…;x_n)S. [2, c. 55]

Если n-местное отношение S задано на множестве X своих элементов, т.е. X₁=X₂=…=X_n, то R Xⁿ. [3, c. 34]

n-арное отношение представляет собой множество упорядоченных n-ок (читается: «энка»). Упорядоченную n-ку называют иначе кортежем. Подмножество кортежей из n элементов образует n-арное отношение. При п = 2 имеет место бинарное отношение, при п = 3 используется термин тернарное отношение. [1, c. 17]

Многоместные отношения используются, например, в теории баз данных. Само название «реляционная» база данных происходит от слова relation (отношение). [4, c. 45]

Композиция отношений

Пусть R₁ A Ч C -- отношение между A и C, а R₂ С Ч B - отношение между С и В. Композицией двух отношений R₁ и R₂ называется отношение R A Ч B между А и В, определяемое следующим образом:

R=R₁?R₂={(a,b) | a?A & b?B & c?C aR₁c & cR₂b}.

Композиция отношений на множестве A является отношением на множестве A. [4, c. 45]

Степень отношения

Пусть R - отношение на множестве А. Степенью отношения R на множестве А называется его композиция с самим собой. Обозначение:

Соответственно, R⁰ = I, R¹ = R, R² = R?R и вообще Rⁿ = R^n-1?R.

Теорема: Если некоторая пара (a,b) принадлежит какой-либо степени отношения R на множестве А мощности n, то эта пара принадлежит и некоторой степени R не выше n-1:

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

Существование требуемой степени k отношения R обеспечивается следующим построением.

While k ? n do

c₀ := a; c_k := b

(a,b) ? R^k c₁,…,c_k-1 ? A c₀Rc₁Rc₂R…Rc_k-1Rc_k

|A| = n i,j c_i = c_j c₀Rc₁R…Rc_iRc_j+1R…Rc_k-1Rc_k (a,b) ? R^k-(j-i)

k := k - (j-i)

end while

Следствие

[4, c. 45]

Ядро отношения

Если R?AЧB -- отношение между А и В, то R?R^-1 называется ядром отношения R и обозначается kerR. Ядро отношения R между А и В является

отношением на А:

Примеры

1. Пусть отношение N₁ «находиться на расстоянии не более 1» на множестве целых чисел определено следующим образом:

Тогда ядром этого отношения является отношение N₂ «находиться на расстоянии не более 2»:

2. Ядром отношения «быть знакомыми» является отношение «быть знакомыми или иметь общего знакомого».

Замечание

Термин «ядро» и обозначение ker используются также и для других объектов. Их не следует путать - из контекста обычно ясно, в каком смысле используется термин «ядро». [4, c. 46]

Вопрос 2. Методы пересчета. Перестановки, сочетания, транспозиции

Комбинаторика - один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в ВТ, кибернетике, робототехнике. Большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств, поэтому эти две темы - элементы теории множеств и комбинаторика - рассматриваются взаимосвязано. Упорядоченные множества. Перестановки

Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от до где - число элементов множества.

Всякое конечное множество можно сделать упорядоченным, если, например, переписать все элементы множества в некоторый список ( .), а затем каждому элементу присвоить номер.

Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком.

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

Пример. Перестановки множества из 3-х элементов имеют вид .

Число перестановок из элементов !

Задача 1. Сколькими способами можно разместить на плате 4 элемента? . дискретная математика комбинаторика бинарный

Задача 2. Сколькими способами можно выстроить в линейку 10 человек (5 девушек и 5 юношей) с условием, чтобы девушки и юноши чередовались? 5 девушек можно разместить ! способами, а 5 юношей аналогично !. Следовательно, всего способов .

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

Пример перестановки:

Пример транспозиции:

Любую перестановку множества S можно осуществить посредством нескольких транспозиций. Например, перестановка {2,4,1,3} является результатом трех транспозиций множества S :

Перестановка с повторением

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

Пусть - множество из элементов и - натуральные числа, такие, что их сумма равна , а .

Каждый упорядоченный набор элементов содержащий элемент ровно раз ( ) называется перестановками множества с повторением:

Примечание: при получим перестановки множества из элементов без повторений.

Пример. Сколько различных шестизначных чисел можно составить из цифр 1, 1, 1, 5, 5, 9? Подставим в формулу различных шестизначных чисел.

Задача 2. Сколько различных слов можно получить, переставляя буквы слова "математика"?

Перестановки предметов, расположенных в круг

Задача 1. "Хоровод". Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг (рис.1,а)?

Если бы они стояли на месте, то количество способов - . Но так как танцующие кружатся, то их положение относительно окружающих не имеет роли, следовательно, важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга, надо считать одинаковыми. Но из каждой перестановки можно получить еще 6 путем вращения - 7 мест: различных перестановок девушек в хороводе.

В общем случае, если рассматривать предметов, расположенных в круг, и считать одинаковыми расположения, переходящие друг в друга при вращении, то число различных перестановок равно

Задача 2. Сколько ожерелий можно составить из 7 бусинок?

По аналогии с предыдущей задачей можно подумать, что 720. Но ожерелье можно не только вращать, но и перевернуть (рис. 1,б). Поэтому ответ , т. е.



рисунок 1

Упорядоченные подмножества. Размещения

Упорядоченные -элементные подмножества множества из элементов называются размещениями из элементов по .

Различные размещения из по отличаются компонентами либо их порядком. Общее число размещений без повторений из элементов по обозначаются и равно

Так как повторение элементов не допускается, то всегда . Будем считать, что при имеем одно размещение (элементы вообще не выбираются), т. е. положим .

Размещение элементов можно представить себе как заполнение некоторых позиций элементами заданного множества. При этом 1-ю позицию можно заполнить различными способами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать способами. Если этот процесс продолжить, то после заполнения позиций с 1-й по -ю будет иметься способов заполнения последней -й позиции. Перемножая эти цифры, мы получаем формулу.

В частном случае, когда , имеем

Пример. Пусть дано множество из четырех элементов . Какие различные размещения по два элемента можно составить и сколько их, т. е. ?

Количество размещений .

Множество размещений .

Задача. Студенту необходимо сдать 4 экзамена за 8 дней. Сколькими способами можно это сделать, если в один день сдавать не более одного экзамена?

Искомое число способов равно числу четырехэлементных упорядоченных подмножеств (дни сдачи экзаменов) множества из 8 элементов:

Размещения с повторением

Любой упорядоченный набор элементов множества, состоящего из элементов называется размещением с повторением из элементов по . Число различных размещений с повторениями есть

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

Задача. Все буквы, цифры, знаки в ЭВМ кодируются двоичными последовательностями определенной длины, компоненты которой равны 0 или 1.

Например:

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

Обратная задача. Сколько различных чисел (знаков) может быть записано двоичными словами длиной 4, 8 , 16:

Или имеется алфавит из 64 слов. Сколько необходимо разрядов, чтобы закодировать в двоичной системе.

Любое подмножество из элементов множества , содержащего элементов, называется сочетанием из элементов по . Сочетания различаются компонентами . Примечание. Если объединить все размещения из элементов по , состоящие из одних и тех же элементов (не учитывая расположения) в классы эквивалентности, то каждому классу будет соответствовать ровно одно сочетание и наоборот:

Пример. Для множества из предыдущего примера число различных двухэлементных сочетаний .

Задача. Сколько различных комбинаций может выпасть в спортлото "5 из 36":

а в спортлото "6 из 45" - .

Сочетания с повторениями

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

Например. Для множества двухэлементные сочетания с повторениями .

Число различных сочетаний из элементов по c повторениями равно

Пример. Кости домино можно рассматривать как цифры 0, 1, 2, 3, 4, 5, 6. Число сочетаний по два элемента равно

Свойства сочетаний

(6.1)

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

(6.2)

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

Составим -элементные сочетания из элементов и разобьем их на два класса:

1-й класс - сочетания, содержащие элемент ;

2-й класс - сочетания, не содержащие элемент .

Если из любого сочетания 1-го класса откинуть элемент , то останется сочетание из , их число .

Сочетания 2-го класса являются -элементными сочетаниями, составленными из , их число . Поскольку любое -элементное сочетание из принадлежит одному и только одному из этих классов, а общее число равно , то приходим к равенству (6.2).

Пример.

Пусть дано множество . Тогда .

.

С другой стороны, . .

 (6.3)

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

- это число всех размещений с повторениями из элементов двух типов. Разобьем эти размещения на классы, отнеся в -й класс те, в которые входят элементов 1-го типа и элементов 2-го типа. Размещения k-го класса - это не что иное, как всевозможные перестановки из элементов 1-го типа и элементов 2-го типа. Мы знаем, что число таких перестановок равно

Вспомним формулу

где . Значит, общее число размещений всех классов равно . С другой стороны, это же число равно . Тем самым соотношение доказано.

Рассмотрим -элементные сочетания с повторениями, составленные из элементов типов, скажем из букв a, b, c,..., x. Число таких сочетаний равно

Разобьем все сочетания на классы, отнеся к -му классу сочетания, в которые раз входит буква , остальные мест могут быть заняты оставшимися буквами с повторениями. Поэтому в -й класс входит столько сочетаний, сколько можно составить -элементных сочетаний с повторениями из элементов типов, т. е. , значит, общее число всех сочетаний равно . С другой стороны, мы видим, что это число равно , т. е. утверждение доказано.

	(6.4)

1. Заменяя на и на в соотношении (6.4), и помня, что , получаем, что

	(6.5)

2. Частными случаями формулы (6.5) при являются следующие суммы рядов:

1. :

	(6.6)

2. :

	(6.7)

3. Аналогично для :

Следовательно,

С помощью формулы (6.7) легко найти сумму квадратов натуральных чисел от до

Методы пересчета

В классической комбинаторике используются три основных метода пересчета: геометрический, рекуррентных соотношений и производящих функций. Метод производящих функций является одним из наиболее развитых комбинаторных методов. Главные его идеи были впервые высказаны в конце XVIII века в работах Лапласа по теории вероятностей. Поясним их на следующем примере.

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

Решение. Рассмотрим биномиальный ряд Ньютона

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

1) Пусть - натуральное число , тогда все слагаемые в правой части, начиная с + 2 слагаемого ( + 1), обращаются в нуль. Получаем в этом случае бином Ньютона

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

а)

б)

Складывая и вычитая полученные соотношения, получаем еще два свойства для чисел сочетаний:

где - целая часть числа

В данном случае функцию = (1 + называют производящей функцией числа сочетаний из элементов.

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

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

Решение. Пусть у нас есть предметов , , ..., , . Любую их перестановку можно получить, если присоединить элемент к перестановке , , ..., . Число различных мест, которые может занять элемент , равно , и поэтому перестановок из элементов в раз больше, чем перестановок из элементов. Тем самым установлено рекуррентное соотношение

пользуясь которым, последовательно выводим, что

Поскольку из одного элемента можно сделать лишь одну перестановку, то и

Пример 3 (числа Фибоначчи, 1202 год). Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?

Решение. Обозначим через количество пар кроликов по истечении месяцев с начала года, тогда через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца , то есть еще пар кроликов. Следовательно, имеет место рекуррентное соотношение

По условию и , а далее последовательно находим , Числа называют числами Фибоначчи.

Геометрический способ в комбинаторике основан на подсчете различных кратчайших путей (ломаных), ведущих из точки в точку . Такие пути можно зашифровать последовательностью из нулей и единиц: нуль означает место, где ломаная идет вправо, а единица - место, где она идет вверх. Число последовательностей из нулей и единиц равно числу перестановок с повторениями

Пример 14. Используя геометрический метод, докажите свойства числа сочетаний (с повторениями и без повторений):

а)	или
б)	или

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

а) Поскольку от точки до точки , ( , существует путей, то по правилу сложения получаем

Полученное соотношение можно переписать на языке сочетаний с повторениями:

б) Учитывая, что количество кратчайших путей от точки до точки можно найти и иначе, а именно как , получаем следующее соотношение:

Пример 15. Доказать, что

Решение. 1 способ (вычислительный).

2 способ (комбинаторный).

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

3 способ (геометрический).

Обратим внимание на то, что к точке можно пройти обязательно через одну из двух точек и , а к ним ведут и путей соответственно. Тогда получаем

4 способ (производящих функций).

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

Вопрос 1.

Условие. Пусть U - множество точек плоскости, на которой задана декартова система координат. Найти пересечение множеств , объединение , разности множеств А\В, В\А, дополнения множеств А', В', изобразить их на плоскости:

;

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

;

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

;

3) Разность множеств

;

4) Разность множеств

;



5) Дополнения множеств А'

;

6) Дополнения множеств В'



Вопрос 2 [2.1(1)]

Условие. Доказать выполнимость следующего соотношения .

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

Пусть , , .

а) Рассмотрим . Найдем множество . По определению .

Обозначим через x все элементы, которые удовлетворяют следующим условиям: , , а через у все элементы с, такие что .

Следовательно, , .

По определению декартового произведения множеств

(1)

б) Рассмотрим выражение .

По определению декартового произведения множеств

;

.

Тогда состоит из множества всех упорядоченных пар <a, c>, <b, c> таких, что a=b=x, c=y, т. е.

(2)

Из равенства правых частей соотношений (1) и (2) следует, что .

Вопрос 3 [3.2(15)]

Условие. Построить композиции отображений g°f и f°g; проверить, являются ли они инъективными, сюръективными или биективными.

f:C>R⁺, y=|x|² , g:R>R, y=log₂(x²+3)

Композиция функций не является сюрьецией, так как нет ни одного элемента , для которого есть образ, например, y=0. Композиция функций не является инъекцией, так как для разных элементов есть одинаковые образы .

Таким образом, - ни сюръекция, ни инъекция, но является отображением, так как каждому элементу соответствует только один элемент .

Композиция функций не является сюрьецией, так как нет ни одного элемента , для которого есть образ y<0. Композиция функций не является инъекцией, так как для разных элементов есть одинаковые образы . Таким образом, композиция функций - не биективно, но является отображением, так как каждому элементу соответствует только один элемент .

Вопрос 4 [4.2(14)]

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

, ; ; ;

Проверим, является ли отображение изотонным.

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

Вопрос 5 [7.3(1)]

Условие. Проверить полноту систем функций.

Проверить полноту системы функций.

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

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

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

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

- класс монотонных функций;

- класс линейных функций.

Для исследуемой системы составим таблицу Поста. Если функция входит в функционально замкнутый класс, то в таблице Поста в соответствующей ячейке ставится знак «+», иначе - знак «-».

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

1. Обозначим .

0	0	1
0	1	1
1	0	0
1	1	1

Из таблицы видно, что функция не сохраняет 0 и сохраняет 1. Данная функция немонотонна, так как набор (0, 0) предшествует набору (1, 0), но . На противоположных наборах (0, 0) и (1, 1) функция принимает одинаковые значения 1, следовательно, она несамодвойственна.

Для проверки линейности построим канонический полином Жегалкина:

. Функция не линейна, так как содержит элемент .

2. Обозначим .

0	0
1	0

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

3. Построим таблицу Поста для заданной системы.

	-	+	-	-	-
	+	-	-	+

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

Вопрос 6 [8.1(1)]

Условие. Является ли формула тавтологией?

Построим таблицу истинности для данной формулы:

0	0	0	1	1	1	1	1
0	0	1	1	1	1	1	1
0	1	0	1	0	1	1	1
0	1	1	1	1	1	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	1
1	1	0	1	0	0	1	1
1	1	1	1	1	1	1	1

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

Вопрос 7. Синтезировать в базисе И-НЕ (ИЛИ-НЕ) устройство, заданное логической функцией:

Решение

а) приводим функцию к базису И-НЕ



Построим логическую схему.

б) приводим функцию к базису ИЛИ-НЕ

Построим логическую схему.

Вопрос 8. Для автомата, заданного таблицей, постройте диаграмму Мура. Задайте этот автомат системой булевых функций.

Решение

Из таблицы выделим число состояний, входных и выходных сигналов:

а) Входной алфавит X={0, 1}

б) Выходной алфавит Y={0,1}

в) Множество состояний Q={0, 1, 2, 3}

Диаграмма Мура.

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

m=|X|=1 тогда k=1 (число двоичных разрядов для записи m)

n=|Q|=4 тогда r=2 (число двоичных разрядов для записи n)

p=|Y| =2 тогда s=1 (число двоичных разрядов для записи p)

Составим таблицу кодирования входных, выходных символов и состояний

Она содержит k+r+r+s=6 столбцов и 2^k+r =8 строк.

Закодируем автомат

а) Входной алфавит X ={0, 1}

б) Выходной алфавит Y ={0,1}

в) Множество состояний Q={00, 01, 10, 11}

x	z1	z2	д1	д2	л
0	0	0	0	1	0
0	0	1	1	1	1
0	1	0	1	0	1
0	1	1	1	0	1
1	0	0	1	0	1
1	0	1	1	0	0
1	1	0	1	1	0
1	1	1	1	1	0

Канонические уравнения

Вопрос 9. Конечные автоматы.

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

Из рисунка диаграммы определим :

1) Входной алфавит X={x1, x2}

2) Выходной алфавит Y={1,2}

3) Множество состояний Q={ 1, 2, 3}

x	q
	1	2	3
x1	(3; 2)	(2; 1)	(3,1)
x2	(1; 1)	(1; 1)	(2,2)

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

1) Входной алфавит X={x1, x2}={0,1}

2) Выходной алфавит Y={1,2}={0,1}

3) Множество состояний Q={ 1, 2, 3}={00,01,10}

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

m=|X|=2 => k=1 (число двоичных разрядов для записи m)

n=|Q|=4=> r=2

p=|Y| =2 => s=1

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

X	z1	z2	д1	д2	л
0	0	0	1	0	1
0	0	1	0	1	0
0	1	0	1	0	0
0	1	1	0	1	0
1	0	0	0	0	0
1	0	1	0	0	0
1	1	0	0	1	1
1	1	1	0	1	1



Вопрос 10. Для автомата, заданного каноническими уравнениями, постройте диаграмму Мура и соответствующую таблицу.

Получим таблицу

x	z	д	л
0	0	0	1
0	1	0	0
1	0	1	0
1	1	1	1

Проанализировав данные таблицы, выделим число состояний, входных и выходных сигналов:

а) Входной алфавит X. X={0, 1}={0, 1}

б) Выходной алфавит Y. Y={0, 1,}={0, 1,}

в) Множество состояний Q={0, 1}={0, 1}

x	q
	0	1
0	(0;1)	(0; 0)
1	(1;0)	(1; 1)



Литература

1. Таран Т. А. Основы дискретной математики: Учеб. Пособие / Т. А. Таран - К: Нросгата, 2003. - 288 с.

2. Ерусалимский Я. М. Дискретная математика: теория, задачи, приложения. 3-е издание / Я. М. Ерусалимский - М.: Вузовская книга, 2000. - 280 с.

3. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие / Г.И. Москинова - М.: Логос, 2003. -240 с.

4. Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. 2-е изд. / Ф.А. Новиков - СПб.: Питер. 2006. - 364 с.

5. http://portal.tpu.ru/SHARED/k/KONVAL/Sites/Russian_sites/2/01.htm#

6. http://www.intuit.ru/department/algorithms/thsetcomb/6/3.html

7. http://cito-web.yspu.org/link1/metod/theory/node5.html

Размещено на Allbest.ru

...