Сборник задач по дискретке

В M1 также можно выбрать некоторый элемент a2 M1 , причем a2 ¹ a1 . После удаления этого элемента из M1 получим непустое (см. 75)

множество M2 = M1 \ {a2 } = M0 \ {a1,a2 }.

Методом математической индукции можно показать, что для произ-

вольного n ³1 множество Mn = M0 \{a1 ,...,an }			(a1 M0 , …, an Mn−1 ) не-
пустое, а значит, существует элемент an+1 Mn			и an+1 Ï Mn+1 = Mn	\{an+1} .
Таким образом, все элементы an , nÎ¥, попарно различны				и множе-
ство {an		n Î¥} счетно.

78. Так как исходное множество счетно, то его элементы можно про- нумеровать. Тогда требуемое разбиение можно определить следующим образом:

Ai = {an n = km - i,mΥ}, i = 0,k -1,

где aj – элемент исходного множества с номером j .

79. Пусть B – бесконечное подмножество счетного множества A. Так как B A , то мощность B не превышает мощность A. Пусть C – счетное подмножество множества B (см. 77). Тогда мощность B не меньше мощности C . Следовательно, B – счетное множество.

80. 1) Счетность множества A \ B следует из задач 75 и 79.

Для доказательства счетности объединения положим

h k = ì bk , k £ m, ( ) íî f (k - m), k > m,

где A = f (¥), m – число элементов в множестве B . Тогда h отображает

¥ на A U B , а значит, A U B не более чем счетно (см. 73 и 79). Поскольку его подмножество A счетно, оно и не менее чем счетно.

2) Пусть A = f (¥), B = g (¥), для инъекций f : ¥ → A и g : ¥ → B .

Положим

h(2k ) = f (k ), h(2k -1) = g (k ), k ¥.

Тогда h отображает ¥ на A U B , а значит, A U B не более чем счетно (см. 73 и 79). Так как A U B бесконечно, то A U B счетно.

71

3)	Пусть Ai = {a1i , a2i , a3i , ..., ani		}, ni ¥. Полагаем
		i
	f (aij ) = n1 + ... + ni 1 + j −1, i ¥, j ≤ ni .
			−
Тогда f есть инъекция из UAi на ¥.
		i ¥
4)	Пусть Ai = {a1i , a2i	, a3i , ...} , i ¥. Положим		1, ..., a1n } .
	B1 = {a11}	, B2 = {a21 , a12}, …, Bn = {a1n , an2
			−

Тогда UAi = UBi		– не более чем счетно (см. 80.3). Но UAi не может
i ¥	i ¥	i ¥
быть конечным, так как оно содержит счетное множество A1 .
82. 1)	Пусть	A1 – счетное подмножество A (см. 77.1). Тогда

A1 U B : A1 (см. 80.1). Следовательно,

A U B = ( A \ A1 ) U( A1 U B) : ( A \ A1 ) U A1 = A.

2) Следует из пункта 1, так как A = ( A \ B) U B и A несчетно.

83. Докажем сначала, что прямое произведение двух счетных множеств счетно. Пусть A1 = {a1n n ¥}, A2 = {an2 n ¥}. Тогда

A1 × A2 = {(ai1,a2j ) i, j ¥}= U{(ai1,ak2 ) i ¥}: A1 .

k ¥

Поэтому A1 × A2 счетно (см. 80.4).

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

го выше и того, что A1 × A2 ×...× An−1 × An : (A1 × A2 ×...× An−1 )× An .

85. Следует из задач 80.4 и 83, так как множество всех конечных последовательностей есть объединение по n ¥ множеств последова- тельностей фиксированной длины n .

86. Следует из задачи 85.

87. Следует из задачи 85, так как многочлен a1xn1 + a2 xn2 + ... + ak xnk можно представить как конечную последовательность элементов счетно- го множества {x,+}U¥.

88. Следует из задачи 87, так как множество корней любого много- члена конечно.

72

89. Пусть A – множество всевозможных последовательностей нулей и единиц – является счетным множеством. Тогда существует некоторая биекция между A и ¥, т.е. каждой последовательности поставлено в соответствие некоторое натуральное число и наоборот. Упорядочим последовательности согласно этой биекции:

{a11,a21 ,...,ak1 ,...},

{a12 ,a22 ,...,ak2 ,...}, …,

{a1n ,a2n ,...,akn ,...},

…
Рассмотрим последовательность
	ì	k	= 0,
{b1,b2 ,...,bk ,...}, bk =	1,ak			k Υ.
	îí0,akk = 1,

Очевидно, что эта последовательность не совпадает с ранее зануме- рованными, что противоречит допущению, что любая последовательность имеет свой номер.

С другой стороны, рассматриваемое множество содержит подмноже- ство последовательностей, в каждой из которых только один член отли- чен от 0. Это подмножество, очевидно, счетно, а значит, A бесконечно.

Следовательно, множество A бесконечно и не является счетным.

90.	Пусть P(¥)	– булеан	множества	¥.	Тогда равномощность
заданных множеств доказывает биекция:					ì0, k Ï A,
	A « {x1, x2 ,..., xk ,...}:		AÎ P(¥) и xn =
					îí	1, k Î A, k Î¥.
91.	Докажем от	противного. Пусть		есть		некоторая биекция

f : ¥ ® [0,1] . Упорядочив точки сегмента согласно нумерации, введем обозначение:

f (n) = 0,a1na2n ...akn ..., aij Î{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, i Î¥, j Î¥.

Построив вещественное число b = 0,b1b2...bk ... следующим образом:

ì1, ak ¹1, bk = í0, akk =1,

î k

получим, что "n f (n) ¹ b .

73

Докажем, что множество точек отрезка [0,1] равномощно множеству

всевозможных последовательностей нулей и единиц, которое контину-

ально (см. 71, 90).

В двоичной записи каждая точка единичного отрезка [0,1] может быть записана в виде 0.h1h2h3..., где hi {0,1} для всех i ¥.

Такая запись единственна, за исключением чисел вида 2nk . Числам

такого вида соответствуют в точности две записи (у одной, начиная с неко- торого номера, все цифры равны 0, а у другой – все 1). Множество точек

вида 2nk счетно, следовательно, множество последовательностей, им соот-

ветствующих, также счетно; значит, эти множества эквивалентны и между ними существует взаимно однозначное соответствие.

Каждой точке x = (0.h1h2h3...) , за исключением точек вида 2nk , поста-

вим в соответствие последовательность h1,h2 ,h3 ,....

Таким образом, доказано, что между точками отрезка [0,1] и множе- ством последовательностей, составленных из 0 и 1, существует взаимно однозначное соответствие. Следовательно, множество точек отрезка [0,1] имеет мощность континуум.

94. Рассмотрим две окружности радиусами r и R , совместив их цен- тры в начале координат. Тогда точке (r cosϕ,rsinϕ) можно поставить

в соответствие точку (Rcosϕ, Rsinϕ).

95. Так как континуальное множество и произвольный отрезок – равномощные множества, то справедливость утверждения следует

из соотношений: [0,1] U[i,i +1] = ¡.

i ¥

96. Докажем сначала, что прямое произведение двух континуальных множеств континуально. Для этого достаточно доказать, что множество

всех упорядоченных пар двоичных последовательностей эквивалентно множеству всех таких последовательностей.

74

Паре последовательностей (a,b) , поставим в соответствие последо- вательность α0 ,β0 ,α1,β1,...,αn ,βn ,.... Это соответствие, очевидно, будет взаимно однозначным.

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

ного выше и того, что A1 ´ A2 ´...´ An−1 ´ An

: ( A1 ´ A2 ´...´ An−1 ) ´ An .

100. 1) да, да; 2) нет, нет; 3) да, да.

Свойство

101.

102.

104.

1

2

1

2

3

4

5

6

1

2

3

4

5

6

а

б

в

а

б

в

а

б

в

а

б

в

Идемпотентность

+

+

+

+

+

+

+

+

+

+

+

+

+

+

Коммутативность

+

+

+

+

+

+

+

+

+

+

+

+

+

Ассоциативность

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

é1 2 3ù

105. aob = ê

1

ú.

ë2

3û

106. aob og =

é1

2

3ù

é1

2

3ù

ê

1

ú , g ob oa =

ê

2

ú .

ë2

3û

ë3

1û

é1

2

3ù

é1

2

3ù

107. 1) a = ê

2

ú

2) b = ê

2

1

ú.

ë3

1û

ë

3û

é1 2 3ù

, aobog =

é1 2 3ù

,

é1 2 3ù

108. a = ê

ú

ê

ú

g oboa = ê

ú .

ë2 3 1û

ë1 2 3û

ë1 2 3û

110. Изоморфизмом A на B является:

1)любая биекция между множествами A и B ;

2)отображение Γ : x → ln x ;

3), 4)

отображение G : ¥ ® {0, 1, 2, 3}, где G(n) = n mod4 – остаток

от деления на 4.

111. Нет, так как

¹

U

(а также

¹

I

).

A U B

A I B

A

B

A

B

112. Да.

113. 1)

да;

2) нет;

3) да;

4) нет.

114. 1)

нет;

2) да;

3) да;

4) нет.

75

Булева алгебра

2. 1) нет; 2) нет; 3) да.

3. 1) z ; 2) существенных переменных нет, f = const0; 3) y ; 4) p.

6. 1. а) x, xy, yz , б) x, yz ; 2) а) xy, xyz, xz , б) xy, xz ; 3) а) xyp, xyz , б) xyp .

7 1)	x z x y z ; 2) y x z x z ; 3) z x y; 4) x y y z ;
5)	x y z y z p x z p или x y z y z p x y p ;
6)	x y z p ; 7) z p y z x z x y p ;
8)	x p y p x y z x yz y z p x y z ,
	x p y p x y z x y z x	y	z x z p,
	x p y p x y z x yz y z p x z p.
8. 1)	x z x y z ; 2) y x z x z ; 3) z x y; 4) x y y z ;
5)	x y z y z p x z p или x y z y z p x y p ; 6) x y z p ;
7)	z p x y z x y p ; 8) x y z p x z ;

9)x z p x y p x y p x z p ;

10)x p y p x y z x yz y z p x y z ,

x p y p x y z x y z x yz x z p, x p y p x y z x yz y z p x z p.

9. 1)	x z x y z ; 2) y x z x z ; 3) z x y; 4) x y y z ;
5)	x y z ; 6) x y y z x z или y z x z x y .
10. 1)		x y z y z p x z p или x y z y z p x y p ;
2)		x y z p ; 3) z p x y z x y p ; 4) x y z p x z ;
5)		y z p x z p x y ; 6) x z y z z p; 7) y p z y x p ;
8)		x z x p x y x y z ; 9) y p y z x z p;

10)z p y p x y z ; 11) y z x p y z x p;

12)x p y p x y z x yz y z p x y z , x p y p x y z x yz x yz x z p,

x p y p x y z x yz y z p x z p , x p z p x y z x y z x y z x y p , x p z p x y z x y z y z p x y p ,

x p z p x y z x y z y z p x y z ,

13)y p x z x y p y z p x yz x z p ;

14)x z y x z p x z p x y z .

76

11. 1) x y z, y z p, x z p, x y p;

2)x y, y z p, x z p, x z p, x y z, y z p ;

3)z p, y p, z y, x y p, x y z, x z p.

12. 1) y z y z x y , y z y z x z ;

2)x y y z x z , x y y z x z ,

y z y z x y x y , y z y z x z x z , x y x y x z x z ;

3)x y z y z p x z p , x y z y z p x y p ;

4) x y y z p x z p, x y x z p x y z x z p,

x y x z p x y z y z p , x y y z p x y z y z p ;

5)x z p x z p x y z z y p ,

x z p x z p x y z x z p x y p,

x z p x z p x y p x z p x z p x y p , x z p x z p x y p x z p x z p y z p .

13. 1) импликанты: g1, g3 , из них простые: g1;

2)импликанты: g1, g2 , g3 , g4 , из них простые: g1, g2 ;

3)импликанты: g1, g3 , g4 , g5 , из них простые: g5 ;

4)импликанты: g3 , g4 , g5 , g6 , из них простые: g3 .

18. 1)

f P0 ; 2)

f P1 ; 3) f P0 , f P1 , f M ;

4)

f P0 ;

5) не принадлежит всем классам;

6)

f P0 .

Базисы: { f1, f2 },

{ f5},

{ f2 , f4 },

{ f2 , f6 }.

19. 1)

Система не полная, так как

f1 P1

и

f2 P1 ;

2

}

{

2

}

{

2

}

Базисы:

2)

{

f

2

, f

3}

,

{

f

2

, f

4 }

;

3)

{

1

, f

2 }

,

{

f

3}

; 4)

{

1

, f

,

f

,

f

f

f

,0

,1 .

21. 1)

3)

	x		x	y
			2)
	z		z
		y	z	y
	x	p	4)
			x	z

yz

x

5)	y	z	6)	y	x	z
	y	z			x	z
	x

y z

77

		x	y			x	y	z
22. 1)					2)
							y	z
		y	x	z		x	z
	3)				4)
				x		x
							y
							x	z
	5)	z			6)
								y
							y
								z
23. Эквивалентны 3 и 4, а 1 и 2 – нет.
		x	y
24.		x	y
		x	y
		x	z
25.		y	z
					z
				y	p
					q
			x	z	p
					q
				p	q
26.	1)
				z	p
			y		q
				p	q
			z	p	q
					78

		y			x	y
	x	z				z
					x
		p	q		x	p	q
		z
					y	z
2)	y			или
		p
					y	p
	z	p			z	p
		y	z
			p
					q
	x
			z p	p
		z
		p	p	y	q
3)			z	y
		y	p
	z		p	x	q
		p
			x	y
				y	z
					p
			x
				z	p
			y	z	p
				y	z	p
	или		x	z	y	p
				p	y	z
							q
				z	x
			y			p
				p
					x	z
			z	p	x	y

79

Исчисление высказываний

1. Истинны высказывания: 2, 3, 4, 5, 7, 8, 10.

2. 1) любой день, кроме понедельника; 2) любой день; 3) понедельник.

4. 1) Если отрезки являются диагоналями квадрата, то отрезки взаим- но перпендикулярны.

2)Если число является суммой углов треугольника, то оно равно 180°.

3)Если он кентавр, то он имеет шесть ног.

5. Эквивалентны утверждения в парах 2), 3), 5).

6. 1), 6). 7. 2), 5). 8. Да.

9. Для того чтобы не выполнялось B , достаточно, чтобы не выполня- лось A.

10. 1) Да.

2)Нет. A и C являются следствиями B , никакая другая связь между A и C из условия задачи не вытекает.

3)Нет. B являются следствиями как A, так и C , никакая другая связь между A и C из условия задачи не вытекает.

4)Да.

11. «необходимо, но недостаточно» – 1, 4, 6, 7, 9, 12, 14; «достаточно, но не необходимо» – 2, 5, 8, 13, 15, 16; «необходимо и достаточно» – 3, 10, 11.

12. 1) Для того чтобы треугольник был прямоугольным, необходимо,

чтобы квадрат одной стороны треугольника был равен сумме квадратов двух других сторон.

2)Для того чтобы четырехугольник был прямоугольным, необходимо, чтобы диагонали четырехугольника были равны.

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

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

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

углов равнялась 180o .

3) Для того чтобы треугольник имел ось симметрии, достаточно, чтобы он был равнобедренным.

80