2. Примеры решения задач

Пример 1. Дано множество А={1,2,3,4,5}.

α={(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4),(5,5)}

Написать программу, доказывающую, что α-транзитивно.

{процедура ввода множества}

Procedure InputVariety(var A:variety_type);

Var i, temp:integer;

Begin

for i:=1 to n do

begin

writeln('Введите ', i, '-ый элемент массива');

readln(temp);

A[i]:=temp;

end;

End;

{процедура ввода отношения}

Procedure InputRelation(var Alfa:relation_type);

Var i, j, temp:integer;

Begin

for i:=1 to kol do

begin

writeln('Введите ', i, '-ую пару отношения');

readln(Alfa[i,1], Alfa[i,2]);

end;

End;

{процедура вывода множества}

Procedure OutputVariety(A:variety_type; n:integer);

Var i:integer;

Begin

for i:=1 to n do

write(A[i],' ');

writeln;

End;

{процедура вывода отношения}

Procedure OutputRelation(Alfa:relation_type; kol:integer);

Var i, j:integer;

Begin

for i:=1 to kol do

begin

for j:=1 to 2 do

write(Alfa[i, j], ' ');

writeln;

end;

End;

{функция проверки свойства рефлексивности}

Function ReflexCheck(Alfa:relation_type; A:variety_type):boolean;

Var i, j, k, Ref:integer;

Begin

Ref:=0;

for k:=1 to n do

for i:=1 to kol do

if (A[k]=Alfa[i,1]) AND (A[k]=Alfa[i,2]) then

begin

Inc(Ref);

break;

end;

if Ref = n then ReflexCheck := true

else ReflexCheck := false;

End;

3. Контрольные вопросы

1. Что такое n-арные отношения? Приведите примеры.

2. Основные свойства бинарных отношений и их характеристики.

3. Какому свойству соответствует матрица с главной диагональю, содержащей только единицы?

4. Какому свойству соответствует матрица с главной диагональю, содержащей только нули?

5. Основные виды отношений.

6. Свойства отношения эквивалентности.

7. Свойства отношения порядка.

8. Свойства отношения толерантности.

4. Задания для самостоятельного решения

Написать программы, выполняющие следующие задания и проверить вычислением вручную.

1. Найти все элементы бинарных отношений R, построить таблицы(матрицы) и графы этих отношений:

1. xRy,  x<y на множестве A={1;2;3;4};

2. xRy,  x|y на множестве A = {5;6;…15};

3. xRy,  y=x+1 на множестве A= {1;2;…;10}.

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

1) Отношения R заданы на множестве R:

1. xRy,  x2 = y2;

2. xRy,  x2 + y2 = 1;

3. xRy,  xy>1;

4. xRy,  y=|x|.

2) Отношения R заданы на множестве Z:

1. xRy,  x ≤ y + 1;

2. xRy,  x2 + y2 = 1;

3. xRy,  2x=3y.

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

1. отношение R задано на множестве N2+: (a,b) R (c,d)  a+b = = c+d, a, b, c, d N;

2. отношение R задано на множестве N2: (a,b) R (c,d)  ad=bc, a,b,c,d N;

3. отношение G задано на множестве R: aGb  a2=b2;

4. отношение G задано на множестве R: aGb  a-b Z.

4. Отношение R задано на множестве М={2,3,4,5,6,7,8,9,10}.Задайте отношение R списком, матрицей, графом, если R ={(a,b):a+3b делится на a}. Определите отношение, обратное к R и дополнение к R. Какими свойствами обладают данные отношения?

5. Отношение R задано на множестве М={2,3,4,5,6,7,8,9,10,12}.Задайте отношение R списком, матрицей, графом, если R ={(a,b) | a+b четное}. Определите отношение, обратное к R и дополнение к R. Какими свойствами обладают данные отношения?

6. Отношение R задано на множестве: М={2,3,4,5,6,7,8,9,10,12}.Задайте отношение R списком, матрицей, графом, если R означает - «быть делителем». Определите отношение, обратное к R и дополнение к R. Какими свойствами обладают данные отношения?

7. Отношение R задано на множестве: М={2,3,4,5,6,7,8,9,10,12}.Задайте отношение R списком, матрицей, графом, если R означает-«иметь один и тот же делитель, отличный от единицы».Определите отношение, обратное к R и дополнение к R. Какими свойствами обладают данные отношения?

8. Отношение R задано на множестве: М={2,3,4,5,6,7,8,9,10,12}.Задайте отношение R списком, матрицей, графом, если R ={(a,b):a+b делится на a}. Определите отношение, обратное к R и дополнение к R. Какими свойствами обладают данные отношения?

9. Отношение R задано на множестве М={3,4,5,6,7,8,9,10,11,12}. Задайте отношение R списком, матрицей, графом, если R ={(a,b):a+b делится на 5}. Определите отношение, обратное к R и дополнение к R.Какими свойствами обладают данные отношения?

10. Какими свойствами характеризуются следующие отношения на М={1,2,3,…,9}:

1. R₁={(a,b): (a-b) - четное};

2. R₂={(a,b): (a+b) - четное};

3. R₃={(a,b): (a+1) – делитель (a+b)};

4. R₃={(a,b): a – делитель (a+b), a≠1}.

11. Пусть М={1,3,5,7} и отношение R M×М. Задать списком отношение R, обратное отношение R^-1, дополнение ^, транзитивное R^o и рефлексивное R^* замыкания, если:

1. R={(a,b): a≤b};

2. R={(a,b): a+2=b};

3. R={(a,b): (a+b)/2 М};

4. R={(a,b): (a+b-1) М};

5. R={(a,b): a-1=b};

6. R={(a,b): 2a+b М}.

12. Пусть М={a,b,c} и β(M) – множество всех подмножеств множества М. Задать списком отношение R, заданное на β(М), а также обратное отношение R^-1, дополнение , транзитивное R^o и рефлексивное R^* замыкания, если:

1. R={(A,B):AB};

2. R={(A,B):AB};

3. R={(A,B):AB};

4. R={(A,B):A∩B≠Ø};

5. R={(A,B):A∩B=Ø};

6. R={(A,B):A∩B=Ø и AB=U}.