Министерство общего и профессионального образования

Российской Федерации

Южно-Уральский Государственный Университет

Кафедра АиУ.

Реферат

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

ТЕОРИЯ МНОЖЕСТВ

Выполнил: Подрезов Сергей Валерьевич

Группа: ПС-243

Преподаватель: Разнополов Олег Александрович

Челябинск 2005

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.. 3

1. МНОЖЕСТВА И ИХ СВОЙСТВА.. 3

1.1. Основные понятия теории множеств. 3

1.2. Множества и их спецификации. 5

1.3. Операции над множествами. 8

1.4. Тождества алгебры множеств. 12

2. Отображение и функция. 15

2.1. Соответствия. 15

2.2. Отображения. 16

2.3. Взаимосвязь понятий “отношение”, “соответствие”, “отображение”. 17

2.4. Функции. 18

2.4.1. Понятие функции. 18

2.4.2. Инъективная, сюръективная и биективная функции. 19

2.4.3. Обратная функция. 19

2.4.4. Понятие функционала. 20

2.5 Понятие оператора. 20

Список используемой литературы.. 21

ВВЕДЕНИЕ

В современной иерархии математических наук дискретная математика является промежуточным звеном между рядом дисциплин естественно-научного и технического профиля. Дискретная математика тесно связана с такими дисциплинами, как алгебра, геометрия, логика. Она также непосредственно связана с технической кибернетикой и информатикой.

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

На сегодняшний день наиболее значимым направлением развития дискретной математики являются информационные технологии. Это объясняется, прежде всего, необходимостью создания и эксплуатации персональных ЭВМ, компьютерных сетей, систем управления, а также автоматизированных средств обработки информации.

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

1. МНОЖЕСТВА И ИХ СВОЙСТВА

1.1. Основные понятия теории множеств

Почти во всех разделах дискретной математики используется понятие множества. Как правило, специалистам-математикам приходится рассматривать некоторую совокупность объектов как единое целое.

Создателем теории множеств был немецкий учёный Георг Кантор (1845-1918), утверждавший: “множество есть многое, мыслимое нами как единое”. Это утверждение, разумеется, не может служить математически строгим определением множества; такового на сегодняшний день просто не существует.

Понятие множества определяется, по-видимому, некоторым свойством, которым должен либо обладать, либо не обладать каждый из рассматриваемых объектов. В свете сказанного, дадим множеству нестрогое определение.

☼ (нестрогое). Множество – это совокупность объектов, обладающих одним и тем же определённым свойством.

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

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

☼ Отдельные объекты, из которых состоит множество, называются элементами множества.

Например, число 3 – элемент множества натуральных чисел, буква б – элемент множества букв русского алфавита.

Заметим, что элементы множества сами могут являться множествами.

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

Общим обозначением множества служит пара фигурных скобок: { }.

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

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

A₁, A₂ ...

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

a, s, x ...

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

a₁, a₂ ...

Для указания того, что некоторый элемент a является элементом множества S, используется символ Î принадлежности множеству. Запись

a Î S

означает, что элемент a принадлежит множеству S, а запись

x Ï S

означает обратное. Запись

x1, x2, ... , xn Î S

используется в качестве сокращения отдельных записей

x1Î S, x2Î S, ... , xnÎ S.

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

Во-первых, проблематична отличимость элементов. В частности, возникает вопрос: символы a и a - это один элемент множества A или же два разных элемента ?

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

В теории множеств важную роль играют понятия универсального множества (универсума) и пустого множества.

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

Чаще всего оно имеет обозначение: U.

☼ Пустым называется множество, не содержащее ни одного элемента.

Пустое множество обозначается символом Æ.

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

Иногда бывает трудно определить, является ли данное множество пустым.

Иначе, к примеру, обстоит дело с множеством Z₁ всех решений в целых положительных числах уравнения

В этом случае мы знаем метод, с помощью которого мы можем решить вопрос о том, является ли множество Z₁ пустым, но необходимые для этого вычисления весьма трудоёмки (деление числа на некоторые числа <).

Далее, фундаментальными являются также понятия конечного и бесконечного множества.

☼ Непустое множество называют конечным, если возможно указать число его элементов.

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

Например, множество китов в океане конечно, а множество

рациональных чисел бесконечно.

Пустое множество условно будем считать конечным.

В теории множеств также применяется понятие равенства множеств.

☼ Множества, состоящие из одних и тех же элементов, называют равными (совпадающими).

Если два множества A и B равны, то есть состоят из одних и тех же элементов, то пишут

A=B.

В противном случае пишут

A¹B.

Конкретнее, последняя запись означает, что либо во множестве A есть такой элемент, которого нет в множестве B, либо во множестве B есть такой элемент, которого нет в множестве A, или же имеет место и то, и другое.

Очевидно, что равны два конечных множества, отличающиеся друг от друга лишь порядком их элементов, например:

{a, b, c} = {c, a, b}.

Понятие равенства множеств обладает следующими свойствами:

X=X – рефлексивность;

Если X=Y, то Y=X – симметричность;

Если X=Y и Y=Z, то X=Z – транзитивность.

Как уже упоминалось, во множестве не должно быть неразличимых элементов. Поэтому во множестве не может быть одинаковых элементов. В частности, запись {2, 2, 3, 5} некорректна и её следует заменить на {2, 3, 5}.

В теории множеств существует и понятие равномощных множеств.

☼ Мощностью конечного множества называется число его элементов, и обозначается |M|.

☼ Два конечных множества A и B называются равномощными при условии равенства их мощностей.

Теперь, пользуясь понятием равномощности, дадим определение счётному и несчётному множествам.

☼ Счётное множество – это такое конечное либо перечислимое бесконечное множество, мощность которого не превосходит мощности множества натуральных чисел. Прочие бесконечные множества называются несчётными.

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

понятий и выяснении их логических связей.

1.2. Множества и их спецификации

Чтобы оперировать с конкретными множествами, их нужно уметь задавать. На сегодняшний день существует 3 способа задания конечных множеств:

перечисление;
описание;
посредством порождающей процедуры.

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

Остановимся на трёх указанных способах более подробно.

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

{Иванов, Петров, Сидоров}.

Другая сокращённая запись данного способа – вводят множество индексов

I={1, 2,..., n}

и пишут:

A={ai}, iÎ I.

При втором способе применяется запись

A={x Î M | x – отличник группы},

что читается следующим образом:

“множество A отличников группы состоит из элементов x множества M студентов этой группы, обладающих тем свойством, что x – это отличник

группы”.

Когда нет сомнений, из какого множества берутся элементы x, указание о принадлежности x множеству M можно не делать. Тогда множество A записывается в виде:

A={x | x – отличник группы}.

Приведём ещё примеры ко второму (описательному) способу:

{x | x – чётное} – множество чётных чисел;

{x | x2-1=0} – множество {+1, - 1}.

Третий способ, как уже упоминалось, состоит в использовании порождающей процедуры.

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

Пример для третьего способа:

M={n | for n from 1 to 9}.

Для конечных множеств, заданных перечислением (первым способом), задача нахождения наибольшего и наименьшего элемента множества не представляет труда. Например, для множества T={4, 3, 5, 6}

6 – максимум, а 3 – минимум.

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

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

Пусть S – множество вещественных чисел. Верхней границей S является число C такое, что для любого xÎS имеет место:

x£C.

Чисел, которые могут рассматриваться в качестве верхней границы множества, может быть бесконечно много, а может и не быть вообще.

Пример в множестве

m<S<M

любое C³M является верхней границей.

☼ Точной верхней границей (супремумом) множества называется такая верхняя граница, которая не превосходит любую другую верхнюю границу.

Для множества S обозначение точной верхней границы будет таким:

sup S.

Для примера справедливо

sup S=M.

Множество может иметь только одну верхнюю границу.

Пусть S – множество вещественных чисел. Нижней границей S является число с такое, что для любого xÎS имеет место:

x³c.

☼ Точной нижней границей (инфинумом) множества называется нижняя граница, не меньшая любой другой нижней границы.

Для множества S обозначение точной верхней границы будет таким:

inf S.

Для примера справедливо

inf S=m.

Второй, описательный способ задания множеств, таит некоторые опасности, поскольку “неправильно” заданные свойства могут привести к противоречию. Укажем один из наиболее типичных теоретико-множественных парадоксов – парадокс Рассела.

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

Y={X | X ÏX} (*)

Если множество Y существует, то мы должны иметь возможность ответить на следующий вопрос:

YÎY ?

Допустим, что YÎY, тогда в соответствии с (*)

YÏY.

Теперь допустим, что YÏY, тогда в соответствии с (*)

YÎY.

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

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

A{xÎM | Q(x)},

где M – известное, заведомо существующее множество (универсум).

Для Y универсум не указан, а потому Y множеством не является.

Использовать типы.

Объекты имеют тип 0, множества имеют тип 1, множества множеств – тип 2 и т. д.

Y не имеет типа и множеством не является.

Задавать A(x) в виде вычислимой функции (алгоритма).

Способ вычисления значения XÎX не задан, а потому Y множеством не является.

В качестве центральных в теории множеств выступают понятия подмножества и надмножества.

☼ Множество A называется подмножеством множества B, если любой элемент множества A принадлежит и множеству B.

B в этом случае называется надмножеством множества A.

☼ Если множество B включает в себя A, что выражается AÌB,

но при этом A¹B, то A называется собственным подмножеством B.

Очевидно, что часть собственного подмножества данного множества всегда является собственным подмножеством этого множества.

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

Два множества равны, если они являются подмножествами друг друга.

Применительно к введённым понятиям подмножества и надмножества действует следующая Теорема о верхней и нижней границах подмножества.

Если

BÍA,

то имеет место

inf B³ inf A, sup B £ sup A.

Для определения подмножества характерно использование следующих символов:

" - символ, называемый квантором и означающий “любой”, “каков бы ни был”, “для всех”;

® - символ следствия (импликации), означающий “влечёт за собой”.

При помощи этих двух символов определение подмножества можно сформулировать так:

" x [xÎX ® xÎY],

что читается следующим образом: для любого x утверждение “x принадлежит X” влечёт за собой утверждение “x принадлежит Y”.

Отметим некоторые свойства подмножества, вытекающие из его определения:

XÍX (рефлексивность);

[XÍY и YÍZ] ® XÍZ (транзитивность).

Для любого множества M справедливо

Æ Í M.

Естественно, что пустое множество Æ не содержит элементов. Следовательно, при добавлении к M пустого множества мы фактически не добавляем ничего. Поэтому всегда считается, что любое множество M содержит в себе пустое в качестве подмножества.

☼ Совокупность всех подмножеств множества A называется его булеаном или множеством-степенью и обозначается 2A:

2A={B | BÌA}.

Множества удобно изображать графически. В конце XIX века английский учёный Джордж Венн усовершенствовал введённые Эйлером круги для иллюстрации множеств, добавив к изображению объёма рассматриваемого понятия X изображение объёма логически противоположного ему понятия НЕ X (ØX). Объём понятия ØX дополняет объём понятия X.

☼ Изображение множества в виде областей в прямоугольнике, представляющем универсальное множество, называется диаграммой Эйлера-Венна

Рис. Представление множества диаграммой Эйлера-Венна

1.3. Операции над множествами

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

Пусть A и B – некоторые числа, A+B – их сумма, AB – их произведение. Сумма и произведение чисел обладают следующими свойствами:

A+B=B+A; AB=BA – коммутативный или переместительный закон

(A+B)+C=A+(B+C); (AB)C=A(BC) – ассоциативный или сочетательный закон

(A+B)C=AC+BC – дистрибутивный или распределительный закон

Интересно отметить, что в ассоциативном и коммутативном

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

Однако в дистрибутивном законе такой симметрии нет.

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

☼ Объединением множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X, Y, т. е. принадлежат X либо принадлежат Y, что обозначается так:

XÈY.

Формальное определение объединения множеств имеет вид:

XÈY={x | xÎX или xÎY}.

Если X={1, 2, 3, 4, 5} и Y={2, 4, 6, 7}, то XÈY={1, 2, 3, 4, 5, 6, 7}.

Рассмотрим два круга. Если X – это множество точек левого круга, а Y – множество точек правого круга, то объединение XÈY представляет собой заштрихованную область, ограниченную обоими кругами.

Рис. Объединение множеств

Для объединения множеств справедливы коммутативный и ассоциативный законы:

XÈY= YÈX;

(XÈY) ÈZ=XÈ(YÈZ).

☼ Пересечением множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y, что обозначается так:

XÇY.

Формальное определение объединения множеств имеет вид:

XÇY={x | xÎX или xÎY}.

Для множеств X={1, 2, 3, 4, 5} и Y={2, 4, 6, 7}: XÇY={2, 4}.

Рассмотрим два круга, представленных на рис. 1.3. Если X – это множество точек левого круга, а Y – множество точек правого круга, то пересечение XÇY представляет собой заштрихованную область, общую для обоих кругов.

Операция пересечения позволяет установить ряд соотношений между двумя множествами.

☼ Множества X и Y называют непересекающимися, если они не имеют общих элементов, т. е. если

XÇY=Æ.

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

Непересекающимися множествами, например, являются:

множества {1, 2, 3} и {4, 5, 6};

множество отличников и множество неуспевающих студентов в группе;

множества точек кругов.

Непересекающиеся множества

Существует три условия, при соблюдении которых два множества X и Y находятся в т. н. общем положении:

существует элемент множества X, не принадлежащий Y;

существует элемент множества Y, не принадлежащий X;

существует элемент множества, принадлежащий как X, так и Y.

Отметим одно отличие теории множеств от алгебры чисел. Так, если a и b – два числа, то между ними должно выполняться одно из соотношений:

a<b, a=b, b<a.

Что же касается двух множеств X и Y, то для них может не выполняться ни одно из соотношений

XÌY, X=Y, YÌX.

На практике между двумя множествами X и Y возможны ещё два

соотношения:

XÇY=Æ;

пребывание X и Y в общем положении. Нетрудно заметить, что пересечение множеств обладает коммутативным свойством, а именно

XÇY=YÇX,

а также ассоциативным:

(XÇY) ÇZ=XÇYÇZ.

Имеет место и соотношение

XÇÆ=Æ,

что аналогично соотношению a×0=0 в обычной алгебре.

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

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

☼ Разностью множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат X и не принадлежат Y, что обозначается так:

X \ Y;

на рисунке разность множеств – это заштрихованная фигура. Т. о., формальное определение:

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

X \ Y={x | xÎX и xÏY}.

Для множеств X={1, 2, 3, 4, 5} и Y={2, 4, 6, 7} их разности:

X \ Y={1, 3, 5}, Y \ X={6, 7}.

Симметрическая разность множеств

☼ Симметрической разностью множеств X и Y называется множество

;

Т. о., её формальное определение есть

Для множеств X={1, 2, 3, 4, 5} и Y={2, 4, 6, 7}:

{1, 3, 5, 6, 7}.

Более подробно остановимся на понятии универсального множества, определение которому было дано в п. 1.1.

Подобно тому, как пустое множество играет роль нуля в алгебре множеств, универсальное множество U играет роль единицы, т. е. удовлетворяет условию:

XÇU=X,

аналогичное условию

a×1 = a

в обычной алгебре.

Указанное соотношение означает, что пересечение или “общая часть” множества U и множества X совпадает с самим этим множеством. Это возможно лишь в том случае, если множество U содержит все элементы, из которых может состоять множество X, так что любое множество X полностью содержится в множестве U.

Если U есть совокупность всех натуральных чисел, то X, скажем,

может обозначать множество всех чётных чисел; если U обозначает совокупность всех точек на плоскости, то X может быть множеством точек какого-то круга и проч.

В алгебре множеств существуют также операции дополнения и разбиения множеств.

☼ Множество X, определяемое из соотношения

называется дополнением множества X (до универсального).

Формальное определение имеет вид:

={x | xÎU и xÏX}.

Если U={1, 2, 3, 4, 5, 6, 7} и X={3, 5, 7}, то ={1, 2, 4, 6}.

Из определения множества X следует, что X и ØX не имеют общих элементов, т. е.

XÇ=Æ.

Кроме того, не имеется элементов множества U, которые не принадлежали бы ни X, ни , поскольку элементы, не принадлежащие X, принадлежат . Следовательно,

XÈ=U.

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

☼ Разбиением непустого множества A называется совокупность подмножеств, объединение которых даёт A, причём упомянутые подмножества взаимно не пересекаются.

Если же последнее условие не выполняется, то говорят не о разбиении, а о покрытии.

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

Если N – множество натуральных чисел, а A₀ и A₁ – множество чётных и нечётных чисел, то система {A₀, A₁} будет разбиением множества N.

1.4. Тождества алгебры множеств

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

Логическая терминология	Язык теории множеств
“A или B”	A+B
“A и B”	AB
“Не A”	A’
“Ни A, ни B”	(A+B)’, или, что то же, A’B’
“Не сразу A и B”	(AB)’, или, что то же, A’+B’
“Всякое A есть B”, или “Если A, то B”, или “Из A следует B”	AÌB
“Какое-то A есть B”	AB¹Æ
“Никакое A не есть B”	AB=Æ
“Какое-то A не есть B”	AB’¹Æ
“Нет никакого A”	A=Æ

Кроме того, в терминах теории множеств силлогизм “если всякое A есть B и всякое B есть C, то всякое A есть C”, принимает простой вид:

если AÌB и BÌC, то AÌC.

Аналогично “закон противоречия”, утверждающий, что “объект не может одновременно обладать и не обладать некоторым свойством, записывается в виде:

AA’=Æ,

и “принцип исключённого третьего”, говорящий, что “объект должен или обладать, или не обладать некоторым свойством”, записывается:

A+A’=U.

На основе слияния логического анализа математики и математического анализа логики создалась новая дисциплина – математическая логика.

Установление тождеств алгебры множеств посредством рассматривавшейся диаграммы Эйлера-Венна не всегда оказывается удобным. Существует более общий способ установления тождественности двух алгебраических выражений.

Пусть этими выражениями являются следующие:

a (X, Y, Z) и b (X, Y, Z).

Пусть также они получены путём применения операций объединения, пересечения и дополнения к множествам X, Y, Z. Чтобы доказать справедливость того, что

a =b,

необходимо и достаточно будет показать, что

a Íb и что b Ía.

Далее, чтобы показать, что a Íb, следует убедиться, что из xÎa следует xÎb. Аналогичным образом, чтобы показать, что b Ía, следует убедиться в том, что из xÎb следует xÎa.

Докажем таким способом следующее тождество, называемое в литературе тождеством де-Моргана:

Предположим, что xÎ, т. е. что xÏ. Это означает, что xÏX и xÏY,

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

Предположим теперь, что , т. е. что и . Это

значит, что yÏX и yÏY, т. е. что yÏ XÈY. Отсюда следует: .

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

☼ Кортежем называется последовательность элементов, т. е. такая их совокупность, в которой каждый элемент занимает определённое место.

Сами элементы при этом называются компонентами кортежа (первая компонента, вторая компонента и т. д.).

Примеры кортежей:

множество людей, стоящих в очереди;

множество слов во фразе;

числа, характеризующие долготу и широту какой-либо

географической точки и т. д.

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

В технических задачах эта определённость часто является просто предметом договорённости. В частности, только договорённостью можно объяснить, почему при описании географической точки долготу ставят на первое место, а широту на второе.

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

Например, если обозначить через h высоту полёта летательного

аппарата, а через v обозначить его скорость, то кортеж

X=(h, v)

будет описывать состояние самолёта.

☼ Длиной кортежа называется число его элементов.

Например, множество

a=(a1, a2, ..., an)

является кортежем длины n с элементами a1, a2, ..., an.

Кортежи длины 2 называют парами, кортежи длины 3 – тройками, 4 – четвёрками и т. д.

Для кортежей возможны следующие частные случаи:

кортеж (a) длиной 1;

пустой кортеж длины 0, обозначаемый ( ).

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

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

Например, кортеж (a₁, a₂) может рассматриваться как точка на плоскости или вектор, проведённый из начала координат в данную точку (рис. 1.7). Компоненты a₁ и a₂ будут проекциями вектора на оси 1 и 2, т. е.

Пр₁(a₁, a₂)= a1; Пр₂(a₁, a₂)= a₂.

Проекции 2-элементного кортежа

Трёхэлементный кортеж (a1, a2, a3) может рассматриваться как точка в трёхмерном пространстве или как трёхмерный вектор, проведённый из начала координат в эту точку. Компоненты a1, a2, a3 будут проекциями вектора на оси 1, 2, и 3, т. е.

Пр_i(a₁, a₂, a₃)= a_i, i=1, 2, 3.

В дальнейшем мы будем рассматривать компоненты n-элементного кортежа как проекции его на соответствующие оси, т. е.

Пр_i a = a_i,

☼ Прямым произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая – множеству Y.

Таким образом, элементы прямого произведения множеств представляют собой 2-элементные кортежи вида (x, y).

Формальное определение записывается следующим образом:

Пусть X={1, 2}, Y={1, 3, 4}. Тогда прямое произведение двух этих множеств будет таким:

={(1, 1), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4)}.

(x, y)

3 Y y

0 1 2 X

a б

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

Полученный результат поясняется на рисунке а.

Пусть X и Y – это отрезки вещественной оси.

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

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

Операция прямого произведения множеств распространяется и на большее количество множеств.

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

☼ s-той степенью произвольного множества M называется прямое произведение s одинаковых множеств, равных M.

Это выражается следующей записью:

s раз

2. Отображение и функция

2.1. Соответствия

Рассмотрим два множества X и Y. Элементы этих двух множеств могут каким-либо образом сопоставляться друг с другом, образуя пары (x, y).

☼ Если способ сопоставления двух множеств X и Y определён, т. е. если для элемента xÎX указан элемент yÎY, с которым сопоставляется элемент x, то говорят о наличии соответствия между двумя множествами. При этом совершенно необязательно, чтобы в сопоставлении участвовали все элементы множеств X и Y.

Для задания соответствия необходимо указать:

множество X, элементы которого сопоставляются с элементами другого множества;
множество Y, с элементами которого сопоставляются элементы первого множества;
множество , определяющее закон, согласно которому

осуществляется соответствие.

Соответствие, обозначенное через q, представляет собой тройку множеств

, где .

☼ В вышеуказанном выражении первая компонента X называется областью отправления соответствия, вторая компонента Y называется областью прибытия соответствия, третья компонента Q называется графиком соответствия.

Кроме того, с каждым соответствием неразрывно связаны ещё два множества:

1) Пр1 Q, называемое областью определения соответствия (в него входят элементы множества X, участвующие в сопоставлении);

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

Пример. На предприятии имеются три автомашины: две грузовые a и b, работающие в две смены, и автобус g, используемый редко. Машина b находится в ремонте. В штате имеются три шофёра a, b, c, из которых с находится в отпуске. Распределение шоферов по машинам представляет собой соответствие. Одним из возможных соответствий будет следующее:

Геометрически это соответствие изображается, как показано на рисунке а. На этом рисунке элемент a соответствует элементам a и b, а элемент g соответствует элементу a. Соответствие q определено на a и b, но не определено на c, следовательно, областью определения соотвествия является множество {a, b}. Областью значений соответствия является множество {a, g}.

a b c a b c

a b g a b g

а) б)

Геометрическое представление прямого (а) и обратного (б) соответствий

2.2. Отображения

Рассмотрим два множества X и Y.

☼ Если бинарное отношение R между двумя множествами X и Y является всюду определённым соответствием, т. е. каждому элементу x соответствует элемент y, то имеет место отображение X в Y. Это записывается в виде:

Другая форма записи:

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

Если в предыдущем примере исключить из рассмотрения шофёра c и грузовик b и пересадить шофёра b на автобус g вместо шофёра a, то получим отображение

в котором X={a, b} – множество шоферов,

Y={a, g} – множество автомашин,

f={(a, a), (b, g)} – распределение шоферов по автомашинам.

a b

a g

Геометрическое представление отображения

☼ Отображение множества X на само себя, т. е.

называется перестановкой множества X.

2.3. Взаимосвязь понятий “отношение”, “соответствие”, “отображение”

Взаимосвязь понятий “отношение”, “соответствие” и “отображение”

показана на рисунке.

Унарное

n-местное

Бинарное

Полная (отображение)

Частичная

Взаимосвязь понятий “отношение”, “соответствие”, “отображение”

2.4. Функции

2.4.1. Понятие функции

☼ Функцией (полной) называется отображение

f: X ®Y,

причём область определения данной функции совпадает с множеством X.

☼ Функции, не являющиеся отображениями, но являющиеся не всюду определёнными соответствиями, называются частичными.

Рассмотрим некоторые наиболее общие свойства функций, не касаясь свойств конкретных классов функций.

Из данного города в другой можно добраться по железной дороге, автобусом либо самолётом. Стоимость билета соответственно пусть будет 19, 5 и 90 руб.

Стоимость билета в этом примере может быть выражена через функцию от вида транспорта. Для этого следует рассмотреть два множества:

X={ж/д, авт., сам.};

Y={19, 5, 90}.

Функция

f: X ®Y,

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

f={(ж/д, 19), (авт., 5), (сам., 90)}.

Таким образом, символ f используется при определении функции в двух смыслах:

1) f является множеством, элементами которого являются пары (x, y), участвующие в соответствии;

2) f(x) является обозначением для , соответствующего данному .

Существуют 3 способа задания функции: табличный, аналитический

и графический.

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

Формальное определение функции записывается в виде:

С понятием функции связано ещё одно понятие, называемое

сужением функции.

☼ Пусть f: X ®Y – произвольная функция и – произвольное множество. Сужением функции f на множество A называется функция fA, содержащая все те и только те пары ,

в которых , а значит, . Следовательно,

По указанному принципу построены таблицы логарифмов,

тригонометрических функций и некоторых других.

2.4.2. Инъективная, сюръективная и биективная функции

Пусть имеет место функция f: X ® Y.

☼. Функция называется инъективной, если

Þ .

☼ Функция называется сюръективной, если

, где y=f(x).

☼ Функция f называется биективной (взаимнооднозначной), если она одновременно является инъективной и сюръективной.

X Y X Y X Y

x₁

x₂

a) б) в)

Функции:

a) инъективная, но не сюръективная;

б) сюръективная, но не инъективная;

в) биективная.

2.4.3. Обратная функция

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

☼ Функцией, обратной по отношению к функции

, называется функция

определяемая обратным отображением .

При аналитическом способе задания функции f принято аргумент и прямой, и обратной функции обозначать одной и той же буквой, например, x. Поэтому для нахождения обратной функции следует уравнение разрешить относительно x и затем x и y обменять

местами. При этом обратная функция запишется в виде

2.4.4. Понятие функционала

Важным для теории и практики является случай, когда множество X представляет собой множество функций, а множество Y – множество вещественных чисел. Этот случай приводит к понятию функционала.

Представим себе некоторую линию y=f(x), соединяющую точки A и B, по которой свободно скатывается шарик. Обозначим через t время, необходимое шарику для перемещения из т. A в т. B. Это время зависит от характера линии AB, т. е. от вида функции f(x).

f(x)

К понятию функционала

Обозначим далее через F(x) множество возможных траекторий движения шарика, а через T обозначим множество вещественных чисел t, определяющих время движения шарика. Тогда зависимость времени t движения шарика от вида функции f(x) может быть записана в виде бинарного отношения

где , причём ; .

Если же r – не только бинарное отношение, но и функция, то

будет функционалом, где r – функция от f(x); t – функционал.

2.5 Понятие оператора.

Оператором L называется отображение: , в котором множества х и у являются множествами функций с элементами x(t) и y(t), так что элементами множества L будут пары (x(t), y(t)). В этом случае говорят, что оператор L преобразует функцию x(t) в функцию y(t) = L[x(t)].

В задачах управления роль оператора часто выполняет сама управляемая система, преобразующая по некоторому закону L входной сигнал x(t) в выходной сигнал y(t), как это показано на рисунке.

Список используемой литературы

Судоплатов C. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 c.
Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2001. – 304 с.
Коршунов Ю.М. Математические основы кибернетики. Москва Энергоатомиздат, 1987 – 496 с.