Специальные бинарные отношения




1. Доказать, что если отношения r1 и r2 рефлексивны, то рефлексивны и отношения:

r1 È r2, r1 Ç r2, r1-1, r1 · r2.

2. Доказать, что если r1 и r2 иррефлексивны, то иррефлексивны и отношения

r1 È r2, r1 Ç r2, r1-1. Показать, что композиция r1 · r2 иррефлексивных отношений может не быть иррефлексивной.

3. Доказать, что если r1 и r2 симметричны, то симметричны и отношения

r1 È r2, r1 Ç r2, r1-1, r1 · r1-1.

4. Доказать, что композиция r1 · r2 симметричных отношений симметрична тогда и только тогда, когда r1 · r2 = r2 · r1.

5. Доказать, что

5.1. если отношения r1 и r2 антисимметричны, то антисимметричны также r1 Ç r2 и r1-1;

5.2. объединение r1 È r2 антисимметричных отношений антисимметрично тогда и только тогда, когда r1 Ç r2-1 Í iA.

6. Построить бинарное отношение

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

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

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

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

6.5. симметричное, транзитивное, не рефлексивное.

7. Доказать, что если r есть транзитивное и симметричное отношение на А

и dom r È rng r=А, то r есть эквивалентность на А.

8. Доказать, что любое отношение на А, симметричное и антисимметричное одновременно, является транзитивным.

9. Доказать, что отношение r на множестве А является одновременно

эквивалентностью и частичным порядком в том и только в том случае, когда r=iA.

10. Пусть rÍА2. Доказать, что r есть эквивалентность Û (r · r-1) È iA = r

ª r - эквивалентность Þ r-1 = r, r · r= r, iA Í r. Следовательно, (r · r-1) È iA Í r. Обратно,

r · r-1 симметрично для любого r. Поэтому r также симметрично и r · r= r · r-1 Í r. Следовательно, r симметрично, транзитивно и рефлексивно, т.е. r - эквивалентность. §

11. Доказать, что объединение r1 È r2 эквивалентностей r1 и r2 является эквивалентностью тогда и только тогда, когда r1 È r2 = r1 · r2.

ª Пусть r1 È r2 - эквивалентность. Тогда r1 · r2 Í(r1 È r2) ·(r1 È r2) Í r1 È r2, r1 È r2=

(r1 ·iA) È (iA · r2) Í r1 · r2. Обратно, пусть r1 È r2 = r1 · r2. Тогда r2 · r1= r2-1 · r1-1. Тогда

r2 · r1 = r2-1 · r1-1 = (r1 · r2)-1 = =(r1 È r2)-1= r1 È r2. (r1 Èr2) · (r1 È r2)=

(r1 · r1) È(r2 ·r1) È(r1 · r2) È (r2 · r2) Í r1 È r2, т.е. r1 Èr2 транзитивно. Симметричность и рефлексивность r1 È r2 очевидны. §

12. Доказать, что композиция двух эквивалентностей r1 · r2 является эквивалентностью тогда и только тогда, когда r1 · r2=r2 ·r1.

 

Мощность множества

1. Доказать, что равномощность множеств есть отношение эквивалентности.

ª Пусть отношение равномощности е задано на булеане конечного множества M. Множество X равномощно множеству Y (XеY) означает, что существует взаимно однозначное отображение f множества X на Y: f:X®Y. Согласно определению отношение эквивалентности рефлексивно, симметрично и транзитивно. Рефлексивность означает, что диагональ несущего множества целиком входит в отношение, т.е. idAÍ M, т.е. Действительно, существует взаимно однозначное отображение множества в себя, например, тождественное отображение, элементами которого являются элементы диагонали несущего множества и только они.

Симметричность означает, что Если X е Y, то существует взаимно однозначное отображение f:X®Y. В силу взаимной однозначности отображения f обратное отображение f—1:Y®X также является функциональным, следовательно, оно ставит каждому элементу y ÎY единственный элемент xÎX. Следовательно, Y е X.

Транзитивность означает, что композиция отношения равномощности с самим собой равна самому себе, т.е., XеY означает, что существует отображение f:X®Y такое, что то "X$!Y:f(X)=Y. Аналогично YеZ означает

"Y$!Z: f (Y)=Z. В силу взаимной однозначности отображения f каждому элементу X оно ставит в соответствие единственный элемент Y, а каждому элементу Y – единственный элемент Z. Пусть (X,Y) Îе·е. Тогда $z: X e Z и Z e Y. В силу рефлексивности отношения е, в множестве значений Z найдется значение Z=Y. Тогда (X,Y) Î e и (X,Y)Î e· e. Т.е. e · e Í e. Обратное включение доказывается аналогично, что и доказывает транзитивность отношения эквивалентности. Следовательно, равномощность множеств есть эквивалентность. Это отношение образует разбиение несущего множества М на классы эквивалентности, каждый из которых включает все равномощные подмножества множества М.¨

2. Доказать, что всякое подмножество конечного множества конечно.

3. Доказать, что объединение конечного числа конечных множеств конечно.

4. Доказать, что конечное множество не равномощно никакому своему истинному подмножеству.

5. Доказать, что множество целых чисел счетно.

Для доказательства достаточно найти способ взаимно однозначного сопоставления каждому целому числу единственного натурального числа.

6. Доказать, что мощность множества точек полуокружности равна мощности континуума.

7. Привести геометрическое построение, доказывающее равномощность множества точек двух концентрических окружностей.

8. Доказать, что множества точек внутри квадрата равномощно множеству точек его стороны.

Элементы комбинаторики

1. Определить максимальное число переборов при попытке взлома пароля, состоящего из 32 бит.

2. Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они не могли бить друг друга.

3. Сколькими способами можно указать на шахматной доске два квадрата: белый и черный?

4. Сколькими способами можно указать на шахматной доске два квадрата без ограничения цвета квадратов?

5. Сколькими способами можно выбрать три краски из имеющихся пяти?

6. Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях среди этих карт не окажется ни одного туза? В скольких случаях в числе этих десяти карт окажется:

· ровно один туз?

· Хотя бы один туз?

· Ровно два туза?

7. Сколькими способами можно расставить 12 белых и 12 черных шашек на черных полях шахматной доски?

Ответ: (

8. Найти число векторов , координаты которых удовлетворяют условиям:

8.1.

8.2.

8.3.

9. Каково число матриц из n строк и m столбцов с элементами из множества {0,1}?

10. Каково число матриц из n строк и m столбцов с элементами из множества {0,1}, у которых строки попарно различны?

11. Доказать следующие свойства биномиальных коэффициентов:

11.1.

11.2.

11.3.

12. Доказать, что возрастает по n при фиксированном k.

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

13.1. Сколько существует бинарных отношений между элементами множеств А и В?

13.2. сколько имеется функций из А в В?

13.3. Сколько имеется 1-1 функций из А в В?

13.4. Сколько существует взаимно однозначных отображений из А в В. При каких m и n существует такое отображение?



Поделиться:




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

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-26 Нарушение авторских прав и Нарушение персональных данных


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