3) Доказать или опровергнуть, что для множеств а,в,с, где причем справедливы высказывания:

Пр₂(А∩В) = Пр₂А Пр₂В

Теоретическая часть:

См. задание 1,2.

;

Операция проектирования справедлива для множеств, элементами которых являются кортежи одинаковой длины.

Операция проектирования множества, состоящего из кортежей - операция выделения первых, вторых и т. д. компонент кортежей и образование из них нового множества.

;

Проекция множеств:

A , (x,y)A ,Пр₁(A)=x, Пр₂(A)=y

Пр₁(AB)= Пр₁(A)  Пр₁(B)

Пр₂(AB)= Пр₂(A)  Пр₂(B)

Пр₁(A)= Пр₂(A)^-1

Пр₂(A)= Пр₁(A)^-1

Практическая часть:

а)

Докажем с помощью метода взаимного включения

Прямое включение доказано.

Обратное включение доказано.

Значит

б) Пр₂(А∩В) = Пр₂А Пр₂В

Докажем с помощью метода взаимного включения

Прямое включение доказано. Пр₂(А∩В) Пр₂А Пр₂В;

Обратное включение доказано. Пр₂А Пр₂В Пр₂(А∩В);

Пр₂(А∩В) = Пр₂А Пр₂В т. е. исходное равенство верно.

4) Доказать, что если А∩В=Ø → А∪В = А▲В.

Теоретическая часть:

См. задание 1,2.

Практическая часть:

А∩В=Ø → А∪В = А▲В

А∪В = А▲В ;А▲В = (А∪В) \ ( А∩В) => А∪В = (А∪В) \ ( А∩В), т.к А∩В=Ø то А∪В = (А∪В) \ Ø =>

=> А∪В= А∪В. Ч.т.д.

5) Построить отношения:

Построить отношение:

(1) Не рефлексивное, симметричное, транзитивное

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

Теоретическое введение:

Отношением  F на произвольном множестве Х называется пара множеств Х и F, где FХ*Х. Множество Х называется областью задания, F – график.

Используемые свойства отношений:

1. рефлексивность:

2. антирефлексивность:

3. не рефлексивность:

4. симметричность:

5. несимметричность:

6. нетранзитивность:

7. транзитивное: ;

Решение (1) Решение (2)

X1

X2

X1

X2

X3

X3

6) Доказать, что если отношения R₁ и R₂ рефлексивны, то рефлексивно отношение R₁\R_2.

Теоретическая часть:

См. задание 5.

Практическая часть:

Пусть R₁AA и

R₂BB

Т.к. R₁ и R₂ рефлексивны, то

aA aR1a, bB bR2b

A∪B=C

a,bC aR1a\ bR2b

пусть R₁\R₂=R a,bC aRa\ bRb

 сC сRс  R₁\R₂ –рефлексивно. Ч.т.д.

Рефлексивное отношение r1, aa aR1a:

Рефлексивное отношение R₂, bB bR₂b:

О тношение R₁\R₂, a, bC aRa & ⌐bRb

Из рисунка видно, что R₁\R₂ тоже рефлексивно.

7) Задать морфизмы между отношениями, являющиеся: гомоморфизмом, изоморфизмом;

Теоретическая часть:

Морфизм – перенесение свойств одного объекта на другой.

В дискретной математике под функцией подразумевается отображение некоторого множества на .

Функцией называется функциональное соответствие:

Область определения:

Область значений:

- тотальная, если:

- инъективная, если:

- всюду определенная, если:

- сюръективная, если:

- биективная, если она тотальная, инъективная, всюду определенная и сюръективная.

и - некоторые отношения, тогда:

;

;

Если , то данный морфизм – гомоморфизм между отношениями.

Если гомоморфизм – инъективен, то он – мономорфизм.

Если гомоморфизм – сюръективен, то он – эпиморфизм.

Если гомоморфизм – биективен, то он – изоморфизм.

Практическая часть:

Гомоморфизм:

Отношение φ = (X,F) Отношение ψ = (Y,G)

Изоморфизмом:

Отношение φ = (X,F) Отношение ψ = (Y,G)