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

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

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

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

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

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

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

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

Замечание. В рассмотренном примере 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. Проверить справедливость всех рассмотренных аксиом для отношений, заданных следующими матрицами:

а) б)

б)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8. Дано множество V всех векторов двухмерного евклидового пространства Е², в котором скалярное произведение векторов`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(f₁, f₂)= «"xÎ[a, b](÷ f₁(х)÷ ≤÷ f₂(х)÷ )».

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

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