Множества и их спецификация

Работа добавлена на сайт samzan.net:

Оглавление:

1.  Множества и их спецификация……………………………………………………3
2.  Функции и отображения…………………………………………………………...12
3.  Отношения………………………………………………………………………….20
4.  Переключательные функции. Способы задания…………………………………25
5.  Специальные разложения ПФ……………………………………………………..29
6.  Теорема о функциональной полноте………………………………………………32
7.  Минимизация ПФ и неполностью определённых ПФ……………………………36
8.  Минимизация ПФ и неполностью определённых ПФ методами, основанными   на геометрическом представлении функций алгебры логики……………………40
9.  Основные понятия теории графов………………………………………………….44
10.  Маршруты, циклы, связность………………………………………………………49

Практическая работа №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∘g1 )(у) = g(g1(y)) = 1 – ( 1– y ) = y и (g1∘g )(х) = – тождественные отображения.

По свойствам композиции

f(A) = { y = f(x), где xA }, поэтому f(A)=[–1; 3].

Аналогично, g(A) = { y = g(x), где xA } = [–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): yB и (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.

•  f=cos(x),  g=cos(x)-0.5,  A=[-,],  B=(-]
•  f=(x-1)/3,  g=y3,  A=[-1,2],  B=(1,3]
•  f=x-3,  g=(y+1)2,  A=[1,12],  B=(-4,0)

2.

•  A={-2,-4,2,4}, R=x2-1, G=y+2
•  A=, R=x/2, G=y2/2

Вариант №2

1.

•  f=sin(x)/2,  g=2cos(x),  A=[-,],  B=(-]
•  f=2(x-1),  g=(y+2)/2,  A=[1,4],  B=[11,0]
•  f=x,  g=3y2,  A=(0,1],  B=[-1,1)

2.

•  A={0,0.1,0.2,0.3,0.4}, R=0.25x-0.75,G=y2
•  A=, R=x0.5, G=y2

Вариант №3

1.

•  f=2sin(x),  g=1+cos(x),  A=[-,],  B=(-]
•  f=x,  g=(y2+2)/2,  A=[-1,1],  B=[5,8]
•  f=+x,  g=y-2,  A=[-1,1],  B=(-1,1)

2.

•  A={0,1,2,3,4}, R=x+1, G=(y+1)2
•  A=, R=x0.5, G=y2

Вариант №4

1.

•  f=sin(x)/3,  g=cos(x/3),  A=[-,],  B=[-]
•  f=x3-x,  g=1-,  A=(-1,4),  B=[-3,6]
•  f=2x,  g=y2/3,  A=(-5,1),  B=[0,-1)

2.

•  A={1,3,5,7}, R=x-3,G=(y+5)/3
•  A=, R=x+1, G=2y2

Вариант №5

1.

•  f=sin(x/2),  g=2cos(2x),  A=[0,),  B=(-)
•  f=,  g=y,  A=[-2,4],  B=(1,10)
•  f=-x2,  g=1/y2,  A=(0,1],  B=[-1,1)

2.

•  A={-4,-3,-2,-1}, R=(x-1)2,G=y+1
•  A=, R=2x G=y2/2

Вариант №6

1.

•  f=sin2(x)  g=2cos(x),  A=[-,],  B=(-2]
•  f=x2+1,  g=(y+2)/(2-y),  A=[-2,2],  B=[-6,0)
•  f=2x/(1-x2),  g=y+3,  A=[0,1],  B=(-2,0)

2.

•  A={1/3,1/9,1/12,1/15}, R=3x, G=y2
•  A=, R=1/(x+2), G=y/(1-y)

Вариант №7

1.

•  f=sin(x)/2+sin2x,  g=cos(x),  A=[,],  B=(-]
•  f=1-x2/2,  g=y+2,  A=(0,4),  B=[-3,3]
•  f=,  g=y/3,  A=(0,1],  B=[-1,1)

2.

•  A={3,5,9,10}, R=2x, G=1/y;
•  A=, R=x+4, G=y/(y+1)

Вариант №8.

•  f=sin(x)/2,  g=2cos(x),  A=[-,],  B=(-]
•  f=2(x-1),  g=(y+2)/2,  A=[1,4],  B=[-11,0]
•  f=x,  g=3y2,  A=(0,1],  B=[-1,1)

2.

•  A={0,0.1,0.2,0.3,0.4}, R=0.25x-0.75,G=y2
•  A=, R=x0.5, G=y2

Вариант №9

1.

•  f=sin(x)-1,  g=(2cos(x))/3,  A=[-,],  B=(-]
•  f=x+х2,  g=5y+2,  A=[-3,3],  B=[-4,0]
•  f=x/3+1,  g=(y+1)2,  A=(-3,-1),  B=(-1,1)

2.

•  A={-21, -14, -7, 0, 7, 14, 21}, R=x/7,G=y+7
•  A=, R=x+1, G=y/2

Вариант №10

1.

•  f=х/2+sin(x),  g=cos(x)+cos(x/3),  A=[,],  B=(-]
•  f=2x-х/4,  g=y+у2,  A=(-2,2),  B=[1,10]
•  f=(x+4)/3,  g=y2/2,  A=(0,1],  B=[1,2)

2.

•  A={-1, 1, -2, 2, -3, 3}, R=x, G=y2
•  A=, R=2x, G=3y

Вариант №11

1.

•  f=sin(x)-2tg(x),  g=cos(x)-cos(2)/2,  A=[,],  B=(-]
•  f=(3/x)+(x/3),  g=y-y2,  A=[-3,3],  B=[6,9]
•  f=2+x,  g=3y-1,  A=(-2,1),  B=(4,1)

2.

•  A={0,5,10,15,20}, R=x-5, G=y/5
•  A=, R=2x, G=y+2

Вариант №12

1.

•  f=tg(3x),  g=sin(x)+1,  A=[-,],  B=(-)
•  f=2x-1,  g=1/(y+1),  A=(0,2),  B=[-3,2]
•  f=x-4,  g=3y/2,  A=(1,1],  B=(-4,4)

2.

•  A={-1,-3,-5,-7,-9}, R=x+1,G=y/2
•  A=, R=x/3, G=y2

Вариант №13

1.

•  f=3sin(x),  g=sin(x/3),  A=[-,],  B=(-]
•  f=3/(x-2),  g=y2+3,  A=[-1,0],  B=(2,12)
•  f=x3,  g=y-7,  A=(-8,8],  B=[1,7]

2.

•  A={-8, 8, 15, 22, 29}, R=x-1,G=y/7
•  A=, R=3x-2, G=2y2

Вариант №14

1.

•  f=cos(x),  g=tg(x)-1,  A=[-),  B=[]
•  f=1/x,  g=y+4,  A=[3,7],  B=[-7,2]
•  f=x4,  g=2y-2,  A=[-10,1],  B=[0,5)

2.

•  A={5, 3, 6, 4, 2}, R=2x-1,G=y+4
•  A=, R=x+2, G=y/3

Вариант №15

1.

•  f=(sin(x))/3,  g=3cos(x),  A=[-],  B=(]
•  f=x2-3,  g=(y+2)2,  A=[2,5],  B=(-3,-1)
•  f=6x-1,  g=4-y2,  A=(-4,4],  B=[2,8)

2.

•  A={1/3, 1/6, 1/9, 1/12}, R=(3x)2, G=y-3
•  A=, R=4x, G=y2-2

Вариант №17

1.

•  f=sin(x)/2,  g=2cos(x),  A=[-,],  B=(-]
•  f=2(x-1),  g=(y+2)/2,  A=[1,4],  B=[11,0]
•  f=x,  g=3y2,  A=(0,1],  B=[-1,1)

2.

•  A={0,0.1,0.2,0.3,0.4}, R=0.25x-0.75,G=y2
•  A=, R=x0.5, G=y2

Вариант №18

1.

•  f=sin(x)+cos(x),  g=tg(x)/3,  A=[-,],  B=()
•  f=x2,  g=,  A=[1,4],  B=[3,9]
•  f=2+x,  g=y2/3,  A=[-4,4),  B=[-2,2]

2.

•  A={1/2, 1/3, 1/4, 1/5}, R=3x, G=y+3
•  A=, R=2x, G=y/2

Вариант №19

1.

•  f=sin(x),  g=2ctg(x),  A=[,],  B=(-)
•  f=(x/3)+(x/5),  g=4y,  A=(-1,4],  B=[0,9]
•  f=x+1,  g=y2+4,  A=(-6,6],  B=[-5,1)

2.

•  A={-5, 5, -6, 6, -7, -8, 8}, R=x+4, G=y2
•  A=, R=x-5, G=y/3

Вариант №20

1.

•  f=tg(x)/2,  g=2cos(x),  A=[-,],  B=(-]
•  f=x,  g=y,  A=[-1,1],  B=(-3,3)
•  f=2x/(x+3),  g=y/3,  A=(3,4],  B=[-2,5)

2.

•  A={-1, -2,-3,-5,-7,-11, -13}, R=4x,G=y/2
•  A=, R=(x-1)2, G=y

Практическая работа №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)}

1.  P  ℝ 2 и Р = {(x, y) : x · y > 1, где x, y  ℝ – вещественные числа }
2.  P  ℝ 2 и Р = {(x, y) : 3x- y < -1, где x, y  ℝ – вещественные числа }

Вариант №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)}

1.  Р ℝ2  и Р = {(x, y) : x2 + y2 = 1, где x, y ℝ– вещественные числа }
2.  Р ℝ2  и Р = {(x, y) : -2xy = 1, где x, y ℝ– вещественные числа }

Вариант №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)}

1.  P  ℝ2  и Р = {(x, y) : y = |x|, где x, y ℝ– вещественные числа }
2.  P  ℝ2  и Р = {(x, y) :x-2 y = x+2y, где x, y ℝ– вещественные числа }

Вариант №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)}

1.  P Í ℝ2 и  P = {(x, y): x2 + y2 = 4,  x, y Îℝ – вещественные числа }

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)}

1.  Pℤ2,  P = {(x, y): x = –y, где x, yℤ – целые числа }

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);}

1.  Pℤ2,  P = {(x, y): x +1 = y, где x, y ℤ – целые числа }

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

1.  f(x,y,z)=(0,5,8,9,10,12,13,15)
2.  

Вариант №2

1.  f(x,y,z)=(0,8,,9,10,12,13,15)
2.  

Вариант №3

1.  f(x,y,z)=(1,2,3,12,13,14,15)
2.  

Вариант №4

1.  f(x,y,z)=(2,3,7,8,10,11,12,15)
2.  

Вариант №5

1.  f(x,y,z)=(0,4,6,7,8,10,13,15)
2.  

Вариант №6

1.  f(x,y,z)=(0,4,5,7,8,10,11,13,15)
2.  

Вариант №7

1.  f(x,y,z)=(0,4,5,6,7,14,15)
2.  

Вариант №8

1.  f(x,y,z)=(2,4,7,9,10,14,15)
2.  

Вариант №9

1.  f(x,y,z)(0,3,7,8,9,10,11,12,15)
2.  

Вариант №10

1.  f(x,y,z)=(0,2,4,7,8,10,13,15)
2.  

Вариант №11

1.  f(x,y,z)=(0,2,4,7,8,10,13,15)
2.  

Вариант №12

1.  f(x,y,z)=0,3,6,8,9,12,13,15)
2.  

Вариант №13

1.  f(x,y,z)=(2,4,7,9,10,11,13,15)
2.  

Вариант №14

1.  f(x,y,z)=(2,3,4,5,9,10,11,15)
2.  

Вариант №15

1.  f(x,y,z)=(5,7,8,9,10,11,15)
2.  

Вариант №16

1.  f(x,y,z)=(2,3,4,9,10,11,14,15)
2.  

Вариант №17

1.  f(x,y,z)=(0,2,4,8,12,14,15)
2.  

Вариант №18

1.  f(x,y,z)=(2,3,4,6,8,9,11,12)
2.  

Вариант №19

1.  f(x,y,z)=(5,6,7,8,9,10,11,12,13)
2.  

Вариант №20

1.  f(x,y,z)=(3,5,7,10,11,12,13,14)
2.  

Практическая работа №5.

Тема: Специальные разложения ПФ.

Задание №1.

Для функции, заданной своими истинностными значениями, запишите: СДНФ, СКНФ и СПНФ.

f(x, y, z) = ( 1, 0, 1, 0, 0, 1, 1, 0 )

Решение: СКНФ строится по нулевым наборам, СДНФ – по единичным наборам, а СПНФ может быть получена из СДНФ путем замены «»  на «» и «» на «x1». См. таблицу .

Таблица

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))=.

Используем тождество: aa=0.

СПНФ(f(x,y,z))=(x1)(y1)(z1)  (x1)y(z1)  x(y1)z  xy(z1)= (xyzxyxzxyzyz1)  (xyzxyyzy)  (xyzxz)  (xyzxy) = xzzx1.

Задание №2

С помощью эквивалентных преобразований приведите формулу к виду ДНФ, КНФ, СДНФ, СКНФ.

Решение: используем тождества:

Для компактности записи вместо «a&b» , будем писать «ab».

ДНФ=

КНФ=

Совершенную дизъюнктивную нормальную форму (СДНФ) получим из ДНФ. Для этого к первой элементарной конъюнкции добавим единичный множитель , а ко второй –.

СДНФ=

Совершенную конъюнктивную нормальную форму (СКНФ) получим из КНФ. Для этого к первой элементарной дизъюнкции добавим нулевое слагаемое , а ко второй – .

СКНФ=

СПНФ=xyz  xy(z1)  (x1)yz  (x1)(y1)z  x(y1)z = xyz  xyz  xy  xyz  yz  xyz  xz  yz  z  xyz  xz = xyzxyz

Задания для самостоятельного выполнения:

Задание №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

1.  f(x,y,z)=(3,4,7)
2.  

Вариант №6

1.  f(x,y,z)=(0, 1, 2, 3, 4)
2.  

Вариант №7

1.  f(x,y,z)=(1, 2, 5, ,7)
2.  

Вариант №8

1.  f(x,y,z)=(1, 2, 4)
2.  

Вариант №9

1.  f(x,y,z)=(0, 1, 2, 3, 4, 5, 6)
2.  

Вариант №10

1.  f(x,y,z)=(1, 2, 3, 4, 5, 6)
2.  

Вариант №11

1.  f(x,y,z)=(2, 3, 4, 5)
2.  

Вариант №12

1.  f(x,y,z)=(0, 2, 3, 4, 7)
2.  

Вариант №13

1.  f(x,y,z)=(0, 3, 4, 6, 7)
2.  

Вариант №14

1.  f(x,y,z)=(1, 2, 3, 7)
2.  

Вариант №15

1.  f(x,y,z)=(0, 1, 2, 5)
2.  

Вариант №16

1.  f(x,y,z)=(1, 2, 4, 5)
2.  

Вариант №17

1.  f(x,y,z)=(0, 3, 4, 7)
2.  

Вариант №18

1.  f(x,y,z)=(1, 2, 4, 5, 6)
2.  

Вариант №19

1.  f(x,y,z)=(1,2, 3, 6)
2.  

Вариант №20

1.  f(x,y,z)=(0, 1, 3, 4, 6, 7)
2.  

Практическая работа №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), то fS (класс самодвойственных функций).

Рассмотрим наборы:  (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

СПНФ () = (x1)(y1)=xy1

СПНФ () =

Оформим в виде принадлежность функций из F классам Поста:

	T0	T1	S	M	L
	–	–	–	–	–
	-	–	+	–	+

Т.к. в системе F имеются функции: не сохраняющая ноль, не сохраняющая единицу, не самодвойственная, немонотонная и нелинейная, то по теореме Поста о полноте система F является полной. В то же время базиса она не образует, т.к. из неё может быть удалена функция (), и при этом оставшаяся система будет полной.

Задания для самостоятельного выполнения:

Задание №1.

Определите к каким классам относится функция следующего вида:

Задание №2

Определите, является ли полной система функций? Образует ли она базис?

Варианты заданий:

Вариант №1

1.  f(x,y,z)=(7, 8, 9, 10, 12, 15)
2.  

Вариант №2

1.  f(x,y,z)=(7, 9, 11, 12, 14)
2.  

Вариант №3

1.  f(x,y,z)=(1, 3, 5, 7, 8, 9, 11, 12, 14)
2.  

Вариант №4

1.  f(x,y,z)=(7, 8, 9, 10, 11, 12, 15)
2.  

Вариант №5

1.  f(x,y,z)=(7, 8, 9, 10, 12, 15)
2.  

Вариант №6

1.  f(x,y,z)=(0,4, 8, 9, 10, 14)
2.  

Вариант №7

1.  f(x,y,z)=(1, 2, 7, 8, 12, 15)
2.  

Вариант №8

1.  f(x,y,z)=(2, 3, 4, 5, 7, 8, 12, 15)
2.  

Вариант №9

1.  f(x,y,z)=(0, 1, 3, 5, 7, 9, 11)
2.  

Вариант №10

1.  f(x,y,z)=(4, 6, 8, 10, 12, 14)
2.  

Вариант №11

1.  f(x,y,z)=(3, 5, 7, 8, 11, 13, 14)
2.  

Вариант №12

1.  f(x,y,z)=(3, 5, 6, 7, 9, 12, 13, 15)
2.  

Вариант №13

1.  f(x,y,z)=(4, 7, 8, 9, 11, 12, 15)
2.  

Вариант №14

1.  f(x,y,z)=(2, 6, 8, 9, 10, 11, 12, 13, 14)
2.  

Вариант №15

1.  f(x,y,z)=(0, 2, 3, 4, 5, 8, 9)
2.  

Вариант №16

1.  f(x,y,z)=(3, 4, 5, 6, 7, 8, 9, 10, 12, 13)
2.  

Вариант №17

1.  f(x,y,z)=(0, 1, 2, 3, 4, 10, 11, 12, 15)
2.  

Вариант №18

1.  f(x,y,z)=(0,3,7,8,11,13,14,15)
2.  

Вариант №19

1.  f(x,y,z)=(0, 2, 4, 5, 6, 8, 10, 11)
2.  

Вариант №20

1.  f(x,y,z)=(5, 6, 8, 9, 12, 13, 14, 15)
2.  

Практическая работа №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.  ДНФ = k kx x  k ky y  k kz z  k kyy
     kx x  kx y x y  k kzz  kxx kx z x z
    k kzz  kyy  ky z y z  k kzz
     kyy  ky zy z  kxx  kxz xz  kx yx y
    kx y z x y z
2.  Теперь последовательно подставляя в ДНФ каждый набор значений переменных и приравнивая при этом получаемые выражения к значению функции на этом наборе, получим следующую систему уравнений:
   ДНФ(0,0,0):    k k k k k k k=0;
   ДНФ(0,0,1):    k k kz  k kz  kz  kz =1;
   ДНФ(0,1,0):    k ky  k ky  k ky ky=1;
   ДНФ(0,1,1):    k ky  kz  ky  kz  ky z  ky z =1;
   ДНФ(1,0,0):    kx  k k kx kx k kx=1;
   ДНФ(1,0,1):    kx  k kz  kx kx z  kz  kxz =1;
   ДНФ(1,1,0):    kx  ky  k kx y  kx ky kx y=1;
   ДНФ(1,1,1):    kx  ky  kz  kx y  kx z  ky z  kx y z =0;
3.  Выполним шаг 3, приравнивая все коэффициенты первого и последнего уравнений к нулю.
4.  Вычеркнув все нулевые коэффициенты, получим новую систему уравнений, в которой число неизвестных меньше, чем в исходной, но все же превышает число самих уравнений:        kz  kz  kz =1;
                                         ky  ky ky=1;
                                         ky  kz  ky z =1;
                                         kx kx kx=1;
                                         kx kz  kxz =1;
                                         kx ky kx y=1;

В каждом уравнении полученной системы имеется по два коэффициента, которые могут быть приравнены к 1. Отсюда вытекает неоднозначность решения задачи. Учитывая то, что в каждом уравнении следует выбрать лишь один коэффициент, получим следующие два решения:

Первое:  kz =1;  ky=1;  kx=1;

Второе:  kz =1;  ky =1;  kx=1;

Остальные коэффициенты в обоих случаях приравниваем к нулю.

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

1.  f(x,y,z)=(2,3,5,6)
2.  f(x,y,z)=(3,6,7,8,10,11,14)

Вариант №2

1.  f(x,y,z)=(1,2,3,7)
2.  f(x,y,z)=(2,3,4,5,10,12,13,15)

Вариант №3

1.  f(x,y,z)=(0,3,4,5)
2.  f(x,y,z)=(6,7,8,10,11,13)

Вариант №4

1.  f(x,y,z)=(5,6,7)
2.  f(x,y,z)=(2,4,6,9,10,11,12,13)

Вариант №5

1.  f(x,y,z)=(1,2,4,5,6,7)
2.  f(x,y,z)=(2,4,5,6,8,11,12,14)

Вариант №6

1.  f(x,y,z)=(0,2,3,5,7)
2.  f(x,y,z)=(2,3,5,6,7,8,10,12,14)

Вариант №7

1.  f(x,y,z)=(0,3,5,7)
2.  f(x,y,z)=(2,3,4,5,12,13,14)

Вариант №8

1.  f(x,y,z)=(0,1,2,3)
2.  f(x,y,z)=(1,2,5,7,8,12,13,14)

Вариант №9

1.  f(x,y,z)=(1,2,4,6,7)
2.  f(x,y,z)=(1,5,6,7,8,9,10,15)

Вариант №10

1.  f(x,y,z)=(0,1,2,3,4)
2.  f(x,y,z)=(2,3,9,10,13,14,15)

Вариант №11

1.  f(x,y,z)=(1,3,4,6)
2.  f(x,y,z)=(0,2,5,6,8,11,12,13)

Вариант №12

1.  f(x,y,z)=(2,4,5,7)
2.  f(x,y,z)=(1,4,6,7,10,11,12,14)

Вариант №13

1.  f(x,y,z)=(1,2,3,6)
2.  f(x,y,z)=(0,2,5,7,8,9,11,12)

Вариант №14

1.  f(x,y,z)=(0,1,2,3,4)
2.  f(x,y,z)=(1,2,5,7,8,9,10,11,15)

Вариант №15

1.  f(x,y,z)=(0,1,2,6)
2.  f(x,y,z)=(3,5,6,7,8,9,13,14)

Вариант №16

1.  f(x,y,z)=(2,3,6,7)
2.  f(x,y,z)=(0,1,2,7,8,9,10,13,14)

Вариант №17

1.  f(x,y,z)=(3,4,5,6)
2.  f(x,y,z)=(2,6,7,10,12,14,15)

Вариант №18

1.  f(x,y,z)=(3,4,6,7)
2.  f(x,y,z)=(1,2,4,5,8,9,11,12)

Вариант №19

1.  f(x,y,z)=(3,5,6,7)
2.  f(x,y,z)=(3,4,5,6,8,9,10,11)

Вариант №20

1.  f(x,y,z)=(0,5,6,7)
2.  f(x,y,z)=(1,3,5,8,9,10,11,12)

Практическая работа №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

1.  f(x,y,z)=(0,5,8,9,10,12,13)
2.  f(x,y,z)=(0,8,10,11,13,15)

Вариант №2

1.  f(x,y,z)=(1,2,3,12,13,14,15)
2.  f(x,y,z)=(2,3,7,8,10,11,12,15)

Вариант №3

1.  f(x,y,z)=(0,4,6,7,8,10,13,15)
2.  f(x,y,z)=(2,3,7,8,10,11,13,15)

Вариант №4

1.  f(x,y,z)=(0,4,5,6,7,14,15)
2.  f(x,y,z)=(0,3,7,8,9,10,11,12,15)

Вариант №5

1.  f(x,y,z)=(2,4,7,9,10,14,15)
2.  f(x,y,z)=(0,2,3,5,11,12,15)

Вариант №6

1.  f(x,y,z)=(0,2,4,7,8,10,13,15)
2.  f(x,y,z)=(3,6,8,9,12,13,15)

Вариант №7

1.  f(x,y,z)=(2,4,7,9,10,11,13,15)
2.  f(x,y,z)=(0,2,3,4,5,9,10,12)

Вариант №8

1.  f(x,y,z)=(5,7,8,9,10,11,15)
2.  f(x,y,z)=(2,3,4,9,10,11,14,15)

Вариант №9

1.  f(x,y,z)=(0,2,4,8,12,14,15)
2.  f(x,y,z)=(2,3,4,6,7,9,11,12)

Вариант №10

1.  f(x,y,z)=(5,6,7,8,9,10,11,12,13)
2.  f(x,y,z)=(3,5,7,10,11,12,13,14)

Вариант №11

1.  f(x,y,z)=(1,2,3,4,9,11,12,14)
2.  f(x,y,z)=(3,4,5,6,11,13,15)

Вариант №12

1.  f(x,y,z)=(0,1,2,6,10,12,13,14)
2.  f(x,y,z)=(2,3,4,8,12,14,15)

Вариант №13

1.  f(x,y,z)=(1,2,4,5,9,10,13,14)
2.  f(x,y,z)=(0,3,4,6,7,11,12,15)

Вариант №14

1.  f(x,y,z)=(0,1,5,6,8,11,12)
2.  f(x,y,z)=(2,3,7,8,10,13,14,15)

Вариант №15

1.  f(x,y,z)=(1,2,3,4,9,11,12,14)
2.  f(x,y,z)=(3,4,6,11,13,15)

Вариант №16

1.  f(x,y,z)=(0,2,3,4,10,11,12,15)
2.  f(x,y,z)=(3,4,5,9,11,13,15)

Вариант №17

1.  f(x,y,z)=(1,2,3,4,7,8,9,11,12,14)
2.  f(x,y,z)=(1,2,3,4,6,11,13,15)

Вариант №18

1.  f(x,y,z)=(2,3,7,9,11,12,14)
2.  f(x,y,z)=(2,4,5,8,11,13,15)

Вариант №19

1.  f(x,y,z)=(1,2,3,4,5,11,13,14)
2.  f(x,y,z)=(2,4,5,6,7,10,15)

Вариант №20

1.  f(x,y,z)=(6,7,8,9,10,14,15)
2.  f(x,y,z)=(0,3,5,6,7,11,12,13)

Практическая работа №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).  

Решение:

1.  Выделяем вершинно пустые подграфы графа, т.е. подмножества не инцидентных вершин:

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}.

1.  Строим двумерную таблицу,число строк которой равно числу подграфов, а число столбцов – числу вершин. На пересечении столбца и строки ставим единицу, если вершин содержится в подграфе.
2.  Определяем покрытие столбцов строками, т.е. в каждом столбце должна быть хотя бы одна единица. Каждое покрытие порождает раскраску. Покрытие минимальной мощности определяет хроматическое число графа.

	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

AB

-0.5

2

-2

C

A

AC

C

B

BC

A

B

C

AB

A

B

C

A

B

C

AC

A

B

C

1)

)

3)

4)

5)

A

B

C

BC

(AB)(BC)

(AB)(BC)(AC)

5)

A

B

C

(AB)(BC)(AC)

1)

A

B

C

AB

2)

A

B

C

BC

3)

A

B

C

AC

4)

A

B

C

(AB)(BC)

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