- •Глава 3. Элементы дискретной математики
- •§1. Основные понятия теории множеств
- •§2. Отображения, соответствие, равномощность
- •§3. Алгебра высказываний
- •§4. Логика предикатов
- •§4. Элементы комбинаторики
- •§5. Элементы теории графов
- •Алгоритм Дейкстра для отыскания минимального пути
- •Упражнения
- •1. Множества
- •2. Математическая логика
Упражнения
1. Множества
1. Пусть R множество всех вещественных чисел, N – множество натуральных чисел, Q – множество рациональных чисел, Z – множество целых чисел. Указать какие из этих множеств являются подмножествами других множеств.
2. Пусть А множество делителей числа 72, В – множество делителей числа 54. Найти множества: а) АÈВ; б) АÇВ; в) А \ В; г) В \ А.
3. Пусть множество А состоит из натуральных чисел, делящихся на 4, множество В – из натуральных чисел, делящихся на 6, и множество С – из натуральных чисел, делящихся на 5. Записать символически эти множества и найти множества: АÇВ, АÇС, ВÇС, АÇВÇС.
4. Пусть множество А состоит из натуральных делителей числа 70, В - из натуральных делителей числа 105. Найти множества: а) АВ; б) АВ; в) А \ В; г) В \ А.
5. Пусть множество А состоит из натуральных делителей числа 72, В - из натуральных делителей числа 54. Найти множества: а) АВ; б) АВ; в) А \ В; г) В \ А.
6. Пусть множество А состоит из натуральных чисел, делящихся на 4, множество В – из натуральных чисел, делящихся на 6, и множество С – из натуральных чисел, делящихся на 5. Записать символически эти множества и
найти множества а) АВ, б) АС, в) ВС, г) АВС.
7. Пусть А = ( ; 5], B = [1; 3], C = [2; +). Изобразите на чертеже множества: а) А \ В; б) (А В) С; в) (ВС) \ А.
8. Найти множества АВ, АС, ВС, (АВ) С, АВС, если
1). A = [0; 3], B = (1; 5), C = 2; 0]; 2). A = (; 1], B = [1; ), C = (0; 10).
9. Построить интервалы изменения переменного х, удовлетворяющего неравенствам:
1). (х1)(х2) £ 0; 2). (х1)(х2) ³ 0; 3). (х3)(х5) < 0; 4). (х3)(х5) >0;
5). 4 – х2 ³ 0; 6). х2–4 ³ 0; 7). |x| £ 1; 8). |x+1| £ 2.
10. Пусть А и В множества точек М(х, у) плоскости, координаты которых удовлетворяют неравенствам 2х + 3у 6, 3х у 3, соответственно. Изобразите множество АВС, где С множество точек М(х, у), координаты которых удовлетворяют неравенствам х 0, у 0.
11. Пусть А и В множества точек М(х, у) плоскости, координаты которых удовлетворяют неравенствам 3х + 5у 15, 5х 3у 15, соответственно. Изобразите множество АВС, где С множество точек М(х, у), координаты которых удовлетворяют неравенствам х 0, у 0.
12. С помощью равенств теоремы 1 доказать следующие равенства:
а). (АВD) (АВСDE) (АDА) = АВD;
б). (АВС) (АВС) В С = U;
в). (АВ С D) (АС) (BC) (C D) = C.
13. Из 64 студентов занимаются спортом 40 человек, любят слушать музыку 30 человек. При этом занимаются спортом и любят слушать музыку 21 студент. Сколько человек не занимается спортом и не любит слушать музыку?
14. Среди 35 туристов одним английским языком владеют 11 человек, английским и французским – 5 человек. 9 человек не владеют ни английским, ни французским. Сколько человек владеют только французским языком?
15. Из 40 учащихся книгу А читали 25 учеников, книгу В – 22 ученика, книгу С – также 22 ученика. Книгу А или В читали 33 ученика, книгу А или С – 32, В или С – 32; все три книги прочли 10 учеников. Сколько учеников прочли только по одной книге? Сколько учеников не читали ни одной из этих книг?
16. В течение недели в кинотеатре демонстрировались фильмы А, В, С. Из 40 школьников каждый просмотрел либо все 3 фильма, либо 1 фильм. Кроме того, фильм А видели 13, фильм В – 16, фильм С – 19 ребят. Сколько ребят просмотрели все 3 фильма?
17. Из 64 студентов занимаются спортом 40 человек, любят слушать музыку 30 человек. При этом занимаются спортом и любят слушать музыку 21 студент. Сколько человек не занимается спортом и не любит слушать музыку?
18. Среди 35 туристов одним английским языком владеют 11 человек, английским и французским – 5 человек. 9 человек не владеют ни английским, ни французским. Сколько человек владеют только французским языком?
19. Среди 57 школьников в шахматы умеют играть 35 человек, в шашки – 40 человек, причем в обе игры умеют играть 21 человек. Сколько человек не умеют играть ни в шахматы, ни в шашки?
20. Из 220 школьников 163 играют в баскетбол, 175 – в футбол, 24 не играют в эти игры. Сколько человек одновременно играют в баскетбол и футбол?
21. В классе 30 учеников. Все, кроме двух, имеют оценки «5», «4» и «3». Число учащихся, имеющих оценки «5» – двенадцать, «4» – четырнадцать, «3» – шестнадцать. Трое учатся лишь на «5» и на «3», трое – лишь «5» и на «4» и четверо лишь
22. Доказать, что следующие множества счетные: а) множество нечетных чисел; б) множество простых чисел; в) множество троек целых неотрицательных чисел.
23. Доказать, что множество точек окружности равномощно множеству точек прямой линии.
24. Доказать, что множество точек плоскости равномощно множеству точек прямой линии.