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

f(x) = x3 + 3x2 - 9x - 27 .

61.Найти прообраз множества (0;+¥) относительно функции

f(x) = x3 + x2 - 6x .

62.Пусть f – функция. При каких условиях отношение f −1 является функцией?

63.Пусть f : X → Y и g :Y → Z – некоторые функции. Доказать, что отношение f o g является функцией.

64.Пусть f : X → Y – функция. Доказать, что:

1)если A B X , то f ( A) Ì f (B);

2)если A B Y , то f −1 ( A) Ì f −1 (B).

65.*Доказать, что для любой функции f и произвольных A и B :

67.*Привести примеры отношений P , для которых:

1)P−1 (A I B) ¹ P−1 (A)I P−1 (B);

2)P−1 (A \ B) ¹ P−1 ( A) \ P−1 (B);

3)P−1 (A)Ë P−1 (A).

68.Пусть f : X → Y – функция. Доказать, что f инъективна тогда и

только тогда, когда для всех подмножеств A и B множества X справед- ливо тождество f (A I B) = f (A)I f (B).

21

69.Пусть X – конечное множество и f : X → X – инъекция. Доказать, что f – биекция.

70.Пусть f : X → Y , g :Y → Z . Доказать, что если:

4)f и g – биекции, то ( f o g )−1 = g−1 o f −1 .

71.Доказать, что если:

1)A : B , B : C , то A : C ;

2)A : A1 и B : B1 , то A× B : A1 × B1;

3)A : A1 , B : B1 , A I B = , A1 I B1 = , то A U B : A1 U B1 .

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

1) A×B :B× A; 2) ( A×B)×C :B×( A×C); 3) ( A×B)×C : A×B×C .

73.Доказать, что мощность области значений функции не превосходит мощности ее области определения.

74.Доказать, что:

1)всякое подмножество конечного множества конечно;

2)разность двух конечных множеств конечна;

3)пересечение конечного числа конечных множеств конечно;

4)объединение конечного числа конечных множеств конечно;

5)прямое произведение конечного числа конечных множеств конечно.

75.Доказать, что если множество A бесконечно, а B – конечно, то мно- жество A \ B – бесконечно.

76.Доказать, что булеан множества имеет мощность, большую чем мощность самого множества.

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

78.Доказать, что всякое счетное множество можно разбить на k непе- ресекающихся счетных подмножеств.

79.Доказать, что любое бесконечное подмножество счетного множе- ства счетно, т.е. счетное множество является наименьшим по мощности бесконечным множеством.

22

80. Доказать, что если:

1) A счетно, а B конечно, то множества A \ B и A U B счетны;

2)A и B счетны, то A U B счетно;

3)все Ai конечны, непусты и попарно не пересекаются, то UAi счетно;

i ¥

4) все Ai счетны, то UAi счетно.

i ¥

81.Привести пример счетного семейства непустых конечных множеств, объединение которых конечно.

82.Доказать, что если:

1)A бесконечно, а B – не более чем счетно, то AUB : A;

2)A несчетно, а B – не более чем счетно, то A \ B : A.

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

84.Доказать, что счетными являются следующие множества:

1)целых чисел;

2)рациональных чисел;

3)рациональных чисел сегмента [a,b] ;

4)простых чисел;

5)точек плоскости, координаты которых рациональны;

6)точек квадрата [a,b] ×[c,d ] , координаты которых рациональны.

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

86.Доказать, что множество всех конечных подмножеств счетного множества счетно.

87. Доказать, что множество многочленов от одной переменной

сцелыми коэффициентами счетно.

88.Доказать счетность множества алгебраических чисел, т.е. чисел, являющихся корнями многочленов от одной переменной с целыми коэф- фициентами.

23

89.Доказать, что множество всевозможных последовательностей нулей

иединиц несчетно (теорема Кантора).

90.Доказать, что множество всевозможных последовательностей нулей

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

91.Доказать, что множество точек отрезка [0,1] несчетно.

92.Доказать, что множество точек отрезка [0,1] континуально.

93.Доказать, что (0,1) :[0,1] :[0,1) : (0,1] :[a,b] : ¡.

94.Доказать, что множества точек двух окружностей равномощны.

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

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

97.Определить мощность множества:

1){[1,2], [1,3], [4,5], [4,6]} U{1, 2, 3} ;

2){[1,2], [1,3], [4,5], [4,6]}×{1, 2, 3} ;

10){(x, y) x, y ¡ x2 + y2 ≤ 25}U{(x, y) x, y ¡ (x −1)2 + ( y − 4)2 ≤ 4};

11){(x, y) x, y ¡ x2 + y2 ≤ 25} \{(x, y) x, y ¡ (x −1)2 + ( y − 4)2 ≤ 4};

12) {(x, y) x, y ¡ x2 + y2 = 25}.

13) [0,1]3 ; 14) [1,2]×[3,6]×[7,9]; 15) ¡2 ; 16) (¡+ )2 ;

17)иррациональных чисел;

18)трансцендентных (неалгебраических) чисел.

24

98.Привести примеры счетных множеств A и B , для которых: а) A I B , A \ B конечны, в) A I B конечно, A \ B счетно, б) A I B , A \ B счетны, г) A I B счетно, A \ B конечно.

99.Привести примеры множеств таких, что A континуально,

1)B счетно,

а) A I B конечно, б) A I B счетно;

2)B континуально,

а) A I B , A \ B конечны,

б) A I B , A \ B континуальны,

в) A I B конечно, A \ B континуально, г) A I B континуально, A \ B конечно.

100.Определить, является ли операция ϕ :{1,2,3}2 →{1,2,3} идемпотент-

ной, коммутативной, если:

101. Определить, является ли операция ϕ :{0,1}2 →{0,1} идемпотентной, коммутативной, ассоциативной, если:

102. Определить, является ли операция ϕ : A2 → A идемпотентной, коммутативной, ассоциативной, если:

5)a ϕ b = a +2 b , A = ¡;

6)a ϕ b = max{a,b}, A = ¡.

25

103.Определить, какими свойствами (идемпотентность, коммутатив- ность, ассоциативность) не обладают следующие бинарные операции. Ответ обосновать примерами:

1)арифметические операции сложения и умножения;

2)объединение и пересечение множеств;

3)произведение квадратных матриц;

4)композиция бинарных отношений;

5)сложение n -мерных векторов;

6)конъюнкция и дизъюнкция.

104.Определить, является ли операция g : ¡2 ® ¡ дистрибутивной

26

11.Найти все простые импликанты функций:

1)x y z p x y z p x y z p x y z p x y z p ;

2)f (x, y, z, p) = (1111 1000 0100 1100);

3)z p y p x y z .

12.Построить все тупиковые ДНФ следующих функций:

1)f (x, y, z) = (1011 1001);

2)f (x, y, z) = (0111 1110);

3)f (x, y, z, p) = (1100 0101 0000 0001);

4)f (x, y, z, p) = (1111 1000 0100 1100);

5)f (x, y, z, p) = (11101 0110 0001 0101).

13.Определить, является ли функция gi импликантой (простой импли- кантой) функции f :

1)f = (0101 0111):

g1 = (0101 0101), g2 = (0101 1111), g3 = (0101 0001); 2) f = (0011 0011 0001 1111):

g1 = x z , g2 = yz , g3 = x z p g4 = x yz , g5 = xz ;

3) f = x y z p Ú x y z p Ú x y z p Ú x y z p Ú x y z p Ú x y z p Ú x y z p :

g1 = y z p x z p , g2 = x y z , g3 = x y z p , g4 = x y z , g5 = z p ; 4) f = x y z Ú x y p Ú z p :

g1 = z , g2 = p , g3 = zp , g4 = xzp , g5 = x yzp , g6 = x y z p .

14.Выписать все сравнимые наборы для функции двух, трех и четырех переменных.

15.Доказать следующие утверждения.

1)Если функция f (x1,..., xn ), n ³ 2 принимает значение 1 на нечет-

ном количестве наборов, то она нелинейна.

4) Если в СДНФ знак везде заменить на знак Å, то получится формула, эквивалентная исходной.

16. Сколько 1 в наборе значений самодвойственной функции n пере- менных?

30