О бинарных отношениях для математиков и информатиков

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

Каждое практическое задание курса предваряется лекцией (с использованием презентации) по теме занятия. Например, при изучении темы «Симметрия» перед выполнением практических заданий учащимся предлагается познакомиться с понятием «симметрия», «асимметрия», различными видами симметрии («осевая симметрия», «поворотная симметрия» и др.), применением симметрии в науке, технике, различных видах искусства и природе. После этого учащимся предлагается выполнить несколько практических упражнений по теме в программе Adobe Flash: построить различные симметричные объекты и их композиции, составить из данных объектов симметричное изображение. При выполнении данных заданий учащиеся могут использовать любые возможности программы (графические, анимационные, ActionScript). Получив симметричное изображение, можно подчеркнуть его красоту различными спецэффектами, предоставляемыми возможностями программы, преобразовать его в еще более интересную форму.

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

Примечания

1. Волошинов А. В. О союзе эстетики и математики в истории культуры // Обсерватория культуры. 2006. № 6. С. 100-109; Саранцев Г. И. Эстетическая мотивация в обучении математике. Саранск, 2003. 136 с; Черник О. В. Развитие эстетической воспитанности учащихся при обучении математике: дис. ... канд. пед. наук. Киров, 2003. 165 с.

2. Бабкин А. А. Изучение элементов фрактальной геометрии как средство интеграции знаний по математике и информатике в учебном процессе пед-колледжа: дис. ... канд. пед. наук. Вологда, 2007. 202 с.

УДК 51

Е. М. Вечтомов

О БИНАРНЫХ ОТНОШЕНИЯХ ДЛЯ МАТЕМАТИКОВ И ИНФОРМАТИКОВ

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

The paper considers the content and methods of teaching students of mathematical and natural science faculties about binary relations. There given some tasks and research problems.

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

Keywords: set, binary relation, map, equivalence relation, methods of studying.

Понятие бинарного отношения

Бинарные отношения занимают важное место в современной математике и ее приложениях [1]. Наряду с бинарными операциями они входят в структурно-понятийный фундамент математики. Выделяются различные свойства бинарных отношений, по которым их можно классифицировать. Особую роль играют такие виды бинарных отношений, как функции, эквивалентности, порядки. Поэтому изучение бинарных отношений в вузе вполне оправданно. Однако усвоение студентами темы «Бинарные отношения» вызывает большие трудности. Прежде всего, это связано с непониманием формального определения бинарного отношения, которое первоначально не возбуждает у них знакомых и адекватных ассоциаций. Следовательно, нужно грамотно выстроить методику их преподавания.

Естественнее начать с определения 1 и простых наглядных примеров.

Определение 1. Бинарным отношением (или соответствием) между множествами A и B (на паре множеств A, B) называется произвольная направленная связь (закон) р между отдельными элементами а е A и b е B. Если элементы а и b связаны р, то пишут арЬ и говорят также, что а и b находятся в отношении р. Фактически, бинарное отношение р на паре множеств A, B - это двуместный предикат P(x, y), в котором переменная x пробегает множество A, а y - множество B. При A = B отношение р называют бинарным отношением на множестве A.

Определение 2. Говоря формально, бинарным отношением между множествами A и B называет-

© Вечтомов Е. М., 2012

ся любое подмножество р прямого произведения А х В, то есть произвольное множество упорядоченных пар (а; Ь), а е А, Ь е В, рассматриваемое вместе с парой множеств А, В. При этом само множество пар {(а; Ь): а е А, Ь е В, а р Ь}называют бинарного отношения р. Замечание 1. Связь между содержательным (Б есть закон) и формальным (р с АхВ) определениями бинарного отношения задается отождествлением р/+А, {(а; Ь): арЬ}, В). Это типичный акт математической формализации. Он не совсем адекватен подлинному положению дел, поскольку разные (по существу) законы р и о могут давать одно и то же множество пар: р = о с А х В. Например, на множестве А = {2я: п е 14} обычные отношения # и «делит» формально совпадают. А. Робинсон вполне допускает такую ситуацию, но не отвергает и возможность теоретико-множественной точки зрения [2, с. 27, 41-42].

Бинарные отношения можно задавать описательно, формулами, графически. Бинарные отношения р между конечными множествами А и В зачастую удобно представлять таблицами и/или графами. В последнем случае множества А и В изображаются на диаграмме Эйлера - Венна, и при арЬ, где аеА и ЬеВ, из точки а в точку Ь проводится стрелка а^Ь.

Пусть, например, А = {1, 2, 3, 4, 5} и В есть множество всех ненулевых цифр. Зададим бинарное отношение р между множествами А и В условием: арЬ означает, что число а является делителем числа Ь. Это отношение можно представить таблицей или 0, 1 - матрицей размера 5х9.

Операции над бинарными отношениями

Пусть даны бинарные отношения р между множествами А, В и о между множествами В, С. Бинарное отношение р-1 между множествами В и А называется ой^йшкм* к отношению р, если У а е АУЬ е В(Ьр-1а ] арЬ). ^ожиози^игй отношений р и о называется бинарное отношение ро= о-р между множествами А и С, определяемое формулой

У а е АУс е С (а (ро)с ] >Ь е В(арЬ & Ьрс)) (на «языке стрелок» проводим стрелку а^с, если существуют стрелки а ^ Ь и Ь ^ с для некоторого элемента Ь е В).

Рассмотрим всевозможные бинарные отношения между множествами А и В, то есть всевозможные подмножества в АхВ. Они образуют бу-леан В (АхВ), на котором определены отношение включения с и операции объединения и, пересечения и дополнения '. Именно, для любых р, о е В(А х В) имеем:

р с о ] УаеАУЬеВ(арЬ ^ а^Ь), рио = {(а; Ь): арЬ V аоЬ}, рпо = {(а; Ь): арЬ & аоЬ}, р' = {(а; Ь) 0 Ах В: ]арЬ}.

Возьмем произвольное бинарное отношение р между множествами A и B. O^^acw&w ои/^гёг-«ия (domain) отношения р называется множество D(p) = (а е A: 3b е B арЬ),

а или о^/юзож

отношения D называется множество

Im р = р (A) = (b е В: За е A арЬ) = D(p').

Отношение р называется:

если D^) = A; (или адсшитеой из A в

B), если

Va е AVb^ b2 е В(арЬ1 & арЬ2 y = b2); когда

Va1, а2 е AVb е В(а1рЬ & а2рЬ y а1 = а2); когда Im р = В;

фу«к^ио«йё&«ьш, если оно всюду определено и однозначное;

если оно инъективно, сюръектив-но и функционально.

Всюду определенность бинарного отношения р между множества A и B графически означает, что из каждой точки множества A в В выходит хотя бы одна стрелка. Однозначность отношения р означает, что из каждой точки множества A выходит не более одной стрелки. Инъективность р иллюстрируется тем, что из разных точек множества A не могут выходить стрелки с общим «концом» в В, а сюръективность - тем, что, каждая точка множества В служит концом некоторой стрелки. Функциональность отношения р говорит о том, что из каждой точки множества A выходит ровно одна стрелка.

Атомарными (исходными) свойствами бинарных отношений, которыми они могут обладать, служат: всюду определенность, однозначность, инъ-ективность и сюръективность. Многие другие свойства бинарных отношений определяются в терминах этих четырех понятий. Всего имеется 24 = 16 комбинаций данных свойств; все они реализуются на конкретных примерах (моделях).

Отображения

Произвольное функциональное отношение р между множествами A и В называется из A в В, или A в В, в записи

р: A ^ В. Точнее говоря, отображение множества A во множество В - это упорядоченная тройка +A, f, В), где f: A ^ В - функциональный закон. Термины «отображение» и «функция» являются синонимами.

Функции (отображения) будем обозначать малыми латинскими буквами f, g, h (как это обычно делается).

Пусть f: A ^ В - некоторая функция. Поскольку для любого а е A существует единственный элемент b е В, для которого а/b, то его обозначают b = Да) = аf и называют о^^азож а при действии f. Для C с A через f(C) обозначают

множество образов всех элементов из подмножества C (при действии f). Если же C с B, то прообразом подмножества C (при действии f) называется множество f-1(C) = {aeA: af e C}; в частности, в случае C = {с} говорят просто о прообразе f-1(c) элемента с.

Предположим, что вместе с f заданы функции g: B ^ C и h: C ^ D. Композиция fg: A ^ C определяется правилом: a(fg) = (af)g для всех a e A. Композиция называется еще суперпозицией или последовательным выполнением (функций). Мы знак функции записали справа от аргумента, а не слева, как это обычно делается. Иногда вместо af или f(a) пишут af с показателем f. Легко видеть, что композиция функций есть функция, а операция композиции ассоциативна там, где определена (имеет смысл): для любого a e A

a((fg)h) = (a(fg))h) = ((af)g)h) = (af){gh) = a(f(gh)), т. е. (fg)h = f(gh) как функции A ^ D. Пусть f: A ^ B - отображение и C с A. Отображение f* C: C ^ B, совпадающее с f на C, называется огрaничением (сужением) f на C. Отображение f: A ^ B называется: инъекцией, если соответствующее бинарное отношение f инъективно, т. е. f(a1) * f(a2) при любых a1 * a2 из A;

сюръекцией (отображением на), если отношение f сюръективно;

биекцией (взaимно однозшчным соответствием), если отношение f биективно.

Для биекции f: A ^ B существует обрaтное отобрaжение (биекция) f-1: B ^ A, определяемое через обратное отношение:

œaeAœbeB(f1(b) = a « f(a) = b). Обозначим через 1A тождественное отобрa-жение A ^ A, для которого a1A = a для всех a e A. Ясно, что как бинарное отношение 1A есть отношение равенства на множестве A. Если f: A ^ B -биекция, то f-1 = 1A и f-1f = 1B (верно и обратное).

Замечание 2. Достаточно удобно изображать бинарные отношения между конечными множествами A и B «строчечно», в виде слов с пробелами в алфавите значков (букв), обозначающих элементы из A и B. В строчку выписывается ряд элементов из A и B с учетом пробелов. При этом только рядом стоящие слева направо буквы считаются находящимися в отношении р. Например, бинарное отношение {(a, c), (b, c)} между множествами A = {a, b} и B = {c, d} запишется как слово ac bc, задающее неинъективную и несюръективную функцию A ^ B. Мы видим, что в случае различных множеств A и B моделирующее слово является последовательностью двухбуквенных слов (первая буква из A, вторая из B), разделенных пробелами (порядок расположения двухбуквенных слов не имеет значения). Если же рассматривается бинарное отношение на множестве A, то в моделирующем данное отношение на A слове могут встре-

чаться слова без пробелов с тремя и более буквами. Так, десятисимвольное (с одним пробелом) слово aabba ccdd задает отношение квазипорядка на множестве A = {a, b, c, d}, не являющееся ни отношением эквивалентности (оно не симметрично), ни отношением порядка (и не антисимметрично).

О категории множеств

Пусть S - класс всех множеств. Для любых множеств A и B обозначим через M(A, B) множество всех отображений A ^ B. Для любых множеств A, B и C существует отображение M(A, B)xM(B, C) ^ M(A, C), сопоставляющее каждой упорядоченной паре (f, g) отображений f: A ^ B и g: B ^ C их композицию fg: A ^ C. При этом для любых трех отображений f: A ^ B, g: B ^ C и h: С ^ D справедлив закон ассоциативности композиции: (fg)h = f(gh). Для каждого множества A имеется тождественное отображение 1A: A ^ A, обладающее свойством «единицы»: 1Af = f и g1A = g при любых f: A ^ B и g: B ^ A (предполагается, что 1i = 0). Это позволяет сказать, что множества и отображения образуют категорию - категорию множеств Set.

Введем некоторые исходные понятия для категории Set. Множества называются объектами категории Set, а отображения множеств - морфизмами. Множество A называется начальным объектом (финальным объектом) категории Set, если для всякого множества B существует ровно одно отображение A ^ B (B ^ A). Легко видеть, что в категории Set единственным начальным объектом является пустое множество 0, а финальными объектами служат в точности одноэлементные множества. Отображение f: A ^ B называется: мономорфизмом, если для любых отображений g, h: С ^ A

gf = hf y g = h (можно сокращать на f справа); эпиморфизмом, если для любых отображений g, h: B ^ C

fg = fh y g = h (можно сокращать на f слева); биморфизмом, если f - мономорфизм и эпиморфизм;

изоморфизмом, если для некоторого отображения g: B ^ A

fg = 1a и gf = 1b; эндоморфизмом, если A = B;

автоморфизмом, если f - изоморфизм и эндоморфизм.

Замечание 3. Сформулированные понятия являются категорными, поскольку выражаются только на языке объектов, морфизмов и композиции морфизмов категории Set. Абстрактное понятие категории ввели американские математики С. Мак-лейн и С. Эйленберг в 1944 году. Теория категорий стала альтернативным теории множеств языком в математике. См. [3].

Приведем ряд утверждений о категорных свойствах отображений:

Утверждение 1. Дёя и/>оизйоё»«ого ошо^/>ажг-«ия /: А 6 В, А * 0, зкйийаё^«ш«м сл^ую^иг сйойсшйа:

1) Г - инъекция;

2) Г - мономорфизм;

3) су^сшйу^ш шакой жо/>физж к: В 6 А, ^шо А = 1а;

4) ¿ёя ёю^мх и: А 6 С и V: С 6 В иж^ж: гсёи / = и^, шо и - жо«ожо/>физж.

Доказательство проведем по циклу 1) — 3) — 4) — 2) -1).

1) У3). Если отображение f инъективно и а -фиксированный элемент из А, то отображение к: В 6 А зададим формулой

т=

х, если f(x)-b

[а, если Ъ е В \ Ьп/.

3) -4). Пусть выполнено условие 3) и f = для некоторых и: А 6 С и V: С 6 А. Рассмотрим произвольные морфизмы ¿: Б 6 А, для которых = ¿и. Тогда

g = = gfk = = ¿и^к = ¿/к = ¿1А = ¿.

4) — 2). Достаточно заметить, что / = /1В.

2) — 1). Предположим от противного, что мономорфизм / не является инъекцией. В А существуют такие элементы а1*а2, что /(а1) = /(а2). Возьмем любое непустое множество С и рассмотрим отображения g, ¿: С 6 А, для которых g(С) = {а1} и ¿(С) = {а2}. Тогда g * £, но gf = ¿/. Получили противоречие.

Следствие 1. £сёи fg - и«»^кция, шо f - и«»гк-ция.

Следствие 2. .Кожиозиция «^скоё^ких (ио^хо-¿я^их) и«»гкций и«»^кция.

Утверждение 2. Дёя и/>оизйоё»«ого ошо^/>ажг-«ия f: А 6 В зкйийаё^«ш«м сё^ую^и^ сйойсшйа:

1) Г - сюръекция;

2) Г - эпиморфизм;

3) су^сшйу^ш шакой жо/>физж к: В 6 А, ^шо

¥ = V

4) ¿ёя ёю^мх и: А 6 С и V: С 6 В ижгт: гсёи f = и^, шо V - эиижо/>физж.

Доказательство проведем по циклу 1) —3) —4) —2) —1).

1) ^3), Отношение равнообразности сюръ-екции / определяет разбиение {/-1(Ь): Ь е В} множества А, По аксиоме выбора возьмем в каждом классе /-1(Ь) по элементу Ь', Отображение к: В 6 А, к(Ь) = Ь' для всех Ь е В удовлетворяет равенству к/" = 1в,

3) ^4). Пусть выполнено условие 3) и f = для некоторых и: А ^ С и V: С ^ В. Рассмотрим такие морфизмы g, ¿: В ^ Б, Что г^ = Тогда

g =1^ = kfg = ки^ = = к^ =1в£=£.

Для доказательства импликации 4) ^2) заметим, что f = 1а/.

2) Предположим, что f не сюръекция. Тогда B\lm f ф i. Возьмем множество C, содержащее различные элементы c и d. Рассмотрим отображения g, h: B ^ C, совпадающие на Imf и такие, что g(B\lm f) = {c} и h(B\lm f) = {d}. Для них fg = fh, но g ф h. Значит, f не эпиморфизм. И теорема доказана.

Следствие 3. Если fg - сю/^гк^ия, wo g -сю/^гк^ия.

Следствие 4. .Кожиози^ия игсколйких (ио^хо-¿>я^их) сю/^гк^ий гсшй сю/^гк^ия.

Утверждение 3. Для произвольного отображения f: A ^ B равносильны следующие утверждения:

1) f - биекция;

2) f - биморфизм;

3) f - изоморфизм;

4) если f = uv, то u - мономорфизм, v - эпиморфизм.

В силу теорем 1 и 2 достаточно проверить, что равенства fg = 1A и hf = 1B влекут g = h для произвольных g, h: B ^ A. Если fg = 1A и hf = 1B, то g = l5g = (hf)g = h(fg) = blA = h.

Утверждение 4. Для любого жиожгсшйа A и любого иашу/алйиого ^исла и зк^и^алгишим условия:

2) <?яя каждого (¿Ья игкошо/ого) фииалйиого о^&гкша X су^гсшйугш /ойио и жо/физжой X ^ A;

3) о^гкш A ижггш /ойио ия эи^ожо/физжой;

4) о^гкш A ижггш /ойио и! айшожо/физжой.

Замечание 4. Понятия мономорфизма и эпиморфизма ¿>йойсшйгиим между собой, поскольку формулировка одного из них получается из формулировки другого перестановкой морфизмов в композиции и сменой направления соответствующих мор-физмов (стрелок). Двойственными являются понятия начального и финального объектов, а также свойства 3), 4) из теорем l и 2 соответственно. Если некоторое категорное утверждение является теоремой, то теоремой будет и двойственное ему утверждение. В этом заключается и/ии^ии ¿>йойс-шйгииосши в теории категорий. См. доказательства импликаций 3) y4) в утверждениях l и 2.

Бинарные отношения на множестве

Произвольное бинарное отношение р на непустом множестве A может обладать некоторыми из следующих пяти часто встречающихся свойств (Va, b, c е A):

1) рефлексивность: apa (т. е. lfp);

2) симметричность: apb y ¿pa (p-1cp);

3) транзитивность: apb&bpc y apc (ppcp);

4) антирефлексивность: ]apa (неверно, что apa);

5) антисимметричность: apb&bpa y a = b (pnp-

Теоретически возможны 25 = 32 комбинации этих свойств. Но 23 = 8 таких комбинаций содержат взаимно противоречивые свойства рефлексив-

ности и антирефлексивности. Поэтому реально остаются 32 - 8 = 24 комбинации. Если отношение р одновременно симметрично и антисимметрично, то оно не может связывать никакие два различных элемента, то есть является подмножеством (в качестве множества пар) отношения равенства 1А; такие отношения транзитивны. Поэтому не осуществимы «нетранзитивные» комбинации, содержащие свойства симметричности и антисимметричности, - новых подобных комбинаций три. Приходим к 21 возможной комбинации. Заметим, что на (непустых) множествах нет отношений, обладающих всеми пятью выделенными свойствами. Пустое отношение удовлетворяет четырем из указанных свойств - всем, кроме рефлексивности. (На пустом множестве имеется лишь пустое отношение, обладающее всеми пятью перечисленными свойствами.) Отношение равенства обладает всеми свойствами, кроме антирефлексивности. Если симметричное антисимметричное р рефлексивно (анти-рефлексивно), то р = 1А (р = 0). Далее, поскольку антирефлексивные транзитивные отношения антисимметричны, то нужно выбросить еще антирефлексивные транзитивные отношения, не являющиеся антисимметричными, - новых таких комбинаций две. В результате получаем 19 комбинаций, каждая из которых реализуема, то есть имеет модель.

Наиболее важными типами бинарных отношений являются следующие виды отношений. Бинарное отношение на множестве называется:

отношением эквивалентности (или эквивалентностью, одинаковостью), если оно рефлексивно, симметрично и транзитивно;

отношением порядка (порядком), если оно рефлексивно, транзитивно и антисимметрично;

отношением строгого порядка (строгим порядком), если оно антирефлексивно и транзитивно;

отношением квазипорядка (квазипорядком, предпорядком), если оно рефлексивно и транзи-тивно;

отношением сходства (сходством, толерантностью), если оно рефлексивно и симметрично;

турниром, если оно рефлексивно и антисимметрично.

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

Рассмотрим подробнее отношение эквивалентности. Заметим, что методика изучения другого важнейшего вида бинарных отношений - отношения порядка - изложена нами в статье [4].

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

Отношение эквивалентности математически выражает идею классификации того или иного множества вещей по определенному признаку. Отно-

шение «быть родственником» на любом непустом множестве людей является эквивалентностью, но отношение «быть близким родственником» на достаточно большом множестве людей есть сходство, не являющееся эквивалентностью. Отношением эквивалентности служит бинарное отношение совместной принадлежности растений или животных к одному виду (роду, семейству, типу). Математические примеры приведем чуть позднее. Поскольку понятие эквивалентности теснейшим образом связано с понятием разбиения множества, то определим последнее.

Разбиением множества А называется любое множество непустых попарно непересекающихся подмножеств множества А, объединение которого совпадает с А. Иными словами, разбиение данного множества А - это семейство множеств 5 = (А)., такое, что: 1) А. * 0 для всех /е I; 2) АрА. = 0

при любых / * ] из I; 3) А. = А. Множества А.

называются классами разбиения.

Возьмем произвольное непустое множество А и покажем, что между разбиениями множества А и эквивалентностями на А имеется взаимно однозначное соответствие. Пусть дано разбиение (АД.е/ множества А. Для произвольных элементов х, у е А положим:

х-у ] х и у лежат в одном классе разбиения (3. е I х, у е А).

Очевидно, что отношение - рефлексивно, симметрично и транзитивно, т. е. является эквивалентностью на множестве А.

Обратно, рассмотрим некоторое отношение эквивалентности р на множестве А. Построим разбиение ^ множества А, объявив его классами множества [а]р = {х е А: хра}, а е А. Докажем, что попарно различные классы [а] образуют разбиение

5 = А/р = {[а]р: /е А} с В(А) множества А. В силу рефлексивности отношения р имеем а е [а]р для всех а е А. Следовательно, выполняются условия 1) и 3), предъявляемые к разбиению. Для проверки условия 2) возьмем пересекающиеся классы [а]р и [Ь]р из 5 и покажем, что [а]р = Ир. Предположим, что с е [а]рп[Ь]р. Для любого х е [а]р имеем сра, срЬ и хра, откуда в силу симметричности (ар с) и транзитивности отношения р получаем последовательно хрс и хрЬ. Значит, [а]р с [Ь]р. Поэтому и [Ь]р с [а]р. Стало быть, [а]р = [Ь]р.

Теорема. Переходы (АДе/ ^ - и р ^ А/р осуществляют взаимно однозначное соответствие между множеством всех разбиений произвольного множества А и множеством всевозможных эк-вивалентностей на А.

Завершим доказательство теоремы. Для эквивалентности - на А и элемента а е А обозначим

а = [а]_. Тогда для любых а, Ь е А очевидно имеем

а = ь ] а - Ъ.

Поэтому отображения (АД.е/ ^ - и р ^ А/р обратим друг другу.

Для любого отношения эквивалентности р на множестве А разбиение А/р называется фак-шо/ж«ож^сшйож множества А по эквивалентности р. Приведем соответствующие примеры.

Примеры. 1. Отношение равенства = на любом непустом множестве А, при этом А/=/А.

2. Отношение сравнимости по модулю п, п е 14, на множестве Ъ всех целых чисел: а / b(mod п) означает, что а-Ь делится на п нацело. Фактормножество Ъ//п = Ъя = {о,!,...,«^} - это множество

классов вычетов по модулю п, соответствующих остаткам от деления на п.

3. Отношение параллельности на множестве всех прямых обычного пространства. Ему отвечает фактормножество всевозможных неориентированных направлений в пространстве.

4. Отношение подобия на множестве всех многогранников. Соответствующее фактормножество представляет собой множество «форм» многогранников.

5. Бинарное отношение равноудаленности от фиксированной точки О плоскости на множестве всех точек данной плоскости. Фактормножеством плоскости по отношению равноудаленности служит множество всех концентрических окружностей плоскости с центром в точке О, включая вырожденную окружность {О}. Это фактормножество можно мыслить так же, как множество неотрицательных действительных чисел (радиусов окружностей).

6. Отношение /ай«ожо^«осши - множеств из наименьшего универсального множества и. Фактормножество и/- есть множество достижимых мощностей (достижимых кардинальных чисел). Напомним, что два множества называются /ай«о-жо^«мжи, если между ними существует взаимно однозначное соответствие.

7. Отношение /ай«оо^/аз«осши на множестве А для любого отображения /: А ^ В: х-^у ] /(х) = /(у) для любых х, у е А. Фактормножество А/~ = (/-1(Ъ): Ъ е 1т /} можно отождествить с 1т /.

Упражнения

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

2. Докажите, что однозначность бинарного отношения р равносильна инъективности обратного отношения р-1.

3. Проверьте, что любое отображение / является композицией сюръекции g и инъекции Ь. Что при этом означает биективность /, инъективность g, а сюръективность Ь?

4. Докажите, что биективность бинарного отношения р на паре множеств А и В равносильна выполнению равенств рр-1 = 1А и р-1р = 1в.

5. А что означает выполнение каждого из равенств рр-1 = 1А и р-1р = 1в по отдельности?

6. Т^о/^жа о гожожо/физжах ¿ёя ж«ож^сшй: Для всякой сюръекции /: А ^ В существует единственная биекция g: А/-6 В, такая, что / = я^, где я: Аб А/— каноническое отображение множества А на свое фактормножество по отношению равнообразности: а-Ъ ] а/= Ъ/.

7. бифункциональные соответствия. Бинарное отношение р между множествами A и B называется дифункциональным, если для любых a, c e A, b, d e B из apb, apd, cpb следует cpd (равносильно, pp-1p с p). Опишите дифункциональные отношения между данными множествами (см. [5, с. 34]).

8. Пусть даны произвольные бинарные отношения р, о между множествами A и B и б, ( между множествами B и С. Докажите следующие соотношения:

р с о ] р-1 с о-1 ] о'с р'; 1Ар = р = р1в; (р-1)-1 = р; (рб)-1 = б"1р-1;

р с рр 1р, причем р = рр 1 ] р инъективно; (рио)б = биоб; (рпо)б с рбпоб; р (б и () = рбиру; р(бпу) с рбпру.

9. Какие еще связи имеют место для отношений р, о, б, ( из предыдущего упражнения?

10. Исследовать булеву алгебру B(A х A) бинарных отношений на непустом множестве A с дополнительными операциями композиции отношений и взятия обратного отношения. Такая алгебра называется реляционной алгеброй на A.

11. Пусть р - бинарное отношение между множествами X, Y и A, B с X. Докажите следующие соотношения:

а) р (AuB) = р (A) и р (B);

б) р (AnB) с р (A) п р (B);

в) (VC, D с X р (С п р) = р (C) п р (р)) ] р инъ-ективно.

12. Верны ли утверждения предыдущего упражнения для семейств подмножеств в X?

13. Докажите равенство f 1

( A.) = Q/ для любого отображения f: X^Y

и произвольного семейства (A).0I подмножеств множества Y.

14. Задача Рамсея. Докажите, что среди любых шести человек найдутся трое попарно знакомых или трое попарно незнакомых между собой людей.

15. Если на множестве A задано отношение порядка #, то бинарное отношение <, определяемое как пересечение отношений # и *, есть строгий порядок на множестве A. Обратно, если < - произвольный строгий порядок на множестве A, то бинарное отношение #, определяемое как объединение отношений < и =, является отношением порядка на множестве A. Тем самым между порядками и строгими порядками на любом множестве A устанавливается естественное взаимно однозначное соответствие. Докажите эти утверждения.

16. В терминах разбиений опишите все симметричные транзитивные отношения на произвольном множестве.

17. Пусть р - отношение квазипорядка на множестве A. Для произвольных элементов а, b е A положим а-b, если арЬ и Ьра. Покажите, что отношение - является эквивалентностью на A. На фактор-множестве A/- задается отношение порядка J по формуле

] арЬ для любых а, b е A.

Проверьте корректность этого утверждения.

18. Покажите, что отношение равночисленнос-ти (A-B ] | A| = \B \) на множестве всех конечных множеств универсального множества является эквивалентностью. Что представляет собой соответствующее фактор-множество?

19. На множестве р действительных чисел зададим бинарное отношение р формулой: арЬ означает, что а-b е Z (а, Ь е R). Докажите, что р есть эквивалентность на R. Дайте геометрическую интерпретацию фактор-множества R/р.

20. Рассмотрим множество S = B(X)\{i} всех непустых подмножеств непустого множества X. Для любых A, B е S положим: AрB ] AnB * 0. Покажите, что отношение является отношением сходства на S. Заметим, что любое отношение сходства определенным образом сводится к описанному сходству D [6].

21. Привести примеры бинарных отношений для всех 16 комбинаций следующих четырех свойств отношений: всюду определенность, однозначность, инъективность и сюръективность.

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

Замечание 5. Рекомендуется иллюстрировать все основные понятия и утверждения о бинарных отношениях рисунками, таблицами, диаграммами (как это сделано на рисунке в упражнении 6).

Порядок изучения бинарных отношений

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

2. Дается и обсуждается содержательное определение 1.

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

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

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

6. Рассмотрение операций над бинарными отношениями.

7. Приводится и комментируется формальное определение 2.

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

9. Для закрепления материала необходимо продумать и дать систему упражнений как на понимание вводимых понятий, так и на их применение. См. упражнения из книг [7].

10. Наконец, можно более углубленно изучать бинарные отношения на студенческих научных кружках и в рамках курсовых и дипломных работ. Для этого привлекаются учебно-исследовательские задачи (см. указанные выше упражнения 6, 7, 10, 14, 15, 17, 20-22).

Примечания

1. Мальцев А. И. Алгебраические системы. М.: Наука, 1970. 392 с.; Кук Д, Бейз Г. Компьютерная математика. М.: Наука, 1990. 384 с.

2. Робинсон А. Введение в теорию моделей и метаматематику алгебры. М.: Наука, 1967. 376 с.

3. Цаленко М. Ш., Шульгейфер Е. Г. Основы теории категорий. М.: Наука, 1974. 256 с.

4. Вечтомов Е. М. Изучение порядковой структуры // Вестник Вятского государственного гуманитарного университета. 2010. № 2(1). С. 111-120.

5. Мальцев А. И. Алгебраические системы. М.: Наука, 1970. 392 с.

6. Шрейдер Ю. А. Равенство. Сходство. Порядок. М.: Наука, 1971. 256 с.

7. Столл Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968. 232 с.; Вечтомов Е. М. Основные структуры классической математики. Киров: Изд-во ВятГГУ, 2007. 252 с.

УДК 371.311.1:519

Е. А. Вас^иииа ПРОБЛЕМНО-ДЕЯТЕЛЬНОСТНЫЙ ПОДХОД

И инДивидуализация как факторы реализации интеллектуально-ориентированного процесса обучения информатике

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

The intellectually-oriented process of teaching Computer science based on the ideas of individualization, activity theory and the attention to the mentality is discussed in the article.

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

Key words: the intellectually-oriented process of teaching Computer science, problem, activity theory, individualization.

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

© Васенина Е. А., 2012

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

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

Приоритеты в обучении определяются на этапе целеполагания, ибо аджу у^иш» и как это делать для учителя определено тем, за^ж это делается и какой ожидается /^зуё&шаш. Если для учителя самым важным является, к примеру, знание определения (пусть будет определение понятия «файл»), выраженное в способности ученика его безошибочно воспроизвести, или умение четко и быстро выполнить последовательность действий (пусть будет «Построение круговой диаграммы без легенды на отдельном листе» - задание взято из учебника [1]), он выберет для этого методику, которая непременно и с наименьшими затратами приведет к этому результату. Однако если, по меньшей мере, в равной степени (не говоря уже о приоритете) для него важно формирование у школьника разностороннего взгляда на изучаемый объект (в нашем примере - файл), способности к оценке и соотнесению разных подходов к его определению, а также способности к самостоятельному планированию деятельности и привычки нести ответственность за ее результаты, выбранная методика будет совершенно иной. В этом случае учитель уж точно не будет конкретизировать инструкцию до уровня названия кнопки, пункта меню или точной ссылки на диапазон, как это сделано в указанном источнике.

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

Рассмотрим следующий пример. Возьмем тему «Массивы» и определим следующие цели ее изучения:

1. Сформировать понятия массива, элемента массива и его номера (индекса).

2. Научить формировать массив и выводить его.

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

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

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