Задачи для самостоятельного решения. - рефлексивность: xRх - истинно;

Задачи и упражнения

Свойства отношений

- рефлексивность: xRх - истинно;

- антирефлексивность: xRх - ложно;

- симметричность: xRy®уRх;

- антисимметричность: xRy ÙуRх®х=у;

- несимметричность: xRy - истинно ® уRх - ложно;

- транзитивность: xRy Ù уR z ®хR z .

Отношением эквивалентности называют отношение, обладающие следующими свойствами:

· рефлексивности xRх;

· симметричности xRy®уRх;

· транзитивности xRy Ù уR z ®хR z .

Отношением нестрогого порядка называют отношение, обладающие следующими свойствами:

· рефлексивности х³х (х£х);

· антисимметричности х£у Ù у£х®x=у (х³у Ù у³х®x=у);

· транзитивности х³у Ù у³ z ®x³ z (х£у Ù у£ z ®x£ z ).

Отношением строгого порядка называют отношение, обладающие следующими свойствами:

· антирефлексивности (х< х - ложно );

· несимметричности (х< у и у< х - ложно );

· транзитивности (х< у Ùу< z ®x< z ).

1. Доказать или опровергнуть, что для любого бинарного соответствия φ и для любых множеств А и В справедливо равенство:

φ(АÇВ) = φ(А)Ç φ(В).

Решение

"уÎφ(АÇВ)®$хÎАÇВ/(х,у)Îφ®($хÎА/(х,у)Îφ) Ù ($хÎВ/(х,у)Îφ)®

®уÎφ(А) Ù уÎφ(В)® уÎ φ(А)Ç φ(В) ® φ(АÇВ) Í φ(А)Ç φ(В);

"уÎφ(А)Ç φ(В)® уÎφ(А) Ù уÎφ(В)® ($аÎА/(а,у)Îφ) Ù ($вÎВ/(в,у)Îφ).

На этом этапе решения может представиться два случая:

а) аÎАÇВ Ù вÎАÇВ;

в) аÏАÇВ Ù вÏАÇВ.

В случае “а” уÎφ(АÇВ)® φ(А)Ç φ(В)Í φ(АÇВ), т.е. равенство выполняется.

В случае “б” ничего нельзя сказать о том, является ли у элементом множества φ(АÇВ) или нет. Таким образом, для любого бинарного соответствия φ справедли-во утверждение: φ(АÇВ) = φ(А) Í φ(В).

2. Пусть дано отображение Q:Х®У,

Х={х ₁, х ₂, х ₃, х ₄, х ₅ }, У={у ₁, у ₂, у ₃, у ₄ };

Q={(х ₁, у ₂ ), (х ₂, у ₁ ), (х ₂, у ₃ ), (х ₃, у ₂ ), (х ₄, у ₁ ), (х ₅, у ₄ )}.

Найти Q(А), Q ^-1 (В), А={ х ₁, х ₂, х ₃ }, В={ у ₂, у ₃, у ₄ }.

3. Доказать или опровергнуть, что для любого бинарного соответствия φ и для любых множеств А и В справедливо:

а) φ(АÈВ) = φ(А)È φ(В);

б) φ(АÇВ) = φ(А)Ç φ(В);

в) φ(А\В) = φ(А)\φ(В);

г) φ ^-1 (АÈВ) = φ ^-1 (А)È φ ^-1 (В);

д) φ ^-1 (АÇВ) = φ ^-1 (А)Ç φ ^-1 (В);

е) φ ^-1 (А\В) = φ ^-1 (А)\ φ ^-1 (В);

ж) φ(А)= φ(А)Ç φ(АÈВ);

з) φ(ÈА _i )=È φ(A _i );

и) φ(ÇА _i )=Ç φ(A _i );

к) φ ^-1 (ÈА _i )=È φ ^-1 (А _i );

л) φ ^-1 (ÇА _i )=Ç φ ^-1 (А _i ).

4. Доказать, что для любой функции ƒ и для любых множеств А и В

ƒ(АÇВ) Í ƒ(А)Ç ƒ(В).

5. Доказать, что ƒ удовлетворяет условию ƒ(АÇВ)=ƒ(А)Ç ƒ(В) для любых множеств А и В тогда и только тогда, когда ƒ есть единичная функция.

6. Доказать, что ƒ(А)\ƒ(В)Í ƒ(А\В) для любой функции ƒ.

7. Доказать, что если в предыдущем примере ƒ есть единичная функция, то выполняется равенство.

8. Доказать, что если АÍВ, то ƒ(А)Í ƒ(В) для любой функции ƒ.

9. Доказать, что если АÍВ, то ƒ ^-1 (А)Í ƒ ^-1 (В) для любой функции ƒ.

10. Доказать, что если АÍd _¦ и ВÍr _¦, где d _¦ и r _¦ соответственно области определения и значения функции ƒ, то:

а) АÍ ƒ ^-1 (ƒ (А));

б) ƒ (ƒ ^-1 (В))=В;

в) ƒ (А)ÇВ= ƒ (АÇ ƒ ^-1 (В));

г) ƒ (А)Ç ƒ(В)=Æ «АÇ ƒ ^-1 (В)=О;

д) ƒ (А)ÍВ«АÍ ƒ ^-1 (В).

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

а) RÇR=R;

б) RÈR=R;

в) (R ^-1 ) ^-1 =R;

г) (R ₁ ÈR ₂ ) ^-1 = R ₁^-1 ÈR ₂^-1;

д) (R ₁ ÇR ₂ ) ^-1 = R ₁^-1 ÇR ₂^-1 ;

е) ù (R ₁^-1 )=(ùR) ^–1.

12. Для каких бинарных отношений R справедливо R ^-1 =R.

13. Пусть А и В- конечные множества, состоящие из m и n элементов соот-

ветственно. При каких m и n существует взаимно однозначное соответствие между А и В?

14. Составить алгоритм, выполняющий операцию пересечения двух множеств, заданных перечислением.

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

16. Составить алгоритм, выполняющий операцию разности двух множеств, за- данных перечислением.

Список литературы

1. Автоматы / Под. Ред. К.Э. Шеннона и Дж. Маккарти.─ М.: ИЛ, 1956

2. Адельсон-Вельский, Г.М., Диниц Е.А., Карзанов А.Б. Потоковые алгоритмы.─ М.: Наука, 1975.

3. Акимов О.Е. Дискретнаяматематика: логика, группы, графы. 2-е изд., дополн.─ М.: Лаборатория Базовых Знаний, 2001.─ 376 с.

4. Алфёрова З.В. Теория алгоритмов.─ М.: Статистика, 1973.

5. АхоФ., Ульман Дж. Теория статистичекого анализаи её приложения, перевода и компиляции. М.: Мир, т. 1б2, 1978

6. АхоФ., Хопкрофт Дж, Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

7. Бауер Ф.Л., Гооз Г. Информатика.- М.:Мир, 1990

8. Белов В.В., Воробъёв Е.М., Шаталов В.Е. Теория графов.- М.: Высш. Шк., 1976

9. Берж К. Теория графов и её применения. М.: Изд-во иностр. Лит., 1962

10. Виленкин Н.Я. Комбинаторика.─ М.: Наука, 1969

11. Гаврилов Г.П., Сапоженко А.А. Задачи и управжнения по дискретной математике: Учеб. пособие. ─ 3-е изд., перераб.─М.: ФИЗМАТЛИТ, 2006.─416 с.

12. Дискретная математика для программистов/ Ф.А. Новиков ─ СПб: Питер, 2000.─ 304 с.

13. Исследования по дискретной математике. М.: Наука, 1973

14. Клини С.К. Математическая логика.- М.: Мир, 1973

15. Клини С.К. Введение в математику.- М.: Изд.-во иностр. Лит., 1957

16. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. – М.: Наука, 1969

17. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.- М.: Физматлит, 2001

18. Мальцев А.И. Алгоритмы и рекурсивные функции.- М.: Наука, 1986

19. Мендельсон Э. Введение в математическую логику.- М.: Наука, 1984

20. Фрейденталь Ч. Язык логики.- М.: Наука, 1969

21. Яблонский С.В. Введение в дискретную математика.- М.: Высш. Шк., 2002

22. Яблонский С.В., Гаврилов В.П., Кудрявцев В.Б., Функции алгебры логики и классы Поста.- М.: Наука, 1966

[1] Более подробно понятие «отображение» будет раскрыто позже.

[2] Георг Кантор (1845-1918 гг.), немецкий математик, профессор университета в Галле. Свои работы по теории множеств опубликовал в журнале Mathematische Annalen

Дата добавления: 2014-01-05