Расчетная работа по дискретной математике

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Кафедра №805

«Математическая кибернетика»

Вариант №19

Расчетная работа по дискретной математике

Студент: Чумин Олег

Группа: №18-101

Преподаватель: доцент Рыбин

Владимир

Васильевич.

- 2000…2001 гг. -

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

2

Элементы математической логики и теории булевых функций.

1. Определить для заданной формулы логики высказываний:

а.) Определить таблицу истинности.

б.) ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований.

в.) Задать табличным способом соответствующую булеву функцию.

г.) Найти СДНФ и СКНФ табличным способом (сравнить со СДНФ, СКНФ,

полученными в пункте «б»).

д.) Указать минимальную ДНФ и соответствующую ей переключательную

схему.

е.) Построить многочлен Жегалкина.

Формула - (Y&Z) ~ (Z⊃X).1

Решение:

а) Определяем таблицу истинности.

Придавая каждой переменной формулы одно из истинностных значений

{И, Л}2 и учитывая, что каждое вхождение знака  относится к наикратчайшей

подформуле, следующей за ним. Список переменных формулы содержит три 3

переменных – <X, Y, Z> ! ∃23 = 8 – оценок3 списка переменных.

X, Y, Z, Y&Z, (Y&Z), Z, Z⊃X, (Y&Z) ~ (Z⊃X)

X Y Z Y&Z (Y&Z) Z Z⊃X (Y&Z) ~ (Z⊃X)

1 И И И И Л Л И Л

2 И И Л Л И И И И

3 И Л И Л И Л И И

4 Л И И И Л Л И Л

5 И Л Л Л И И И И

6 Л Л И Л И Л И И

7 Л И Л Л И И Л Л

8 Л Л Л Л И И Л Л

б.) Определяем ДНФ4, КНФ5, СДНФ6, СКНФ7 методом равносильных

преобразований.

1  символ отрицания «не A»

& символ коньюнкции двух высказываний A&B «A и B», есть высказывание истинное тогда и только

тогда, когда истинны оба высказывания A и B;

V символ дизьюнкции двух высказываний AVB «A или B», есть высказывание ложное тогда и только

тогда, когда оба высказывания ложны

~ символ эквиваленции двух высказываний A~B «A эквивалентно B», есть высказываение истинное

тогда и только тогда, когда истинны A и B;

⊃ символ импликации двух высказываний A ⊃ B «A влечет B», есть высказывание ложное тогда и только

тогда, когда A истинно, а B ложно.

2 И – истина, Л - ложь

3 сопоставление каждой переменной списка некоторого истинностного значения

4 Формула находится в дизьюнктивной нормальной форме (ДНФ), если она является дизьюнкцией (быть может

одночленной) элементарных коньюнкций

5 Формула находится в коньюктивной нормальной форме (КНФ), если она является коньюнкцией (возможно

одночленной) элементарных дизьюнкций

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

3

Находим ДНФ, пользуясь алгоритмом нахождения ДНФ:

1-й этап. Преобразуем исходную формулу в равносильную, в которой

отсутствуют операции эквиваленции « ~ » и импликации « ⊃ ». Для этого

заменяем любые подформулы вида A ⊃ B на A V B, так как

A B A ⊃ B A A V B

И И И Л И

И Л Л Л Л

Л И И И И

Л Л И И И

т.е. A ⊃ B ≡ A V B.

A ~ B ≡ (A & B) V (A &B)

A B A B A & B A &B (A & B) V (A &B) A ~ B

И И Л Л И Л И И

И Л Л И Л Л Л Л

Л И И Л Л Л Л Л

Л Л И И Л И И И

(Y&Z) ~ (Z ⊃X) ≡ (Y&Z) ~ (Z V X) ≡ (Y V Z) ~ (Z V X) ≡

≡ ((Y V Z) & (Z V X)) V ((Y V Z) & (Z V X)) ≡

2-й этап.

Вносим знак отрицания «» под скобки, пользуясь законами де Моргана8, и

сокращаем «»по закону снятия двойного отрицания9.

≡ ((Y V Z) & (Z V X)) V ((Y & Z) & (Z &X)) ≡

≡ ((Y V Z) & (Z V X)) V ((Y & Z) & (Z &X)) ≡

3-й этап.

Так как полученная формула не находится в ДНФ (V не элементарных

конъюнкций), то применяем законы дистрибутивности & относительно V10.

≡ [(Y V Z) & (Z V X)] V [(Y & Z) & (Z &X)] ≡

≡ [(Y V Z) & (Z V X)] V (Y & Z &Z &X)11 ≡

≡ [((Y V Z) & Z) V ((Y V Z) & X)] V (Y & Z &Z &X) ≡

6 СДНФ – совершенная дизьюнктивная нормальная форма

7 СКНФ – совершенная коньюктивная нормальная форма

8 (A&B)≡A VB – первый закон де Моргана, (A V B)≡A &B – второй закон де Моргана

9 A ≡ A – закон снятия двойного отрицания

10 A&(B V C) ≡ (A&B) V (A&C) – закон дистрибутивности & относительно V

11 скобки можно убрать пользуясь законом коммутативности по &: A&B≡B&A и по этому же закону меняем

местами подформулы

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

4

≡ [(Z & (Y V Z)) V (X & (Y V Z))] V (Y & Z &Z &X) ≡

≡ [((Z &Y) V (Z &Z)) V ((X &Y) V (X & Z))]12 V (Y & Z &Z &X) ≡

≡ (Z &Y) V (Z &Z) V (X &Y) V (X & Z) V (Y & Z &Z &X) ≡

полученная формула находится в ДНФ

Используя закон поглощения13 сокращаем полученную формулу до вида:

≡ (Z &Y) V (X &Y) V (X & Z) V (Z &Z) V ((Z &Z) &(Y &X) ≡

≡ (Z &Y) V (X &Y) V (X & Z).

Находим КНФ (Y&Z) ~ (Z⊃X) пользуясь алгоритмом.

Для этого воспользуемся формулой с «тесными» отрицаниями, полученной в

предыдущем пункту14 (2-й этап) при нахождении ДНФ:

≡ ((Y V Z) & (Z V X)) V ((Y & Z) & (Z &X)) ≡

так как формула не находится в КНФ то применяем закон дистрибутивности V

относительно &15

≡ ((Y V Z) & (Z V X)) V (Y & Z & Z &X) ≡

≡ (Y & Z & Z &X) V ((Y V Z) & (Z V X)) ≡

≡ [(Y & Z & Z &X) V (Y V Z)] & [(Y & Z & Z &X) V (Z V X)] ≡

≡ [(Y V Z) V ((Y & Z) & (Z &X))] & [(Z V X) V ((Y & Z) & (Z &X))] ≡

≡ [((Y V Z) V (Y & Z)) & ((Y V Z) V (Z &X))] & [((Z V X) V (Y & Z)) &

& ((Z V X) V (Z &X))] ≡

≡ [(Y V Z) V (Y & Z)] & [(Y V Z) V (Z &X)] & [(Z V X) V (Y & Z)] &

& [(Z V X) V (Z &X)] ≡

≡ [((Y V Z) V Y) & ((Y V Z) V Z)] & [((Y V Z) V Z) & ((Y V Z) VX)] &

& [((Z V X) V Y) & ((Z V X) V Z))] & [((Z V X) V Z) & ((Z V X) VX)] ≡

≡ (Y V Z V Y) & (Y V Z V Z) & (Y V Z V Z) & (Y V Z VX) &

& (Z V X V Y) & (Z V X V Z) & (Z V X V Z) & (Z V X VX) ≡

≡ (Y V Z V Y) & (Y V Z V Z) & (Y V Z V Z) & (Y V Z VX) &

& (Z V X V Y) & (Z V X V Z) & (Z V X V Z) & (Z V X VX) ≡

полученная формула находится в КНФ, воспользовавшись законом

индемпотентности V16, получаем следующий сокращенный вид формулы:

≡ (Y V Z V Y) & (Y V Z V Z) & (Y V Z) & (Y V Z VX) &

& (Z V X V Y) & (Z V X) & (Z V X V Z) & (Z V X VX) ≡

теперь применяем 1-й закон поглощения17:

≡ (Y V Z) & (Z V X).

Находим СДНФ по алгоритму:

1-й этап. Воспользовавшись полученной ДНФ

12 скобки убираем, пользуясь законом коммутативности по V: AVB≡BVA

13 2-й закон поглощения AV(A&B) ≡ A

14 можно также воспользоваться следующей равносильностью A ~ B ≡ (A V B) & ( A V B)

15 A V (B & C) ≡ (A V B) & (A V C) – закон дистрибутивности V относительно &

16 AVA≡A – закон идемпотентности V

17 A&(AVB)≡A – 1-й закон поглощения

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

5

≡ (Z &Y) V (X &Y) V (X & Z) ≡

2-й этап. Вычеркиваем все элементарные &, в которые входит одновременно

переменная и ее отрицание – это тоже уже проделано, так как в полученной

формуле, находящейся в ДНФ мы провели сокращение, пользуясь законами

поглощения.

3-й этап

Этот этап тоже выполнен, так как в каждой элементарной конъюнкции

полученной тождественной формулы любая переменная или ее отрицание

встречается только один раз.

4-й этап

относительно всего списка переменных <X, Y, Z> в формуле

≡ (Z &Y) V (X &Y) V (X & Z) ≡ (X &Y) V (Y & Z)V (X & Z) ≡

в каждой из элементарных конъюнкций отсутствует одна из переменных

списка. Применяем 2-ю формулу расщепления18:

≡ (X &Y) V (Y & Z)V (X & Z) ≡ [((X &Y) & Z)V((X &Y) & Z)] V [((Y & Z)

& X) V ((Y & Z)&X)] V [((X & Z) & Y) V ((X & Z) & Y)] ≡

≡ (X &Y & Z) V (X &Y&Z) V (Y & Z & X) V (Y & Z&X) V (X & Z & Y) V

(X & Z & Y) ≡

5-й этап. В каждой элементарной конъюнкции полученной формулы

переставляем конъюнктивные члены, так, чтобы для каждого i = (1, 2, 3, … n)

на i-м месте стоял Xi или Xi.

≡ (X &Y & Z) V (X &Y&Z) V (X &Y & Z) V (X & Y & Z) V (X & Y &Z) V

(X &Y & Z) ≡

6-й этап. Повторяющиеся элементарные конъюнкции по закону

идемпотентности сокращаем:

≡ (X &Y & Z) V (X &Y&Z) V (X &Y & Z) V (X & Y & Z) V (X & Y &Z) V

(X &Y & Z) ≡

≡ (X &Y & Z) V (X &Y&Z) V (X & Y & Z) V (X & Y &Z) V (X&Y&Z) ≡

≡ (X &Y & Z) V (X &Y&Z) V (X & Y & Z) V (X & Y &Z).

Получили тождественную формулу, находящуюся в СДНФ.

Определяем СКНФ по такому же алгоритму, что и СДНФ, но с заменой знаков

V на & и & на V:

1-й этап.

Используем формулу, полученную при нахождении КНФ.

≡ (Y V Z) & (Z V X) ≡

18 формулы расщепления: A ≡ (A&B)V(A&B) - 1-я, A ≡ (AVB)&(AVB) – 2-я

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

6

2-й этап. Пройден при нахождении КНФ.

3-й этап. Пройден при нахождении КНФ.

4-й этап.

≡ (Y V Z) & (Z V X) ≡ [((Y V Z) V X) & ((Y V Z) V X)] & [((Z V X) V Y)

& ((Z V X) V Y)] ≡

≡ (Y V Z V X) & (Y V Z V X) & (Z V X V Y) & (Z V X V Y) ≡

5-й этап.

≡ (X VY V Z) & (X VY V Z) & (X V Y V Z) & (X V Y V Z) ≡

6-й этап.

≡ (X VY V Z) & (X VY V Z) & (X V Y V Z) & (X V Y V Z).

Сокращать нечего, все элементарные дизъюнкции попарно различны,

полученная тождественная формула находится в СКНФ.

в.) Задаем табличным способом соответствующую булеву19 функцию {И = 1,

Л = 0}.

X Y Z Y&Z (Y&Z) Z Z⊃X (Y&Z) ~ (Z⊃X)

1 1 1 1 1 0 0 1 0

2 1 1 0 0 1 1 1 1

3 1 0 1 0 1 0 1 1

4 0 1 1 1 0 0 1 0

5 1 0 0 0 1 1 1 1

6 0 0 1 0 1 0 1 1

7 0 1 0 0 1 1 0 0

8 0 0 0 0 1 1 0 0

г.) Определяем СДНФ и СКНФ табличным способом:

СДНФ

Выберем в таблице соответствующей булевой функции все те строки, в

которых fA = (Y&Z) ~ (Z⊃X) = 1:

X Y Z Y&Z (Y&Z) Z Z⊃X (Y&Z) ~ (Z⊃X)

2 1 1 0 0 1 1 1 1

3 1 0 1 0 1 0 1 1

5 1 0 0 0 1 1 1 1

6 0 0 1 0 1 0 1 1

19 произвольная n-местная функция измножества {0, 1}

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

7

Для каждой из этих строк строим ассоциированные с ними элементарные

конъюнкции:

<X, Y, Z>

<1, 1, 0> !(X & Y &Z)

<1, 0, 1> !(X &Y & Z)

<1, 0, 0> !(X &Y &Z)

<0, 0, 1> !(X &Y & Z)

Составляем дизъюнкцию, полученных элементарных конъюнкций:

(X & Y &Z) V (X &Y & Z) V (X &Y &Z) V (X &Y & Z),

полученная тождественная формула находится в СДНФ для исходной.

СКНФ

Выберем в таблице соответствующей булевой функции все те строки, в

которых fA = (Y&Z) ~ (Z⊃X) ≠ 1:

X Y Z Y&Z (Y&Z) Z Z⊃X (Y&Z) ~ (Z⊃X)

1 1 1 1 1 0 0 1 0

4 0 1 1 1 0 0 1 0

7 0 1 0 0 1 1 0 0

8 0 0 0 0 1 1 0 0

Для каждой из этих строк строим ассоциированные с ними элементарные

дизъюнкции:

<X, Y, Z>

<1, 1, 1> !(X V Y VZ)

<0, 1, 1> !(X VY V Z)

<0, 1, 0> !(X VY V Z)

<0, 0, 0> !(X V Y V Z)

Составляем конъюнкцию, полученных элементарных дизъюнкций:

(X V Y VZ) & (X VY V Z) & (X VY V Z) & (X V Y V Z)

полученная тождественная формула находится в СКНФ для исходной.

Сравниваем со СДНФ и СКНФ, полученными в пункте «б».

СДНФ

(X &Y & Z) V (X &Y&Z) V (X & Y & Z) V (X & Y &Z) тождественными

преобразованиями,

(X & Y &Z) V (X &Y & Z) V (X &Y &Z) V (X &Y & Z) " по таблице,

видно, что полученные СКНФ различны только расположением элементарных

дизъюнкций.

СКНФ

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

8

(X VY V Z) & (X VY V Z) & (X V Y V Z) & (X V Y V Z) тождественными

преобразованиями,

(X V Y VZ) & (X VY V Z) & (X VY V Z) & (X V Y V Z) " по таблице,

различны только расположением элементарных конъюнкций.

д.) Определение минимальной ДНФ.

Пользуемся методом Блейка определяем сокращенную ДНФ.

1-й этап.

Воспользуемся полученной формулой, находящейся в СДНФ относительно

списка переменных <X, Y, Z>:

(X &Y & Z) V (X &Y&Z) V (X & Y & Z) V (X & Y &Z).

2-й этап.

Применяем правило обобщенного склеивания20:

Записываем все возможные склеивания элементарных конъюнкций.

(X & (Y & Z)) V (X & (Y & Z)) ≡ (X &Y & Z) V (X & Y & Z) V (Y & Z),

((X &Y) & Z) V ((X &Y) &Z) ≡ (X &Y & Z) V (X &Y &Z) V (X &Y),

(X &Y & Z) V (X & Y &Z) no,

(X &Y&Z) V (X & Y &Z) ≡ (X &Y&Z) V (X & Y &Z) V (X & Z),

(X &Y&Z) V (X & Y & Z) no,

(X & Y & Z) V (X & Y &Z) no.

В результате получаем формулу, находящуюся в ДНФ и выражающую

функцию fA:

(X &Y & Z) V (X & Y & Z) V (Y & Z) V (X &Y & Z) V (X &Y &Z) V (X

&Y) V (X &Y&Z) V (X & Y &Z) V (X & Z) ≡

3-й этап. Применяем законы идемпотентности и поглощения:

≡ (Y & Z) V (X &Y) V (X & Z), которая отличается только расположением

конъюнктивных членов от полученной формулы в ДНФ ≡ (Z &Y) V (X &Y) V

(X & Z).

Получили сокращенную формулу, находящуюся в ДНФ:

(Y & Z) V (X &Y) V (X & Z)

Дальнейшие склеивания невозможны, так как в элементарных конъюнкциях

переменные разноименные.

Определяем минимальную ДНФ с использование ядровых импликантов.

(Y & Z) V (X &Y) V (X & Z)

20 (A & B) V (A & B) ≡ (A & B) V (A & B) V B – правило ______обобщенного склеивания.

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

9

Выделим ядровые импликанты,21 для этого составим таблицу значений для

простых импликантов булевой функции fA(X, Y, Z)

X Y Z Y Z fA(X, Y, Z) Y & Z X &Y X & Z

1 0 0 0 1 1 0 0 0 0

2 0 0 1 1 0 1 1 0 0

3 0 1 0 0 1 0 0 0 0

4 1 0 0 1 1 1 0 1 1

5 1 0 1 1 0 1 1 1 0

6 1 1 0 0 1 1 0 0 1

7 1 1 1 0 0 0 0 0 0

8 0 1 1 0 0 0 0 0 0

Из таблицы видно, что оценка <1, 0, 0> является собственной22 оценкой для

Y & Z, а оценка <0, 0, 1> - для X & Z, т.е. эти импликанты являются ядровыми

и войдут в минимальную ДНФ. Рассмотрим V найденных ядровых

импликантов: (Y & Z) V (X & Z). В каждой из строк с номерами 2, 4,5,6 в

которых fA принимает значение 1, содержится, по крайней мере, одна единица в

столбцах соответствующих X & Z и Y & Z, т.е. указанные импликанты

«покрывают» булеву функцию fA.

Определили минимальную ДНФ: (Y & Z) V (X & Z).

Строим переключательную схему, соответствующую найденной минимальной

ДНФ (Y & Z) V (X & Z):

(Y & Z) V (X & Z)

21 Допустимой коньюнкцией или имликантом булевой функции fA (X1, X2, … Xn) называется элементарная

коньюнкция C ≠ 0 со списком переменных < X1, X2, … Xn > такая, что C V fA ≡ fA. Импликант называется

простым, если после отбрасывания любой переменной из C получается элементарная коньюнкция, не

являющаяся импликантом.

Простой импликант булевой функции fA называется ядровым, если удаление его из сокращенной ДНФ функции

fA приводит к ДНФ, которая не равносильна исходной ДНФ.

22 Простой импликант является ядровым тогда и только тогда, когдасуществует оценка списка переменных, на

которой он имеет значение 1 а остальные простые импликанты принимают значение 0.

Z

X Z

Y

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

10

е.) Строим многочлен Жегалкина23.

1-й этап. : (Y&Z) ~ (Z ⊃ X), избавляемся от знаков ~, ⊃V используя

равносильности A ⊃ B ≡ (A & B), A~B ≡ A+B+124, AVB ≡ (A &B) –

(Y&Z) ~ (Z ⊃ X) ≡ (Y&Z) + (Z ⊃ X) + 1 ≡ (Y&Z) + (Z & X) + 1 ≡

2-й этап. & Заменяем на « ! », A на A+1.

3-й этап. Раскрываем скобки.

≡ (YZ) + ((Æ + 1)(X + 1)) + 1 ≡ YZ + 1 + (ÆX + X + Z + 1) + 1 ≡

≡ YZ + 1 + ÆX + X + Z + 1 + 1 + 1 ≡

4-й этап. Полученный многочлен упрощаем.

≡ YZ + ÆX+ X + Z.

Многочлен Жегалкина для заданной формулы имеет следующий вид:

YZ + ÆX+ X + Z.

2. Проверить правильность рассуждений.

Если я встречу своего приятеля, то мы с ним пропустим

первое занятие. Либо я рано утром поеду в институт, либо

я пропущу первое занятие. Если я поеду рано утром в

институт, то встречу своего приятеля. Следовательно, я

пропущу первое занятие только тогда, когда встречусь со

своим приятелем.

Решение: встречу своего приятеля – X1; пропустим первое занятие – X2; я рано

утром поеду в институт – X3;

X1⊃X2, X3~X2, X3⊃X1

X1⊃X2

F = [(X1⊃X2)&(X3~X2)&(X3⊃X1)]⊃(X1⊃X2);

G = (X1⊃X2)&(X3~X2)

H = (X1⊃X2)&(X3~X2)&(X3⊃X1);

23 Многочлен Жегалкина - Многочлен Жегалкина представляет собой сумму попарно различных членов вида

Xi1 Xi2 … Xik (0 < i1 < i2 < … < ik < n+1), а также свободного члена d, где d ∈{0, 1}.

24Логическое сложение – X+Y и X&Y.

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

11

Составляем таблицу истинности (23 = 8 строк):

X1 X2 X3 X1⊃X2 X3~X2 X3⊃X1 G H F

И И И И И И И И И

И И Л И Л И Л Л И

И Л И Л Л И Л Л И

И Л Л Л И И Л Л И

Л И И И И Л И Л И

Л И Л И Л И Л Л И

Л Л И И Л Л Л Л И

Л Л Л И И И И И И

Рассуждение правильно, так как формула тождественно истинная (см.

построенную выше таблицу).

В случае большего числа высказывательных переменным (>3) можно проверить

следующим образом (доказательство от противного): Пусть F не тождественно

истинная формула, тогда в силу свойств коньюнкции получаем, что:

[(X1⊃X2) & (X3~X2) & (X3⊃X1)] ⊃ [X1⊃X2]

Но так как X1⊃X2 = И, то приходим к противоречию, что и доказывает

правильность рассуждений и истинность формулы.

Начальные понятия теории множеств.

3. Доказать тождество.

(A \ B) \ C = (A \ C) \ (B \ C). 25

25 A\B – Относительное дополнение множества B до множества A

И И И л

л

И

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

12

Множества, стоящие в левой и правой частях равенства изображаем с

помощью диаграмм Эйлера – Венна:

Рис. 1

A\B – все элементы A, которые не

принадлежат B.

Рис. 2

(A \ B) \ C - все элементы A \ B,

которые не принадлежат C

Рис. 3

(A \ B) \ C

Рис. 4

A \ C - все элементы A,

которые не принадлежат C.

Рис. 5

B \ C – все элементы B, которые не

принадлежат C.

A

C

B

U

A

C

B

U

A

C

B

U

A

C

B

U

U

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

13

Рис. 6

(A \ C) \ (B \ C) – все элементы A \ C,

которые не принадлежат B \ C.

Рис. 7

(A \ C) \ (B \ C)

Рис. 3 и 7 иллюстрируют равенство множеств (A \ B) \ C и (A \ C) \ (B \ C).

Решение-2 (по принадлежности элемента): Пусть x∈(A\B)\C ⇒ x∈A\B x∉C ⇒

x∉C и (x∈A и x∉B)

x∈A, x∉B, x∉C ⇒ x∈A\C и x∉B\C ⇒x∈(A\C)\(B\C)

x∈(A\C)\(B\C) ⇒ x∈A\C и x∉B\C ⇒ x∈A, x∉C и x∉B\C

x∈A, x∉B, x ∉C ⇒ x∈(A\B)\C.

Решение-3 (метод тождественных преобразований)

(A \ C) \ (B \ C) = (A"C)" (B "C) = A"C " (B #C) = (A"C " B) #(A"C "C) = A"C " B =

= (A \ B) \ C.

Решение-4 (метод характеристической функции)

  

∉

∈

=

x A

x A

A 0,

1,

á ; A#B A B A"B á =á +á −á ; A B A B á =á ⋅á " 1 . A A á = −á

= = ⋅ ⋅ = ⋅ (1− ) ⋅ (1− ) = ( − ⋅ ) ⋅ (1− ) = ( A\B)\C A B C A B C A B C A A B C á á á á á á á á á á á á " "

( ); A A C A B A B C = á −á ⋅á −á ⋅á +á ⋅á ⋅á

= = ⋅ (1− ) ⋅ = ⋅ (1− ) ⋅ ( + − ) = ( A\C)\(B\C) A"C"(B"C) A C B#C A C B C B"C

á á á á á á á á á á

= ⋅ (1− ) ⋅ ( + − ⋅ ) = ⋅ (1− ) ⋅ (1− + − (1− ) ⋅ ) = A C B C B C A C B C B C á á á á á á á á á á á á

= ( − ⋅ ) ⋅ (1− + − ( − )) = ( − ⋅ ) ⋅ (1− + − + ) = A A C B C C C B A A C B C C C B á á á á á á á á á á á á á á á á

= − ⋅ ⋅ − + = − + ⋅ ⋅ − ⋅ + ⋅ ⋅ − ⋅ ⋅ ⋅ = A A C B C B A A B A B C A C A B C A B C C (á á á ) (1 á á á ) á á á á á á á á á á á á á á á

A A B A B C A C =á −á á +á ⋅á ⋅á −á ⋅á

A

C

B

U

U

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

14

Решение-5 (логический метод)

A# B→ XVY; A" B→ X &Y; A→ X

(A \ C) \ (B \ C) = (A"C) "(B "C) =(X&Z)&(Y&Z)=X&Z&(YVZ) = G;

(A \ B) \ C = A"C " B =X&Z&Y = I;

Составляем таблицу истинности (23=8 строк):

X Y Z Y Z YVZ X&Z G I

И И И Л Л И Л Л Л

И И Л Л И Л И Л Л

И Л И И Л И Л Л Л

Л И И Л Л И Л Л Л

Л Л И И Л И Л Л Л

Л И Л Л И Л Л Л Л

И Л Л И И И И И И

Л Л Л И И И Л Л Л

У правой и левой частей доказываемого тождества формулы логики

высказываний, соответствующие этим частям равносильны.

Отношения и функции.

4. Задано бинарное отношение ñ = {<1, 1>, <1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>,

<3, 4>, <4, 4>}

на множестве X = {1, 2, 3, 4}. Является ли оно рефлексивным,

симметричным, антисимметричным, транзитивным?

Найти D(ñ), R(ñ), ñ−1, ñ2 или (ñ ï ñ).

Изобразите указанное бинарное отношение на координатной плоскости.

Решение:

Пользуясь определением и рассматривая первые и вторые компоненты

упорядоченных пар, находим соответственно:

- область определения заданного отношения ñ

D(ñ) = {x ∈X | ∃ y ∈X, ! <x, y> ∈ ñ} = {1, 2, 3, 4};26

- область ___________значений заданного отношения ñ

R(ñ) = {y ∈ X | ∃ x ∈ X, ! <x, y> ∈ ñ} = {1, 2, 3, 4}.

Находим обратное отношение ñ-1 к заданному ñ:

- ñ-1 = {<y, x> | <x, y> ∈ ñ} =

= {<1, 1>, <4, 1>, <2, 2>, <3, 2>, <4, 2>, <3, 3>, <4, 3>, <4, 4>}.

Для нахождения композиции ñïñ составляем таблицу:

ñ2 = ñïñ = {<x, z> | y ∈ X, ! <x, y> ∈ ñ и <y, z> ∈ ñ}

26 “!” - следует

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

15

<x, y> ∈ ñ <y, z> ∈ ñ <x, z> ∈ ñïñ

<1, 1> <1, 1>

<1, 4>

<1, 1>

<1, 4>

<1, 4> <4, 4> <1, 4>

<2, 2> <2, 2>

<2, 3>

<2, 4>

<2, 2>

<2, 3>

<2, 4>

<2, 3> <3, 3>

<3, 4>

<2, 3>

<2, 4>

<2, 4> <4, 4> <2, 4>

<3, 3> <3, 3>

<3, 4>

<3, 3>

<3, 4>

<3, 4> <4, 4> <3, 4>

<4, 4> <4, 4> <4, 4>

ñïñ = {<1, 1>, <1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4, 4>}.

Отношение ñ рефлексивно, так как x ñ x для ∀x ∈ X:

<1, 1>, <2, 2>, <3, 3>, <4, 4>, кроме этого отношение равенства IX на

множестве X таково, что IX = {<x, x> | x∈X } =

= {<1, 1>, <2, 2>, <3, 3>, <4, 4>} ⊆ ñ. 27

Условие IX ⊆ ñ является необходимым и достаточным для того, чтобы ñ

было рефлексивно.

Отношение ñ несимметрично, так как x ñ y не ! y ñ x для ∀x, y∈X:

например <1, 4> ∈ ñ, но <4, 1> ∉ ñ. Кроме этого, ñ-1 ⊄ñ, так как

ñ-1 = {<1, 1>, <4, 1>, <2, 2>, <3, 2>, <4, 2>, <3, 3>, <4, 3>, <4, 4>} ⊄ñ = {<1, 1>,

<1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4, 4>} ! например уже <4, 1>∈ñ-1,

но <4, 1>∉ñ.

Условие ñ-1 ⊆ñ является необходимым и достаточным для симметричности

отношения ñ, но оно не выполняется, также как не выполняются условия ñ⊆ñ-1

! ñ-1=ñ.

Отношение ñ транзитивно, так как x ñ y и y ñ z ! x ñ z для ∀x, y, z ∈X:

<x, y> ∈ ñ и <y, z> ∈ ñ ! <x, z> ∈ ñ

<1, 1> <1, 1>

<1, 4>

<1, 1>

<1, 4>

<1, 4> <4, 4> <1, 4>

<2, 2> <2, 2>

<2, 3>

<2, 4>

<2, 2>

<2, 3>

<2, 4>

<2, 3> <3, 3>

<3, 4>

<2, 3>

<2, 4>

<2, 4> <4, 4> <2, 4>

<3, 3> <3, 3>

<3, 4>

<3, 3>

<3, 4>

<3, 4> <4, 4> <3, 4>

<4, 4> <4, 4> <4, 4>

27 ⊆ - символ отношения включения одного множества в другое

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

16

0

1

2

3

0 1 2 3 4 5

x

y

0

1

2

3

4

5

0 1 2 3 4 5

x

y

Действительно, ñïñ ⊆ñ, более того ñïñ = ñ:

ñïñ = {<1, 1>, <1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4, 4>}=

= ñ = {<1, 1>, <1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4, 4>}, что является

необходимым и достаточным условием транзитивности ñ.

Отношение ñ антисимметрично, так как x ñ y и y ñ x ! x = y для∀x, y∈X:

x y y x

<1, 1> и <1, 1> ! 1 = 1,

<1, 4> <4, 1> ∉ ñ,

<2, 2> и <2, 2> ! 2 = 2,

<2, 3> и <3, 2> ∉ñ,

<2, 4> и <4, 2> ∉ñ,

<3, 3> и <3, 3> ! 3 = 3,

<3, 4> и <4, 3> ∉ ñ,

<4, 4> и <4, 4> ! 4 = 4.

ñ" ñ-1 ⊆IX 28 : что выполняется – ñ" ñ-1 = {<1, 1>, <2, 2>, <3, 3>, <4, 4>} = IX.

Изображаем на координатной плоскости заданное бинарное отношение:

ñ = {<1, 1>, <1, 4>, <2, 2>, <2, 3>, <2, 4>, <3, 3>, <3, 4>, <4, 4>}

5. График функции f(x) представляет собой ломаную, звенья которой

параллельны координатной оси x, либо биссектрисам координатных углов

(угловые коэффициенты звеньев равны ±1 или 0). Координаты каждой

вершины ломаной являются целыми числами. f(x) определяет отношение ñf

на множестве X = [0..5 : x1ñfx2 ⇔29 f(x1) = f(x2)]. Докажите ñf

эквивалентность на X. Перечислите все классы эквивалентности30.

Решение:

Докажем эквивалентность заданного отношения ñf на X:

ñf – рефлексивно, так как f(x) = f(x),

ñf – симметрично, так как f(x1) = f(x2) ! f(x2) = f(x1),

ñf – транзитивно, так как f(x1) = f(x2) и f(x2) = f(x3) ! f(x1) = f(x3)

28 " - символ пересечения множеств (A" B = {x | x∈A и x∈B})

29 ⇔- тогда и только тогда, когда выполняется условие …

30 Классом эквивалентности, порожденным элементом a, называется подмножество [a]ñ={t∈A| añt}

Классы эквивалентности:

[a]ñ ∈[0; 1) {a, 5 - a},

[a]ñ ∈ [1], [3, 4] {1} # [3,

4],

[a]ñ ∈ (1, 2) {a, 4 – a},

[a]ñ ∈ [2] {2}

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

17

I

E

G H

B

D F

A

C

Специальные бинарные отношения.

6. В частично упорядоченном множестве31, заданном диаграммой32, найдите

наибольший, наименьший, минимальный, максимальный элементы.

Продолжите заданное отношение частичного порядка до линейного33.

Решение:

наибольшего элемента нет.

наименьший элемент, он минимальный – A,

максимальные элементы I и H,

Линейный порядок может быть например следующим E, D, F, C, I, G, B, A, H.

      



      





      



      





=

( , )

( , )

( , ) ( , )

( , ) ( , )

( , ) ( , ) ( , )

( , ) ( , ) ( , )

( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , )

( , ) ( , ) ( , ) ( , )

( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , )

I I I

H H H

G G G G I

F F F F H

E E E E G E I

D D D D G D I

C C C C D C E C F C G C H C I

B B B B E B G B I

A A A A B A C A D A E A F A G A H A I

A B C D E F G H I

ñ

31 Частично упорядоченное множество – это множество с заданным на нем частичным (линейным) порядком.

Рефлексивное, антисимметричное и транзитивное отношение называется отношением частичного порядка на

множестве X и обозначается символом «$ ».

32 Называется диаграммой Хассе: схема, где каждый элемент изображается точкой, и если y покрывает x, то

соответствующие точки соединяют линией, и x располагают ниже y.

Говорят, что элемент y покрывает элемент x, если не существует такого элемента u, что x $ u$ y.

33 Отношение линейного порядка –если для любого элемента частично упорядоченного множества выполняется

одно из условий x≤ y или y≤ x, то множество называется линейно упорядоченным.

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

18

Элементы теории графов и сетей.

7. Матрица смежности данного орграфа имеет вид

   





   





0 0 0 0

1 1 0 0

1 0 0 1

0 1 0 1

не решать.

8. Используя алгоритм Тери34 определить замкнутый маршрут, проходящий

ровно по два раза, по разу в каждом направлении, через каждое ребро графа.

Решение: V1!V5!V4!V3!V2!V1!V2!V5!V2!V3!V4!V5!V1.

34 Алгоритм Тери:

- отмечаем прохождение ребра в некотором направлении

- второй раз в этом направлении не движемся

- особо отмечаем ребро, по которому заходим в вершину первый раз

- по особо отмеченному ребру в обратном направлении движемся, если только других возможностей нет.

V4

V3

V2

V1 V5

V4

V3

V2

V1 V5

1

2

3

4

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

19

9. Используя алгоритм фронта волны, найти все минимальные пути из 1-й

вершины в последнюю вершину орграфа заданного матрицей смежности.

        





        





1 1 0 1 1 0 0

0 0 0 1 1 0 0

1 0 0 1 1 1 0

0 1 0 0 1 1 0

1 1 0 1 1 0 1

1 0 1 0 1 0 0

0 0 0 0 1 1 0

!

          





          





1 1 0 1 1 0 0

0 0 0 1 1 0 0

1 0 0 1 1 1 0

0 1 0 0 1 1 0

1 1 0 1 1 0 1

1 0 1 0 1 0 0

0 0 0 0 1 1 0

7

6

5

4

3

2

1

1 2 3 4 5 6 7

V

V

V

V

V

V

V

V V V V V V V

Рисуем подграф35 заданного ориентированного графа, где указаны все

вершины, достижимые из V1: минимальный путь = 5, число минимальных

путей – 2.

35 Подграфом графа называется граф, являющийся подмоделью исходного графа. Иначе говоря, подграф

содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в

подграф).

V1

V6 V5

V4

V2

V3

V7

Минимальные

пути:

V1!V5!V4!V2

!V3!V7 или

V1!V6!V4!V2

!V3!V7

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

20

10. Используя алгоритм Форда-Белмана найти все минимальные пути36 из

первой вершины во все достижимые вершины нагруженного37 орграфа,

заданного матрицей длин дуг38.

          





          





∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

8 11

5 1 5

6 3

2

7 4 2

4 5 3

6 2 6

7 1 2

Решение:

           





           





∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

8 11

5 1 5

6 3

2

7 4 2

4 5 3

6 2 6

7 1 2

8

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8

V

V

V

V

V

V

V

V

V V V V V V V V

!

           





           





∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞

8 11

5 1 5

6 3

2

7 4 2

4 5 3

6 2 6

7 1 2

8

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8

j

j

j

j

j

j

j

j

i i i i i i i i

c

c

c

c

c

c

c

c

c c c c c c c c

10.1. Строим таблицу значений (k )

i ë

, k = 0, … , n-1; i = 1, … , n.39 При этом, если

(n−1) = ∞

i ë

, то вершина Vi не достижима из V1.

(k )

i ë

- определяется следующим образом:

) 0 (

1ë = 0, ) 0 (

i

ë = ∞, i = 2, … n; (считаем любой путь из v в v путем нулевой длины)

при i = 2, .. n, k≥ 0 справедливо равенство ( 1) min{ ( ) }

ji

k

j

k

i ë + = ë + c , 1 ≤ j ≤ n

а при i = 1, k≥ 0 справедливо равенство min{0;min{ }} 1

) ( ) 1 (

1 j

k

j

ë k + = ë + c , 1 ≤ j ≤ n

36 Путь – последовательность вершин и дуг в орграфе v1x1v2x2v3x3…xkvk+1, где k ≥ 1, vi∈V, i = 1, … , k+1, xj∈X, j =

1, … , k дуга xj имеет вид (vj, vj+1), соединяющих вершину v1 и vk+1.

Длиной пути называют сумму длин дуг этого пути. Путь из v в w называется минимальным, если он имеет

минимальную длину по сравнению со всеми путями из v в w.

37 Орграф D = (V, X), V = {v1, v2, … vn}, n ≥ 2 называют нагруженным, если на множестве дуг X определена

некоторая функция l: X! R, называемую весовой, т.е. для каждой дуги x ∈ X поставлено в соответствие

некоторое действительное число l(x) – длина дуги x.

38 Матрица длин дуг – квадратная матрица, порядка n:



 

∞ ∉

∈

=

, ( , ) .

( , ), ( , ) ;

v v X

l v v v v X

c

i j

i j i j

ij

39 (k )

i ë

- длина минимального пути из V1 в Vi , содержащего не более k дуг, если такие пути существуют;

- ∞, если таких путей нет; i = 1, …, n; k = 1, 2, …

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

21

В данном случае1 ≤ j ≤ 8 :

k = 1

) 1(1ë

          





          





∞

∞

∞

8

5

7

4

6

1 V

+

          





          





∞

∞

∞

∞

∞

∞

∞

0

(0)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

∞

! }} min{ ; 0 min{ ) 1(1

          





          





∞

∞

∞

∞

∞

∞

∞

∞

ë = = 0;

(1)

2 ë

          





          





∞

∞

∞

∞

∞

∞

6

7

2 V

+

          





          





∞

∞

∞

∞

∞

∞

∞

0

(0)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

7

! }

7

(1) min{

2

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 7;

(1)

3 ë

          





          





∞

∞

∞

∞

∞

∞

∞

1

3 V

+

          





          





∞

∞

∞

∞

∞

∞

∞

0

(0)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

1

! }

1

(1) min{

3

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 1;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

22

(1)

4 ë

          





          





∞

∞

∞

∞

∞

∞

3

5

4 V

+

          





          





∞

∞

∞

∞

∞

∞

∞

0

(0)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

∞

! (1) min{ }

4

          





          





∞

∞

∞

∞

∞

∞

∞

∞

ë = = ∞;

(1)

5 ë

          





          





∞

∞

∞

∞

∞

∞

1

4

5 V

+

          





          





∞

∞

∞

∞

∞

∞

∞

0

(0)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

∞

! (1) min{ }

5

          





          





∞

∞

∞

∞

∞

∞

∞

∞

ë = = ∞;

(1)

6 ë

          





          





∞

∞

∞

∞

∞

11

3

2

6 V

+

          





          





∞

∞

∞

∞

∞

∞

∞

0

(0)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

2

! }

2

(1) min{

6

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 2;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

23

(1)

7 ë

          





          





∞

∞

∞

∞

∞

∞

2

2

7 V

+

          





          





∞

∞

∞

∞

∞

∞

∞

0

(0)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

∞

! (1) min{ }

7

          





          





∞

∞

∞

∞

∞

∞

∞

∞

ë = = ∞;

(1)

8 ë

          





          





∞

∞

∞

∞

∞

5

2

6

8 V

+

          





          





∞

∞

∞

∞

∞

∞

∞

0

(0)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

∞

! (1) min{ }

8

          





          





∞

∞

∞

∞

∞

∞

∞

∞

ë = = ∞;

k = 2

) 2 (

1ë

          





          





∞

∞

∞

8

5

7

4

6

1 V

+

          





          





∞

∞

∞

∞

2

1

7

0

(1)

j ë

=

          





           



∞

∞

∞

∞

∞

∞

5

13

! }}

5

13

min{ ; 0 min{ ) 2 (

1

          





          





∞

∞

∞

∞

∞

∞

ë = = 0;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

24

(2)

2 ë

          





          





∞

∞

∞

∞

∞

∞

6

7

2 V

+

          





          





∞

∞

∞

∞

2

1

7

0

(1)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

8

7

! }

8

7

(2) min{

2

          





          





∞

∞

∞

∞

∞

∞

ë = = 7;

(2)

3 ë

          





          





∞

∞

∞

∞

∞

∞

∞

1

3 V

+

          





          





∞

∞

∞

∞

2

1

7

0

(1)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

1

! }

1

(2) min{

3

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 1;

(2)

4 ë

          





          





∞

∞

∞

∞

∞

∞

3

5

4 V

+

          





          





∞

∞

∞

∞

2

1

7

0

(1)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

5

6

! }

5

6

(2) min{

4

          





          





∞

∞

∞

∞

∞

∞

ë = = 5;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

25

(2)

5 ë

          





          





∞

∞

∞

∞

∞

∞

1

4

5 V

+

          





          





∞

∞

∞

∞

2

1

7

0

(1)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

∞

! (2) min{ }

5

          





          





∞

∞

∞

∞

∞

∞

∞

∞

ë = = ∞;

(2)

6 ë

          





          





∞

∞

∞

∞

∞

11

3

2

6 V

+

          





          





∞

∞

∞

∞

2

1

7

0

(1)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

4

2

! }

4

2

(2) min{

6

          





          





∞

∞

∞

∞

∞

∞

ë = = 2;

(2)

7 ë

          





          





∞

∞

∞

∞

∞

∞

2

2

7 V

+

          





          





∞

∞

∞

∞

2

1

7

0

(1)

j ë

=

           



          





∞

∞

∞

∞

∞

∞

∞

9

! }

9

(1) min{

7

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 9;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

26

(2)

8 ë

          





          





∞

∞

∞

∞

∞

5

2

6

8 V

+

          





          





∞

∞

∞

∞

2

1

7

0

(1)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

13

! }

13

(2) min{

8

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 13;

k = 3

) 3 (

1ë

          





          





∞

∞

∞

8

5

7

4

6

1 V

+

          





          





∞

13

9

2

5

1

7

0

(2)

j ë

=

          





          





∞

∞

∞

21

14

12

5

13

! }}

21

14

12

5

13

min{ ; 0 min{ ) 3 (

1

          





          





∞

∞

∞

ë = = 0;

(3)

2 ë

          





          





∞

∞

∞

∞

∞

∞

6

7

2 V

+

          





          





∞

13

9

2

5

1

7

0

(2)

j ë

=

          





           



∞

∞

∞

∞

∞

∞

8

7

! }

8

7

(3) min{

2

          





          





∞

∞

∞

∞

∞

∞

ë = = 7;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

27

(3)

3 ë

          





          





∞

∞

∞

∞

∞

∞

∞

1

3 V

+

          





          





∞

13

9

2

5

1

7

0

(2)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

1

! }

1

(3) min{

3

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 1;

(3)

4 ë

          





          





∞

∞

∞

∞

∞

∞

3

5

4 V

+

          





          





∞

13

9

2

5

1

7

0

(2)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

5

6

! }

5

6

(3) min{

4

          





          





∞

∞

∞

∞

∞

∞

ë = = 5;

(3)

5 ë

          





          





∞

∞

∞

∞

∞

∞

1

4

5 V

+

          





          





∞

13

9

2

5

1

7

0

(2)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

10

9 ! }

10

9

(3) min{

5

          





          





∞

∞

∞

∞

∞

∞

ë = = 9;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

28

(3)

6 ë

          





          





∞

∞

∞

∞

∞

11

3

2

6 V

+

          





          





∞

13

9

2

5

1

7

0

(2)

j ë

=

          





          





∞

∞

∞

∞

∞

24

4

2

! }

24

4

2

(3) min{

6

          





          





∞

∞

∞

∞

∞

ë = = 2;

(3)

7 ë

          





          





∞

∞

∞

∞

∞

∞

2

2

7 V

+

          





          





∞

13

9

2

5

1

7

0

(2)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

7

9

! }

7

9

(3) min{

7

          





          





∞

∞

∞

∞

∞

∞

ë = = 7;

(3)

8 ë

          





          





∞

∞

∞

∞

∞

5

2

6

8 V

+

          





          





∞

13

9

2

5

1

7

0

(2)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

14

13

! }

14

13

(3) min{

8

          





          





∞

∞

∞

∞

∞

∞

ë = = 13;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

29

k = 4

) 4 (

1ë

          





          





∞

∞

∞

8

5

7

4

6

1 V

+

          





          





13

7

2

9

5

1

7

0

(3)

j ë

=

          





          





∞

∞

∞

21

12

12

5

13

! }}

21

12

12

5

13

min{ ; 0 min{ ) 4 (

1

          





          





∞

∞

∞

ë = = 0;

(4)

2 ë

          





          





∞

∞

∞

∞

∞

∞

6

7

2 V

+

          





          





13

7

2

9

5

1

7

0

(3)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

8

7

! }

8

7

(4) min{

2

          





          





∞

∞

∞

∞

∞

∞

ë = = 7;

(4)

3 ë

          





          





∞

∞

∞

∞

∞

∞

∞

1

3 V

+

          





          





13

7

2

9

5

1

7

0

(3)

j ë

=

           



          





∞

∞

∞

∞

∞

∞

∞

1

! }

1

(4) min{

3

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 1;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

30

(4)

4 ë

          





          





∞

∞

∞

∞

∞

∞

3

5

4 V

+

          





          





13

7

2

9

5

1

7

0

(3)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

5

6

! }

5

6

(4) min{

4

          





          





∞

∞

∞

∞

∞

∞

ë = = 5;

(4)

5 ë

          





          





∞

∞

∞

∞

∞

∞

1

4

5 V

+

          





          





13

7

2

9

5

1

7

0

(3)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

8

9 ! }

8

9

(4) min{

5

          





          





∞

∞

∞

∞

∞

∞

ë = = 8;

(4)

6 ë

          





          





∞

∞

∞

∞

∞

11

3

2

6 V

+

          





          





13

7

2

9

5

1

7

0

(3)

j ë

=

          





          





∞

∞

∞

∞

∞

24

4

2

! }

24

4

2

(4) min{

6

          





          





∞

∞

∞

∞

∞

ë = = 2;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

31

(4)

7 ë

          





          





∞

∞

∞

∞

∞

∞

2

2

7 V

+

          





          





13

7

2

9

5

1

7

0

(3)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

7

9

! }

7

9

(4) min{

7

          





          





∞

∞

∞

∞

∞

∞

ë = = 7;

(4)

8 ë

          





          





∞

∞

∞

∞

∞

5

2

6

8 V

+

          





          





13

7

2

9

5

1

7

0

(3)

j ë

=

          





          





∞

∞

∞

∞

∞

12

11

13

! }

12

11

13

(4) min{

8

          





          





∞

∞

∞

∞

∞

ë = = 11;

k = 5

) 5 (

1ë

          





          





∞

∞

∞

8

5

7

4

6

1 V

+

          





          





11

7

2

8

5

1

7

0

(4)

j ë

=

          





           



∞

∞

∞

19

12

12

5

13

! }}

19

12

12

5

13

min{ ; 0 min{ ) 5 (

1

          





          





∞

∞

∞

ë = = 0;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

32

(5)

2 ë

          





          





∞

∞

∞

∞

∞

∞

6

7

2 V

+

          





          





11

7

2

8

5

1

7

0

(4)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

8

7

! }

8

7

(5) min{

2

          





          





∞

∞

∞

∞

∞

∞

ë = = 7;

(5)

3 ë

          





          





∞

∞

∞

∞

∞

∞

∞

1

3 V

+

          





          





11

7

2

8

5

1

7

0

(4)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

∞

1

! }

1

(5) min{

3

          





          





∞

∞

∞

∞

∞

∞

∞

ë = = 1;

(5)

4 ë

          





          





∞

∞

∞

∞

∞

∞

3

5

4 V

+

          





          





11

7

2

8

5

1

7

0

(4)

j ë

=

           



          





∞

∞

∞

∞

∞

∞

5

6

! }

5

6

(5) min{

4

          





          





∞

∞

∞

∞

∞

∞

ë = = 5;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

33

(5)

5 ë

          





          





∞

∞

∞

∞

∞

∞

1

4

5 V

+

          





          





11

7

2

8

5

1

7

0

(4)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

8

9 ! }

8

9

(5) min{

5

          





          





∞

∞

∞

∞

∞

∞

ë = = 8;

(5)

6 ë

          





          





∞

∞

∞

∞

∞

11

3

2

6 V

+

          





          





11

7

2

8

5

1

7

0

(4)

j ë

=

          





          





∞

∞

∞

∞

∞

22

4

2

! }

22

4

2

(5) min{

6

          





          





∞

∞

∞

∞

∞

ë = = 2;

(5)

7 ë

          





          





∞

∞

∞

∞

∞

∞

2

2

7 V

+

          





          





11

7

2

8

5

1

7

0

(4)

j ë

=

          





          





∞

∞

∞

∞

∞

∞

7

9

! }

7

9

(5) min{

7

          





          





∞

∞

∞

∞

∞

∞

ë = = 7;

Расчетная работа по дискретной математике

студента группы 18-101 Чумина Олега www.chuminoleg.boom.ru

Вариант №19.

34

(5)

8 ë

          





          





∞

∞

∞

∞

∞

5

2

6

8 V