Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Оглавление:
Практическая работа №1.
Тема: Множества и их спецификация.
Задание №1.
Даны множества:
А = –1; 0; 1,
В = –2; 0) – полуинтервал на числовой оси,
С = –0.5; 2 - отрезок на числовой оси.
Найти:
АВ, АВС, АВ, ВС, АВС, A \ B, B \ A, A \ C, C \ A, (А \ В) \ С, А \ (В \ С), А B, A B C.
Изобразить на плоскости: А В, А С, В С. Найти , считая универсальным множеством множество всех вещественных чисел.
Решение:
Объединением двух множеств A и B называется множество, состоящее из всех элементов, являющихся элементами хотя бы одного из множеств A или B, поэтому:
АВ = –2; 0; 1
АВС = –2; 2
Пересечением двух множеств A и B называется множество элементов, принадлежащих одновременно и A, и B, поэтому:
АВ = –1
ВС = –0.5; 0)
АВС = – пустое множество
Относительным дополнением множества B до множества A называется множество тех элементов A, которые не являются элементами B, поэтому
А \ В = 0; 1
В \ А = –2; –1); (–1; 0)
А \ С = –1
С \ А = –0.5; 0); (0; 1); (1; 2
(A \ B) \ C =
A \ (B \ C) = {0; 1}
Симметрической разностью двух множеств A и B называется объединение двух разностей A \ B и B \ A, а абсолютным дополнением множества A называется множество всех элементов, не принадлежащих A, поэтому:
Декартовым (прямым) произведением двух множеств A и B называется множество всех упорядоченных пар (a,b) таких, что и , поэтому:
Задание№2
Для заданного семейства множеств где Г – заданное индексное множество, найдите объединение и пересечение всех множеств семейства, т.е. и (по всем возможным индексам ).
{Ak}kℝ, где для всякого вещественного индекса k множество
Аk={ (x, y): |x|+|y| ≤ |γ| и x, yℝ }.
Решение: рассмотрим множества Аk для некоторых фиксированных индексов k.
При k=0 множество А0={ (x, y): |x|+|y| ≤ 0}={(0;0)} – центр вещественной плоскости.
При k=0.5 и k= –0.5 А0.5=А 0.5={ (x, y): |x|+|y| ≤ 0.5} – ромб в центре вещественной плоскости с диагоналями, равными 1 и направленными вдоль осей координат.
При k=2 и k= –2 А2=А 2={ (x, y): |x|+|y| ≤ 2} – ромб с диагоналями, равными 4 и т. д..
При увеличении абсолютной величины индекса k диагонали ромба, расположенного в центре вещественной плоскости, увеличиваются и при |k|→+ ромб А занимает всю вещественную плоскость. Таким образом, объединение по всем вещественным индексам k равно = ℝ ℝ = ℝ2 – вся вещественная плоскость, а пересечение по всем вещественным индексам k равно – центр вещественной плоскости.
Задание№3
Докажите тождество, используя только определения операций над множествами:
Решение: (1) Пусть , тогда . Отсюда следует, что 1) и или 2) и . В первом случае из того, что следует, что х принадлежит также объединению множества А с любым другим множеством, в том числе и множеством В, т.е. . Но в то же время и, следовательно, х принадлежит также объединению с любым другим множеством, в том числе и множеством , т.е. . Таким образом, , т.е. . Аналогично во втором случае: из того, что следует, что х принадлежит также и . И в то же время, поскольку , то х принадлежит также объединению , с любым другим множеством, в том числе и множеством , т.е. . И также как в первом случае имеем: , тем самым .
(2) Пусть теперь . Тогда , отсюда . Следовательно, если , то , т.е. . Если же , то и значит . Таким образом, , что равносильно тому, что . Из (1) и (2) следует справедливость тождества.
Задание№4
Докажите тождество, используя диаграммы Эйлера-Венна.
Решение: Изобразим диаграмму для левой части тождества по шагам:
Теперь диаграмму правой части по шагам:
Ввиду того, что заштрихованные области, полученные на последнем шаге для левой и правой части тождества, одинаковы, можно заключить, что исходное выражение верно.
Задания для самостоятельного решения:
Задание №1
Для заданных множеств А, В и С найдите:
АВ, АС, ВС, АВС, АВ, АС, ВС, АВС, A \ B, B \ A, A \ C, C \ A, B \ C, C \ B, (А \ В) \ С, А \ (В \ С), А B, А С, B C, A B C. Изобразите на плоскости АВ, АС, ВС. Найдите считая универсальным множеством множество ℝ – всех вещественных чисел (всю числовую ось).
Задание №2
Для заданного семейства множеств где Г – заданное индексное множество, найдите объединение и пересечение всех множеств семейства, т.е. и (по всем возможным индексам ).
Задание №3
Докажите тождества, используя только определения операций над множествами.
Задание №4
Докажите тождество, используя диаграммы Эйлера – Венна.
Варианты заданий:
Вариант№1
1. А = (0; 2] – полуинтервал на числовой оси
В = [1; 5] – отрезок числовой оси
С = (–1; 2) – интервал на числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
4. . (А \ В) (В \ С) (В \ А) (С \ В) = А С
Вариант№2
1. А = {0, 1, 2, 3}– четырехэлементное множество
В = [–3; 3] – отрезок числовой оси
С = (-2; 2) – интервал на числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
4. (А \ В) (В \ С) (С \ А) = (В \ А) (С \ В) (А \ С)
Вариант №3
1. А = (–1; +∞)– интервал на числовой оси
В = (–∞; 10] – полуинтервал на числовой оси
С = [–5; +15] – отрезок числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
4. (А В) (СD) = В С, если А В = D и CD = A
Вариант №4
1. А = (–∞; 2]– полуинтервал на числовой оси
В = [–3; 3] – отрезок числовой оси
С = (0; 4) – интервал на числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
4.
Вариант №5
1. А = (–2; 3) – интервал на числовой оси
В = [0; 4] – отрезок числовой оси
С = {2; 3} – двухэлементное множество
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
Если
4.
Вариант №6
1. А = [–5; 4]– отрезок числовой оси
В = (-∞; ∞)– интервал на числовой оси
С = (–1; 0] – полуинтервал на числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
4.
Вариант №7
1. А = (2; 5]– полуинтервал на числовой оси
В = (0; 1)– интервал на числовой оси
С = {–2; -1; 0} – трехэлементное множество
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
где U – универсальное множество
4.
Вариант №8
1. А = (–1; 1)– интервал на числовой оси
В = [1; 2] – отрезок числовой оси
С = (–∞; 1] - полуинтервал на числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
4.
Вариант №9
1. А = (5; 15] – полуинтервал на числовой оси
В = [5; 10] – отрезок числовой оси
С = {4; 5; 6} – трехэлементное множество
2. , где ℕ – множество всех натуральных чисел и kℕ
3. если
если
4.
Вариант №10
1. А = (0; 3) – интервал на числовой оси
В = [–1; 3] – отрезок числовой оси
С = (–1; 0] - полуинтервал на числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
4.
Вариант №11
1. А = [–5; 2) – полуинтервал на числовой оси
В = [–5; 5] – отрезок числовой оси
С = (–1; 1) - интервал на числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
Если
4.
Вариант №12
1. А = (0; 5) – интервал на числовой оси
В = {-2, 0; 1; 2} – четырехэлементное множество
С = [–1; 1] - отрезок числовой оси
2. , где ℕ – множество всех натуральных чисел и kℕ
3.
4.
Вариант №13
1. А = (–∞; ∞) – интервал на числовой оси
В = [0; +∞) – полуинтервал на числовой оси
С = (–∞; 5) - интервал на числовой оси
2. , где ℕ– множество всех натуральных чисел и kℕ
3.
4.
Вариант №14
1. А=[–; 3) – полуинтервал на числовой оси
В=[3; 10] – отрезок числовой оси
С=(3; +) – интервал на числовой оси
2. {Аk}kℝ, где ℝ – множество всех вещественных чисел и k ℝ
3. (A B) \ C=(A \ C) (B \ C)
(A B) (C D) (A C) (B D)
4. (A (A \ B)) =
Вариант № 15
1. А=[–11; 1] –отрезок числовой оси
В=[–1; 3) – полуинтервал на числовой оси
С=(-2; 2) – интервал на числовой оси
2. {Аk}kℝ, где ℝ – множество всех вещественных чисел и k ℝ
3. A \ (B C) = (A \ B) (A \ C); (A \ B) C = (A C) \ (B C)
4. ((A C) (B D))
Вариант №16
1. А = (–0; 1) –интервал на числовой оси
В = {–1; 0; 1} – трехэлементное множество
С = [5; 10] – отрезок числовой оси
2. {Аk}kℝ, где ℝ – множество всех вещественных чисел и k ℝ
3.
4.
Вариант №17
1. А=(-1; 0] – полуинтервал на числовой оси
В=(0; 1) – интервал на числовой оси
С={-5;- 1; 1} – трехэлементное множество
2. {Аk}k ℝ, где ℝ – множество всех вещественных чисел и k ℝ
3.
4.
Вариант №18
1. А= {–1; 0; 1} – трехэлементное множество
В=(–1; 0.5) – интервал на числовой оси
С=[0; 1] – отрезок числовой оси
2. {Аk}kℝ, где ℝ – множество всех вещественных чисел и k ℝ
Ak = {xℝ : x2 ≥ k2 + 1 }
3.
4.
Вариант №19
1. А= [–6; +6) – полуинтервал на числовой оси
В=[–10; 2] –отрезок на числовой оси
С={-1} – одноэлементное множнство
2. {Аk}kℝ, где ℝ – множество всех вещественных чисел и k ℝ
Ak = {xℝ: x2 +1< k2 }
3.
4.
Вариант № 20
1. А= (–1; 4) – интервал на числовой оси
В=[0; 1] – отрезок числовой оси
С=(-2; 0] – полуинтервал на числовой оси
2. {Аk}kℝ, где ℝ – множество всех вещественных чисел и k ℝ
Ak = { (x, y): |x| + |y| ≥ |k|, где x, y ℝ }
3.
4.
Практическая работа №2
Тема: Функции и отображения.
Задание №1
Даны отображения (числовые функции) ƒ и g. Найдите область определения и область значений отображений. Определите, являются ли они инъективными, сюрьективными или биективными в найденных областях. Найдите композицию ƒ ◦ g, g ◦ ƒ, обратные (слева и справа) отображения: ƒ–1, g-1, (ƒ ◦ g)-1, (g ◦ ƒ)-1. Для заданных множеств A, B ℝ найдите f(A), g(A), ƒ –1(B), g-1(B). Найдите также неподвижные точки отображений.
и , A = [0; 3] и B = [ 1; 0].
Решение: область определения отображения f – это множество таких значений х, для которых имеется вещественное число у такое, что у=f(x). И, так как для любого вещественного числа х найдется число у с указанным свойством, то пр1f = ℝ – множество всех вещественных чисел.
Аналогично, область определения отображения g: пр1g = ℝ.
Область значений отображения f – это множество всех образов элементов хпр1f. Тем самым, пр2f ={y ℝ.: y -1 }. А область значений отображения g – это множество всех вещественных чисел, т.е. пр2g = ℝ.
Отображение g является инъективным, поскольку для каждого упр2g, имеется ровно один х пр1g (или каждый образ имеет ровно один прообраз). Отображение f инъективным не является, т.к. для некоторых упр2f, имеется более одного прообраза, например: для у=0 прообразами будут х=1 и х=3.
Отображение g является сюрьективным, поскольку для каждого упр2g, имеется хотя бы один хпр1g (или каждый образ имеет хотя бы один прообраз). Отображение f также является сюрьективным, т.к. для каждого упр2f, имеется хотя бы один хпр1f такой, что у = f(x).
Так как g одновременно инъективно и сюрьективно, то оно является биективным отображением.
Найдем композицию отображений:
(f∘g)(x) = f(g(x)) = (g(x)–2)2–1 = (1–x–2)2 –1 = (–x–1)2 – 1=(x+1)2–1,
(g∘f)(x) = g(f(x)) =1– f(x) = 1 – (x–2)2 +1 = 2 – (x–2)2.
Отображение f обратимо справа, как сюрьекция. И , где y –1. Из выражения найдем x. Тогда и , где y –1.
При этом, (f∘f 1)(у) = f(f 1(y))= – тождественное отображение при y 1.
Отображение g обратимо как слева, так и справа, как биекция. И , где y любое. Из выражения следует: . И при этом: (g∘g 1 )(у) = g(g 1(y)) = 1 – ( 1– y ) = y и (g 1∘g )(х) = – тождественные отображения.
По свойствам композиции
f(A) = { y = f(x), где xA }, поэтому f(A)=[–1; 3].
Аналогично, g(A) = { y = g(x), где xA } = [–2; 1].
Найдем неподвижные точки. По определению это такие х, что: f(x)=x и g(x)=x. Таким образом, x = (x–2)2–1. Отсюда x2–5x+3=0 и т. к. дискриминант D=25–12=13>0, то – две неподвижные точки f(x).
Из g(x)=x следует, что x=1–x и – неподвижная точка g(x).
Задание №2
Найти композицию соответствий S Г и множества B,C, если известно множество А={1,2,3,4}, законы R=2x+3 и G=y2, Г=(G,A,B), S=(R,B,C).
Решение:
По определению композиция это: S∘Г=(R∘G, А, С), в свою очередь, композиция законов это: R∘G={(x,z): yB и (x,y)G и (y,z)R}. Значит, для нахождения композиции графиков нужно в график R вместо переменной x подставить график G: RG=2y2+3. Для получения значений элементов множества В, нужно применить закон G к элементам множества А: В={12,22,32,42}={1,4,9,16}. Получение значений элементов множества С возможно двумя способами: первый – применить закон R к элементам множества В: С={2}={5, 11, 21, 35}; второй – применить композицию графиков ко множеству А.: C={}={5, 11, 21, 35}. Результаты двух способов совпадают. Все компоненты найдены и композиция соответствий будет иметь вид: SГ=(2y2+3, {1,2,3,4}, {5,11,21,35})
Задания для самостоятельного решения:
Задание №1
Даны отображения (числовые функции) ƒ и g. Найдите область определения и область значений отображений. Определите, являются ли они инъективными, сюрьективными или биективными в найденных областях. Найдите композицию (ƒ ◦ g), (g ◦ ƒ), обратные (слева и справа) отображения: ƒ–1, g-1, (ƒ ◦ g)-1, (g ◦ ƒ)-1. Для заданных множеств A, B ℝ найдите f(A), g(A), ƒ –1(B), g-1(B). Найдите также неподвижные точки отображений.
Задание №2
Найти композицию соответствий S Г и множества B,C.
Варианты заданий:
Вариант №1
1.
2.
Вариант №2
1.
2.
Вариант №3
1.
2.
Вариант №4
1.
2.
Вариант №5
1.
2.
Вариант №6
1.
2.
Вариант №7
1.
2.
Вариант №8.
2.
Вариант №9
1.
2.
Вариант №10
1.
2.
Вариант №11
1.
2.
Вариант №12
1.
2.
Вариант №13
1.
2.
Вариант №14
1.
2.
Вариант №15
1.
2.
Вариант №17
1.
2.
Вариант №18
1.
2.
Вариант №19
1.
2.
Вариант №20
1.
2.
Практическая работа №3
Тема: Отношения.
Задание №1
Даны множества и два бинарных отношения: и . Найдите Р1-1, Р2-1, Определите, является ли отношение Р2 рефлексивным, транзитивным, симметричным, антисимметричным.
P1={(a,1); (a,3); (b,2); (c,1); (c,4)}
P2={(1,1); (1,3); (2,2); (2,1); (2,4); (3,3); (4,1); (4,4)}
Решение: По определению обратное отношение . Таким образом, Р1-1={(1,a); (3,a); (2,b); (1,c); (4,c)} и P2-1={(1,1); (3,1); (2,2); (1,2); (4,2); (3,3); (4,4); (1,4)}.
По определению композиции бинарных отношений
Таким образом, ={(a,1); (a,3); (b,2); (b,1); (b,4); (c,1); (c,3); (c,4)}.
Тогда -1={(1,a); (3,a); (2,b); (1,b); (4,b); (1,c); (3,c); (4,c)}.
={(1,a); (1,c); (3,a); (3,c); (2,b); (1,b); (4,b); (4,c)}
Последние два множества совпадают, что и должно быть по свойствам композиции.
Отношение Р2 рефлексивно, т. к. в соответствии с определением рефлексивности .
Отношение Р2 не является транзитивным, поскольку по определению транзитивности требуется, чтобы для любых пар (x, y) и (y, z), таких что (x, y) следовало бы, чтобы пара . Однако это не так. Например, пары (2,1) и (1,3) Р2, но пара (2,3) Р2.
Отношение Р2 не является симметричным, т. к. по определению симметричности для любой пары (x, y) Р2 должно быть и (y, x) Р2 . Однако это не так. Например, пара (1,3) Р2 , но пара (3,1) Р2.
Отношение Р2 антисимметрично, поскольку для любой пары (x, y) Р2 такой, что (y, x) Р2 обязательно следует, что x=y.
Задание №2
Дано бинарное отношение P ℕ2 и P = { (x, y): x mod y = 2 }, где «mod» – операция нахождения остатка от деления x на y.
Найдите область определения и область значений отношения Р. Является ли отношение Р рефлексивным, транзитивным, симметричным, антисимметричным? Является ли оно отношением эквивалентности или упорядоченности?
Решение: областью значений отношения Р является множество таких натуральных чисел y, что в остатке от деления на y может быть получено значение 2. В качестве такого делителя y можно взять любое натуральное число >2. Таким образом, пр2 Р = { y ℕ: y 3 } – область значений.
Область определения отношения Р – это множество тех натуральных чисел x, для которых может быть получен остаток, равный 2, при делении на y 3. Выразим x через y: x=k.y+2, где k=0,1,2,… и y 3. Отсюда возможными значениями x являются числа: 2, 5, 6, 7, 8,… Таким образом, пр1 Р={2,5,6,7,8,9,…}=ℕ \ {1,3,4} – область определения.
Отношение Р не является рефлексивным, т. к. для всех x ℕ (x, x) P. Действительно, x ℕ x mod x = 0.
Отношение Р не является транзитивным, т. к. существуют такие пары (x, y)P и (y, z)P, но (x, z)P. Например, пары (7,5) и (5,3) обе Р, но пара (7,3)Р, т. к. 7 mod 3 = 1.
Отношение Р не является симметричным, поскольку существуют такие пары, что (x, y)P , но (х, у)Р . Например , пара (7,5)Р , но (5,7)Р, т.к. 5 mod 7=5.
По определению антисимметричности для всех таких пар (х, у), что (у, х)Р и (х, у)Р обязательно следует, что х=у. Но для заданного отношения Р не существует пар (х, у) таких, что (х, у)P и (у, х)Р, поскольку равенство (х mod y = y mod x =2) не выполняется ни при каких х, уℕ. Поэтому данное отношение Р является антисимметричным.
По набору свойств отношение Р не является ни отношением эквивалентности, ни отношением упорядоченности.
Задания для самостоятельного решения
Задание №1
Даны множества и два бинарных отношения: и . Изобразите Р1, Р2 графически. Найдите Р1-1, Р2-1, Определите, является ли отношение Р2 рефлексивным, транзитивным, симметричным, антисимметричным.
Задание №2
Найдите область определения и область значений отношения Р. Является ли отношение Р рефлексивным, транзитивным, симметричным, антисимметричным? Является ли оно отношением эквивалентности или упорядоченности?
Варианты заданий:
Вариант №1
1. Р1 = {(а, 2); (а, 3); (а, 4); (b, 3); (с, 1); (с, 4)}
Р2 = {(1, 1); (2, 3); (2, 2); (3, 4); (1, 4); (2, 4); (4, 2)}
Вариант №2
1. Р1 = {(b, 2); (а, 3); (b, 1); (b, 4); (с, 1); (с, 2); (с, 4)}
Р2 = {(1, 1); (1, 2); (1, 4); (2, 2); (2, 4); (3, 3); (3, 2); (3, 4); (4, 4)}
Вариант №3
1. Р1 = {(а, 3); (а, 2); (а, 4); (b 1); (с, 2); (с, 4); (с, 3)}
Р2 = {(1, 1); (2, 2); (2, 1); (3, 3); (4, 4); (4, 3); (1, 4); (2, 4); (3, 2); (3, 4)}
Вариант №4
1. Р1 = {(b, 1); (а, 3); (а, 4); (с, 2); (с, 4); (b, 4)}
Р2 = {(1, 1); (2, 3); (2, 2); (2, 4); (3, 3); (3, 4); (4, 2); (4, 4)}
2. P ℝ2 и Р = {(x, y) : x2 + x = y2 + y, где x, y Îℝ– вещественные числа }
3. P ℝ2 и Р = {(x, y) : x = y-4, где x, y Îℝ– вещественные числа }
Вариант №5
1. Р1 = {(а, 2); (а, 4); (b, 1); (b, 2); (b, 4); (с, 2); (с, 4)}
Р2 = {(1, 1); (2, 2); (2, 4); (3, 3); (4, 4); (3, 2); (1, 3); (4, 1)}
2. P Í ℝ2 и Р = {(x, y) : x – y ℤ, где x, y Îℝ– вещественные числа }
3. P ℝ2 и Р = {(x, y) : x2 + x = y2 , где x, y Îℝ– вещественные числа }
Вариант №6
1. Р1 = {(а, 2); (а, 4); (а, 3); (с, 1); (с, 2); (с, 3)}
Р2 = {(1, 1); (1, 4); (2, 3); (3, 3); (4, 1); (4, 3); (4, 4)}
2. P Í ℝ2 и Р = {(x, y) : x + y = –2, где x, y Îℝ– вещественные числа }
3. P ℝ2 и Р = {(x, y) : - x = 2 y, где x, y Îℝ– вещественные числа }
Вариант №7
1. Р1 = {(а, 1); (b, 2); (b, 3); (с, 1); (с, 3); (с, 4)}
Р2 = {(1, 1); (1, 2); (1, 3); (2, 2); (2, 3); (3, 3); (3, 4); (4, 1); (4, 4)}
3. P Í ℝ2 и Р = {(x, y) : x -2 y = 4, где x, y Îℝ– вещественные числа }
Вариант №8
1. Р1 = {(а, 3); (b, 4); (b, 3); (с, 1); (с, 2); (с, 4)}
Р2 = {(1, 2); (1, 3); (1, 4); (2, 3); (4, 3); (4, 2)}
2. P Í ℝ2 , P = {(x, y): y < x –1 и x, y Îℝ – вещественные числа }
3. P Í ℝ2 и Р = {(x, y) : x + y <2, где x, y Îℝ– вещественные числа }
Вариант№9
1. Р1 = {(а, 3); (b, 4); (b, 3); (b, 1); (b, 2); (c, 2)}
Р2 = {(1, 1); (1, 3); (2, 4); (3, 1); (3, 3); (4, 2)}
2. P Í ℝ2 , P = {(x, y): x2 = y, где x, y Îℝ – вещественные числа }
3. P ℝ2 и Р = {(x, y) : 2x2 = y2 , где x, y Îℝ– вещественные числа }
Вариант №10
1. Р1 = {(а, 2); (а, 3); (a, 4); (b, 1); (b, 2); (b, 4)}
Р2 = {(1, 1); (1, 3); (1, 4); (2, 2); (2, 3); (3, 2); (3,3); (4,3); (4,4)}
2. P Í ℝ2 , P = {(x, y): x2 y, где x, y Îℝ – вещественные числа }
3. Р ℝ2 и Р = {(x, y) : 2x2 + y2 = 3, где x, y ℝ– вещественные числа }
Вариант №11
1. Р1 = {(а, 1); (а, 2); (b, 3); (b, 4); (c, 3); (c, 4)}
Р2 = {(1, 1); (1, 4); (2, 1); (2, 2); (2, 4); (3, 3)}
2. P ℤ2 , P = {(x, y): x2 + y2 = 1, где x, yℤ – целые числа }
3. Р ℝ2 и Р = {(x, y) : x + y<- 1, где x, y ℝ– вещественные числа }
Вариант №12
1. Р1 = {(а, 2); (а, 3); (а, 4); (с, 3); (c, 1); (c, 4)}
Р2 = {(1, 4); (2, 3); (2, 1); (3, 4); (4, 2)}
2. Pℤ2, P = {(x, y): x + y – кратно 3, где x, yℤ – целые числа}
3. Р ℝ2 и Р = {(x, y) : x + y<-4, где x, y ℝ– вещественные числа }
Вариант №13
1. Р1 = {(а, 1); (а, 2); (а, 4); (b, 2); (b, 4); (c, 3)}
Р2 = {(1, 1); (2, 2); (2, 4); (3, 3); (4, 4);(4,2)}
2. Pℤ2, P = {(x, y): x – y, кратно 2, где х, уℤ – целые числа}
3. Р ℝ2 и Р = {(x, y) : x/2 =y, где x, y ℝ– вещественные числа }
Вариант №14
1. Р1 = {(b, 1); (b, 3); (c, 1); (c, 2); (c, 3); (c, 4)}
Р2 = {(1, 1); (2, 2); (2, 3); (2, 4); (3, 2); (3, 3); (3, 4); (4, 2); (4, 3); (4, 4)}
2. Pℤ2 , P = {(x, y): 2x = 3y, где x, yℤ – целые числа }
3. Р ℝ2 и Р = {(x, y) : 2x<y+1, где x, y ℝ– вещественные числа }
Вариант №15
1. Р1 = {(a, 2); (a, 4); (b, 3); (c, 1); (c, 2)}
Р2 = {(1, 1); (1, 3); (2, 4); (3, 1); (3, 4); (4, 3); (4, 2)}
2. Pℤ2, P = {(x, y): x + y нечетно, где x, yℤ – целые числа }
3. Р ℝ2 и Р = {(x, y) : x3<y+3, где x, y ℝ– вещественные числа }
Вариант №16
1. Р1 = {(а, 3); (а, 2); (b, 2); (b, 3); (c, 1); (c, 4)}
Р2 = {(1, 1); (1, 2); (2, 2); (3, 3); (4, 1); (4, 4)}
2. Pℤ2, P = {(x, y): x – y четно, где x, yℤ – целые числа }
3. Р ℝ2 и Р = {(x, y) : 1/x>y, где x, y ℝ– вещественные числа }
Вариант №17
1. Р1 = {(а, 1); (а, 2); (а, 4); (b, 3); (c, 1); (c, 4)}
Р2 = {(1, 3); (1, 2); (2, 3); (3, 2); (3, 4); (4, 1)}
2. Pℤ2, P = {(x, y): 5x = 2y, где x, yℤ – целые числа }
3. Р ℝ2 и Р = {(x, y) : x+2y=6, где x, y ℝ– вещественные числа }
Вариант№18
1. P1={ (a, 1); (b, 3); (c; 1); (c, 4); (c, 3); (c, 2)}
P2={(1, 1); (1, 2); (1, 4); (2, 1); (2, 2); (2, 3); (3, 3); (3, 2); (3, 4); (4, 3); (4, 4); (4, 1)}
3. Р ℝ2 и Р = {(x, y) : x +2 y<=-4, где x, y ℝ– вещественные числа }
Вариант №19
1. P1={(a, 1); (b, 3); (b, 1); (b, 4); (c, 3); (c, 2)}
P2={(1, 3); (1, 4); (2, 2); (3, 3); (4, 3); (4, 4);}
3. Р ℝ2 и Р = {(x, y) : x=>y, где x, y ℝ– вещественные числа }
Вариант №20
1. P1={(a, 1); (a, 2); (a; 4); (b, 1); (b, 4); (c, 3)}
P2={(1, 1); (2, 4); (2, 1); (3, 3); (4, 2); (4, 1)}
2. Pℤ2, P = {(x, y): y ≥ x – 2, где x, yℤ – целые числа }
3. Р ℝ2 и Р = {(x, y) : x<1/y, где x, y ℝ– вещественные числа }
Практическая работа №4.
Тема: Переключательные функции. Способы задания.
Задание №1.
Для f(x,y,z) заданной следующей таблицей истинности удалить несущественную переменную.
Решение:
|
x |
y |
z |
f(x,y,z) |
|
|
0 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
|
|
|
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
1 |
|
|
|
1 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
Проверим, является ли переменная х существенной. Для этого рассмотрим наборы на которых значения переменных y и z остаются неизменными, а значение переменной х меняется. На наборе (0,0,0) значение функции равно 1, на наборе (1,0,0) значение функции равно 0. Т.е. при неизменных y и z значение функции меняется, если меняется значение х. Значит, переменная х является существенной и её удалять нельзя. Проверим, является ли переменная у существенной. Рассмотрим наборы на которых х и z не меняется, а меняется только у. На наборе (0,0,0) значение функции равно 1, и на наборе (0, 1, 0) значение функции также равно 1. Проверяя все остальные наборы видно, что значение функции не меняется с изменением переменной у, т.е. у несущественная переменная и её можно удалить. Таким же способом проверяется существенность переменной z. По наборам (1,0,0) и (1,0,1) видно, что z существенная переменная. Получается, что у данной функции есть одна несущественная переменная у. Для её удаления необходимо вычеркнуть столбец значений переменной у и строчки в которых эта переменная равна 1. Полученная функция будет эквивалентна исходной и будет зависеть от двух переменных.
Задание №2
Проверьте двумя способами, будут ли эквивалентны следующие формулы: . а) составлением таблиц истинности; б) с помощью эквивалентных преобразований.
Решение: а) составим сокращенные таблицы истинности обеих формул:
|
x |
(y |
z) |
(x |
y) |
(x |
z) |
|||||
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Поскольку полученные столбцы не совпадают, формулы не эквивалентны.
б)
Преобразуем формулы к виду СДНФ. Для этого воспользуемся тождествами: и , где a и b – произвольные формулы. Тогда (по закону де Моргана) = (по закону дистрибутивности) = .
.
Формулы (*) и (**) не совпадают, поэтому исходные формулы не эквивалентны.
Задания для самостоятельного решения
Задание №1
Для f(x,y,z) равной единице на указанных наборах удалить несущественные переменные.
Задание №2
Проверьте двумя способами а) составлением таблиц истинности; б) с помощью эквивалентных преобразований, будут ли эквивалентны формулы.
Варианты заданий:
Вариант №1
Вариант №2
Вариант №3
Вариант №4
Вариант №5
Вариант №6
Вариант №7
Вариант №8
Вариант №9
Вариант №10
Вариант №11
Вариант №12
Вариант №13
Вариант №14
Вариант №15
Вариант №16
Вариант №17
Вариант №18
Вариант №19
Вариант №20
Практическая работа №5.
Тема: Специальные разложения ПФ.
Задание №1.
Для функции, заданной своими истинностными значениями, запишите: СДНФ, СКНФ и СПНФ.
f(x, y, z) = ( 1, 0, 1, 0, 0, 1, 1, 0 )
Решение: СКНФ строится по нулевым наборам, СДНФ – по единичным наборам, а СПНФ может быть получена из СДНФ путем замены «» на «» и «» на «x1». См. таблицу .
Таблица
|
x |
y |
z |
f(x,y,z) |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
0 |
СКНФ(f(x,y,z))=.
СДНФ(f(x,y,z))=.
Используем тождество: aa=0.
СПНФ(f(x,y,z))=(x1)(y1)(z1) (x1)y(z1) x(y1)z xy(z1)= (xyzxyxzxyzyz1) (xyzxyyzy) (xyzxz) (xyzxy) = xzzx1.
Задание №2
С помощью эквивалентных преобразований приведите формулу к виду ДНФ, КНФ, СДНФ, СКНФ.
Решение: используем тождества:
Для компактности записи вместо «a&b» , будем писать «ab».
ДНФ=
КНФ=
Совершенную дизъюнктивную нормальную форму (СДНФ) получим из ДНФ. Для этого к первой элементарной конъюнкции добавим единичный множитель , а ко второй –.
СДНФ=
Совершенную конъюнктивную нормальную форму (СКНФ) получим из КНФ. Для этого к первой элементарной дизъюнкции добавим нулевое слагаемое , а ко второй – .
СКНФ=
СПНФ=xyz xy(z1) (x1)yz (x1)(y1)z x(y1)z = xyz xyz xy xyz yz xyz xz yz z xyz xz = xyzxyz
Задания для самостоятельного выполнения:
Задание №1
Для функции, заданной своими истинностными значениями, запишите: СДНФ, СКНФ и СПНФ.
Задание №2
С помощью эквивалентных преобразований приведите формулу к виду ДНФ, КНФ, СДНФ, СКНФ.
Варианты заданий:
Вариант №1
1. f(x,y,z)=(0,1,2,6,7,8,12,13,14)
2.
Вариант №2
1. f(x,y,z)=(4,6,8,9,11,12)
2.
Вариант №3
1. f(x,y,z)=(0,1,2,3,6,12)
2.
Вариант №4
1. f(x,y,z)=(0,6,10,14)
2.
Вариант №5
Вариант №6
Вариант №7
Вариант №8
Вариант №9
Вариант №10
Вариант №11
Вариант №12
Вариант №13
Вариант №14
Вариант №15
Вариант №16
Вариант №17
Вариант №18
Вариант №19
Вариант №20
Практическая работа №6.
Тема: Теорема о функциональной полноте.
Задание №1.
Определите к каким классам относится функция следующего вида:
(0, 1, 1, 0, 0, 1, 1, 1)
|
x |
y |
z |
f(x,y,z) |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
Решение:
Запишем значения функции в таблицу истинности.
Т.к. f(0,0,0)=1, то fT0 (класс функций, сохраняющих ноль).
Т.к. f(1,1,1)=1, то fT1 (класс функций, сохраняющих единицу).
Т.к. f*(x,y,z)=(0, 0, 0, 1, 1, 0, 0, 1)f(x,y,z), то fS (класс самодвойственных функций).
Рассмотрим наборы: (0,0,1) и (0,1,1). Заметим, что f() =1, f() =0.
Т.к. , но f()f(), то f M (класс монотонных функций).
Найдем полином Жегалкина (СПНФ):
f(x,y,z)= xyz y x.
Т.к. в СПНФ имеются нелинейные слагаемые, то f L (класс линейных функций).
Задание №2
Определите, является ли полной система функций? Образует ли она базис?
F={}.
Решение: построим таблицы истинности для функций системы F .
|
x |
y |
||
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
СПНФ () = (x1)(y1)=xy1
СПНФ () =
Оформим в виде принадлежность функций из F классам Поста:
|
T0 |
T1 |
S |
M |
L |
|
|
– |
– |
– |
– |
– |
|
|
- |
– |
+ |
– |
+ |
Т.к. в системе F имеются функции: не сохраняющая ноль, не сохраняющая единицу, не самодвойственная, немонотонная и нелинейная, то по теореме Поста о полноте система F является полной. В то же время базиса она не образует, т.к. из неё может быть удалена функция (), и при этом оставшаяся система будет полной.
Задания для самостоятельного выполнения:
Задание №1.
Определите к каким классам относится функция следующего вида:
Задание №2
Определите, является ли полной система функций? Образует ли она базис?
Варианты заданий:
Вариант №1
Вариант №2
Вариант №3
Вариант №4
Вариант №5
Вариант №6
Вариант №7
Вариант №8
Вариант №9
Вариант №10
Вариант №11
Вариант №12
Вариант №13
Вариант №14
Вариант №15
Вариант №16
Вариант №17
Вариант №18
Вариант №19
Вариант №20
Практическая работа №7
Тема: Минимизация ПФ и не полностью определённых ПФ.
Задание №1
Пусть дана функция от трех переменных f(x, y, z)=(0,1,1,1,1,1.1,0). Найти её МДНФ методом неопределённых коэффициентов.
Решение:
Построим таблицу истинности для данной функции. Она будет иметь следующий вид:
|
x |
y |
z |
f(x,y,z) |
|
|
0 |
0 |
0 |
0 |
В ДНФ общего вида такой функции будет |
|
0 |
0 |
1 |
1 |
26 неопределенных коэффициентов. Для обо- |
|
0 |
1 |
0 |
1 |
значения этих коэффициентов будем |
|
0 |
1 |
1 |
1 |
использовать букву К с нижним индексом, |
|
1 |
0 |
0 |
1 |
указывающим конъюнкцию, перед которой |
|
1 |
0 |
1 |
1 |
стоит этот коэффициент. С учетом всех |
|
1 |
1 |
0 |
1 |
принятых обозначений ДНФ общего вида |
|
1 |
1 |
1 |
0 |
запишется так: |
В каждом уравнении полученной системы имеется по два коэффициента, которые могут быть приравнены к 1. Отсюда вытекает неоднозначность решения задачи. Учитывая то, что в каждом уравнении следует выбрать лишь один коэффициент, получим следующие два решения:
Первое: kz =1; ky=1; kx=1;
Второе: kz =1; ky =1; kx=1;
Остальные коэффициенты в обоих случаях приравниваем к нулю.
МДНФ1 = z y x; и
МДНФ2 = z y x;
Задание№2
Пусть функция от трех переменных f(x, y, z) задана в виде f(x,y,z)=(1,0,0,0,1,0,1,1). Построить её СокрДНФ.
Решение:
Для нахождения СокрДНФ необходимо построить СДНФ. Для данной функции СДНФ будет иметь вид: f(x, y, z) = x x y x y z
Используя законы склеивания ( x A B = x A B AB - склеивание; или x A A = A - полное склеивание или x A A = x A A A - неполное склеивание)
выполним всевозможные склеивания, т.е. будем склеивать первую конъюнкцию со второй, третьей, четвертой, затем вторую с третьей и четвертой, и наконец, третью с четвертой.
Тогда f(x, y, z) = x x y x y z y
y z x xx z x y = x x y x y z
x x y
Теперь выполняя всевозможные поглощения (A AB = A - поглощение, где A и B - элементарные конъюнкции), получим:
f(x, y, z) = x x y
Поскольку преобразования больше невозможны, последняя формула является СокрДНФ.
Задания для самостоятельного решения:
Задание №1
Пусть дана функция от трех переменных f(x, y, z). Найти её МДНФ методом неопределённых коэффициентов.
Задание№2
Пусть дана функция от четырёх переменных f(x, y, z, w). Построить её СокрДНФ.
Варианты заданий:
Вариант №1
Вариант №2
Вариант №3
Вариант №4
Вариант №5
Вариант №6
Вариант №7
Вариант №8
Вариант №9
Вариант №10
Вариант №11
Вариант №12
Вариант №13
Вариант №14
Вариант №15
Вариант №16
Вариант №17
Вариант №18
Вариант №19
Вариант №20
Практическая работа №8
Тема: Минимизация ПФ и не полностью определённых ПФ методами, основанными на геометрическом представлении функций алгебры логики
Задание№1
Пусть функция имеет следующие значения: f(x, y, z)=(1, 0, 0, 1, 1, 0,1, 1). Найти МДНФ функции методом Куайна.
Решение:
Для данной функции запишем её СДНФ: .
Построим СокрДНФ:
|
xyz |
|||||
|
1 |
1 |
||||
|
yz |
1 |
1 |
|||
|
1 |
1 |
||||
|
xy |
1 |
1 |
Используя сокращённую и совершенную ДНФ построим таблицу Куайна. В верхней строке запишем дизъюнкты совершенной ДНФ, в левом столбце запишем дизъюнкты сокращённой ДНФ. В тех ячейках, где дизъюнктасокращённой ДНФ покрывает дизъюнкту совершенной ДНФ ставим 1. Ввиду наличия единственной единицы в столбцах 1 и 2, конъюнкции и yz являются ядровыми. Таким образом, единицы ядра находятся в столбцах: 1, 2, 3 и 5. Ни одна из единиц 4–го столбца не покрывается ядром. Тем самым, обе остальные конъюнкции входят в ДНФ Куайна, которая в данном случае совпадает с Сокращенной ДНФ. Для построения МДНФ достаточно иметь одну единицу в 4–ом столбце, это равносильно удалению из СокрДНФ любой из конъюнкций: или xy. При этом получаются две минимальные ДНФ: и .
Задание №2
Для функции заданной следующим образом f(x,y,z,w)=(1,1,1,1,0,1,0,0,1,0,0,1,1,0,1,1) построить МДНФ с помощью карт Карно.
|
z w |
|||||
|
00 |
01 |
11 |
10 |
||
|
00 |
1 |
1 |
1 |
1 |
|
|
x |
01 |
1 |
|||
|
y |
11 |
1 |
1 |
1 |
|
|
10 |
1 |
1 |
Рисунок 1
Решение:
Значения функции перечислены в порядке естественного увеличения наборов значений переменных, рассматриваемых как четырехразрядные двоичные числа.
Изобразим карту Карно для данной функции, проставляя в ней только единичные значения.
Разобьем единицы по группам, как показано на рисунке1. Тогда соответствующая этому разбиению
МДНФ1 =w x x z w x y z
|
z w |
|||||
|
00 |
01 |
11 |
10 |
||
|
00 |
1 |
1 |
1 |
1 |
|
|
x |
01 |
1 |
|||
|
y |
11 |
1 |
1 |
1 |
|
|
10 |
1 |
1 |
Рисунок 2
Очевидно, что ДНФ той же сложности будет получена, если разбить единицы на группы так, как показано на рис. 2
Соответствующая этому разбиению
МДНФ2 =w x z w x y z
|
z w |
|||||
|
00 |
01 |
11 |
10 |
||
|
00 |
1 |
1 |
1 |
1 |
|
|
x |
01 |
1 |
|||
|
y |
11 |
1 |
1 |
1 |
|
|
10 |
1 |
1 |
Рисунок 3
Для разбиения, показанного на рисунке 3, МДНФ имеет ту же сложность и равна:
МДНФ3 =w x x z w x y
|
z w |
|||||
|
00 |
01 |
11 |
10 |
||
|
00 |
1 |
1 |
1 |
1 |
|
|
x |
01 |
1 |
|||
|
y |
11 |
1 |
1 |
1 |
|
|
10 |
1 |
1 |
Рисунок 4
А для рисунка 4
МДНФ4 =w x z w x y
Другие варианты разбиения не приведут к более коротким ДНФ. Таким образом для данной функции получено четыре минимальных ДНФ.
Задания для самостоятельного решения:
Задание №1
Пусть дана функция от четырёх переменных f(x, y, z, w). Найти МДНФ функции методом Куайна.
Задание №2
Для функции от четырёх переменных f(x,y,z,w) построить МДНФ с помощью карт Карно.
Варианты заданий:
Вариант №1
Вариант №2
Вариант №3
Вариант №4
Вариант №5
Вариант №6
Вариант №7
Вариант №8
Вариант №9
Вариант №10
Вариант №11
Вариант №12
Вариант №13
Вариант №14
Вариант №15
Вариант №16
Вариант №17
Вариант №18
Вариант №19
Вариант №20
Практическая работа №9
Тема: Основные понятия теории графов.
Задание №1
Дан граф T:
Задать данный граф матрицей смежности и инцидентности.
Решение:
Матрица инцидентности – это прямоугольная матрица, число строк которой равно числу вершин, количество столбцов – числу дуг (рёбер) графа. На пересечении строки и столбца ставится 1, если вершина является началом дуги, -1 – если концом дуги, 0 – если вершина и дуга не инцидентны.
|
AB |
AG |
AF |
FE |
FG |
GB |
GM |
EG |
EM |
ED |
DC |
MC |
BC |
|
|
A |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
B |
-1 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
C |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
|
D |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
|
E |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
F |
0 |
0 |
-1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
G |
0 |
-1 |
0 |
0 |
-1 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
M |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
-1 |
0 |
0 |
1 |
0 |
Матрица смежности – это квадратная матрица, размер которой определяется числом вершин в графе. На пересечении строки и столбца ставится 1, если вершины инцидентны и 0 в противном случае.
|
A |
B |
C |
D |
E |
F |
G |
M |
|
|
A |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
B |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
C |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
D |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
E |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
F |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
G |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
|
M |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
Задание №2
Для данного графа (см. задание №1) вычислить хроматическое число h(T).
Решение:
E1={F, B, M, D}, E2={A, E, C}, E3={F, C}, E4={A, M, D}, E5={G, D}, E6={G, C},
E6={F, M}, E8={B, E}.
|
A |
B |
C |
D |
E |
F |
G |
M |
|
|
E1 |
1 |
1 |
1 |
1 |
||||
|
E2 |
1 |
1 |
1 |
|||||
|
E3 |
1 |
1 |
||||||
|
E4 |
1 |
1 |
1 |
|||||
|
E5 |
1 |
1 |
||||||
|
E6 |
1 |
1 |
||||||
|
E7 |
1 |
1 |
||||||
|
E8 |
1 |
1 |
Минимальное покрытие столбцов строками является множество {E1, E2, E5}. Следовательно, хроматическое число графа h(T)=3
Задания для самостоятельного решения:
Задание №1
Задать данный граф матрицами смежности и инцедентности.
Задание №2
Для данного графа (см. задание №1) вычислить хроматическое число h(T).
Варианты заданий:
|
Вариант №1 |
Вариант №2 |
|
Вариант №3 |
Вариант №4 |
|
Вариант №5 |
Вариант №6 |
|
Вариант №7 |
Вариант №8 |
|
Вариант №9 |
Вариант №10 |
|
Вариант №11 |
Вариант №12 |
|
Вариант №13 |
Вариант №14 |
|
Вариант №15 |
Вариант №16 |
|
Вариант №17 |
Вариант №18 |
|
Вариант №19 |
Вариант№20 |
Практическая работа №10
Тема: Маршруты, циклы, связность.
Задание №1
По заданной матрице смежности определить число маршрутов длины 3 между любой парой вершин в графе:
|
A |
B |
C |
D |
|
|
A |
0 |
1 |
0 |
1 |
|
B |
1 |
0 |
1 |
1 |
|
C |
0 |
1 |
0 |
0 |
|
D |
1 |
1 |
0 |
0 |
Восстановить маршрут из вершины С в вершину А.
Решение:
Вычислим последовательно степени матрицы S.
Из полученной матрицы S3 следует, что имеется два (A-A)-маршрута длины 3, четыре (B-A)-маршрута длины 3, один (C-A)-маршрут длины 3, три (D-A)-маршрута длины 3, т.е. число в (i, j) ячейке определяет количество маршрутов длины 3 из i-ой вершины в j-ую вершину.
Восстановим (C-A)-маршрут: элемент , равный единице, был получен в результате умножения элементов и , в свою очередь элемент получился путем умножения и . Тем самым, в формировании элемента участвовали элементы , и матрицы смежности, поэтому (C-A)-маршрут есть последовательность вершин (C, B, D, A).
Задание №2
По заданной матрице определить сильные компоненты связности графа:
|
A |
B |
C |
D |
E |
|
|
A |
0 |
1 |
1 |
0 |
0 |
|
B |
1 |
0 |
1 |
0 |
0 |
|
C |
1 |
1 |
0 |
1 |
0 |
|
D |
0 |
0 |
1 |
0 |
1 |
|
E |
0 |
0 |
0 |
1 |
0 |
Решение:
Максимальная степень, в которую надо возвести матрицу смежность для определения сильных компонент связности равна диаметру графа. Для данного графа диаметр равен 3. Возведём матрицу смежности в 3 степень:
Компоненте сильной связности в матрице достижимости соответствует подматрица максимального размера, каждый элемент которой не равен 0. В данной матрице можно выделить три подматрицы:, (2), (2).
Это значит, что граф, описанный матрицей смежности имеет три сильные компоненты: {A, B, C}, {D}, {E}.
Задания для самостоятельного решения:
Задание №1
По заданной матрице смежности определить число маршрутов длины 3 между любой парой вершин в графе.
Задание №2
По заданной матрице определить сильные компоненты связности графа
Варианты заданий:
|
Вариант №1 A B C D E A 0 1 1 0 0 B 1 0 0 1 0 C 1 0 0 1 0 D 0 1 1 0 1 E 0 0 0 1 0 |
Вариант №2 A B C D E A 0 1 0 1 1 B 1 0 1 0 0 C 0 1 0 0 1 D 1 0 0 0 0 E 1 0 1 0 0 |
|
Вариант №3 A B C D E A 0 0 1 0 1 B 0 0 1 1 1 C 1 1 0 0 0 D 0 1 0 0 0 E 1 1 1 0 0 |
Вариант №4 A B C D E A 0 1 1 0 0 B 1 0 1 0 1 C 1 1 0 1 0 D 0 0 1 0 0 E 0 1 0 0 0 |
|
Вариант №5 A B C D E A 0 0 1 0 0 B 0 0 0 1 1 C 1 0 0 0 0 D 0 1 0 0 0 E 0 1 0 0 0 |
Вариант №6 A B C D E A 0 1 1 0 0 B 1 0 1 1 0 C 1 1 0 1 0 D 0 1 1 0 0 E 0 0 0 0 0 |
|
Вариант №7 A B C D E A 0 1 0 0 0 B 1 0 1 0 0 C 0 1 0 0 0 D 0 0 0 0 1 E 0 0 0 1 0 |
Вариант №8 A B C D E A 0 1 0 0 0 B 1 0 1 0 1 C 0 1 0 0 0 D 0 0 0 0 1 E 0 1 0 1 0 |
|
Вариант №8 A B C D E A 0 1 0 0 1 B 1 0 1 1 1 C 0 1 0 1 0 D 0 1 1 0 0 E 1 1 0 0 0 |
Вариант №10 A B C D E A 0 0 0 0 1 B 0 0 0 1 1 C 0 0 0 1 0 D 0 1 1 0 0 E 1 1 0 0 0 |
|
Вариант №9 A B C D E A 0 1 0 0 0 B 1 0 1 1 1 C 0 1 0 0 0 D 0 1 0 0 0 E 0 1 0 0 0 |
Вариант №12 A B C D E A 0 1 0 0 0 B 1 0 0 0 0 C 0 1 0 0 0 D 0 1 0 0 1 E 0 1 0 1 0 |
|
Вариант №11 A B C D E A 0 1 0 0 1 B 1 0 1 1 1 C 0 1 0 1 0 D 0 1 1 0 1 E 1 1 0 1 0 |
Вариант №14 A B C D E A 0 1 0 0 1 B 1 0 1 0 0 C 0 1 0 1 0 D 0 0 1 0 1 E 1 0 0 1 0 |
|
Вариант №15 A B C D E A 0 0 1 0 0 B 0 0 1 1 0 C 1 1 0 0 1 D 0 1 0 0 0 E 0 0 1 0 0 |
Вариант №16 A B C D E A 0 1 1 1 1 B 1 0 0 0 1 C 1 0 0 1 0 D 1 0 1 0 0 E 1 1 0 0 0 |
|
Вариант №17 A B C D E A 0 0 0 0 1 B 0 0 0 1 0 C 0 0 0 1 1 D 0 1 1 0 0 E 1 0 1 0 0 |
Вариант №18 A B C D E A 0 0 0 1 0 B 0 0 0 1 1 C 0 0 0 0 1 D 1 1 0 0 1 E 0 1 1 1 0 |
|
Вариант №19 A B C D E A 0 0 0 0 0 B 0 0 1 0 1 C 0 1 0 0 1 D 0 0 0 0 0 E 0 1 1 0 0 |
Вариант №20 A B C D E A 0 0 0 1 0 B 0 0 1 0 1 C 0 1 0 0 0 D 1 0 0 0 1 E 0 1 0 1 0 |
PAGE 33
EMBED Equation.3
-1
0
1
-2
-1
0
1
2
-0.5
B
A
AB
-0.5
2
-2
C
A
AC
C
B
BC
A
B
C
AB
A
B
C
A
B
C
AC
A
B
C
1)
)
3)
4)
5)
A
B
C
BC
(AB)(BC)
(AB)(BC)(AC)
5)
A
B
C
(AB)(BC)(AC)
1)
A
B
C
AB
2)
A
B
C
BC
3)
A
B
C
AC
4)
A
B
C
(AB)(BC)
D
C
B
A
F
E
D
C
A
B
E
D
C
A
C
E
D
B
A
F
E
D
C
B
A
E
D
C
B
A
E
D
C
B
A
1
2
1
2
3
C
М
G
F
E
D
C
B
А
A
B
D
C
B
A
E
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
F
F
E
A
B
C
D
A
B
C
D
E
A
B
C
D
E
C
A
B
D
E
A
B
C
D
E
C
A
B
D
A
B
C
D
E
F