- •Курс: «Дискретная математика» Индивидуальное задание
- •Кислицын Александр
- •Оглавление
- •Задание 1
- •1.2.2) Доказательство с помощью диаграмм Эйлера-Вена:
- •Задание 2
- •Задание 3
- •Задание 4
- •Задание 5
- •1)Не рефлексивное, несимметричное, транзитивное:
- •2)Антирефлексивное, симметричное, нетранзитивное.
- •Задание 6
- •Задание 7
- •2) Эпиморфизмом, но не мономорфизм;
- •Задание 8
- •Задание 9
- •Задание 10
- •Задание 11
Задание 4
Доказать, что для любых a, b, c, d : {{a}, {a, b}} = {{c}, {c, d}} ↔ a=c и b=d.
Док-во:
М = {{a}, {a, b}}
N = {{c}, {c, d}}
все элементы M и N тоже равны т.к порядок перечисления элементов множества значения не имеет, а длина подмножества x={a, b} M и длина подмножества y={c, d} N равны x=y {a} M = {c} N
a=c и b=d ч.т.д
Задание 5
Построить отношение:
1)Не рефлексивное, несимметричное, транзитивное:
2)Антирефлексивное, симметричное, нетранзитивное.
Отношением называется кортеж φ=(Х,F), где Х={xi}, i{1,2,…,n} – область задания отношения, F={(xi, xj)}, где xi, xjХ, – график отношения.
Отношение φ=(Х,F) называется нерефлексивным, если (хХ)(хφх).
Отношение φ=(Х,F) называется антирефлексивным, если (хХ)(хφх).
Отношение φ=(Х,F) называется симметричным, если (х,уХ)(хφу уφх).
Отношение φ=(Х,F) называется несимметричным, если (х,уХ)(хφу уφх).
Отношение φ=(Х,F) называется транзитивным, если (x,y,zХ)(хφу&yφz xφz).
Отношение φ=(Х,F) называется нетранзитивным, если (x,y,zХ)(хφу&yφz xφz).
1)Не рефлексивное, несимметричное, транзитивное:
|
X1 |
X2 |
X3 |
X4 |
X5 |
X1 |
1 |
0 |
1 |
0 |
0 |
X2 |
1 |
1 |
1 |
1 |
1 |
X3 |
1 |
0 |
1 |
0 |
0 |
X4 |
0 |
0 |
0 |
0 |
0 |
X5 |
1 |
1 |
1 |
1 |
1 |
2)Антирефлексивное, симметричное, нетранзитивное:
|
X1 |
X2 |
X3 |
X4 |
X1 |
0 |
1 |
1 |
0 |
X2 |
1 |
0 |
1 |
0 |
X3 |
1 |
1 |
0 |
1 |
X4 |
0 |
0 |
1 |
0 |
Задание 6
Доказать, что если отношение R1 антисимметрично, то антисимметрично отношение R1-1
Отношение , тогда - по определению.
Следовательно, для мы можем записать:
; (1)
Т. к. - антисимметрично, то:
;
В силу (1), можно записать:
;
Окончательно:
;
Следовательно, - антисимметрично – ч.т.д.
Задание 7
Задайте морфизмы между отношениями, являющиеся:
1) Мономорфизмом, но не эпиморфизм;
2) Эпиморфизмом, но не мономорфизм;
Теоретическое введение:
Морфизм – перенесение свойств одного объекта на другой.
В дискретной математике под функцией подразумевается отображение некоторого множества на .
Функцией называется функциональное соответствие:
Область определения:
Область значений:
- тотальная, если:
- инъективная, если:
- всюду определенная, если:
- сюръективная, если:
- биективная, если она тотальная, инъективная, всюду определенная и сюръективная.
и - некоторые отношения, тогда:
;
;
Если , то данный морфизм – гомоморфизм между отношениями.
Если гомоморфизм – инъективен, то он – мономорфизм.
Если гомоморфизм – сюръективен, то он – эпиморфизм.
Если гомоморфизм – биективен, то он – изоморфизм.
1) Мономорфизмом, но не эпиморфизм;
2) Эпиморфизмом, но не мономорфизм;