Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Проверка типов отношений. Решение задач



Для строгого доказательства принадлежности введенного на некотором множестве Х бинарного отношения rтому или иномутипу необходимо проверить справедливость выполнения всех аксиом данного типа для всех возможных упорядоченных пар (х, у Х2.

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

Пример 1. Рассмотрим множество всех треугольников {Т}, заданных длинами их сторон(a, b, c)(a, b, c —вещественные числа). Проверить, будет ли устанавливать нестрогий порядок на {Т} отношение Ti r Tj = «периметр Тi не меньше периметра Тj».

Решение. Обозначим периметр треугольника Тi через Р(Тi). Для отношения нестрогого порядка должны выполняться аксиомы рефлексивности, антисимметричности, транзитивности.

1. Рефлексивность." ТiÎ{Т} (Р(Тi)r Р(Тi))означает: «периметр Р(Тi) каждого треугольника Тi не меньше Р(Тi)». Данное условие выполняется для всех элементов {Т}, поскольку для каждого Р(Тi)как для вещественного числасправедливо равенство Р(Тi)= Р(Тi).

2. Антисимметричность. Выполнение аксиомы у заданного отношения для любых треугольников Ti и Tj сводится к выполнению условия «если Р(Тi)≤ Р(ТjР(Тj)≤ Р(Тi), то Ti = Tj », т.е. Ti и Tj — один и тот же элемент. Очевидно, оно нарушается, поскольку можно привести пример двух треугольников с одинаковыми периметрами, у которых не совпадают длины сторон.

Ответ: предложенное отношение не является отношением нестрогого порядка на множестве {Т}, поскольку у него не выполняется аксиома антисимметричности.

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

Пример 2. Выяснить, какой тип отношений вводит на множестве всех множеств U предикат Р(Х, Y)= «мощность множества Х равна мощности множества Y Х½=½Y½)» ?

Решение.

1.Отношение является рефлексивным, поскольку мощность любого множества равна самой себе:"XÎU(X r X).

2. Аксиома симметричности также выполняется, поскольку равенство мощностей множеств не зависит от порядка их упоминания — для "X,YÎU из равенства ½Х½=½Y½следует ½Y½=½Х½.

3. Транзитивность. Допустим, для некоторых множеств Х, Y, Z справедливо:½Х½=½Y½,½Y½=½Z½. Для доказательства транзитивности необходимо сначала доказать, что½Х½=½Z½. По определению эквивалентных множеств из ½Х½=½Y½,½Y½= ½Z½следует, что существуют взаимно однозначные отображения f : Х®Y и g:Y®Z. Композиция h = g f, переводящая Х в Z, по свойству взаимно однозначных отображений также будет взаимно однозначна. Отсюда получим, что ½Х½=½Z½, что и требовалось доказать.

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

Ответ: заданный предикат вводит на множестве всех множеств U отношение эквивалентности.

ЗАДАЧИ

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

а) б)

x\y a b C
a
b
c

 

x\y a b c
a
b
c

б)

 

 

2. На множестве нечетных арабских цифр задать следующие бинарные отношения:

а) рефлексивное и не транзитивное;

б) антирефлексивное и симметричное;

в) задающее строгий порядок;

г) антирефлексивное и асимметричное,

д) антисимметричное и не транзитивное.

3. На множестве из трех элементов {a, b, c} задать при помощи списков или таблиц бинарные отношения следующего типа:

а) эквивалентности (отличное от поэлементного и фиктивного);

б) строгого порядка;

в) нестрогого порядка.

4. На множестве простых чисел в интервале [0; 10] построить примеры отношений:

а) антирефлексивного, симметричного и не транзитивного;

б) транзитивного, но не антисимметричного.

5. Проверить, будут ли разбивать на классы множество N:

а) подмножества N`0 , N`1 , ... , N`k -`1 , состоящие соответственно из чисел, имеющих остаток 0,1,...,k–1 при делении на заданное натуральное число k;

б) подмножества {1}, N2 , N3 , N4 , … , состоящие, соответственно, из числа 1 и чисел, делящихся без остатка на 2, 3, 4,...;

в) подмножества N(1), N(2) , N(3), ... , состоящие из чисел, которые можно представить в виде произведения, состоящего соответственно из одного, двух, трех и т.д. простых чисел, отличных от 1.

6. Будет ли задавать отношение эквивалентности на множестве рациональных чисел в интервале [0, 1]:

а) объединение рациональных чисел в классы, если их можно представить дробью с одинаковым знаменателем;

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

7. Ввести отношения эквивалентности, строгого и нестрогого порядка на множествах:

а) всех кругов на плоскости, заданных декартовыми координатами центра и радиусом,

б) всех прямых на плоскости, заданных в декартовых координатах канонической формулой ax + by + c=0.

8. Дано множество V всех векторов двухмерного евклидового пространства Е2, в котором скалярное произведение векторов`v¢ = (a¢,b¢) и`v¢¢= (a¢¢,b¢¢) определено как (`v¢,`v¢¢)= (a¢× a¢¢ + b¢× b¢¢). Выяснить, будут ли задавать отношение эквивалентности на V следующие предикаты:

а) Р(`v¢,`v¢¢) = «(`v¢,`v¢¢) <0»;

б) Р(`v¢,`v¢¢) = «(`v¢,`v¢¢) ³ 0».

9. На булеане множества {a, b, g} ввести отношения:

а) эквивалентности (отличное от поэлементного и фиктивного);

б) строгого порядка.

10. На множестве целых чисел в интервале Х = [0; 10] построить примеры отношений строгого порядка, которые:

а) задают линейный порядок на Х,

б) не обеспечивают линейный порядок на Х .

11. На множестве F всех функций одной переменной, определенных на отрезке [a, b], отношение задано предикатом P(f1, f2)= «"xÎ[a, b](÷ f1(х)÷ ≤÷ f2(х)÷ )».

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


КОНТРОЛЬНЫЕ ЗАДАНИЯ ПО ТЕМЕ




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.