close

Вход

Забыли?

вход по аккаунту

?

1633 drobotunb.n m ateriali opornih konspektov po integrirovannomu kursu mnojestva logika aksiomaticheskie teorii b.n. drobotun g. s. djarasova

код для вставкиСкачать
^ Ф
пт,тЩ
6
Вестник Л Г У № 4
2003 г.
Физико-математические науки
ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ
УДК 378.146:51
МАТЕРИАЛЫ ОПОРНЫХ КОНСПЕКТОВ ПО
ИНТЕГРИРОВАННОМ У КУРСУ «МНОЖ ЕСТВА,
ЛОГИКА, АКСИОМАТИЧЕСКИЕ ТЕОРИИ»
Б.Н. Дроботун, Г. С. Джарасова
Павлодарский государственный университет им. С.Торайгырова
Жумыста [1]-де келгтршен математ икалык; пэндер бойынша miре к конспектглершщ mypi мен мазмун ерекшетктер1 туралы нускруларды icice асырудыц нак/пы мысалы реттде «Жиын, логика жэне аксиоматикалыц теориялар» пэншщ « Эквивалентгтк
кртынас» тацырыбы бойынша mipeK конспекташщ материалдары усынылады.
В работе предлагается, в качестве конкретной реализации положений по
форме и содержанию опорных конспектов по математическим дисциплинам, выска­
занных авторами в [1], материалы опорного конспекта по теме «Отношение эквива­
лентности» интегрированной дисциплины «Множества, логика, аксиоматические
теории».
Materials o f supporting transcripts on topic «Equivalency relation» ofthe integrated
discipline «Regions, logic and axiomatic theories» as the concrete realization o f statements
concerningform and contents o f supporting transcripts on mathematical disciplines expressed
by authors in [I], are presented in the work.
§ 1. Данная работа является непосредственным продолжением работы [1]. Имея
определенный опыт разработки опорных конспектов по логико-алгебраическим
дисциплинам, авторы, не желая оставаться голословными, сочли нужным дать
практическую реализацию основных положений по форме и содержанию опорных
конспектов, высказанных в работе [1], в виде реального конспекта по конкретной
теме конкретной дисциплины. В качестве дисциплины был взят интегрированный
курс «Множества, логика, аксиоматические теории» учебная программа, структура
и содержание которого разработаны авторами и который на протяжении ряда лет
читался ими для студентов обучающихся по специальностям «Математика и
информатика» и «Информатика». Выбор обусловлен тем, что этот курс является
теоретическим и методологическим обеспечением как дисциплины «информатика»,
так и дисциплин, непосредственно с нею связанных, и служит пропедевтической
основой изучения последующего курса «Дискретная математика». В качестве темы
взята тема «Отношения эквивалентности». Выбор именно этой темы мотивирован
тем, что отношения эквивалентности являются наиболее распространенными в
7
Б.Н. Дроботун, Г. С. Джарасова
математике. Кроме того, отношение эквивалентности лежит в основе одного из
наиболее общих, характерных не только для математики, но и для всей науки в
целом - метода «определения через абстракцию».
§2. Изложение материала темы будет осуществляться в соответствии со
следующим планом: 1. Бинарные отношения и способы их задания. 2. Операции
над бинарными отношениями. 3. Свойства бинарных отношений. 4. Отношение
эквивалентности. 5. Разбиение множества. Фактор-множество. Теорема о
соответствии. 6. Теорема о представлении отображений.
1.
Двухместное отношение Р на множестве А ф 0 называется бинарным
отношением (т.е. Р q А 2 = А х А ). Бинарные отношения на конечном множестве
А = {ах;а2\...',от} удобно задавать а) таблицами; б) графиками; в) графами; г)
сечениями [2].
В случае а), элементы множества д 2 записываем в квадратную таблицу,
имеющую из л строк и п столбцов так, что элемент (я,; aJ) ставится на пересечение
i -ой строки и j -го столбца(/ = 1,2,...,и; j = 1,2,...,и ). В этой таблице отмечаем те
клетки, в которых расположены пары (а,;ау) е Р .
В случае б), на осях декартовой системы координат выбираем по п точек,
которые ставим в соответствие элементам множества А. Отмечаем те точки
декартовой плоскости, для которых (at; a j ) e P (а, А*,).
В случае в), на плоскости (в общем случае, произвольно) выбираем п точек и ставим
их в соответствие элементам множества А • Если (я, Paj) , то из точки, соответствующей
элементу а, проводим стрелку в точку, соответствующую элементу at .
В случае г), для каждого элемента а, € А выписываем подмножество
[a jp » yij/aj € A&.aiPaJ Подмножество [a,\P ^ A называется сечением
отношения Р по элементу а, .
Пример 1. П усть А - {а,;а2;а ,;а 4}. Тогда:
А2 ={<я,;а, >;<л,;а2 >;<в,;в3 >;<а,;а4 >;<о2;а, >;<а2;а2 >;<а2;А} >;<а2;а4 >;
< а 3;а, >;<а3;а2 >;<а3;а, >;<я3;а4 >;<а4;а, >;<а4;а2 >;<а4;в3 >;<а4;а4 >}
Если
/* = {<в,;а2 >;<о2;в, >;<а2;а4>;< д3;а, >;<а3;а2>;
< а 3;а3 >;<а4;а, >;<а4;а2 >;<в4;а4 >}
то представления а), б), в), г) будут иметь вид:
Вестник ПГУN°4 2QQ3 г.
„Ребропетля
Ребро
графа
графа
в)
Физико-математические науки
[ai]P={a2}
[ajp={ai; а4} ♦ [азщ{Щ а2; а3}
[a jp={ai; а2; а4}
Сечения
отношения
г)
Рис. 1
2. Пусть р и Q - бинарные отношения на множестве д ■
2.а. Композицией (произведением) отношений р и Q называется бинарное
отношение P ° Q , определенное на множестве j 2 по правилу:
р о Q = |<
>/< х;,у >е Л2 & (3z е Л)(< x \z >е Р& < z \y >е £?)}
2.6. Обратным к бинарному отношению р называется бинарное отношение
р~1, определенное на множестве А по правилу:
Р~х = {< х;у >/< х;у > е А 2&< у\ х >е р \
Образное представление об этих операциях дают диаграммы (фрагменты
графов):
2.6
Рис. 2
2.с. Так как отношения Р hQ - подмножества д 2, то над ними можно
производить и теоретико-множественные операции: n ;u;\.
9
Б.Н. Дроботун, Г. С. Джарасова
Упражнение 1. Г31 Доказать, что для любых бинарных отношений
P ;Q ;R определенных на множестве д выполняются тождества:
1) (PoQ)oR = Po(QoR)
5) (P nQ )-1 =sP_,n Q "!
2 ) { P o Q y l =Q-'op-'
6>( P v Q ) ° R = {PoR)v(QoR)
7) (P nQ ) o R Q ( P o R ) n ( Q o R )
4) (PvQ )"1«I*"1u Q -1
Указание. Для тождеств 1)-6) применить метод включений. Докажем, для
примера, тождество 5). Для этого нужно доказать два включения
a)
(PnQ)'1q P '1r\Q~* и б) Р'г v Q '1 q (P u Q )'1 . Докажем а). Пуст
< х;у >е (Р п ф 1=>< у;х >е Pr\Q =>< у;х >е Р& <у ;х >е Q =><х;у >е P~l& <х ;у >е Q'1
<х;у>еР'} uQ '1.
3.
Определение 2.Бинарное отношение р , заданное на множестве д
называется:
1) рефлексивным, если (V* е А)(хРх);
2) симметричным, если (Vx;_y € А)(хРу => уРх);
3) антисимметричным, если (Vx;,y е А)(хРу & .уРх => х = у ) ;
4) транзитивным, если (Vx;>>;z € Л)(хРу & yPz => x/*z);
5) связным, если (Vx;jy € Л)(хРу v .уРх).
Простейшим примером рефлексивного отношения на множестве д является
отношение dA = {< х ;х > /хе А], которое называется диагональю множества д .
(Почему?)
Упражнение 2. Пусть р - бинарное отношение на множестве А • Доказать,
что отношение р является:
1) рефлексивным O v dA С Р >
2) симметричным О р -1 * р ;
3) антисимметричным <=> Рс\Р~х c .d A\
4) транзитивным <=> Р °Р cl Р
Свойства бинарного отношения р легко проследить на представляющих
его таблице, графике, графе. Например, наличие ребра-петли у каждой вершины
графа говорить о рефлексивности отношения р , представленного этим графом;
симметрия графика относительно прямой у = х говорит о симметричности
отношения, представленного этим графиком.
Упражнение 3. Для каждого из способов задания а), б), в) бинарного
отношения указать характерный признак, отражающий любое из свойств 1) - 5)
определения 1.
4. Определение 2. Бинарное отношение р на множестве А называется
отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
10
Вестник ЛГУ М 4 2003 г.
Физико-математические науки
Примеры отношений эквивалентности:
а) Отношение «быть в одной группе» на множестве студентов университета;
б) отношение подобия на множестве всех треугольников плоскости;
в) отношение равновеликости на множестве всех плоских фигур;
г) отношение равносильности на множестве всех формул алгебры высказываний;
д) отношение параллельности на множестве всех прямых плоскости.
С каждым отображением <р: А -» А можно связать бинарное отношение <р*
на множестве д , определенное по правилу:
(\/a \b е А)(а<р*Ь о <р(а) = Ъ)
Отношение <р* называется графиком отображения <р.
Упражнение 4. Пусть / : А - > В . Доказать, что ( / о / -1)* - отношение
эквивалентности на д .
Указание. Показать, что (Va; b е A)(a(f ° f ‘') ’ b о f(a) = f(b))
Рис. 3
Отношение ( / о /" ')* называется отношением равнообразности (см. рис.З).
Упражнение 5. Пусть Рх и Р2 - отношения эквивалентности на множестве
А ■Доказать, что:
1) Рх(~^Рг - отношение эквивалентности;
2) Р, и Р2- отношение эквивалентности О
Рхи Р2 = Р1о Р2 ;
3) Р1оР2- отношение эквивалентности <=> Рхо Р2 = Р2 о рг
Указание. Использовать упражнение 1. Например, в 3) пусть Ру ° Р7 = Р2 ° Р}.
Тогда
о Р2)-1 = р~хо р~] = р2 о /> = Рхо Р2 , т.е. отношение Р{°Р2 симметрично.
5. Определение 3 . Система непустых подмножеств £ множества м
называется разбиением этого множества, если:
О й * - * .
2) (УХ-,У € М ) ( Х п У * 0 = > Х = У ) .
Пример 2. Пусть М = {а1;а2;а3;а4;а5;а6} . Тогда система подмножеств
Е = {{а,;а3};{а2;а4;а6};{а 5}} есть разбиение множества \ f .
Пусть £ - разбиение множества д . Определим по разбиению 2 бинарное
отношение Рг на множестве д по правилу:
фа\Ъ € А)(аРгЬ <=>(ЗХе S)(a е Х & Ь е Х ))
По разбиению £ примера 2 найдем отношение Ръ и построим граф этого
отношения.
11
Б.Н. Дроботун, Г. С. Джарасова
Pi
®j»®i >,<а3,а3
а2,а2
< а 2;а6 >\<аь\а2 > ;< а 4;д4 > ;< а 4;а 6 > ;< д 6;а4 >;<а6;а6 >;<а5;а5 >}
-О}
о
Рве. 4
Характер расположения стрелок (ребер) графа говорит о том, что граф,
изображенный на рис. 4., является графом отношения эквивалентности.
Аналогичный результат имеет место в общем случае.
Предложение 1. Если £ - разбиение множества £ , то Рг - отношение
эквивалентности.
Предложение 2. Пусть р - отношение эквивалентности на множестве д и
а е Л • Положим [а], * {b/b е А & а Р Ь }. Тогда:
а) (\/а е А)(а е[а]Р)',
в) (Va; А € А)([а]р п [ft],
[а]р « [б]р);
б) (Va;fc е Л)(аР6 О [а], = ЭДр) ;
г ’)Л = аеЛ
и [4 > .
Предложение 2 показывает, что если р - отношение эквивалентности на
множестве д , то система подмножеств §а\р / а е А} является разбиением множества
А, при этом подмножество \а\р( а ^ А ) называется классом эквивалентности,
порожденным элементом а; множество {[а]/>/я £ Л} всех классов эквивалентности
называется фактор-множеством множества д по отношению р и обозначается
через А/ р.
аеЛ
Рис. 5
Пример 3. Пусть д - множество всех точек декартовой плоскости.
Определим бинарное отношение S на д по правилу: (V p,;p2 е A)(plSp2 о точки
р, и р 2 находятся на одном и том же расстоянии от начала координат) (см. рис.6.).
12
JflgpmwljrYW ЩЗь
Физико-математические науки
Пример 4. Пусть А - множество всех рабочих некоторого предприятия N.
Определим на А бинарное отношение р по правилу:
(Ух; у € А ) ( хРу о рабочие х и у имеют одну и т у ж е профессию).
Очевидно, что р - отношение эквивалентности. Если а е А , то [а\> множество рабочих имеющих одну и ту же профессию; А /р - множество всех тех
профессий, которые имеют рабочие предприятия N.
На этом прим ере н етрудно п рослед и ть вы полнение условий а)-г)
предложения 1.
Пусть 2 - совокупность всех разбиений множества а и Р - совокупность
всех отношений эквивалентности, определенных на множестве д .
Теорема 1 (о соответствии). Отображение <р: Е -» Р , определенное по
правилу: ( V I е 1 )( р (Е )= Рг ) является биективным отображением 2 на Р, при
этом А /р г = £ для любого S е S .
Таким образом, существует взаимно однозначное соответствие между
совокупностью всех разбиений множества А и совокупностью всех отношений
эквивалентности, определенных на этом множестве.
А
Рис. 7
Рис. 8
6. Пусть / : А - ¥ В отображение множества А в множество В • Согласно
упраж нения 4, бинарное отнош ение Р = ( / о / -1)’ является отношением
эквивалентности на множестве А • Согласно этого упражнения, аРЬ о /( д ) = /(/>)
для любых а,Ъ € А .
13
Б.Н. Дроботун, Г. С. Джарасова
Отображение е:А-> А/р определенное по правилу: (Va € А)(е(а) = [я],)
называется естественным отображением. Очевидно, что е - сюръекция (рис.7.).
Пусть B q A Отображение h: В -* А определенное по правилу
(Vb € B)(h(b) = Ь) называется вложением подмножества В в А - Очевидно, что
всякое вложение является инъекцией (рис.8.).
Теорема 2. (о представлении отображений). Пусть / : А -> В - произвольное
отображение множества д в множество в . Тогда для / существует представление
/ шв в /* оh в виде композиции трех отображений, где е - естественное отображение
(сюръекция д на А/р );/* - биективное отображение А/р на /m/и h - вложение Im/ъ В.
*
*
Т.е.
(*•/ °АХ*) = А(/ (*(*)))
для
любого
деЛ.э
где
*(#)**
/ (Мр )“ /(*); *(/(*))*/(*). (смрис.9.)
Таким образом, любое отображение представляется в виде 3-х отображений:
сюръекции, биекции и инъекции, т.е. теорема о представлении выявляет рэль этих
отображений, как базовых (атомных) в совокупности всех отображений.
Рис. 9
Пример 5. Пусть М ~ множество всех точек плоскости с веденной ш ней
декартовой системой координат ХОУ. Определим отображение
множества
М в множество R действительных чисел по правилу:
(VP е M)(f(P) = |о/*|)
(т.е. /(Р)-расстояние точки р от начала координат).
Тогда Imf = R+- множество неотрицательных действительных чисел;
рхРр2 <г>\Орх\ = \Ор2\ для любых точек р };р2 е М ; М/р - множество
концентрических окружностей с общим центром в начале координат, то s (р) окружность с центром в начале координат радиуса |Ор | (символически °\ор\;
/ (% ) *М ;
= М )• (см. пример 3.)
14
Ц ст никП ГУШ
2M U
Физико-математические науки
Пример 6. Пусть R - множество действительных чисел (множество точек
координатной прямой). Определим отображение <p.R-*R по правилу
(V* с ях?К*) = *-!*], где [х] - целая часть числа х.
Тогда Imp = [0;l)
-
множество
точек
полуинтервала
£0; 1);
х1Рх2 о ( х , -[* ,] = х2 -[х 2]) для любых х,;х2 e R , т.е. числа хх и х2 имеют
одинаковые
дробные
части;
R /p = {{n + a / n e Z } / a e [ 0;1)}
(класс
эквивалентности[х]р = {и + а / а = х -[х ],я е Z } для некоторого а € [0;1) наглядно
можно представить так:
а
а
а
а
а
а
rS rS rS rS rS rS
--------- •
и --- M --- M —
- - 5 - 4
-3
-2
x
♦ «— M ------------►
-1
0
1
2
3
4
5 ...
x
Рисунок 10
ромбиками отмечены числа класса [х]р); £(х) = {л + (х - [x])/w е Z}, т.е. а = х - [*];
/ ' ({w+ (х - [х]>/n е Z})=х - [х]; й(х - [х]) = х - [х].
Заметим, что совокупность представителей всех классов эквивалентности это полуинтервал [0;1). Окружность, полученная из этого полуинтервала дает
образное представление о фактор-множестве Mf р.
о
(а)
: -
(б)
Рис. 11
Упражнение 6. Рассмотреть двумерный случай примера 6. (см. [4]).
Указание. См. рис. 12; рис. 13 (а, б, в). Отметим также, что рисунок 12
двумерный аналог рис. 10, а рисунок 13 - рис. 11 (а, б).
15
Б.Н. Дроботун, В.Г. Кадькалов
ЛИТЕРАТУРА
1. Дроботун Б.Н., Джарасова Г.С. Роль и место опорных конспектов в системе
составляющих методического обеспечения учебного процесса./УВестник ПГУ.№3.-2002.
2. Фор К., Кофман А., Дени-Папен М. Современная математика, М.: Мир,
1966.
3. Лавров И.А., Максимова JI.J1. Задачи по теории множеств, математической
логике и теории алгоритмов, М.: Наука, 1975.
4. Кострикин А.И. Введение в алгебру, М.: Наука, 1977.
Документ
Категория
Без категории
Просмотров
1
Размер файла
430 Кб
Теги
mnojestva, kurs, aksiomaticheskie, djarasova, konspekt, aterial, opornih, drobotunb, drobotun, teoria, integrirovanny, logika, 1633
1/--страниц
Пожаловаться на содержимое документа