Материал: Zadanie_po_diskretnoy_matematike

Скачать файл

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Домашнее задание 1: Множества и операции над ними

1) Доказать, что :

à) A B A C B C;

á) A B A ∩ C B ∩ C; â) A B (A \ C) (B \ C); ã) A B (C \ B) (C \ A); ä) A B B A;

å) A B = A ∩ B A = B;

æ) A = B A ∩ B = è A B = U.

2) Показать, что мощность множества 2A всех подмножеств множества A ñ n элементами равна 2n:

|2A| = 2|A|

3)Существуют ли такие множества A, B è C, ÷òî A ∩B ≠ , A ∩ C = ,

(A ∩ B) \ C = .

4)Доказать следующèе тождества:

à) (A ∩ B) (A ∩ B) = (A B) ∩ (A B) = A; á) (A B) ∩ A = A ∩ B;

â) (A \ B) \ C = (A \ C) \ (B \ C); ã) A \ (B C) = (A \ B) \ C;

ä) A \ (B \ C) = (A \ B) (A ∩ C);

: : : :

å) A (B C) = (A B) C;

: :

æ) A ∩ (B C) = (A ∩ B) (A ∩ C).

5)Доказать, что 2A∩B = 2A ∩ 2B.

6)Решить систему уравнений

{

A ∩ X = B; A X = C;

ãäå A, B, C данные множества; B A C.

Домашнее задание 2: Бинарные отношения

1)Доказать, что для произвольных множеств A, B, C, D: à) (A × C) ∩ (B × D) = (A ∩ B) × (C ∩ D);

á) (A × C) (B × D) (A B) × (C D); При каких A, B, C è D

получается равенство?

â) (A B) × C = (A × C) (B × C);

ã) A × (B C) = (A × B) (A × C);

ä) (A B) × (C D) = (A × C) (B × C) (A × D) (B × D); å) (A \ B) × C = (A × C) \ (B × C);

æ) A × (B \ C) = (A × B) \ (A × C);

ç) A × B = (A × D) ∩ (C × B), ãäå A C è B D.

2)Найти D , R , −1, ◦ , ◦ −1, −1 ◦ для следующих отношений: а) = {(x; y) | x; y N; x делит y};

á) = {(x; y) | x; y N;

y делит x};

â) = {(x; y) | x; y R; x + y ≥ 0};

ã) =

{

(x; y)

x; y

; 2x

}

;

≥

ä) = {(x; y) | x; y

[−

2 ;

2 ]; y ≥ sin x}.

3)Доказать, что для любых бинарных отношений:

à) ( 1 2)−1 = −1 1 −2 1;

á) (

∩

)−1

= −1

∩

−1

;

)−1

;

â) −1 = (

ã) (

∩

i)−1 =

i I i−1;

i)−1

∩

ä) ( ii I

= i I i−1.

4)Доказать, что если 1 2, òî à) ◦ 1 ◦ 2;

á) 1 ◦ 2 ◦ ;

â) −1 1 −2 1.

Домашнее задание 3

1) Пусть для функции f определенной на множестве A

f(A) = {y | x A; (x; y) f}:

Доказать, что если A B, то справедливо f(A) f(B) для любой функции f.

2) Доказать, что для любой функции f:

à) f(A) = A ∩ Df = ; á) f−1(A) = A ∩ Rf = .

3) Доказать, что для любой функции f и произвольных множеств: а) f(A B) = f(A) f(B);

á) f ( i I Ai) =						i I f(Ai);
â)	f(	A	B	)	f A			f B	. В каком случае включение можно заменить
	f(			)	( )		∩	( )
		∩					∩

равенством?

ã) f ( i I Ai) i I f(Ai);

ä)	f(	A		f B		f A			B	.
	f(	∩)	\	( )	∩		(	\	)
			\					\

4) Доказать следующие утверждения для любой функции f:

à) f−1(A B) = f−1(A) f−1							(B);
−
á) f−1	( i I Ai) =			i I f−1(Ai);
â) f 1(A		∩	B) = f−1(A)		∩	f−1	(B);
−	∩			∩
		\			\
ã) f−1	(	i I Ai) =		i I f−1(Ai);

ä) f 1(A B) = f−1(A) f−1(B).

5)Доказать, что если A B, то справедливо f−1(A) f−1(B) для любой функции f.

6)Пусть f функция. Доказать, что если A Df è B Rf , òî:

à) A f−1(f(A)); á) f(f−1(B)) = B;

â) f(A) ∩ B = f(A ∩ f−1(B));

ã) f(A) ∩ B = A ∩ f−1(B) = ; ä) f(A) B A f−1(B).

Домашнее задание 4

1) Доказать, что:

а) если отношения 1 è 2 рефлексивны, то рефлексивны и отношения

1 2, 1 ∩ 2, −1 1, 1 ◦ 2;

б) если отношения 1 è 2 иррефлексивны, то иррефлексивны и отношения 1 2, 1 ∩ 2, −1 1;

в) если отношения 1 è 2 симметричны, то симметричны и отношения

1 2, 1 ∩ 2, −1 1.

2) На множестве N × N определим отношение :

(x; y) (u; v) x + v = y + u:

Доказать, что является отношением эквивалентности.

3)Привести пример линейного порядка на множестве N × N.

4)Доказать, что пересечение отношений эквивалентности на множестве X есть отношение эквивалентности на этом множестве.

5) Доказать, что объединение 1 2 двух отношений эквивалентности 1 è 2, заданных на множестве X, является отношением эквивалентности

тогда и только тогда, когда 1 2 = 1 ◦ 2.

6) Доказать, что если нестрогий порядок, то −1 также нестрогий порядок.

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

8)Пусть 1 è 2 линейные порядки на множестве A. При каких условиях

1 ◦ 2 будет линейным порядком? 9) Построить бинарное отношение:

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

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

Домашнее задание 5

1) Пусть n; m N. Доказать равенства:

à) (k) · (l ) = (l ) · (k − l); á) (2n ) =

(i ) ;

−

∑i

â) ïðè m ≤ n верно, что

(

)

( i )

· (i );

n + m

∑i

∑k

∑

ã)

k(k) = n2n−1;

ä)

k=2

k(k − 1)(k) = n(n − 1)2n−2;

∑k

∑

å)

(2k + 1)(k) = (n + 1)2n;

æ)

(k) =

(2n+1 − 1);

k=0

k + 1

n + 1

( 1)k 1 n

∑k

∑

ç)

(−1)k k + 1(k) = n + 1;

è)

− k − (k) = 1 + 2 + · · · + n;

k=1

ê)

( r )(k

r) =

(

);

ë)

(k!)2((n

k)!)2

= ( n ) ;

∑

−

n + m

∑k

−

(2n)!

r=0

(k)(

r )

−

(r)

r=0

−

(r)

k=0 r=0

ì)

n n−k

n n

− k

= 3n;

í)

( 1)k−r n = n−k

( 1)n−k−r n ;

∑ ∑

∑r

−

∑

1; m = n:

r=0

(k + r)( r ) (n k )

k=n

(n)(k ) {

î)

n−k

m = m + n ; ï)

( 1)k−n

k m =

0; m ̸= n;

∑

−

∑

2) Найти коэффициент при tk в разложении:

à) (1 + 2t − 3t2)8;

k = 9;

á) (1 − t + 2t2)10;

k = 7;

â) (2 + t − 2t3)10;

k = 5;

ã) (2 + t4 + t7)15;

k = 17:

Источник: https://studfile.net/preview/16578093/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)