Лекции Русакова, страница 6

Доказать тождества, используя законы алгебры множеств:43( A ∪ B) ∪ (A ∪ B) = B \ A;A \ [(A ∩ B) ∪ (A \ B)] = ∅;(A ∩ B ∩ C ∩ D ) ∪ ( A ∩ C) ∪ ( B ∩ C) ∪ (C ∩ D) = C;(A ∩ B ∩ D) ∪ (A ∩ B ∩ C ∩ D ∩ E) ∪ (A ∩ D ∩ A ) = A ∩ B ∩ D;[(A ∩ B) ∪ (A ∩ C) ∪ ( A ∩ D ∩ E)] ∩ [(A ∩ B ∩ C) ∪ ( A ∩ D ∩ E ) ∪ ( A ∩ B ∩ E)] =(A ∩ B) ∪ ( A ∩ B ∩ D ∩ E).№ 1.23. Для произвольных множеств А, В, С, D ⊂ I построитьдиаграммы Эйлера-Венна при условии:A, B, C ⊂ D; A ∩ B ∩ C ≠ ∅;C ⊂ A ∩ B; D ⊂ B; C ∩ D ≠ ∅;A ⊂ B; C ⊂ D; A ∩ D = ∅; B ∩ C = ∅;C ⊂ A ∪ B; (A \ B) ∩ C ≠ ∅; (B \ A) ∩ C ≠ ∅ .№1.24. С помощью диаграмм Эйлера-Венна установить справедливостькаждого из следующих утверждений относительно произвольных множествА, В, С ⊂ I:(A \ B) \ C = (A \ C) \ (B \ C);если A ∩ B ⊂ C и A ∪ C ⊂ B , то A ∩ C = ∅;если A ⊂ B ∪ C, и B ⊂ A ∪ C, то B ≠ ∅;(A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C).№ 1.25.

показать с помощью диаграмм Эйлера Венна, какое из двухмножеств ( A ∩ B) и (A ∪ B) является подмножеством другого.№ 1.26. Как можно представить следующие множества, используядиаграммы Эйлера-Венна:{A, {A}}, {{a}, {b}}, {X, Y, Z},где Х={x|х=1 или (х-2)∈Х},Y={х|х=3 или (х-3)∈Y},Z={x|x=2 или (х-2)∈Z}?44№ 1.27. Пусть даны множества А, В и С. С ⊆ ВДоказать, что:а) A ∩ C ⊆ A ∩ B; б) A ∪ C ⊆ A ∪ B; в) A \ B ⊆ A \ C; г) C \ A ⊆ B \ A ;д) B \ A ⊆ C \ A.№ 1.28. Доказать, что если A ⊆ B, то P(A) ⊆ P(B) .№ 1.29. Доказать, что A ∪ B = A ∩ B.Решите задачи № 1.30 ÷1.39 с использованием диаграммы Эйлера-Венна.№ 1.30. В студенческом потоке 37 человек хорошо знают математику, а25 человек – электронику, и 19 человек хорошо знают и математику иэлектронику.

Если в потоке каждый из студентов знает хотя бы один из этихпредметов, то сколько студентов в потоке?№ 1.31. Из 250 студентов 151 изучают немецкий язык, 136 –французский язык, 27 – итальянский, 63 – французский и немецкий, 7 –итальянский и французский, 11 – немецкий и итальянский, 4 – все три языка.а) Сколько студентов изучают немецкий или французский язык?б) Сколько студентов изучают только итальянский язык?в) Сколько студентов изучают немецкий и французский язык, но неитальянский?г) Сколько студентов не изучают ни одного языка?д) Сколько студентов изусают хотя два иностранных языка?№ 1.32.

В отчете о количестве студентов, изучающих иностранныеязыки, сообщалось, что из 100 студентов все три языка изучают 5 человек,немецкий и английский – 10 человек, французский и английский – 8 человек,немецкий и французский – 20 человек, английский – 30, немецкий – 23,французский – 50. Инспектор, представивший этот отчет, был отстранен отработы. Почему?№ 1.33 Каждый из 500 студентов обязан посещать хотя бы один из трехспецкурсов: по математике, физике, астрономии. Три спецкурса посещают 1045студентов, по математике и астрономии –25 студентов, спецкурс только пофизике – 80 студентов. Известно также, что спецкурс по математикепосещают 345 студентов, по физике – 145, по асирономии – 100 студентов.Сколько студентов посещают спецкурс только по астрономии? Сколькостудентов посещают два спецкурса?№ 1.34.

Экзамен по математике содержал три задачи: по алгебре,геометрии и тригонометрии. Из 800 абитурентов задачу по алгебре решили250 человек; по алгебре или геометрии – 660 человек; по две задачи решили400 человек, из них две задачи по алгебре и и геометрии решили 150 человек,по алгебре и тригонометрии – 50 человек; ни один абитуриент не решил всезадачи; 20 абитуриентов не решили ни одной задачи; только потригонометрии задачи решили 120 человек.

Сколько абитуриентов решилитолькооднузадачу?Сколькоабитуриентоврешилизадачипотригонометрии?№ 1.35. На курсах иностранных языков учится 600 человек. Из нихфранцузский изучают 220 человек, английский – 270 человек. Слушатели,изучающие английский язык, не изучают немецкий язык; один французскийязык изучают 100 человек, один немецкий язык изучают 180 человек.Сколько человек изучает по два иностранных языка? Сколько человекизучает один иностранный язык?№ 1.36. На кафедре иностранных языков работают 18 преподавателей.Из них 12 преподают английский язык, 11 – немецкий язык, 9 – французскийязык. 5 преподавателей преподают английский и немецкий языки, 4 –английский и французский, 3 – немецкий и французский.

Сколькопреподавателей преподают все три языка? Сколько преподавателейпреподают только два языка?№ 1.37. Группа студентов из 25 человек сдала экзаменационнуюсессию со следующими результатами: 2 человека получили только“отлично”; 3 человека получили отличные, хорошие и удовлетворительные46оценки; 4 человека только “хорошо”; 3 человека только хорошие иудовлетворительные оценки. Число студентов, сдавших сессию только на“удовлетворительно”, равно числу студентов, сдавших сессию только на“хорошо” и “отлично”. Студентов, получивших только отличные иудовлетворительные оценки – нет.

Удовлетворительные или хорошие оценкиполучили только 22 студента. Сколько студентов сдали сессию только на“удовлетворительно”?№ 1.38. Преподаватели кафедры Прикладной математики преподают натрех факультетах: механическом, технологическом, экономическом. Натехнологическом факультете работает 22 преподавателя, на механическом –23 преподавателя, на механическом и экономическом –36 преподавателей.Только на технологическом факультете работают 10 преподавателей. 2 –натрех факультетах.

5 преподавателей работают только на механическом иэкономическом факультетах. Число преподавателей, работающих только намеханическом и технологическом факультетах, равно числу преподавателей,работающих на экономическом и технологическом факультетах. Сколькопреподавателей работает на кафедре? Сколько преподавателей работаеттолько на одном факультете?№ 1.39. Экзамен по математике содержал три задачи: по алгебре,геометрии и тригонометрии. Из 750 абитуриентов задачу по алгебре решили400 абитуриентов, по геометрии – 480, по тригонометрии – 420. Задачи поалгебре или геометрии решили 630 абитуриентов; по геометрии илитригонометрии – 600 абитуриентов; по алгебре или тригонометрии – 620абитуриентов.

100 абитуриентов не решили ни одной задачи. Сколькоабитуриентов решили все задачи? Сколько абитуриентов решили толькоодну задачу?№ 1.40. Доказать аналитически, что для любых трех множеств А, В и Ссправедливы равенства:а) (A ∪ B) ∪ C = A ∪ (B ∪ C);47б) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C);в) A ∪ B = I, если A, B ⊂ I и B ⊂ A;г) A ∪ B = A ∩ B, если A, B ∈ I;д) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);е) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);ж) A ⊂ C, если A ⊂ B и B ⊂ C;з) C ⊂ A, если (A ∩ B) ∪ C = A ∩ (B ∪ C).Глава 2.

Теория графов.2.01. Основные определения теории графов.Определение.Граф G — это упорядоченная пара G=(V,E), где V — это множествовершин или узлов, E — это множество пар различных вершин, называемыхрёбрами.Определение.Ориентированным графом (графом или орграфом) будем называтьтройку G ( X , U , f ) , где X ( ≠ ∅) — множество, называемое множествомвершин графа,дуг, f— множество (возможно и пустое), называемое множеством— отображение, действующее из Uв X × X , называемоеотображением инцидентности.Моментом рождения теории графов как математической дисциплинысчитают появление в 1736 году статьи Эйлера, в которой рассматриваласьзадача о Кёнигсбергских мостах (см. раздел дополнительные сведения).48Эйлер показал, что нельзя обойти семь городских мостов и вернуться висходную точку, пройдя по каждому мосту ровно один раз.Определение.Граф называется не ориентированным, если каждое его ребро неориентировано, и ориентированным, если ориентированы все его рёбра.Определение.Графы G и G' изоморфны, если существует такое взаимно однозначноесоответствие между множествами их вершин V и V', что вершины соединенырёбрами в одном графе в том и только том случае, когда соответствующие имвершины соединены в другом графе.

Если рёбра ориентированы, то ихнаправления так же должны соответствовать друг другу.ПримерДва графа изоморфныне изоморфный первым двум, так как нет ребра междукрайними вершинами.Определение.Вершина, не инцидентная никакому ребру, называется изолированной.49Определение.Граф, состоящий только из изолированных вершин, называется нульграфом.Определение.Если в графе есть петли и/или кратные ребра, то такой граф называютпсевдографом.Определение.Псевдограф без петель называется мультиграфом.Определение.Мультиграф в котором ни одна пара не встречается более одногораза называется графом.Определение.Еслипары(v,w)являютсяупорядоченными,графназываетсяориентированным (орграфом).Ребра ориентированного графа называются дугами.Определение.Полным графом называется граф U = U (V )ребрами, которогоявляются всевозможные пары для двух различных вершин из V.Рис.