Вопросы для повторения

1.Что называется унарным отношением?

2.В чем состоит отличие унарного и бинарного отношений?

3.Перечислите свойства бинарных отношений?

4.Назовите способы задания бинарных отношений?

5.Как выглядит матрица отношения обладающего свойством симметричности?

6.Дайте определение отношению эквивалентности?

7.Что понимают под n-местным отношением?

8.В чем заключается свойство рефлексивности?

9.В чем состоит различие между отношениями строгого и нестрогого порядков?

10.В каком случае отношение называется транзитивным?

11.Есть ли антитранзитивное отношение?

Резюме по теме

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

Тема 1.3. Соответствия и функции

Цель: ознакомиться и разобраться с понятиями соответствие и функция.

Задачи:

1. Рассмотреть соответствия и изучить их свойства.

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

3. Дать определения понятиям функция и отображение.

4. Рассмотреть понятие операция и виды операций.

5. Разобраться с понятиями гомоморфизм и изоморфизм.

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

1.3.1. Соответствия и их свойства

Соответствием между множествами А и В (рис. 1.7) называется некоторое подмножество G их декартова произведения: .

Если , то говорят, что соответствует а при соответствии .

Область определения соответствия G – множество пр₁G={а:(а,b) G}. Область значений соответствия G - множество пр₂G={b:(а,b) G}.

Рис. 1.7. Соответствие G между множествами А и B

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

Свойства соответствий :

1) Соответствие называется полностью определённым, если , то есть каждый элемент множества имеет хотя бы один образ во множестве ; в противном случае соответствие называется частичным.

2) Соответствие называется сюръективным, если , то есть если каждому элементу множества соответствует хотя бы один прообраз во множестве .

3) Соответствие называется функциональным (однозначным), если любому элементу множества соответствует единственный элемент множества .

4) Соответствие называется инъективным, если оно является функциональным, и при этом каждый элемент множества имеет не более одного прообраза.

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

Пример 1.

а) Англо-русский словарь устанавливает соответствие между множествами слов русского и английского языка. Оно не является функциональным, так как почти каждому русскому слову соответствует несколько английских переводов; оно, также, не является, как правило, полностью определённым соответствием, так как всегда существуют английские слова, не включённые в данный словарь. Таким образом, это частичное соответствие.

б) Соответствие между расположенными на шахматной доске фигурами и занимаемыми ими полями является взаимно однозначным.

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