Спирина, М.С. Дискретная математика

чисел (х; у; z), где элементами кортежа являются соответствую­ щие координаты точки. В программировании декартово произведение встречается в некоторых способах представления данных (массивы, одно-, двух-, трех- и многомерные таблицы и др.). Изоморфизм. Пусть дано множество М с введенной на нем функцией двух переменных / : М х М -» М. Такая функция на­ зывается бинарной операцией на М. Обозначим ее знаком Ф: def / ( * , , х2) = х, ® х2 g М. Аналогично пусть задано множество N со своей введенной бинарной операцией, которую обозначим ®. Множества (А/, Ф) и ( N, ®) называются изоморфными, если су­ ществует биекция s: М -» 7V, такая, что для любых элементов хь х2 6 М выполнено условие s(x, Ф х2) = s(X() ® s(x2). Обозначе­ ние: (М, Ф) - ( N ., ®>. В таком случае взаимно-однозначное соответ­ ствие s называется представлением множества М во множестве N. Пользуясь изоморфизмом, можно выявлять структуру одного мно­ жества (Л/) по структуре другого, с которым легче работать, ко­ торое уже было изучено. Например, рассмотрим множество целых степеней числа 3: М = (3*|£ e Z} с Е. Умножение (обычное в К, обозначим его х) двух элементов из М не выводит из М. Каждому элементу х е М поставим в соответствие log3х. Таким образом по­ строено взаимно-однозначное отображение / : х -> log3 х = log3 3* = = к е Z. Посмотрим, как меняется бинарная операция при дей­ ствии / : Vx1; х2 е М f ( x x х х 2) = / ( З*1х 3*!) = /(3* I+*J) = log33*l+*2= кх + + к2 = / (х , ) + f ( x 2), где + означает обычное сложение в Z. Очевидно, что множество (М , х) изоморфно множеству целых чисел Z с опера­ цией сложения: (Л/, х) - (Z, +). С (Z, +) работать удобнее, так как целые числа, например, занимают меньше места в ЭВМ. 1.6. Отношения. Бинарные отношения и их свойства — Почему ты не пьешь больше чаю? — спросил Заяц заботливо. — Что значит «больше»? — обиде­ лась Алиса. —Я вообще ничего тут не пила! — Тем более! — сказал Шляпа. — Выпить больше, чем ничего, — легко и просто. Вот если бы ты выпила мень­ ше, чем ничего, это был бы фокус! Л. Кэрролл Основные понятия. Соответствие между равными множествами А =В называется отношением на данном множестве (А). Отношения 38