Дискретная математика (стр. 17 )

1. Является ли fi существенно зависящей от аргумента x1?

2. Является ли fi существенно зависящей от аргумента x2?

3. Является ли fi существенно зависящей от аргумента x3?

4. Является ли fi сохраняющей ноль?

5. Является ли fi сохраняющей единицу?

6. Является ли fi самодвойственной?

7. Является ли fi монотонной?

8. Является ли fi линейной?

Все положения ответа должны быть обоснованы.

Пример оформления контрольной работы

(Задания данного примера вымышлены и не являются заданиями какого-либо из предлагаемых вариантов)

Псковский государственный политехнический институт

факультет Информатики

Контрольная работа

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

студента группы 682-0902

Иванова Ивана Ивановича

(№ зачетной книжки 0308033)

Вариант № 13

Преподаватель:

Псков

2009

Задание 1

Даны множества: Определить множества:

A = {1, 2, 3, 4, 5, 6, 7, 8}; D1 = B \ (A È C);

B = {2, 4, 6, 8, 10, 12, 14, 16}; D2 = (A D B) Ç C;

C = {1, 3, 5, 7, 9, 11, 13, 15}. D = D1 ´ D2.

A È C = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15}

D1 = B \ (A È C) = {10, 12, 14, 16}

A D B = {1, 3, 5, 7, 10, 12, 14, 16}

D2 = (A D B) Ç C = {1, 3, 5, 7}

D = D1 ´ D2 = {(10, 1), (10, 3), (10, 5), (10, 7), (12, 1), (12, 3), (12, 5), (12, 7), (14, 1), (14, 3), (14, 5), (14, 7), (16, 1), (16, 3), (16, 5), (16, 7)}

Задание 2

A = {1, 2, 3, 4, 5, 6, 7, 8};

B = {2, 4, 6, 8, 10, 12, 14, 16}.

Задать списком:

а) отношение R Í B ´ A = {(b, a) ÷ b является делителем a};

б) обратное отношение R–1;

в) композицию отношений R ° R–1;

г) проекцию множества векторов на вторую ось Пр2(R ° R–1).

а) R = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 4), (4, 8), (6, 6), (8, 8)}

б) R–1 = {(2, 2), (4, 2), (6, 2), (8, 2), (4, 4), (8, 4), (6, 6), (8, 8)}

в) R ° R–1 = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 2), (4, 4), (4, 8), (6, 2), (6, 6), (8, 2), (8, 4), (8, 8)}

г) Пр2(R ° R–1) = {2, 4, 6, 8}

Задание 3

R = {(7, 8), (1, 3), (2, 8), (8, 3)}.

Найти:

а) OOR (область определения соответствия R);

б) ОЗR (область значений соответствия R);

в) образ элемента 8;

г) прообраз элемента 8;

д) является ли соответствие R инъективным? почему?

а) OOR = {7, 1, 2, 8}

б) ОЗR = {8, 3}

в) образ элемента 8 = {3}

г) прообраз элемента 8 = {7, 2}

д) соответствие R не является инъективным, так как не соблюдается условие единственности прообраза. Например, у элемента 3 существует два прообраза: 1 и 8

Задание 4

Нарисовать сильно связный орграф с пятью вершинами, имеющий минимальное количество дуг.

В сильно связном орграфе должен существовать путь из любой вершины в любую другую вершину. Минимальным по количеству дуг будет контур, проходящий по всем вершинам. Покажем существование пути из каждой вершины в каждую. Путь из v1 в v2: v1, v2. Путь из v2 в v1: v2, v3, v4, v5, v1. Аналогично можно указать пути и между любыми другими парами вершин. Существует ли сильно связный орграф с пятью вершинами и меньшим количеством дуг, чем 5? Если дуг будет 4, то в лучшем случае, если граф останется связным, мы получим ордерево, в котором только из корня есть путь ко всем остальным вершинам.

Задание 5

Нарисовать граф по следующей матрице. Обозначить вершины (узлы) и/или ребра (дуги) метками v1, v2, … и е1, е2, … согласно данной матрице.

	1	2	3	4
1	1	1	0	0
2	1	0	1	0
3	0	1	0	1
4	0	0	1	0

В данном случае представленная матрица может быть как матрицей смежности неориентированного графа G1 (матрица квадратная, симметрична относительно главной диагонали), так и матрицей инцидентности неориентированного графа G2 (в каждом столбце матрицы не более двух единиц, но при этом нет отрицательных значений).

 

Задание 6

По следующему графу приведите пример цепи, не являющейся простой (в виде соответствующей последовательности вершин).

b, d, c, g, d, e – данный маршрут является цепью, так как не проходит по одним и тем же ребрам дважды, но не является простой цепью, потому что вершина d встречается в нем более одного раза.

Задание 7

Доказать справедливость соотношения

((`a ® (c Å b)) × (`b ® (a × d)) × (d ® (b Å c)) × (a Å c)) ® a = 1

((`a ® (c Å b)) × (`b ® (a × d)) × (d ® (b Å c)) × (a Å c)) ® a = 

= ((a + (c Å b)) × (b + ad) × (`d + (b Å c)) × (a ×`c + `ac)) ® a =

= ((a + (c Å b)) × (`d + (b Å c)) × (b + ad) × (a ×`c + `ac)) ® a =

= ((a ×`d + (c Å b)) × (ab ×`c +`abc + a ×`cd)) ® a =

= ((a ×`d + b ×`c +`bc) × (ab ×`c +`abc + a ×`cd)) ® a =

= (ab ×`c ×`d + ab ×`c + ab ×`cd) ® a = ab ×`c × (`d + 1 + d) ® a =

= (ab ×`c × 1) ® a = ab ×`c ® a =  =`a +`b + c + a = 1 +`b + c = 1

Задание 8

Найти МДНФ следующей функции без использования карты Карно:

x	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
y	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
z	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
t	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
f	1	–	–	–	0	1	0	0	1	0	–	–	1	–	–	1

= 0000 + 0001 + 0010 + 0011 + 0101 + 1000 + 1010 +

+ 1011 + 1100 + 1101 + 1110 + 1111

0 группа: 0000 *

1: 0001 * 0010 * 1000 *

2: 0011 * 0101 * 1010 * 1100 *

3: 1011 * 1101 * 1110 *

4: 1111 *

0 группа: 000- * 00-0 * -000 *

1: 00-1 * 001- * 0-01 -010 * 10-0 * 1-00 *

2: -011 * 101- * -101 110- * 1-10 * 11-0 *

3: 1-11 * 11-1 * 111- *

0 группа: 00-- 00-- -0-0 -0-0

1: -01- -01- 1--0 1--0 0-01

2: 1-1- 11-- 1-1- 11-- -101

	0000	0101	1000	1100	1111
00--	Ö
-0-0	Ö		Ö
-01-
1--0			Ö	Ö
0-01		Ö
1-1-					Ö
11--				Ö	Ö
-101		Ö

= -0-0 + 11-- + 0-01 =

Задание 9

Определить следующие свойства логической функции, заданной таблицей

x1	0	0	0	0	1	1	1	1
x2	0	0	1	1	0	0	1	1
x3	0	1	0	1	0	1	0	1
f	0	1	0	1	0	1	0	1

1. Является ли f существенно зависящей от аргумента x1?

2. Является ли f существенно зависящей от аргумента x2?

3. Является ли f существенно зависящей от аргумента x3?

4. Является ли f сохраняющей ноль?

5. Является ли f сохраняющей единицу?

6. Является ли f самодвойственной?

7. Является ли f монотонной?

8. Является ли f линейной?

Все положения ответа должны быть обоснованы.

f(0, 0, 0) = f(1, 0, 0)

f(0, 0, 1) = f(1, 0, 1)

f(0, 1, 0) = f(1, 1, 0)

f(0, 1, 1) = f(1, 1, 1) Þ f не зависит существенно от x1

f(0, 0, 0) = f(0, 1, 0)

f(0, 0, 1) = f(0, 1, 1)

f(1, 0, 0) = f(1, 1, 0)

f(1, 0, 1) = f(1, 1, 1) Þ f не зависит существенно от x2

f(0, 0, 0) ¹ f(0, 0, 1) Þ f существенно зависит от x3

f(0, 0, 0) = 0 Þ f сохраняет ноль

f(1, 1, 1) = 1 Þ f сохраняет единицу

f(0, 0, 0) ¹ f(1, 1, 1)

f(0, 0, 1) ¹ f(1, 1, 0)

f(0, 1, 0) ¹ f(1, 0, 1)

f(0, 1, 1) ¹ f(1, 0, 0) Þ f самодвойственна

f(1, 1, 1) > f(0, 0, 0)

f(1, 1, 0) = f(1, 0, 0)

f(1, 1, 0) = f(0, 1, 0)

f(1, 0, 1) > f(1, 0, 0)

f(1, 0, 1) = f(0, 0, 1)

f(0, 1, 1) > f(0, 1, 0)

f(0, 1, 1) = f(0, 0, 1) Þ f монотонна

Из таблицы значений функции f понятно, что f = x3. Эта запись одновременно является и полиномом Жегалкина для функции f. Данный полином – линейный (так как в нем нет слагаемых, являющихся конъюнкциями нескольких переменных), следовательно, и функция f является линейной.

Рекомендуемая литература

1.  Акимов математика: логика, группы, графы: Учеб. для ВУЗов.-2-е изд., доп.- М.: Лаб. Базовых Знаний,2003.-376с.: ил.-ISBN 5-93208-025-6.

2.  Воронов математические понятия : учеб. посо-бие. Ч. 1 / , ; Псковск. гос. политехн. ин-т. - Псков: Изд-во ППИ, 2008. - 103с.: ил. - ISBN 978-5-91116-071-3.

3.  Горбатов дискретной математики: Учеб. пособие для ВУЗов.- М.:Высш. шк.,1986.-311с.: ил.

4.  Закревский основы проектирования дискретных устройств : [учеб. пособие] / , , . - М. : Физматлит, 2007. - 589с. : ил. - (Математика. Прикладная математика). - ISBN 978-5-9221-0811-9.

5.  Иванов математика. Алгоритмы и программы: Учеб. пособие.- М.: Лаб. Базовых Знаний, 2003.-288с.:ил.-ISBN 5-93208-093-0.

6.  Кузнецов математика для инженера. 4-е изд., стер. – СПб: Издательство «Лань», 2005. – 400 с.: ил. – (Учебники для ВУЗов. Специальная литература). – ISBN 5-8114-0570-7.

7.  Новиков математика для программистов: учеб. пособие для ВУЗов/ . - 2-е изд. - СПб.: Питер, 2006. - 363с.: ил. - (Учеб. для ВУЗов). - ISBN 5-94723-741-5.

8.  Поздняков математика : учеб. для ВУЗов / , - М.: Изд. центр «Академия», 2008. -448с.: ил. - (Высшее профессиональное образование). - ISBN

9.  Строганов основы цифровой вычислительной техники: Учеб. пособие/ЛПИ им. -Л.: 1979.-73с.

10.  Шапорев математика. Курс лекций и практических занятий. – Спб.: БХВ-Петербург, 2006. – 400 с.: ил.

11.  Яблонский в дискретную математику: учеб. пособие для ВУЗов/ ; Московск. гос. ун-т им. . - изд. 4-е, стер. - М.: Высш. шк., 2006. - 384с.: ил. - (Классич. унив. учеб.). - ISBN 5-06-005683-Х.

12.  Яхъяева множества и нейронные сети: Учебное пособие /. – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006. – 316 с.: ил., табл. – (Серия «Основы информационных технологий»)

МОТИНА Надежда Владимировна

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические указания по выполнению контрольных работ

Отпечатано с готового оригинал-макета автора

_____________________________________________________________

Формат 60´90/16. Гарнитура Times New Roman. Усл.. п. л. 5,4

Тираж 100 экз. Заказ №.

Адрес издательства:

Россия, 180000, Псков, ул. Л. Толстого 4.

Издательство ППИ