🗊Презентация Основы дискретной математики и теории алгоритмов. Основные понятия теории множеств. Тема 1

Учебная дисциплина «Основы дискретной математики и теории алгоритмов» лекции – 34 часов лабораторные – 34 часов экзамен ВВЕДЕНИЕ

Раздел 1. Множества

Тема 1. Основные понятия теории множеств

Определения, термины, символы Множество — совокупность различимых между собой объектов, объединяемых в целое некоторым общим признаком. Элементы — объекты, из которых состоит множество. Обозначения: А, В, С,... — множества, а, Ь, с,... — элементы (точки) множеств.

Принадлежность: аА — а принадлежит множеству А; аА – а не принадлежит множеству А. Записью а1, а2, …, аnМ пользуются в качестве сокращения для записи а1М, а2М, …, аnМ.

Задание множеств Перечислением элементов: А={ a1, a2, ... , ak }; Указанием характеристического свойства (хар. предикатом): М := {х | Р(х)}; Порождающей процедурой: М := {х | х := f}. Пример: М9: = {1, 2, 3, 4, 5, 6, 7, 8, 9}; M9: = {n | n  N & n < 10}; М9: = {n | for i from 0 to 8 do n := i + l}.

Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения или процедур, возвращающей логическое значение и позволяющая проверить принадлежит ли любой данный элемент множеству. Если для данного элемента условие выполнено, то принадлежит элемента условие выполнено, то он принадлежит определённому множеству, в противном случае не принадлежит. Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения или процедур, возвращающей логическое значение и позволяющая проверить принадлежит ли любой данный элемент множеству. Если для данного элемента условие выполнено, то принадлежит элемента условие выполнено, то он принадлежит определённому множеству, в противном случае не принадлежит. Порождающая процедура – это процедура, которая в процессе работы порождает некоторые объекты, являющиеся элементами определяемого множества.

Подмножество множества А — множество В, у которого все его элементы принадлежат и А : ВА — В включено (или содержится) в А. Если хотя бы один элемент В не содержится в А, то ВА — В не подмножество (не включено в) А. Подмножество множества А — множество В, у которого все его элементы принадлежат и А : ВА — В включено (или содержится) в А. Если хотя бы один элемент В не содержится в А, то ВА — В не подмножество (не включено в) А. Множества А и В равны (А = В), если они состоят из одних и тех же элементов, иначе говоря, если АВ и ВА. Множества А и В не равны (обозначение А  В), если либо во множестве А есть элементы, не принадлежащие В, либо во множестве В есть элементы, не принадлежащие А. при этом одно из множеств может являться подмножеством другого, а может не являться. Говорят что множество В строго включено в множество А (ВА), если В является подмножеством А (ВА) и в тоже время В  А. В таком случае множество В называется собственным (строгим) подмножеством множества А.

Мощностью множества А (|A|) называется количество элементов множества А. Мощностью множества А (|A|) называется количество элементов множества А. Множество, не содержащее ни одного элемента, называется пустым множеством (). Пустое множество является подмножеством любого множества. Любое множество можно разбить на подмножества разными способами. {3;8} = {8;3} A = {3;8} {3;8}, {3}, {8},  – подмножества множества А

Универсальное множество (U) – это множества всех элементов, которые могут встретиться в данном исследовании. В различных конкретных случаях роль универсального множества могут играть конкретные множества. Универсальное множество (U) – это множества всех элементов, которые могут встретиться в данном исследовании. В различных конкретных случаях роль универсального множества могут играть конкретные множества. Множеством степенью (Р(А)) или булеаном (2|А|) множества А называется множество всех подмножеств множества А. Р(А) = {B|BA} Пример: P(A) = {{3;8}, {3}, {8}, } |P(A) = 2|A|

Разбиением множества А называется такая совокупность F непустых подмножеств множества А , что каждый элемент множества А является элементом одного и только одного множества из F. Разбиением множества А называется такая совокупность F непустых подмножеств множества А , что каждый элемент множества А является элементом одного и только одного множества из F. Пример: F = {{1;2},{3},{4;5}} является разбиением множества A = {1;2;3;4;5}

Основные числовые множества Натуральные числа N = {1;2;3;…;n;…} Целые числа Z = {…;-n;…;-2;-1;0;1;2;…;n;…} Рациональные числа Q = {p/q} Действительные числа R – вся числовая ось

Множество, число элементов которого конечно называется конечным и бесконечным в противном случае. Бесконечные множества разделяются на счётные и несчётные. Множество, число элементов которого конечно называется конечным и бесконечным в противном случае. Бесконечные множества разделяются на счётные и несчётные. Если элементы бесконечного множества можно пронумеровать с помощью натурального ряда чисел, то он называется счётным и несчётным в противном случае. Из определения множества следует, что в нём не должно быть неразличимых элементов, поэтому во множестве не может быть одинаковых элементов. {2;2;4;5} = {2;4;5}

Равномощные множества Взаимно однозначным соответствием между двумя множествами А и В называется такое правило (закон) f, по которому каждому элементу аА ставится в соответствие единственным элемент f(a)B, а для любого элемента bB существует единственный элемент аА, такой что f(a)=b. Множества А и В называются равномощными (АВ), если между ними можно установить взаимно однозначное соответствие. В таком случае говорят, что множества А и В изоморфны. Нетрудно видеть, что Любое множество взаимно однозначно соответствует самому себе; Если АВ, то ВА; Если АВ, а ВС, то АС – ассоциативность

Условные обозначения  – любое, для всех  – существует  – существует и единственый  – следствие – символ импликации  – эквивалентность, равносильность (&) – конъюнкция – логическое «и» (||) – дизъюнкция – логическое «или» ( ) – логическое «не»

Добавление и удаление элементов Если А – множество, а x – элемент, причём хА, то х можно добавить в А. А + х = {y|yA  y = x} Аналогично, если А – множество, а х – элемент, причём хА, то х можно удалить из А. А – х = { y|yA  y  x }

Теорема 1. Любое непустое конечное множество равномощно некоторому отрезку натурального ряда. Теорема 1. Любое непустое конечное множество равномощно некоторому отрезку натурального ряда. А| A  |A|<  kN|A|=|1…k| Следствие 1. Любой отрезок натурального ряда конечен. Теорема 2. Между конечными множествами А и В существует взаимно однозначное соответствие тогда и только тогда, когда их мощности равны АВ  |A|=|B|

Пример: Пусть А – множество всех натуральных чётных чисел, а В – множество всех натуральных чисел, представимых в виде суммы двух нечётных натуральных чисел. Доказать, что А = В. Пример: Пусть А – множество всех натуральных чётных чисел, а В – множество всех натуральных чисел, представимых в виде суммы двух нечётных натуральных чисел. Доказать, что А = В. Доказательство: А={2k|kN},.B={(2k-1)+(2m-1)|k,mN} Покажем, что для хАхВ и уВуА  АВ  ВА  А=В. Пусть 2kA, где kN, тогда 2k=(2k-1)+1=>2kB. Пусть (2k-1)+(2m-1)B, где k,mN, тогда (2k-1)+(2m-1)=2(k+m-1)A.

Операции над множествами Равенство множеств Множества А и В равны, А=В, тогда и только тогда, когда А В и В  А, т.е. состоят из одинаковых элементов, в противном случае пишут А В. Пример: если А = {1 ;2; 3}, а В={2;1;3}, то А=В. Объединение (сумма) множеств Объединением (или суммой) множеств А и В называется множество C таких элементов, которые входят либо в А, либо в В (C=AUB={х | хА или хВ }). Пример. Пусть А := {a, b, d}, В := {b, d, e, h}. Тогда АВ = {a, b, d, e, h}.

Пересечение множеств Пересечение множеств Пересечением множеств А и В называется множество С, состоящее из всех элементов, которые принадлежат одновременно двум множествам (С=АВ={х | хА и хВ}). Пример. Пусть А := {1, 2, 3}, В := {3, 4, 5}. Тогда АВ = {3}. Аналогично определяются пересечение и объединение конечного и бесконечного количества множеств (АВС…, АВС…)

Разность множеств Разность множеств Разностью множеств А и В называется множество С, состоящее из тех элементов множества А, которые не содержатся в множестве В (С=А\В={х | хА и хВ}). Пример. Пусть А := {a, b, d}, В := {b, d, e, h}. Тогда А\В = {а}, В\А = {e, h}. В отличии от операций объединения и пересечения множеств данная операция не коммутативна и определяется только для двух множеств. Для произвольных множеств А и В верны соотношения А\В =   АВ, А\ = А, А\В = А  АВ = .

Симметрическая разность множеств Симметрическая разность множеств Симметрической разностью множеств А и В (обозначение АВ) называется множество (А\В)(В\А). Дополнение множеств Дополнением множества А до универсального множества U называется множество всех элементов универсального множества, которые не принадлежат множеству А (А = {x  (xU)&(xA)}, А = U\A Пример. Если U := {1, 2, 3, 4, 5, 6, 7}, А := {3, 5, 7}, тоА = {1, 2, 4, 6}.

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

Алгебраические свойства операций над множествами 1) АА=А 1') АА=А — идемпотентность 2)АВ=В∪А 2’) АВ=ВА — коммутативность 3) (АВ)С=А(ВС) 3') (АВ)С=А(ВС) – ассоциативность 4) А(ВС)=(АВ)(АС) 4’) А(ВС)=(АВ)(AС)—дистрибутивность 5 )AU=U 5') А= 6) AU=A 6')А=А 7 ) А A = U 7`) А A  = 

8) =U 8') U=  8) =U 8') U=  9) А(А  В)=А 9') А(АВ)=А — законы поглощения 10) AB=A B 10') АВ =A B — законы де Моргана 11, 11') A  = А 12, 12') Если AB=U и АВ= то В= A 13) А\В= A B. Доказательство. A\B = {x | (xA)&(xB} = {x | (xA)&(xB)} = A B. 14) Очевидно, что ВА = АВ 15) АВ = (АВ)\(АВ) т.е. Доказательство. (А\В)(В\А) = (АВ)\(АВ).

Докажем, что (А\В)(В\А) = (АВ)\(АВ). Пусть А и В произвольные подмножества некоторого универсального множества U. На рисунке а и б приведены диаграммы Венна для выражений (А\В)(В\А) на рис. а и (АВ)\(АВ) на рис. б. Из объединения А и В вычитается пересечение А и В. Тогда мы видим, что получается одна и та же область. Тем самым доказано справедливость тождества и получена равносильная формула для вычисления симметрической разности множеств.

Тема 2. Упорядоченное множество (кортеж)

Кортеж – это последовательность элементов, т.е. совокупность элементов, а которой каждый элемент занимает определённое место. Кортеж часто называют вектором, а элементы, образующие кортеж – его компонентами или координатами. Компоненты нумеруются слева-направо. Количество компонент называется длиной или размерностью кортежа. Могут быть бесконечные кортежи. Кортеж – это последовательность элементов, т.е. совокупность элементов, а которой каждый элемент занимает определённое место. Кортеж часто называют вектором, а элементы, образующие кортеж – его компонентами или координатами. Компоненты нумеруются слева-направо. Количество компонент называется длиной или размерностью кортежа. Могут быть бесконечные кортежи. В отличие от элементов неупорядоченного множества, компоненты кортежа могут совпадать. Кортеж заключается в круглые скобки: а = (а1, …, аn), ( ) – пустой кортеж Иногда скобки и даже запятые упускаются.

Кортежи длиной 2 называются упорядоченными парами или просто парами. Кортежи длинной 3 называются тройками. В общем случае кортежем длинной n называются упорядоченными n-ми или просто n-ми. Частным случаем является кортеж длинной 1 и пустой кортеж. Кортежи длиной 2 называются упорядоченными парами или просто парами. Кортежи длинной 3 называются тройками. В общем случае кортежем длинной n называются упорядоченными n-ми или просто n-ми. Частным случаем является кортеж длинной 1 и пустой кортеж. Пример. Множество людей, стоящих в очереди; множество слов во фразе; координат точки на местности и т.д. Место каждого элемента в кортеже является вполне определенным и не может быть произвольно изменено.

Два конечных кортежа равны, если они имеют одинаковую длину и соответствующие компоненты равны: Два конечных кортежа равны, если они имеют одинаковую длину и соответствующие компоненты равны: (а1, …, аm) = (b1, …, bn)  m = n и а1 = b1, а2 = b2,…, аm = bm. Прямым произведение множеств А и В (А  В) называется множество, состоящее из всех тех и только тех упорядоченных пар, первые компоненты которого принадлежит множеству А, а вторая – множеству В. А  В = {(а, b) | аА, bВ}.

Пример. Пусть А:= {1, 2}, В:= {1, 3, 4}. Тогда: Пример. Пусть А:= {1, 2}, В:= {1, 3, 4}. Тогда: А  В= {(1, 1), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4)}, В  А= {(1, 1), (1, 2), (3, 1), (3, 2), (4, 1), (4, 2)}. А  ВВ  А. Этот пример показывает, что прямое произведение множеств не коммутативно в общем случае.

Операция прямого произведения легко распространяется на любое количество множеств. Прямым произведением множеств А1, А2,…,Аr, rN называется множество, состоящее из всех тех и только тех кортежей, длинной r, первые компоненты которых принадлежат множеству А1, вторые –А2, и т.д. Операция прямого произведения легко распространяется на любое количество множеств. Прямым произведением множеств А1, А2,…,Аr, rN называется множество, состоящее из всех тех и только тех кортежей, длинной r, первые компоненты которых принадлежат множеству А1, вторые –А2, и т.д. А1  А2  … Аr={(a1, a2, …, ar) | aiAi, i = 1,r}. Частным случаем операции прямого произведения является понятие степени множества. Пусть А–произвольное множество, тогда s-ой степенью, где sN, множества (Аs) называется прямое произведение s одинаковых множеств равных А Будем полагать, что А1 = А, А0 = {( )}.

Проекция кортежа Проекцией кортежа v = (v1, …, vn), nN, на i-ю ось (обозначение прiv) называется его i-я компонента. Проекцией кортежа v на оси с номерами i1, …, ik, 1  i1  i2  …  ik  n, называется кортеж длиной k (обозначение прi1…ikv). Операция проектирования множества тесно связана с операцией проектирования кортежа и может применяться лишь к таким множествам, элементами которого являются кортежи одинаковой длины.

Пусть V–множество кортежей одинаковой длины. Тогда проекция множества V на i-ую ось называется множество проекций всех векторов из V на i-ую ось: прiV={прiV| vV}. В частности, если V=А1 А2 … Аn, то прiV=Ai, i=1,n, прi1…ikV= Аi1 Аi2 … Аin, 1i1<i2<…<ikn. Пусть V–множество кортежей одинаковой длины. Тогда проекция множества V на i-ую ось называется множество проекций всех векторов из V на i-ую ось: прiV={прiV| vV}. В частности, если V=А1 А2 … Аn, то прiV=Ai, i=1,n, прi1…ikV= Аi1 Аi2 … Аin, 1i1<i2<…<ikn. Проекция точки плоскости на первую ось – это её абсцисса(первая координата), на вторую–ордината(вторая координата). Пример. Пусть V:={(1;2;3;4;5),(2;1;3;5;5), (3;3;3;3;3), (3;2;3;4;3)}. Тогда пр2V={2;1;3}, пр2,4V={(2;4),(1;5),(3;3)}.

Булева алгебра Пусть задано множество U, P(U) – булеан множества U. Алгебра В = (P(U), , , –) называется булевой алгеброй множеств над U. Элементами основного множества этой алгебры являются подмножества множества U. Операции объединения, пересечения и дополнения часто называют булевыми операциями над множествами. C помощью булевых операций из множеств можно составлять различные алгебраические выражения. Если оба алгебраических выражения представляют собой одно и то же множество, то их можно приравнять друг к другу, получив алгебраическое тождество. Такие тождества бывают очень полезны при преобразованиях алгебраических выражений над множествами. Часть основных тождеств булевой алгебры множеств была приведена при рассмотрении свойств булевых операций. Приведем доказательство остальных важных тождеств данной алгебры.

Пусть U – универсальное множество, А, В, С – произвольные подмножества U. На рис. приведены диаграммы Эйлера – Венна для выражений (АВ)С (пересечение заштрихованных множеств обозначено двойной штриховкой) и (АС)(ВС) (объединение заштрихованных множеств) соответственно. Их этих диаграмм видно, что оба выражения определяют одно и то же множество, так что в алгебре множеств имеет место тождество: (АВ)С = (АС)(ВС). Пусть U – универсальное множество, А, В, С – произвольные подмножества U. На рис. приведены диаграммы Эйлера – Венна для выражений (АВ)С (пересечение заштрихованных множеств обозначено двойной штриховкой) и (АС)(ВС) (объединение заштрихованных множеств) соответственно. Их этих диаграмм видно, что оба выражения определяют одно и то же множество, так что в алгебре множеств имеет место тождество: (АВ)С = (АС)(ВС).

На рис. приведены диаграммы Эйлера – Венна для алгебраических выражений (АВ)С (объединение заштрихованных множеств) и (АС)(ВС) (пересечение заштрихованных множеств обозначено двойной штриховкой) соответственно. Оба эти выражения дают одно и то же множество, так что имеет место тождество: На рис. приведены диаграммы Эйлера – Венна для алгебраических выражений (АВ)С (объединение заштрихованных множеств) и (АС)(ВС) (пересечение заштрихованных множеств обозначено двойной штриховкой) соответственно. Оба эти выражения дают одно и то же множество, так что имеет место тождество: (АВ)С = (АС)(ВС). Таким образом, объединение дистрибутивно относительно пересечения множеств.

Установление тождеств алгебры множеств с помощью диаграмм Эйлера – Венна в ряде случаев оказывается неудобным. Доказательство тождеств может производиться также методом двустороннего включения, чтобы показать равенство множеств в левой и правой частях тождества (об этом уже упоминалось выше), методом преобразования одной части к другой, методом преобразования обеих частей к одному и тому же выражению. Установление тождеств алгебры множеств с помощью диаграмм Эйлера – Венна в ряде случаев оказывается неудобным. Доказательство тождеств может производиться также методом двустороннего включения, чтобы показать равенство множеств в левой и правой частях тождества (об этом уже упоминалось выше), методом преобразования одной части к другой, методом преобразования обеих частей к одному и тому же выражению. Пусть U – универсальное множество, А, В – его произвольные подмножества. Докажем тождество

Будем использовать метод двустороннего включения. Предположим, что х , т. е. что хАВ. Это значит, что хА и хВ, т. е. х и х Следовательно, х Итак Предположим теперь, что у , т. е. у и у Это значит, что уА и уВ, т. е. что уАВ. Следовательно, у . Итак, Таким образом тождество доказано. Будем использовать метод двустороннего включения. Предположим, что х , т. е. что хАВ. Это значит, что хА и хВ, т. е. х и х Следовательно, х Итак Предположим теперь, что у , т. е. у и у Это значит, что уА и уВ, т. е. что уАВ. Следовательно, у . Итак, Таким образом тождество доказано.

Симметрическая разность Симметрической разностью множеств А и В (обозначение АВ) называется множество (А\В)(В\А). Очевидно, что ВА = АВ для любых множеств А и В, т. е. симметрическая разность коммутативна. Докажем, что АВ = (АВ)\(АВ) для произвольных множеств А и В, т. е. докажем тождество (А\В)(В\А) = (АВ)\(АВ). Пусть А и В – произвольные подмножества некоторого универсального множества. На рис  приведены диаграммы Эйлера-Венна для выражений (А\В)(В\А) (объединение заштрихованных множеств А\В и В\А) и (АВ)\(ВА) (из объединения заштрихованных множеств А и В исключается множество с двойной штриховкой АВ) соответственно. Из этих диаграмм видно, что оба выражения определяют одно и то же множество. Тем самым доказана справедливость тождества и получена равносильная формула для вычисления симметрической разности множеств.

Тема 3. Соответствия

Пусть X и Y – два непустых множества. Если определен способ сопоставления элементов Y элементам Х, то говорят, что между множествами Х и Y установлено соответствие. При этом совершенно не обязательно, чтобы в сопоставлении участвовали все элементы множеств Х и Y. Для того чтобы задать соответствие между множествами Х и Y, нужно задать множество QX  Y, определяющее закон, по которому осуществляется соответствие, т. е. перечисляющий все пары (х, у), участвующие в сопоставлении. Пусть X и Y – два непустых множества. Если определен способ сопоставления элементов Y элементам Х, то говорят, что между множествами Х и Y установлено соответствие. При этом совершенно не обязательно, чтобы в сопоставлении участвовали все элементы множеств Х и Y. Для того чтобы задать соответствие между множествами Х и Y, нужно задать множество QX  Y, определяющее закон, по которому осуществляется соответствие, т. е. перечисляющий все пары (х, у), участвующие в сопоставлении. Таким образом, соответствие, обозначаемое q, представляет собой тройку множеств q = (X, Y, Q), в которой QX  Y. В этом выражении первую компоненту X называют областью отправления соответствия, вторую компоненту Y – областью прибытия соответствия, третью компоненту Q – графиком соответствия.

Кроме рассмотренных множеств X, Y и Q с каждым соответствием неразрывно связаны еще два множества: множество пр1Q, называемое областью определения соответствия, которое состоит из всех элементов множества Х, участвующих в сопоставлении, и множество пр2Q, называемое областью значений соответствия, которое состоит из всех элементов множества Y, участвующих в сопоставлении. Если (х, у)Q, то говорят, что элемент y соответствует элементу х. (xy). Если пр1Q = Х, то соответствие называется всюду определенным, или отображением Х в Y (в противном случае соответствие называется частичным). Если пр2Q = Y, то соответствие называется сюръективным (сюръекцией). Кроме рассмотренных множеств X, Y и Q с каждым соответствием неразрывно связаны еще два множества: множество пр1Q, называемое областью определения соответствия, которое состоит из всех элементов множества Х, участвующих в сопоставлении, и множество пр2Q, называемое областью значений соответствия, которое состоит из всех элементов множества Y, участвующих в сопоставлении. Если (х, у)Q, то говорят, что элемент y соответствует элементу х. (xy). Если пр1Q = Х, то соответствие называется всюду определенным, или отображением Х в Y (в противном случае соответствие называется частичным). Если пр2Q = Y, то соответствие называется сюръективным (сюръекцией).

Множество всех уY, соответствующих элементу хХ, называется образом х в Y при соответствии q. Множество всех хХ, которым соответствует элемент yY, называется прообразом y в Х при соответствии q. Если Спр1Q, то образом множества С называется объединение образов всех элементов С. Aналогично определяется прообраз множества D для любого Dпр2Q. Соответствие q называется инъективным (инъекцией), если любые различные х1 и х2 из пр1Q имеют различные образы и любые различные у1 и у2 из пр2Q имеют различные прообразы при соответствии q. Множество всех уY, соответствующих элементу хХ, называется образом х в Y при соответствии q. Множество всех хХ, которым соответствует элемент yY, называется прообразом y в Х при соответствии q. Если Спр1Q, то образом множества С называется объединение образов всех элементов С. Aналогично определяется прообраз множества D для любого Dпр2Q. Соответствие q называется инъективным (инъекцией), если любые различные х1 и х2 из пр1Q имеют различные образы и любые различные у1 и у2 из пр2Q имеют различные прообразы при соответствии q.

Соответствие q называется функциональным (или однозначным), если образом любого элемента хпр1Q является единственный элемент упр2Q. Соответствие q между множествами Х и Y называется взаимно однозначным, или биективным (биекцией) (иногда пишут «1-1-соответствие»), если оно всюду определено, сюръективно и инъективно. Однозначное отображение называется функцией. Функция является инъективной, если различным х1 и х2 из Х соответствуют различные у1 и у2 из Y, и сюръективной, если она сюръективна как соответствие. Функция называется биективной, если она одновременно инъективна и сюръективна. Соответствие q называется функциональным (или однозначным), если образом любого элемента хпр1Q является единственный элемент упр2Q. Соответствие q между множествами Х и Y называется взаимно однозначным, или биективным (биекцией) (иногда пишут «1-1-соответствие»), если оно всюду определено, сюръективно и инъективно. Однозначное отображение называется функцией. Функция является инъективной, если различным х1 и х2 из Х соответствуют различные у1 и у2 из Y, и сюръективной, если она сюръективна как соответствие. Функция называется биективной, если она одновременно инъективна и сюръективна.

Пример. Пусть Х = {1, 2}, Y = {3, 5}, значит, Х  Y = {(1, 3), (1, 5), (2, 3), (2, 5)}. Это множество дает возможность получить 16 различных соответствий. Графики соответствий: Пример. Пусть Х = {1, 2}, Y = {3, 5}, значит, Х  Y = {(1, 3), (1, 5), (2, 3), (2, 5)}. Это множество дает возможность получить 16 различных соответствий. Графики соответствий: Q0 = {( )} = , Q8 = {(1, 5), (2, 3)}, Q1 = {(1, 3)}, Q9 = {(1, 5), (2, 5)}, Q2 = {(1, 5)}, Q10 = {(2, 3), (2, 5)}, Q3 = {(2, 3)}, Q11 = {(1, 3), (1, 5), (2, 3)}, Q4 = {(2, 5)}, Q12 = {(1, 3), (1, 5), (2, 5)}, Q5 = {(1, 3), (1, 5)}, Q13 = {(1, 3), (2, 3), (2, 5)}, Q6 = {(1, 3), (2, 3)}, Q14 = {(1, 5), (2, 3), (2, 5)}, Q7 = {(1, 3), (2, 5)}, Q15 = {(1, 3), (1, 5), (2, 3), (2, 5)} = X  Y.

Обозначим qi соответствие с графиком Qi, Рассмотрим соответствие q9. Областью определения соответствия q9 является пр1Q9 = {1, 2} = X, поэтому q9 – отображение. Областью значений q9 является пр2Q9 = {5}  Y, поэтому q9 не сюръективно. 5 является образом 1 и 2 при соответствии q9, поэтому q9 не инъективно. Образом множества Х при соответствии q9 является множество {5}. Прообразом множества {5} при соответствии q9 является множество Х. Соответствие q9 функционально, так как каждый из элементов 1 и 2 имеет единственный образ – элемент 5. Обозначим qi соответствие с графиком Qi, Рассмотрим соответствие q9. Областью определения соответствия q9 является пр1Q9 = {1, 2} = X, поэтому q9 – отображение. Областью значений q9 является пр2Q9 = {5}  Y, поэтому q9 не сюръективно. 5 является образом 1 и 2 при соответствии q9, поэтому q9 не инъективно. Образом множества Х при соответствии q9 является множество {5}. Прообразом множества {5} при соответствии q9 является множество Х. Соответствие q9 функционально, так как каждый из элементов 1 и 2 имеет единственный образ – элемент 5.

На рис. изображено геометрическое представление соответствия q11. Графиком обратного соответствия q11–1 является множество Q11–1={(3, 1), (5, 1), (3, 2)}. Геометрическое представление q11–1 приведено на рис. На рис. изображено геометрическое представление соответствия q11. Графиком обратного соответствия q11–1 является множество Q11–1={(3, 1), (5, 1), (3, 2)}. Геометрическое представление q11–1 приведено на рис. Отображениями являются соответствия q6–q9, q11–q15. Сюръективными соответствиями являются q5, q7, q8, q10–q15. Функциональные соответствия: q1–q4, q6–q9. Инъективные соответствия: q1–q4, q7, q8. Функциями являются q6–q9. Биективные функции: q7, q8.

Примеры соответствий Англо-русский словарь Различные виды кодирования Представление чисел в различных системах счислений Секретные шифры Кодирование телефонов г. Минска Множество всех векторов вида (n, 2n), где nN,

Композиция двух соответствий Композицией двух соответствий называется последовательное применение двух соответствий. Композиция двух соответствий есть операция с тремя множествами X, Y, Z, на которых определены два соответствия: Причем область значений первого совпадает с областью определения второго соответствия: пр2Q = пр1Р. Первое соответствие q определяет для любого хпр1Q некоторый, возможно и не один, элемент упр2Q. Согласно определению операции композиции соответствий, теперь нужно для каждого такого у найти все соответствующие элементы zпр2Р, воспользовавшись вторым соответствием р.

Композицию соответствий q и р будем обозначать рq (знак  аналогичен умножению и часто опускается), а график композиции соответствий – через Q P. При этом композиция соответствий р и q запишется в виде: Композицию соответствий q и р будем обозначать рq (знак  аналогичен умножению и часто опускается), а график композиции соответствий – через Q P. При этом композиция соответствий р и q запишется в виде: pq = (X, Z, Q P), Q PX  Z. Например, если q – соответствие, определяющее распределение шоферов по автомашинам, р – соответствие, определяющее распределение автомашин по маршрутам, то соответствие рq есть соответствие, определяющее распределение шоферов по маршрутам.

Естественно, что операцию композиции можно распространить и на большее, чем два, число соответствий. Композиция n соответствий для n = 3, 4, 5, … определяется аналогично случаю n = 2. Естественно, что операцию композиции можно распространить и на большее, чем два, число соответствий. Композиция n соответствий для n = 3, 4, 5, … определяется аналогично случаю n = 2. Пусть Х – множество людей. Для каждого человека хХ обозначим через q(х) множество его детей. Тогда q2(х) – множество внуков х; q3(х) – множество правнуков х; q–1(х) – множество родителей х и т. д. Изображая людей точками и рисуя стрелки, идущие из х в q(х), получаем родословное, или генеалогическое, дерево.

Пусть f: XY – функция. Будем обозначать D(f) область определения функции и E(f) область значений функции f. Каждому элементу хХ f ставит в соответствие единственный элемент уY. Это обозначается записью f(х) = у либо f: ху. Тождественной функцией на множестве Х называется функция е: ХХ, такая что e(х) = х для любого хХ. Если X, YR, то функцию f называют вещественной. Пусть f: XY – функция. Будем обозначать D(f) область определения функции и E(f) область значений функции f. Каждому элементу хХ f ставит в соответствие единственный элемент уY. Это обозначается записью f(х) = у либо f: ху. Тождественной функцией на множестве Х называется функция е: ХХ, такая что e(х) = х для любого хХ. Если X, YR, то функцию f называют вещественной. Пусть даны функции f: XY и g: YZ. Функция h: XZ является композицией функций f и g, h = gf, если для любого xX h(x) = g(f(x)). Часто говорят, что функция h получена подстановкой f в g. Если f(X) состоит из единственного элемента, то f называется функцией-константой. Элемент х называется аргументом функции, у – значением функции на х.

Функция, полученная из f1, …, fn некоторой подстановкой их друг в друга и переименованием аргументов, называется суперпозицией f1,…,fn. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой. Функция, полученная из f1, …, fn некоторой подстановкой их друг в друга и переименованием аргументов, называется суперпозицией f1,…,fn. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой. Если f = (X, Y, Qf), то Qf = {(x, y)X  Y | y = f(x)} = {(x, f(x))X  Y}. Это соотношение позволяет установить способы задания функций.

1. Наиболее простой способ задания функций – это табличный. Таблицы при этом представляют собой конечные списки пар (х, f(х)). Однако таким способом могут быть заданы только функции, определенные на конечных множествах. Приведем примеры. 1. Наиболее простой способ задания функций – это табличный. Таблицы при этом представляют собой конечные списки пар (х, f(х)). Однако таким способом могут быть заданы только функции, определенные на конечных множествах. Приведем примеры. Из одного города в другой можно проехать по железной дороге, автобусом или катером. Стоимость билета будет соответственно 9000, 8000 и 10 000 руб. Стоимость билета можно представить как функцию от вида транспорта f: XY, где Х = {железная дорога, автобус, катер}, Y = {9000, 8000, 10000}. Функция f может быть задана в виде таблицы.

Рассмотрим множество Х := {1, 2, 3} и два преобразования этого множества – функции  и ; : 13, 23, 31 и : 12, 21, 31;  и  могут быть заданы таблично: Рассмотрим множество Х := {1, 2, 3} и два преобразования этого множества – функции  и ; : 13, 23, 31 и : 12, 21, 31;  и  могут быть заданы таблично: Композиции преобразований также можно задать таблично: Отсюда видно, что   . Итак, данный пример показывает, что композиция функций, а в общем случае отображений и вообще соответствий, не коммутативна.

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

Приведем некоторые свойства функций и их композиций. Приведем некоторые свойства функций и их композиций. 1. Композиция сюръективных функций сюръективна (следует из определений). 2. Композиция инъективных функций инъективна (следует из определений). 3. Композиция биективных функций биективна(следует из определений). 4. Композиция функций в общем случае не коммутативна. 5. Композиция функций ассоциативна. Пусть f: X → Y, g: Y → Z, h: Z → W– произвольные функции. Рассмотрим произвольный элемент х  Х. f(x) = y, g(y) = z, h(z) = w. Тогда hgf(x) = h(gf(x)) = h(g(y)) = h(z) = w, (hg)f(x) = hg(f(x)) = hg(y) = = h(g(y)) = h(z) = w; т. е. для любого х  Х h(gf)(x) = (hg)f(x). Значит, h(gf) = (hg)f.

Оператор Оператором называется функциональное отображение l: X → Y, в котором Х и Y являются множествами функций одного аргумента t. l = (X, Y, L), где L = {(x(t), y(t))  X х Y}, L  X х Y. В этом случае говорят, что оператор l преобразует функцию x(t) в функцию y(t) = l[x(t)]. В задачах управления роль оператора часто выполняет сама управляемая система, преобразующая по некоторому закону l входной сигнал х(t) в выходной сигнал у(t), как это показано на рис. (функциональное отображение)

Пример. Рассмотрим предложенную фон Нейманом блок-схему ЭВМ, которая состоит из множества взаимосвязанных устройств М= {a, b, c, d, e}, где а– устройство ввода, b – арифметическое устройство(процессор), с– устройство управления, d– запоминающее устройство, е– устройство вывода. Пример. Рассмотрим предложенную фон Нейманом блок-схему ЭВМ, которая состоит из множества взаимосвязанных устройств М= {a, b, c, d, e}, где а– устройство ввода, b – арифметическое устройство(процессор), с– устройство управления, d– запоминающее устройство, е– устройство вывода. Рассмотрим информационный обмен между устройствами mi и mj, которые находятся в отношении Т(mi, mj), если из устройства mi поступает информация в устройство mj. Опишем отношение Т как множество упорядоченных пар: Т  М2 T = {(a, b), (a, c), (a, d), (b, c), (b, d), (b, e), (c, a), (c, b), (c, d), (c, e), (d, b), (d, c), (d, e), (e, c)}.

Построим матрицу данного отношения: Построим матрицу данного отношения:

Бинарное отношение Бинарное отношение - это отношение между двумя объектами. Бинарное отношение можно определить как совокупность упорядоченных пар, указывающих объекты, находящиеся в данном отношении. Например, если нас интересует отношение «уважать» между двумя конкретными личностями а и b, то такое отношение может иметь различные формы. Так; если имеется отношение R = {(а,b)}, то это означает, что а уважает b. Отношение R1 = {(a,b), (b, а)} означает, что а уважает b и b уважает а. Нетрудно интерпретировать также другие отношения «уважать» между интересующими нас лицами: R2 = {(а,b), (a,a)}, R3= {(a,a), (b,b)} и т. д. В общем случае, если два элемента a, b находятся в данном отношении R, то этот факт записывают (a, b)R или aRb. Если эти элементы не находятся в отношении R, то это записывают так: (a,b)  R, или aR b.

Некоторым из наиболее известных отношений присваивают специальные названия и обозначения. Примеры: эквивалентность (=), отношение порядка(>) или(>), равенство(=), параллельность(||), перпендикулярность (┴) и т. д. Некоторым из наиболее известных отношений присваивают специальные названия и обозначения. Примеры: эквивалентность (=), отношение порядка(>) или(>), равенство(=), параллельность(||), перпендикулярность (┴) и т. д. Очевидно, что всякое бинарное отношение R можно рассматривать как подмножество прямого произведения некоторых множеств А и В: R  AхB Левой областью бинарного отношения называют множество всех первых компонент упорядоченных пар, составляющих данное отношение, то есть R_={a|(a,b) R}. Правой областью бинарного отношения R называют множество всех вторых компонент упорядоченных пар, составляющих данное отношение, то есть R+={b|(a,b) R}. Например, пусть R = {(1, 1), (1, 2), (1, 3), (3, 3)}. Тогда R_= {1, 3}, R+ = {1, 2, 3}.

Полем бинарного отношения R называют объединение его левой и правой областей: F (R)= R_ R+. Полем бинарного отношения R называют объединение его левой и правой областей: F (R)= R_ R+. Бинарное отношение R–1 называют обратным к отношению R, если (a,b)  R–1 тогда и только тогда, когда (b,a) R, то есть R–1={(b,a)|(a,b) R}. Например, если R = {(1, 1), (1, 2), (1, 3), (3, 4)}, то R–1= {(1, 1), (2, 1), (3, 1),(4, 3)}. Пересечением бинарного отношения R по элементу aF(R) называют совокупность всех вторых(различных) компонентов упорядоченных пар, составляющих данное отношение, и таких, у которых первой компонентой есть элемент а. Обозначение: Ra. Например, для предыдущего бинарного отношения R имеем: R1 = {l, 2, 3}, R2= Ø, R3= {4}, R4 = Ø.

Способы задания бинарных отношений Способы задания отношений зависят от свойств бинарного отношения. Различают следующие способы задания таких отношений. 1. Бинарное отношение R можно задать перечислением всех упорядоченных пар, находящихся в отношении R. Очевидно, что такой способ задания отношений приемлем для относительно небольшого числа упорядоченных пар. Например: R1= {(1, 1), (2, 2), (3, 3), (4, 4)}. 2. Если трудно перечислить все упорядоченные пары, составляющие отношение, то его можно задать формулой. Например:S ={(a,b) | (a ‒b)= 0 mod3;a,b {0..10}.

3. Графическое задание бинарного отношения предполагает графическое представление элементов левой и правой областей отношения в виде точек в этих областях, соединенных дугами(направленными отрезками). Каждая дуга представляет некоторую упорядоченную пару, находящуюся в данном отношении. Дуга начинается в точке, соответствующей первой компоненте упорядоченной пары, и заканчивается в точке, соответствующей второй компоненте упорядоченной пары. 3. Графическое задание бинарного отношения предполагает графическое представление элементов левой и правой областей отношения в виде точек в этих областях, соединенных дугами(направленными отрезками). Каждая дуга представляет некоторую упорядоченную пару, находящуюся в данном отношении. Дуга начинается в точке, соответствующей первой компоненте упорядоченной пары, и заканчивается в точке, соответствующей второй компоненте упорядоченной пары. Пример отношения S = {(a, b), (a, c), (b, c), (b, d)] представлен на рисунке

4. Бинарное отношение можно задать в табличной форме. В этой таблице указываются все элементы поля отношения и соответствующие им пересечения данного отношения по выбранному элементу. Например: 4. Бинарное отношение можно задать в табличной форме. В этой таблице указываются все элементы поля отношения и соответствующие им пересечения данного отношения по выбранному элементу. Например: 5. Бинарное отношение можно задать матрицей||ai,j||, в которой строки и столбцы соответствуют полю отношения. В этой матрице i-я строка соотносится с некоторым элементом левой области отношения, а j-й столбец – с некоторым элементом правой области отношения. Тогда ai,j= 1, если соответствующие элементы находятся в данном отношении, и ai,j= 0 в противном случае. Например:

Операции над бинарными отношениями Так как всякое бинарное отношение– это множество упорядоченных пар, то над бинарными отношениями можно выполнять все теоретико-множественные операции: объединение, пересечение, разность, дополнение. Если R – бинарное отношение, то в качестве универсального множества в этом случае рассматривают множество U = F(R) × F(R), где F(R) – поле отношения R. Если совместно рассматривается несколько бинарных отношений, то в качестве универсального множества рассматривают множество U= A × А, где А есть объединение полей каждого из рассматриваемых отношений.

Например, пусть рассматриваются отношения R = {(1, 1), (1, 2), (1, 3), (3, 3)} и S = {(1, 1), (2, 2), (3, 3)}. В этом случае универсальное множество имеет вид: U = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}. Например, пусть рассматриваются отношения R = {(1, 1), (1, 2), (1, 3), (3, 3)} и S = {(1, 1), (2, 2), (3, 3)}. В этом случае универсальное множество имеет вид: U = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}. Тогда результаты некоторых теоретико-множественных операций будут следующими: R= {(2, 1), (2, 2), (2, 3), (3, 1), (3, 2)}; S= {(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)}. R \ S= {(1, 2), (1, 3)}; R⋂ S= {(1, 1), (3, 3)}. Кроме обычных теоретико-множественных операций, над бинарными отношениями определяют специальную операцию.

Композицией бинарных отношений R и S называют бинарное отношение Т, состоящее из всех упорядоченных пар (а,b), для каждой из которых существует элемент cR+⋂S_ такой, что(а, с)  R, (с,b) S (то есть aRc, cSb). Операцию композиции записывают так: Т= R°S. Композицией бинарных отношений R и S называют бинарное отношение Т, состоящее из всех упорядоченных пар (а,b), для каждой из которых существует элемент cR+⋂S_ такой, что(а, с)  R, (с,b) S (то есть aRc, cSb). Операцию композиции записывают так: Т= R°S. Например, пусть R = {(1, 1), (1, 2), (2, 3), (3, 3)}, S = {(2, 4), (2, 5), (3, 2), (5, 5)}. Тогда R°S = {(1, 4), (1, 5), (2, 2), (3, 2)}, S°R = {(3, 3)}.

Свойства бинарных отношений Бинарное отношение R называют рефлексивным, если для любого элемента а F(R) имеет место aRa. Примерами рефлексивных отношений могут служить отношение подобия ( ~ ), отношение параллельности (||), диагональное отношение на множестве А = {а, b, с}: ΔA = {(а, а), (b,b), (с, с)}. Бинарное отношение R называют антирефлексивным, если для любого элемента поля а F(R) имеет место aRa.Примерами антирефлексивных отношений являются отношения порядка (<), (>), отношение перпендикулярности. Если задано бинарное отношение R1 = {(a, а), (а,b), (b,b), (а, с), (с, с)}, то это отношение рефлексивно, а бинарное отношение R = {(a, b), (b, c), (b, b), (a, c)} ‒ нет. Бинарное отношение R3 = {(а,b), (b, с), (а, с)} антирефлексивно.

Бинарное отношение R симметричное, если из aRb следует bRa. Примерами таких отношений являются отношение равенства (=), подобия(~), диагональное отношение ΔA, отношение перпендикулярности, отношение параллельности (||). Бинарное отношение R асимметрично, если из aRb следует bRa. Бинарное отношение R симметричное, если из aRb следует bRa. Примерами таких отношений являются отношение равенства (=), подобия(~), диагональное отношение ΔA, отношение перпендикулярности, отношение параллельности (||). Бинарное отношение R асимметрично, если из aRb следует bRa. Асимметричными являются отношения порядка (<), (>). Бинарное отношение R называют антисимметричным, если из aRb и bRa следует, что а = b. Заметим, что антисимметричное отношение отличается от асимметричного лишь тем, что в антисимметричном отношении допускается существование упорядоченной пары с одинаковыми компонентами. Пример. S1 = {(а, а), (b,b), (с, с)} и S2= {(a,a), (a,b), (a,c), (b,a), (c,a)} симметричны. С другой стороны, бинарные отношения S1 = {(a,a), (b,b), (c, c)}, S3 = {(a,b), (a,c), (a,a), (b,c)} антисимметричны.

Бинарное отношение R называют транзитивным, если из aRb и bRc следует aRc. Примерами транзитивных отношений являются отношение равенства (=), отношение подобия (~), диагональное отношение ΔA, отношения порядка, отношение параллельности (||). Примерами транзитивных отношений также могут служить отношения S1 и S3. Бинарное отношение R называют транзитивным, если из aRb и bRc следует aRc. Примерами транзитивных отношений являются отношение равенства (=), отношение подобия (~), диагональное отношение ΔA, отношения порядка, отношение параллельности (||). Примерами транзитивных отношений также могут служить отношения S1 и S3. В противном случае отношение R называют нетранзитивным. Пример. Отношение перпендикулярности В зависимости от свойств, которыми обладают бинарные отношения, выделяют и исследуют различные типы отношений. Наиболее известные из них ‒ отношения эквивалентности и порядка. Бинарное отношение называют отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Примеры отношения эквивалентности: отношение равенства(=), отношение параллельности (||) и тому подобное.

Классом эквивалентности Ra называют множество всех вторых компонентов упорядоченных пар отношения эквивалентности R, у которых первой компонентой является элемент а: Классом эквивалентности Ra называют множество всех вторых компонентов упорядоченных пар отношения эквивалентности R, у которых первой компонентой является элемент а: Ra = {b | (a, b)  R}. Иначе говоря, классом эквивалентности называют пересечение отношения эквивалентности по элементу поля этого отношения. Так, например, в отношении равенства класс эквивалентности любого элемента а состоит из единственного элемента а, класс эквивалентности отношения параллельности состоит из всех параллельных прямых.

Пример. Бинарное отношение S1 является отношением эквивалентности. В нем каждый класс эквивалентности состоит также из одного элемента: Пример. Бинарное отношение S1 является отношением эквивалентности. В нем каждый класс эквивалентности состоит также из одного элемента: S1(a) = {a},S1(b) = {b} и S1(c) = {с}. Пусть имеется бинарное отношение S = {(а, а), (а,b), (b, а), (b,b), (с, с), (d,d), (d,e), (e,d), (e,e)}. Нетрудно видеть, что данное отношение рефлексивно, симметрично и транзитивно. Следовательно, отношение S есть отношение эквивалентности. Имеем классы эквивалентности: Sa= {a,b},Sb= {a,b},Sc = {c},Sd = {d, e},Se= {d,e}.

Диаграмма Хассе Для графического представления упорядоченного множества R используют диаграмму Хассе. Эта диаграмма строится следующим образом: каждому элементу поля F(R) ставится в соответствие точка (кружок) на плоскости, причем, если aRb, точку, соответствующую элементу а, располагают ниже точки, соответствующей элементу b. Точки, принадлежащие полю отношения порядка, то есть a,b F(R), соединяют линией (ребром), если aRb и не существует элемента с  F(R) такого, что aRc и cRb. Пример. Пусть имеется отношение порядка: R = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 5), (2, 7), (2, 8), (3, 5), (3, 6), (3, 8), (4, 6), (4, 7), (4, 8), (5, 8), (6, 8), (7, 8)}. Диаграмма Хассе данного отношения: