Задания для самостоятельного выполнения
Г.А. Аршинов
Практикум
По математике
для студентов юридического факультета
| |
Практическое занятие №1. Операции над множествами
| Цель занятия: | 1. | изучить способы задания множеств; |
| 2. | получить навыки в применении операций над множествами. |
Множества можно задавать двумя способами:
Перечислением элементов множества.
Например, множество M={x, y, z}. Оно состоит из трёх элементов (порядок элементов произвольный), т.е. {x, y, z}={y, x, z}
описанием элементов множеств:
- описанием характеристических свойств, объединяющих элементы в виде уравнений, диаграмм Эйлера-Венна и геометрически.
Например, множество M = {x2Î N; x – простое число} задано квадратами простых чисел.
- описанием множеств, порожденных процедурами над элементами. Это означает указание алгоритма порождения элементов этого множества.
Например, подмножество М всех нечетных натуральных чисел с помощью порождающей процедуры имеет вид:
M={xÎN: x=1+2n, nÎN}
Операции над множествами
| Рассмотрим операции над множествами в порядке убывания приоритета. Пересечением (произведением) двух множеств называется множество С, состоящее из тех и только тех элементов, которые принадлежат множествам А и В одновременно. Обозначение: С = АìüВ |
| ||
| Объединением (суммой) двух множеств А и В называется множество С, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В (или тому и другому вместе). Обозначение: С =АîþВ |
| ||
| Разностью множеств А и В называется такое множество С, которое состоит из тех и только тех элементов, которые принадлежат множеству А, но не принадлежат множеству В. Обозначение: С =А ½ В или С =А \ В |
| ||
| Дополнением множества А до универсального множества U называется множество С, равное разности U½A. Обозначение: С = U½А или С = Симметрической разностью двух множеств А и В называется множество | |||
| С = Аîþ В | Аìü В. Обозначение: С =А D В Формула включений и исключений для двух множеств А и В: n(АîþВ)= n(А)+ n(В) - n(А∩В). для трех множеств А, В и С: |
|
n(АîþВîþС)= n(А)+n(В)+n(С)-n(А∩В)-n(А∩С)-n(В∩С)-n(А∩В∩С)
где n(Z) – количество элементов множества Z, т.е. его мощность.
Примеры выполнения заданий
1. Заданы множества: А = {1, 3, 5, 7, 9}, B = {1, 2, 3, 4, 5}.
Найдите элементы множеств: D = Аîþ В и Е = АìüВ.
D= {1, 2, 3, 4, 5, 6, 7 ,8, 9}, Е = {1, 3, 5}.
Задания для самостоятельного выполнения
1. Задайте множество А перечислением его элементов:
| 0)A={xÎR|(x2–6x+5)×(x2–x–12)=0} | 1)A={xÎR |(x2–5x+6)×(x2+x–0)=0} |
| 2)A={xÎR|(x2 –5x +4)×(x2–x–6)=0} | 3)A={xÎR|(x2+4x–5)×(x2–x+12)=0} |
| 4)A={xÎR| (x2+3x–4)×(x2+x–12)=0} | 5)A={xÎR |(x2–5x–6)×(x2–x–6)=0} |
| 6)A={xÎR |(x2 +x–2)×(x2–7x+6)=0} | 7)A={xÎR|(x2–3x–4)×(x2–9x+20)=0} |
| 8)A={xÎR |(x2–3x+2)×(x2–4x–5)=0} | 9)A={xÎR |(x2–x–2)×(x2–x–20)=0} |
2. Заданы множества: А = {1, 3, 9, 10, 8}, B = {5, 3, 11, 4, 8}
и C = {1, 4, 8, 9, 10}. Найдите элементы множеств Д и Е:
| 0)Д = АîþВìüС; Е = (А D В) | С; | 1)Д = (АîþС) | (ВìüС); Е = А| ВìüС; |
| 2)Д = АîþВîþС; Е = АìüС D В; | 3)Д = (АîþС)ìüВ; Е = А DВîþС; |
| 4)Д = (АîþС) | В;Е = (В D С) | А; | 5)Д = АìüВìüС; Е = С D В | А; |
| 6)Д = Аîþ(В D С);Е = А | В | С; | 7)Д = (ВîþС)|(АìüС);Е = АîþВ | С; |
| 8)Д = (АîþВ)ìüС; Е = А D В | С; | 9)Д = (АîþВ) D С; Е = АìüВ | С; |
3. Изобразите с помощью диаграмм Эйлера-Венна в двух вариантах расположения следующие множества:
| 0) а)U½ ; б) ìü B½C; | 1)а)CîþА½ ; б)(А½В)îþC; | 2)а) (AD В)½C; б) ìüС; |
| 3)а)АìüВ½С; б)AìüВîþС½А; | 4)а) ½С; б)(В½А)ìüC; | 5)а) ìü ½С; б) ½С; |
| 6)а)С½АîþВ; б) ìü(ВD С); | 7)а)U½ ; б)CìüА½ ; | 8)а)A½ (BD C); б)С½АìüВ; |
| 9) а) (АîþВ)ìü(ВD С); б)AîþВ½C; |
а)
б)
Законы теории множеств
| АîþВ | º ВîþА; | AîþÆ | º А; |
| АìüВ | º ВìüА; | AìüÆ | ºÆ; |
| Аîþ (ВîþС) | º (АîþВ)îþ С; | Aìü | ºÆ; |
| Аìü (ВìüС) | º (АìüВ)ìüС; | AîþA | º А; |
| Аìü (ВîþС) | º (АìüВ)îþ (АìüС) ; | AìüA | º А; |
| Аîþ (ВìüС) | º (АîþВ)ìü(АîþС) ; | º ìü ; | |
| Аîþ U | ºU; | º îþ ; | |
| Aìü U | º А; | Aîþ (AìüB) | º А; |
| Aîþ | ºU; | Aìü (AîþB) | º А |
Равносильности теории множеств
| А½В | º Аìü ; | A½(В½С) | º (А½В)îþ(AìüС) ; |
| А½А | ºÆ; | (A½В)½С | ºA½BîþС; |
| А½ (ВîþС) | º (А½В)ìü(A½С) ; | AD В | º BDA; |
| А½ (ВìüС) | º (А½В)îþ(A½С) ; | AD В | º АîþВ ½ АìüВ; |
| (АìüВ)½С | º(А½С)ìü(В½С) ; | AD В | º (А½В)îþ (В½А) ; |
| (АîþВ)½С | º(А½С)îþ(В½С) ; | AD(ВD C) | º (AD В)D C; |
| А½(А½В) | º AìüB; | Аìü(ВDC) | º (АìüВ)D(AìüC). |
4. Докажите тождества:
| 0)X ∪ º Z ∪ X º ∩ X ∩ ∪ Z | º Z | Y | ( ∪ Z) ºÆ; | 1)X ∩Y∩(X∩Z∪X∩Y∩Z∪Z∩ t) ºX ∩Y∩Z ºY∪ ∪ (X | (X | )) ∪( | ( | ))º ∩ ( | X ∪ ) ºÆ; |
| 2) ∩Y∩ Z∪X∩Zº (X∪Y) ∩Z X∪ ∪ ºX∪Z∪ Y | (Y | X∪ ) ºY ∩ X ( ∩ | X) | ºÆ; | 3)X ∩Y∪X∩Y∩Z∪X∩Y∩Z∪X∩Y∩ZºX∩Y ºX ∩ ∩ Y (X | ) | º X (X ∩ ) | ( ∪ ) ºÆ; |
| 4) ∪ Y ∩ Z ∪ ∪ ∪ ºU ∩ º ∩ | ºZ | Y ºÆ; | 5) ((X∪Y) ∪ ( ∩ )) ∩ ºX ∩ º ( ∪Z) ∩ X | Y∪X ∩ ZºX | Y ∩ ºÆ; |
| 6) ºU ºX ∩ Y | ºX ∩ ∩ Y ∩ (Y ∪ Z) ∩ X ∩Y ºÆ; | 7) (X∪Y∪Z) ∩ (X∪Y) ∪ZºX∪Z∪Y º ∪ Y | (X ∩Y | ) ºY | X | ∪Y ºÆ; |
| 8)X ∪ ∪ X ∩ Z ºU ∪ º ∪ X ∪ ∩ (Y| ) ºX | ∪ ºÆ; | 9) (X∪Z) ∩ (X∪Y) ∩ (Y ∩ Z) ºY ∩ Z ∩ º (Y∪ ) ∩ ( | ) | ºX | Z ∩ ºÆ; |
Практическое занятие №2.
Графы
Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом. Связи между узлами(вершинами) (V), определенные неупорядоченными парами вершин графа, называются ребрами (E), а граф –неориентированным. Если пары вершинупорядочены, связи называются дугами
(рис. 2).
| Пара вершин может быть соединена двумя или более ребрами (дугами), такие ребра (дуги) называются кратными. Вершины, соединенные ребром (дугой) называются смежными. Если ребро начинается и заканчивается в одной и той же вершине, то называется петлей. | Рис. 2. Примеры А) неориентированного и Б) ориентированного графов. |
Определения
Число ребер, исходящих из вершины vi(петля учитывается дважды), называется валентностью (степенью вершины)и обозначается: d(vi).
Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер.
Неориентированный граф называется простым, если он не имеет петель и любая пара вершин соединена не более чем одним ребром.
Графы отображаются на плоскости набором точек и соединяющих их линий или векторов. Грани могут отображаться и кривыми линиями, а их длина не играет никакой роли.
Граф G называется планарным (плоским), если его можно отобразить в плоскости без пересечения его граней (рис. 5).
Граф называется связным, если для любых двух вершин существует последовательность ребер их соединяющая (рис. 3), т.е. граф не имеет изолированных фрагментов (вершин, ребер).
Граф называется полным, если любые две вершины соединены только одним ребром (рис.4). Если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2. Специальными видами графов являются деревья
(рис. 6.)
Рис. 3. Пример связного плоского графа |
Рис. 4. Примерполного графа | Рис. 5. Пример непланарного графа | ||||||||||||||||||||||||
| ГрафG = (V, E) называетсядеревом, если: 1. в нем есть одна вершина, в которую не входят ребра; она называется корнемдерева; 2. в каждую из остальных вершин входит ровно по одному ребру; 3. всевершиныдостижимы изкорня. |
Рис. 6. Пример дерева | |||||||||||||||||||||||||
Ребро (дуга) и любая из его вершин называются инцидентными. Принято говорить, что (дуга) ребро (u, v)соединяет вершины u и v.
Если вершина не инцидентна ни одному ребру (дуге), то она называется изолированной(d(vi)=0), если принадлежит только одному ребру (дуге), то называется висячей (d(vi)=1).
Основные положения о вершинах графа:
1. В графе G сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа, так как каждое ребро участвует в этой сумме ровно два раза.
2. Число нечетных вершин любого графа четно.
3. Во всяком графе с n вершинами, где n³2, всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.
4. Если в графе с вершинами n>2 две вершины имеют одинаковую степень, то в этом графе всегда найдется либо одна вершина степени 0, либо одна вершина степени n - 1.
5. Два графа G1=(V1,E1) и G2=(V2,E2) называются изоморфными, если между их вершинами существует взаимно однозначное соответствие.
Алгоритм распознавания изоморфизма двух графов G1(X, E)и G2(Y,E)
1. Если X ≠ Y, то графы не изоморфны.
2. Выписываем все элементы обоих графов, определяя пары (xi,xj) и (yi, yj) для каждого элемента, где xi, yi - число исходов для каждой вершины обоих графов, а xj, yj – число заходов.
3. Для каждого элемента x графа G1 ищем такой элемент y графа G2, что выполняется условие: число исходов x совпадает с числом исходов y, и число заходов x совпадает с числом заходов y. Найденные элементы x и y соединяем дугой, т.е. строим граф соответствия. Если соответствия нет, то графы неизоморфны.
4. Выписываем подстановку, которая переводит граф G1 в граф G2.