Докажите что формула задает бинарную операцию на множестве
Перейти к содержимому

Докажите что формула задает бинарную операцию на множестве

  • автор:

Бинарные отношения: примеры решений задач

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

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

Понравилось? Добавьте в закладки

Задачи с решениями о бинарных отношения онлайн

Задача 1. Определите свойства следующих отношений:
1. «прямая x пересекает прямую y» (на множестве прямых)
2. «число x больше числа y на 2» (на множестве натуральных чисел)
3. «число x делится на число y без остатка» (на множестве натуральных чисел)
4. «x — сестра y» (на множестве людей).

Задача 2. Проверить, является ли отношением эквивалентности на множестве всех прямых на плоскости отношение «непересекающихся прямых».

Задача 3. Найти область определения, область значений отношения Р. Является ли отношение Р рефлексивным, симметричным, антисимметричным, транзитивным.

Задача 4. Дано множество $А = \< \gt, \lt, \ge, \le\>$. Записать декартовое произведение $А \times А$. Задать 2 бинарных отношения $R_1$ и $R_2$, мощность которых равна 3 и 4 соответственно. Найдите соответствующие замыкания обоих отношений. Изобразите ориентированные графы и запишите матрицы для отношений $R_1$ и $R_2$ и соответствующих замыканий. Вычислите $R_1^$, $R_2^$, $R_2 \cdot R_1$. Изобразите соответствующие ориентированные графы и запишите соответствующие матрицы.

Задача 5. Отношение $R$ на множестве $Х =\$ задано матрицей.
Каковы свойства отношения $R$? Как выглядят матрицы отношений $R^$, $R \cdot R$?

Задача 6. Дано множество $A = \$ и бинарное отношение $R \subset A \times A$:
Проверить, является ли $R$ отношением эквивалентности. Добавить минимальное возможное число пар, чтобы $R$ стало отношением эквивалентности. Найти разбиение $P$.

Задача 7. Доказать, что для любых бинарных отношений

Задача 8. Доказать истинность следующего утверждения: если $Р$ и $S$ – антисимметричны, то $P \cap S$ – антисимметрично.

Задача 9. Для заданных на множестве $А=\$ бинарных отношений $\rho$ и $\tau$:
а) записать матрицы и построить графики;
б) найти композицию $\rho \circ \tau$;
в) исследовать свойства отношений $\rho$, $\tau$ и $\rho \circ \tau$ (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность).

Задача 10. На множестве вещественных чисел $R$ задано бинарное отношение $a \rho b$ $ \Leftrightarrow a^2 + a = b^2 + b$. Докажите, что $\rho$ – отношение эквивалентности. Сколько элементов в классе эквивалентности?

Задача 11. Для бинарного отношения $\rho$ между элементами множеств $A = \$, $B = \, \, \, \\>$, $a \rho X \Leftrightarrow a\notin X$ найдите область определения $D_\rho$ и область значений $R_\rho$?

Задача 12. Дано множество $X=\$ и отношение $R=\$. Показать, что отношение $R$ является отношением порядка. Построить диаграмму Хассе частично упорядоченного множества $(X, R)$. Существует ли в множестве $X$ наибольший и наименьший элементы? Существуют ли несравнимые элементы?

Решение задач об отношениях на заказ

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

Заказать решение задач по бинарным отношениям легко

Бинарные отношения: основные сведения

Бинарным отношением $R$ называется подмножество пар $(a,b)\in R$ декартова произведения $A\times B$, т. е. $R \subseteq A\times B$. При этом множество $A$ называют областью определения отношения $R$, множество $B$ – областью значений.

Записывается это так: $aRb$ (т. е. $a$ и $b$ находятся в отношении $R$, пара $(a,b)$ принадлежит отношению $R$).

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

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

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

Если для бинарного отношения выполняются свойства рефлексивности, симметричности и транзитивности, оно называется отношением эквивалентности. Оно разбивает все пары на классы эквивалентности.

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

Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства

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

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

Определение:Бинарная операцияна непустом множестве– это правило, которое ставит в соответствие любой упорядоченной пареединственный элемент.

Пример 1.1: Арифметическое сложение на множестве целых положительных чисел является бинарной операцией, а разность – не является, т.к. для любыхиразность – не всегда положительное число.

Для некоторых бинарных операций порядок следования операндов несущественен, для других – важен.

Пример 1.2: в произведении порядок элементов роли не играет т.к., а для частного – играет.

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

Замечание:Если прочесть определение повнимательнее, то можно увидеть, что бинарная операция вполне может рассматриваться как функция, которая задаёт элементдля каждой упорядоченной пары элементов.

Определение:Условиеявляется свойством замкнутости бинарной операции. Когда такое условие выполняется будем говорить, чтозамкнутоотносительно операции.

Пример 1.3:Операции сложения, умножения, вычитания являются бинарными операциями на множестве целых чисел. Деление не является бинарной операцией на, т.к. при делении одного целого числа на другое не всегда получается целое число. Т.е.– не является замкнутым множеством относительно операции деления.

Пример 1.4:Операции сложения, умножения, вычитания являются бинарными операциями на множестве рациональных чисел. Деление не является бинарной операцией на, т.кне определено для всех.

Пример 1.5:Если– множество всех подмножеств некоторого множества, то операции пересечения, объединения являются бинарными операциями.

Бинарная операция на конечном множестве может быть определена с помощью таблицы Кейли.

Пример 1.6:Еслито бинарную операциюможно определить следующим образом:

Таблица интерпретируется так:

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

Определение:Бинарная операция, заданная на непустом множественазываетсякоммутативной, если

Пример 1.7:Операции сложения, умножения на множестве рациональных чиселявляются коммутативными. Вычитание не является коммутативной операцией.

Пример 1.8:Операции конъюнкции, дизъюнкции на множестве высказываний являются коммутативным, Импликация не является коммутативной.

Определение:Операция, заданная на непустом множественазываетсяассоциативной, если.

Пример 1.9:Операции сложения, умножения на множестве рациональных чиселявляются ассоциативными.

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

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

Пример 1.10:Элементом идентичности для операции сложения на множестве рациональных чиселявляется элемент 0. Но при этом 0 не является элементом идентичности для операции вычитания, т.к– верно, но.

Определение:Пусть– бинарная операция, заданная на непустом множестве. И существует– элемент идентичности для операции. Элементназываетсяобратнымдляесли.

Обратный элемент обычно обозначают . При этом если– обратный элемент для, то– обратный элемент для.

Пример 1.11:Обратным элементом для операции сложения на множестве рациональных чиселдляявляется число.

Теорема: Пусть – бинарная операция, заданная на непустом множестве . Если элемент идентичности существует, то он единственный.

Доказательство:

Пусть ,– элементы идентичности на множестведля операции. Т.к.— элемент идентичности, то следовательно и для:

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

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

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

и – по определению обратного элемента.

Поэтому .

Следовательно, обратный элемент единственный.

Доказать, что * является бинарной операцией на множестве A и выяснить, какими свойствами она обладает

Author24 — интернет-сервис помощи студентам

Доказать, что * не является бинарной операцией на множестве A
Доброго времени суток. Совсем слаб в этой теме, а решить каким-то образом нужно) Заранее спасибо.

Какими свойствами обладает операция * на множестве М
Какими свойствами обладает операция * на множестве М, если a*b=�� ∩ �� и М –.

Какими свойствами обладает заданное отношение на множестве?
На множестве N*Nзадано отношение <x,y>R<u,v> \Leftrightarrow x+v=y+u. Какими свойствами обладает.

Эксперт по математике/физике

4891 / 3515 / 1137
Регистрация: 01.09.2014
Сообщений: 9,577

Devvvveloper, когда у вас нет домашнего компьютера, вы тоже долго программируете на листе бумаге, пытаясь силой мысли записать нули и единицы на жесткий диск компьютера на работе? Нет компьютера — набирать программу невозможно (хотя обдумывать ее, конечно, имеет смысл). Аналогично, если вы не знаете определений — вы хоть две недели думайте над задачей, все равно нисколько не продвинетесь.

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

Эксперт C

27699 / 17316 / 3811
Регистрация: 24.12.2010
Сообщений: 38,979

Является. Ибо каждой паре элементов множества ставится в соответвие элемент того же множества.
Свойства
— Коммутативна
— Ассоциативна.
— единицы (нейтрального) нет
— соответственно, об обратном речь идти не может.

Какие еще свойства рассматривали?

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Выяснить, какими свойствами обладает данное отношение
1. Выяснить, какими из свойств: рефлексивность, антирефлексивность, симметричность.

Выяснить, какими свойствами обладает данное отношение
1. Выяснить, какими из свойств: рефлексивность, антирефлексивность, симметричность.

Выяснить какими свойствами обладает заданное бинарное отношение
Выяснить какими свойствами (рефлексивность, симметричность, антисимметричность, транзитивность).

Выяснить, какими свойствами обладает заданное бинарное отношение
Выяснить, какими свойствами рефлексивность, симметричность, антисимметричность, транзитивность).

Или воспользуйтесь поиском по форуму:

Докажите что формула задает бинарную операцию на множестве

6. Универсальные алгебры с одной бинарной операцией

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

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

где М — множество, которое должно быть задано одним из возможных строгих способов, R и F — символы отношений и функций, используемых в данной системе. По сути этим способом можно только обозначить некоторую систему, да и то лишь в самом общем виде. Чтобы свойства отношений и функций были однозначно определены, нужно дополнительно указать перечень аксиом, отдельно по каждому отношению и по каждой функции.

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

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

Алгеброй называется система, использующая только функции, причем все функции должны задавать связь вида М n ® M . Не случайно изо всех соответствий именно функции выбраны для построения алгебр. Свойство однозначности образа необходимо для получения однозначных результатов в практических приложениях.

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

Кортеж ( F1, F2, . Fn ) называется сигнатурой алгебры (от signum — знак). Сами функции, образующие сигнатуру называются операциями, определенными в данной алгебре. В зависимости от числа мест различают унарные, бинарные и многоместные операции, а кортеж арностей алгебры называют её типом m . Например, используя обычное сложение и умножение на множестве действительных чисел можно получить алгебру

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

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

а М ; F(a) M.

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

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

Чтобы объяснить явление гомоморфизма, рассмотрим две алгебры:

A = М; F , и B = N; Ф .

Гомоморфизм из А в В существует, т.е. В гомоморфна алгебре А, если одновременно выполняются два условия:

существует отображение из M в N , т.е. каждому элементу из M однозначно соответствует некоторый элемент в N,

результат операции одинаков, независимо от того, выполнена ли она сперва в M с помощью операции F , с последующим отображением в N , или наоборот, сперва выполнено отображение в N с последующим выполнением операции Ф .

Гомоморфизм существует, например: из алгебры L; + (множество логарифмов по сложению) в алгебру (множество положительных и отрицательных чисел по умножению). Алгебра с умножением здесь может заменить алгебру со сложением, но не наоборот, т.к. отрицательные числа не имеют логарифмов. Здесь алгебра с умножением гомоморфна алгебре со сложением.

Другой пример гомоморфизма: из алгебры N; + в алгебру ; 10 . Здесь первая алгебра — множество натуральных чисел по сложению, а вторая — множество чисел от 0 до 9 со сложением по модулю 10. Получается так, что алгебра с конечным и при этом очень небольшим носителем гомоморфна алгебре с бесконечным носителем, но не наоборот.

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

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

Полугруппой называется алгебра с одной бинарной операцией

Здесь для операции * установлена только одна аксиома — аксиома ассоциативности А 1.

a*(b*c) = (a*b)*c.

Прикладной смысл операции * может быть различным. Самое простое её истолкование, это — конкатенация, т.е. приписывание букв или слов к уже имеющимся словам. В континуальной математике эта операция неизвестна, но она широко применяется в теории цифровых автоматов.

Абелевой полугруппой называется алгебра такого же вида, но уже с двумя аксиомами: А 1 (ассоциативности) и А 2 (коммутативности)

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

Моноидом или полугруппой с единицей, называется полугруппа, для которой наряду с аксиомой ассоциативности А 1 принята аксиома А3 о существовании нейтрального элемента е, такого, что е*а = а. Такой нейтральный элемент называется левой единицей. Можно эту аксиому выразить иначе, как А «3: а*е = а. Тогда нейтральный элемент должен называться правой единицей. Если же операция * коммутативна, т.е. кроме аксиом А 1 и А 3 принята аксиома А 2 , то нейтральный элемент будет называться просто единицей и е*а = а*е = а .

Называя нейтральный элемент единицей мы заметно сближаем полугрупповую операцию * с обычным умножением, ведь единица играет роль нейтрального элемента в обычном умножении. Если мы хотим свести полугрупповую операцию к сложению, то должны называть нейтральный элемент нулем, соответственно левым, правым или просто нулем: е+а = а+е = а. Сводя операцию * к умножению мы получаем мультипликативную полугруппу, а к сложению — аддитивную.

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

Алфавит чаще всего определяется как конечное множество, тогда как носитель бывает бесконечным.

Иногда семейство образующих состоит из одного единственного элемента, а все остальные элементы носителя М получаются многократным применением операции *. В этом случае полугруппа называется циклической, а её элементы называются степенями образующей а 0 . Примером циклической группы является множество натуральных чисел, определенное, как N; * , где образующая а 0 = 1, а операция * сведена к инкременту (прибавлению единиц).

Группой называется алгебра М ; * , у которой для операции * приняты аксиомы А 1, А3 или А «3 и дополнительно — аксиома А 4 о существовании обратного элемента а —1 , такого, что

а -1 * а = е; или А «4: a*a -1 = e.

Если считать группу мультипликативной, то нейтральный элемент е можно называть единицей, а если аддитивной, то нейтральный элемент будет называться нулем, а вместо обратного элемента а -1 принимается противоположный элемент —а .

Абелевой группой называется коммутативная группа, т.е. мультипликативная или аддитивная группа, у которой для операции * принята аксиома А 2 . Абелевыми группами являются: множество действительных чисел по сложению, множество рациональных чисел без нуля по умножению. Эти группы имеют бесконечные носители, так как иначе не обеспечивается замкнутость М относительно операции *.

В дискретной математике часто используются конечные группы. В качестве примера рассмотрим так называемую группу самосовмещений. Возьмем квадрат с вершинами A, B, C, D . Закрепим его в центре и будем вращать против часовой стрелки. При каждом повороте на 90 0 будет происходит замена одних букв другими, но всего возможны только четыре расположения, которые будут циклически повторяться. Обозначим поворот на 0 0 буквой а, на 90 0 — буквой b , на 180 0 — буквой с и на 270 0 — d.

Получим четыре унарные операции вращения, из которых составим носитель алгебры: М = a, b, c, d >. В качестве групповой операции примем композицию

Считая композицию вращений операцией ассоциативной и коммутативной, имея в виду наличие нейтрального элемента и противоположного элемента, можно показать, что полученная алгебра является абелевой группой. Но можно поступить иначе. Используя те свойства композиции вращений, которые кажутся очевидными, можно составить таблицу, содержащую все возможные здесь ситуации (табл. 6.1).

a b c d
a a b c d
b b c d a
c c d a b
d d a b c

Таблицы подобного вида были введены в 1854 г. специально для групп англичанином Кэли (A. Cayley), который считается изобретателем матричной алгебры. Таблица Кэли в неявном виде задает все аксиомы алгебры, для которой она построена. На коммутативность групповой операции указывает симметричность таблицы относительно главной диагонали, на существование обратного элемента указывает присутствие нейтрального элемента: а в каждой строке и каждом столбце таблицы.

Группа самосовмещений является циклической группой, так как все её элементы могут быть получены как степени b: a = b 4 , c = b 2 , d = b 3 .

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *