Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ѕримеры рефлексивных отношений




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

ƒокажем это равенство индукцией по n:

Ѕаза индукции:


Ўаг индукции: ѕусть утверждение дл€ верно:

“огда надо доказать утверждение дл€ :

ЌачнЄм доказательство:

»звлечЄм из первой суммы слагаемое при

»звлечЄм из второй суммы слагаемое при

“еперь сложим преобразованные суммы:

„то и требовалось доказать

 

“ема 2. јлгебра множеств

6. ѕон€ти€ множества, подмножества, равенства множеств. —пособы задани€ множеств. ќперации над множествами. —оотношени€ между операци€ми. —пособы доказательства соотношений между операци€ми.

ѕод Ђмножествомї мы понимаем соединение в некое целое M определЄнных хорошо различимых предметов m нашего созерцани€ или нашего мышлени€ (которые будут называтьс€ Ђэлементамиї множества M).

ћножество может быть замкнутым и незамкнутым, полным и пустым, упор€доченным и неупор€доченным, счЄтным и несчЄтным, конечным и бесконечным. Ѕолее того, как в наивной, так и в формальной теори€х множеств любой объект обычно считаетс€ множеством.

ћножество €вл€етс€ подмножеством множества , если любой элемент, принадлежащий , также принадлежит .

ƒва множества и могут вступать друг с другом в различные отношени€.

Ј включено в , если каждый элемент множества принадлежит также и множеству :

Ј включает , если включено в :

Ј равно , если и включены друг в друга:

Ј строго включено в , если включено в , но не равно ему:

Ј строго включает , если строго включено в :

Ј и не пересекаютс€, если у них нет общих элементов:

и не пересекаютс€

Ј и наход€тс€ в общем положении, если существует элемент, принадлежащий исключительно множеству , элемент, принадлежащий исключительно множеству , а также элемент, принадлежащий обоим множествам:

и наход€тс€ в общем положении

 

—равнение множеств

ћножество содержитс€ во множестве (множество включает множество ), если каждый элемент есть элемент :

¬ этом случае называетс€ подмножеством , Ч надмножеством . ≈сли и , то называетс€ собственным подмножеством . «аметим, что . ѕо определению .

ƒва множества называютс€ равными, если они €вл€ютс€ подмножествами друг друга:

»ногда дл€ того, чтобы подчеркнуть, что множества могут быть равны, используетс€ запись:

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

Ѕинарные операции

Ќиже перечислены основные операции над множествами:

Ј пересечение:

Ј объединение:

≈сли множества и не пересекаютс€,то . »х объединение обозначают также: .

Ј разность (дополнение):

Ј симметрическа€ разность:

Ј ƒекартово или пр€мое произведение:

ƒл€ лучшего понимани€ смысла этих операций используютс€ диаграммы Ёйлера Ч ¬енна, на которых представлены результаты операций над геометрическими фигурами как множествами точек.

”нарные операции

Ј јбсолютное дополнение:

ќпераци€ дополнени€ подразумевает некоторый универсум (универсальное множество , которое содержит ):

ќтносительным же дополнением называетс€ ј\¬ (см.выше):

Ј ћощность множества:

–езультатом €вл€етс€ кардинальное число (дл€ конечных множеств Ч натуральное).

Ј ћножество всех подмножеств (булеан):

ќбозначение происходит из того, что в случае конечных множеств.

 

 

7. Ѕулева алгебра всех подмножеств некоторого множества. јксиомы булевой алгебры. ѕримеры алгебраического доказательства некоторых соотношений между операци€ми теории множеств из аксиом.

јксиома коммутативности: x + y = y + x.

јксиома ассоциативности: (x + y) + z = x + (y + z).

”равнение ’антингтона: n (n (x) + y) + n (n (x) + n (y)) = x.

ассоциативность

коммутативность

законы поглощени€

дистрибутивность

дополнительность

 

8. “еоретико-множественные средства моделировани€. ѕон€тие произведени€ множеств A x B. “еорема о числе элементов в A x B дл€ конечных множеств A и B с доказательством методом полной математической индукции.

ќдним из способов конструировани€ новых объектов из уже имеющихс€ множеств €вл€етс€ декартово произведение множеств.

ѕусть и - множества. ¬ыражение вида , где и , называетс€ упор€доченной парой. –авенство вида означает, что и . ¬ общем случае, можно рассматривать упор€доченную n-ку из элементов . ”пор€доченные n-ки иначе называют наборы или кортежи.

ƒекартовым (пр€мым) произведением множеств называетс€ множество упор€доченных n-ок (наборов, кортежей) вида

—тепенью декартового произведени€ называетс€ число множеств n, вход€щих в это декартово произведение.

«амечание. ≈сли все множества одинаковы, то используют обозначение

.

 

9. ѕон€тие множества всех подмножеств P(M) множества M. „исло элементов в P(M) дл€ конечного множества M (с доказательством).

10. ѕон€тие отношени€ и его теоретико-множественна€ модель. ќпределение свойств бинарных отношений: симметричность, рефлексивность, транзитивность. ѕримеры отношений. ќпределение отношени€ пор€дка. ѕримеры отношений пор€дка: больше или равно на числах, быть подмножеством на множествах, лексикографический пор€док на словах.

–ефлексивное отношение

¬ математике бинарное отношение на множестве называетс€ рефлексивным, если вс€кий элемент этого множества находитс€ в отношении с самим собой.

‘ормально, отношение рефлексивно, если .

—войство рефлексивности при заданных отношени€х матрицей характеризуетс€ тем, что все диагональные элементы матрицы равн€ютс€ 1; при заданных отношени€х графом каждый элемент имеет петлю Ч дугу (х, х).

≈сли это условие не выполнено ни дл€ какого элемента множества , то отношение называетс€ антирефлексивным.

≈сли антирефлексивное отношение задано матрицей, то все диагональные элементы €вл€ютс€ нулевыми. ѕри задании такого отношени€ графом кажда€ вершина не имеет петли Ч нет дуг вида (х, х).

‘ормально антирефлексивность отношени€ определ€етс€ как: .

≈сли условие рефлексивности выполнено не дл€ всех элементов множества , говор€т, что отношение нерефлексивно.

ѕримеры рефлексивных отношений

Ј отношени€ эквивалентности:

Ј отношение равенства

Ј отношение сравнимости по модулю

Ј отношение параллельности пр€мых и плоскостей

Ј отношение подоби€ геометрических фигур;

Ј отношени€ нестрогого пор€дка:

Ј отношение нестрогого неравенства

Ј отношение нестрогого подмножества

Ј отношение делимости

¬ математике бинарное отношение на множестве X называетс€ симметричным, если дл€ каждой пары элементов множества выполнение отношени€ влечЄт выполнение отношени€ .

‘ормально, отношение симметрично, если .

јнтисимметричность отношени€ не €вл€етс€ антонимом симметричного отношени€. ќба свойства дл€ некоторых отношений выполн€ютс€ одновременно, а дл€ некоторых не выполн€етс€ ни одно.

ѕримеры

Ћюбое отношение эквивалентности, по определению, €вл€етс€ симметричным (а также рефлексивным и транзитивным). “акже симметрично отношение св€зи вершин графа (неориентированного).

Ќе €вл€ютс€ симметричными (за исключением случа€ тождественной ложности отношени€) отношени€ пор€дка (как полного, так и частичного), а также отношение следовани€ вершин ориентированного графа. ќднако, отношение сравнимости дл€ частичного пор€дка €вл€етс€, по построению, симметричным (хот€, в отличие от самого́ пор€дка, не транзитивным).

ћатрица симметричного отношени€ симметрична относительно главной диагонали (совпадает с транспонированной). ≈сли в графе симметричного отношени€ существует св€зь между двум€ вершинами, то существует и обратна€ св€зь.

“ранзитивность

 

¬ математике бинарное отношение на множестве называетс€ транзитивным, если дл€ любых трЄх элементов множества выполнение отношений и влечЄт выполнение отношени€ .

‘ормально, отношение транзитивно, если .

ѕримеры

Ј –авенство: и , значит (на самом деле, отношение равенства вместе с отношением эквивалентности и параллельности пр€мых обладает более сильным свойством также ещЄ и Ђравенства третьемуї по причине своей симметричности)

Ј ќтношение пор€дка: и , значит или нестрогого пор€дка: и , значит

Ј ѕараллельность пр€мых: и , значит (см. примечание к Ђравенству чиселї)

Ј »мпликаци€: и , значит

Ј Ёквивалентность: и , значит (см. примечание к Ђравенству чиселї)

Ј ¬ключение подмножества: если b €вл€етс€ подмножеством a, и в свою очередь c €вл€етс€ подмножеством b, тогда c €вл€етс€ подмножеством a

Ј ƒелимость: если a делитс€ на b, и b делитс€ на c, тогда a делитс€ на c.

Ј ќтношение следовани€ вершин ориентированного графа: если вершина достижима из вершины , а вершина , в свою очередь, Ч из , то достижима из .

ѕримеры отсутстви€ транзитивности (встречаютс€, когда логические высказывани€ св€заны не арифметическими отношени€ми или их эквивалентами в €зыке, а другими смысловыми отношени€ми):

Ј »гра Ђ амень, ножницы, бумагаї:  амень сильнее Ќожниц; Ќожницы сильнее Ѕумаги; однако  амень не сильнее Ѕумаги (). «десь "сильнее" не имеет буквального значени€, поскольку "сила" Ѕумаги в том, что она просто обертывает  амень.

Ј ¬ круговом турнире часто бывает ситуаци€, когда команда A победила команду B, команда B Ч команду C, а C Ч A. —ледовательно, в таком турнире отношение Ђпобедаї €вл€етс€ нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношени€.

Ј ќтношение св€зи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающеес€ условной вершиной , и две вершины и , вход€щие в состав различных альтернативных ветвей ветвлени€, то вершина св€зана с , св€зана с , однако вершины и не св€заны (они либо параллельны, либо альтернативны).

Ј ќтношение параллельности вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находитс€ вершина , а друга€ представлена альтернативным ветвлением с двум€ ветв€ми, одна из которых содержит вершину , а друга€ Ч , то вершины и наход€тс€ в отношении параллельности, также как и вершины и , однако вершины и не параллельны (они наход€тс€ в отношении альтернативы).

Ј ќтношение альтернативы вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной , а друга€ включает последовательно выполн€емые вершины и , то вершины и наход€тс€ в отношении альтернативы, что справедливо и дл€ вершин и , однако вершины и не состо€т в отношении альт

 

11. ќтношение эквивалентности. ќпределение фактор множества по отношению эквивалентности. ѕримеры.

ќтношение эквивалентности

 

” этого термина существуют и другие значени€, см. Ёквивалентность.

ќтношение эквивалентности () на множестве Ч это бинарное отношение, дл€ которого выполнены следующие услови€:

1. –ефлексивность: дл€ любого в ,

2. —имметричность: если , то ,

3. “ранзитивность: если и , то .

«апись вида Ђї читаетс€ как Ђ эквивалентно ї.

—в€занные определени€

Ј  лассом эквивалентности элемента называетс€ подмножество элементов, эквивалентных . »з вышеприведЄнного определени€ немедленно следует, что, если , то .

ћножество всех классов эквивалентности обозначаетс€ .

Ј ƒл€ класса эквивалентности элемента используютс€ следующие обозначени€: , , .

Ј ћножество классов эквивалентности по отношению €вл€етс€ разбиением множества.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2017-02-24; ћы поможем в написании ваших работ!; просмотров: 7636 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

ƒаже страх см€гчаетс€ привычкой. © Ќеизвестно
==> читать все изречени€...

722 - | 582 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.062 с.