- •1. МНОЖЕСТВА
- •1.1. Отношения между множествами
- •1.2. Разбиения множеств
- •1.3. Произведение множеств
- •1.4. Отображения
- •1.5. Ответы, указания, решения к разделу 1
- •2. КОМБИНАТОРИКА
- •2.1. Задачи
- •2.2 Ответы, указания, решения к разделу 2
- •3. МАТЕМ. АТИЧЕСКАЯ ЛОГИКА
- •3.1. Основные равносильности.
- •3.2. Высказывания
- •3.3. Ответы, указания, решения к разделу 3.2
- •3.4. Предикаты
- •3.5. Ответы, указания, решения к разделу 3.4.
- •4. КОДИРОВАНИЕ ИНФОРМАЦИИ
- •Ответы, указания, решения к разделу 4
- •5. ГРАФЫ
- •Ответы, указания, решения к разделу 5
- •Библиографический список
7 |
|
мАН +мАФ + мНФ + мАНФ = 36. |
(*) |
По условию |
|
мАНФ = мНФ - 2, и мАНФ = мАФ – 4, и мАНФ = мАН – 6. |
|
Сложим эти равенства и получим |
|
3* мАНФ = м АН + мАФ + мНФ + мАНФ -12, т.е.
мАН + мАФ + мНФ + мАНФ = 3* мАНФ + 12.. Подставим в равенство (*). Имеем 4* мАНФ +12 = 36. Отсюда мАНФ = 6.
Тогда имеем мНФ = 6 + 4 = 10. Число изучающих французский или немецкий = мФ + мН + мНФ + + мАНФ = 20 + 14 + 10 + 6 = 50
Число изучающих или французский или немецкий = мФ + мН =34.
Ответ. а) 6, б) 100, в) 50 г) 34.
№1.16. На множестве всех углов определено свойство «быть прямым углом». Определяет ли это свойство разбиение множества на классы?
№1.17. Будут ли разбиением на классы следующие разбиения:
а) множество существительных русского языка разбито на существительные мужского, женского и среднего рода;
б) множество книг в библиотеке разбито на научную, художественную, техническую и математическую литературу;
в) множество натуральных чисел разбито на простые и составные; г) множество студентов разбито на отличников, успевающих и неуспевающих.
№1.18. На какие классы разбивается множество точек плоскости; а) прямой линией?
б) двумя параллельными прямыми? в) двумя пересекающимися линиями?
г) тремя попарно пересекающимися прямыми?
(Определите правило принадлежности точки некоторому классу).
№1.19. На какие классы разбивается множество точек трехмерного пространства: а) плоскостью?
б) двумя параллельными плоскостями? в) двумя пересекающимися плоскостями?
№1.20. Разбить множество треугольников на классы с помощью свойств: «быть равнобедренным» и «иметь прямой угол». Приведите диаграммы Эйлера – Венна.
1.3.Произведение множеств
№1.21. Доказать, что, если х R, y R, то точки К (х, у) и М (у, х) симметричны относительно биссектрисы первого и третьего координатных углов. (Указание: определите расстояния от каждой из точек до прямой).
№1.22. . Найти декартово произведение множеств А х В.Выделить и изобразить на плоскости 6 трехэлементных отношений. Какие из них являются функциями?
0) |
А={2 , 4, 3}, |
B={1, 3, 2} |
1) |
А={2, 4, 7}, |
B={2 , 4, 3} |
2) |
А={1, 3, 2}, |
B={2, 4, 7} |
3) |
А={2 , 4, -3}, |
B={2, 4, 7} |
4) |
А={1, 3, 2}, |
B={2 ,- 4, 3} |
5) |
А={1, 3, 2}, |
B={-2, 4, 7} |
6) |
А={1, 3, 2}, |
B={-1, 3, 2} |
7) |
А={2, 4, 7}, |
B={2 , -4, 3} |
8) |
А={1, 3, 2}, |
B={-2 , -4, 3} |
9) |
А={2 , 4, -3}, |
B={2, 4, 7} |
Пример.
А={2 , 5, 3}, B={2, 6, 7}.
А х В = {(2, 2), (2, 6), (2, 7), (5, 2), (5, 6), (5, 75, (3, 2), (3, 6), (3, 7)}
Трехэлементные отношения: |
|
|
|
||||
М1 |
= {(2, 2), (2, 6), (2, 7)}, |
М2 |
= {(2, 6), (2, 7), (5, 2)}, |
||||
М3 |
= {(2, 7), (5, 2), (3, 6)}, |
М4 |
= {(5, 2), (5, 6), (5, 7)}, |
||||
М5 = {(5, 2), (3, 7), (2, 7)} , |
М6 = {(2, 2), (5, 6), (3, 7)}. |
||||||
|
7 |
|
● |
|
7 |
|
● |
|
|
|
|
||||
|
6 |
|
● |
|
6 |
|
● |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
||
|
2 |
|
● |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
● |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
3 |
|
|
5 |
|
|
|
|
|
|
|
|
|
2 |
3 |
5 |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
Рис. 11. Множество М1 |
|
Рис. 12. Множество М 2 |
|||||||||||||||||||||||||||||||
7 |
|
● |
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
● |
||||||||
6 |
|
|
|
|
● |
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
● |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
2 |
|
|
|
|
|
|
|
|
● |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
● |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
3 |
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|||||||
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
3 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
Рис. 13. Множество М3 |
|
|
|
|
Рис. 14. |
Множество М4 |
||||||||||||||||||||||||||||
|
7 |
|
|
● |
● |
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
● |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
● |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
2 |
|
|
|
|
|
|
|
● |
|
|
|
|
2 |
|
|
● |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
3 |
5 |
|
|
|
|
|
|
|
|
|
2 |
3 |
5 |
|
|
|||||||||||
|
|
Рис. 15. Множество М5 |
|
Рис. 16. Множество М6 |
||||||||||||||||||||||||||||||
Функциями являются отношения М3, М5, М6. |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
№ 1.23. |
Укажите необходимые и достаточные условия, равенства А х В = В х А. |
|||||||||||||||||||||||||||||||||
№ 1.24. Изобразите множество точек: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
а) М [(х, у) N2 и у = х]; |
б) М [(х, у) R2 и у=х]; |
|
|
|
|
|
|
|
||||||||||||||||||||||||||
в) М [(х, у) R2 и у<х]; |
г) М [(х, у) R2 и у<= х]; |
|
|
|
|
|||||||||||||||||||||||||||||
д) М [(х, у) R2 и у>х]; |
|
е) М [(х, у) R2 и у>=х]; |
|
|
|
|
||||||||||||||||||||||||||||
ж) М [(х, у) R2 |
и 0<= х <=1 и 0<= у <=1]; |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
з) М [(х, у) R2 |
и 0<= х <=1 или 0<= у <=1]. |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
Решение з). |
|
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
1 |
|
|
|
|
|
x |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 17. |
Множество М задания з) – вся заштрихованная область |
|||||||||||||||||||||||
№ 1.25. |
Пусть А, В, С – множества. Доказать, что |
|
|
|
|
|
|
|
||||||||||||||||||||||||||
а) (А В) х С = (А х С) (В х С); |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
б) А х (В С) = (А х В) (А х С);
№ 1.26. Пусть А = {1, 2, 3}, В = {3, 4}, С = {5, 6}. Получить множества А х В х С, С х В х А, А х С х В, В х А х С.
№ 1.27. Пусть А = {1, 2, 3},В ={3, 4, 5}. Составить и изобразить на плоскости А х В. Выделить и изобразить на плоскости подмножества
а) М [(х, у) А х В и у = х]; б) М [(х, у) А х В и у < х]; в) М [(х, у) А х В и у<= х].
1.4. Отображения
9
0отношение, в котором каждому элементу х, принадлежащему множеству Х соответствует точно один элемент у из множества У, называется отображением множества Х во множество У.
Если множества равны Х = У, то говорят об отображении на множестве Х (или У). Пример.
Пусть Х = {2, 4, 6, 8, 10}. Зададим на этом множестве отношение «х является делителем у».
Построим график и граф этого отношения. (рис. 18)
10 |
|
• |
|
|
|
|
|
|
• |
2 |
||
|
|
|
|
|
|
|
||||||
8 |
|
• |
• |
|
|
• |
|
|
|
|||
6 |
|
• |
|
|
• |
|
|
10 |
4 |
|||
|
|
|
|
|
||||||||
4 |
|
• |
• |
|
|
|
|
8 |
6 |
|||
2 |
|
• |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
6 |
8 |
10 |
|
Рис.18. График и граф отношения х делит у
№1.28. Построить всевозможные отображения множества А = {a. b} во множество В = {м, н}. Какие из них являются отображениями на множество В?
№1.29. Построить всевозможные отображения множества А = {a. b} в множество А. Какие из них являются отображениями на множество А?
№30. Пусть множество А = {a. b} Составить множество А2. Построить всевозможные отображения типа А2 А, сопоставляющие с каждой парой элементов из А элемент этого же множества А (функции двух аргументов). Сколько всего отображений такого типа?
№1.31. Выяснить какие из отображений будут биективными:
а) f: x y = x3 , x R. y R; |
|
|
б) f: x y = 2x , x R, y R; |
|
|
в) f: x |
y = 2x , x R, y (0, + ); |
|
г) f: x |
y = lg x, x (0, + ), y R; |
|
д) f: x |
y = sin x, x R; y [-1,1]; |
|
е) f: x |
y=sin x, x [-π/2, π/2]; y [-1,1]; |
|
№ 1.32. Записать обратные функции для функций: |
||
а) f: x y = 2x - 5 , x R; |
б) f: x y = 2x , x R; |
|
в) f: x |
y = sin x, x [-π/2, π/2]; |
г) f: x y=cosx, x [0, π]; |
е) f: x |
y=tgх, х (-π/2, π/2); |
|
№1.33. Пусть А = {1, 2, 3}. Построить всевозможные отображения множества А на множество А.
№134. Построить графики:
а) Г1 = М [x N и y = |x|]; |
б) Г2 = М [x Z и y = |x|]; |
в) Г3 = М [x R и y = |x|]; |
|
№1.35. Х – множество студентов группы. У – множество столов в аудитории. Каждому студенту соответствует стол, за которым он сидит. Является ли это соответствие отображением?
№1.36. Х – множество книг в библиотеке. У – множество писателей. Книга х написана писателем у. Является ли это соответствие отображением?
№1.37. Х = {11, 12, 13, 14, 15, 16, 17}. У ={0, 1, 2}. Число х при делении на 3 дает остаток у. Является ли это соответствие отображением?
№1.38. Х – множество пальто в гардеробе института. У – множество номерков в этом гардеробе. Каждому пальто соответствует свой номерок. Является ли это соответствие отображением?
№1.39. Является ли соответствие отображением?
а) паре (а, b) N2 соответствует число (a + b) N; б) паре (а, b) N2 соответствует число (a - b) N; в) паре (а, b) N2 соответствует число (a * b) N; г) паре (а, b) N2 соответствует число (a / b) N;
№ 1.40. Можно ли ввести отображение следующим образом:
каждому отрезку из множества всех отрезков ставиться в соответствие треугольник из множества треугольников, для которого отрезок является средней линией?
№ 1.41. Докажите равномощность множеств Х и У, если
10
а) Х – множество букв в слове «таблица», У – множество цифр числа 6745483 б) Х – множество букв в слове «каравай», У – множество букв в слове «молоток». № 1.42. Доказать счетность а) множества четных натуральных чисел;
б) множества натуральных нечетных чисел; в) множества целых отрицательных чисел; г) множества целых чисел;
д) объединения счетного множества счетных множеств; е) множества рациональных чисел, ж) счетного числа счетных множеств.
№1.43. Из множества четных натуральных чисел выделить два счетных подмножества.
№1.44. Доказать равномощность множества точек
а) двух отрезков; б) двух окружностей: в) сторон треугольника и вписанной в него окружности.
№1.45. Пусть м(А) – мощность множества А. доказать, что м(А В ) = м(А) + м(В) - м( А В) .
1.5.Ответы, указания, решения к разделу 1
№1.4. А = А1, А4 = А5.
№1.7. Равенства 1 – 6 справедливы.
№1.12 . Студенов, не занимающихся ни спортом, ни художественной самодеятельностью и не отличников –
62.Отличников или спортсменов – 22. Только отличников – 0. Спортсменов или участников художественной самодеятельности – 38.
№1.13. Только английский язык изучают 10 студентов, немецкий, но не французский -18.
№1.14. Спортсменов 19. неуспевающих нет.
№1.16. Да.
№.1.17. Да, нет, да, нет.
№1.30. Например
А2 А = {((а, а), а), ((а, b), а), ((b, а), b), ((b, b), а)}. |
Всего 16. |
№1.31. а), в), г), е).
№1.35. Да.
№1.36. Да.
№1.37. Да.
№1.38. Да.
№1.39. Да, нет, да, нет.
№1.40. Нет.
№1.41. Указание. Найдите мощность каждого из множеств.
№1.42. Следует придумать соответствие между данным множеством и множеством натуральных чисел. Докажем, например, счетноссть множества рациональных чисел
Q = {x| x = p/q, p Z, q N}
Числу 0 поставим в соответствие 1. Расположим все рациональные числа в таблицу. В первой строке распо-
ложим все дроби со знаменателем 1, во второй строке дроби со знаменателем 2 и т.д. Будем нумеровать элементы в последовательности, указанной стрелками, пропуская ранее пронумерованные числа.
1/1 |
-1/1 |
2/1 |
-2/1 |
3/1 |
-3/1 … |
1/2 |
-1/2 |
3/2 |
-3/2 |
5/2 |
-5/2 …. |
1/3 |
-1/3 |
2/3 |
-2/3 |
… |
|
… |
|
|
|
|
|