Контрольная по дискретной математике

 

Федеральное агентство связи

 

Сибирский Государственный Университет  Телекоммуникаций и Информатики

 

Межрегиональный центр  переподготовки специалистов

 

 

 

 

 

 

 

 

 

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

По дисциплине: Дискретная математика                                  

                                  

 

 

 

 

 

Выполнил:  

Группа:        

Вариант:      

    

 

 

Проверил: Мурзина Т. С.

 

 

 

 

 

 

 

 

 

 

Новосибирск, 2012 г

Задача I.

 

Задано универсальное  множество U  и множества A,B,C,D. Найти результаты действий a) - д) и каждое действие проиллюстрировать с помощью диаграммы Эйлера-Венна.

 

 

 

Решение.

 

1.           

Рис. 1

 

2.                

 

Рис. 2

 

 

Рис. 3

 

4.    

 

Рис. 4

 

Рис. 5

Задача II.

 

Ввести необходимые  элементарные высказывания и записать логической формулой следующее предложение  – «Если студент подготовился к экзамену плохо, то он не решает задачи и не отвечает на вопросы экзаменатора».

 

Решение.

Введем следующие обозначения:

1. А – студент подготовился к экзамену плохо

2. В – он решает задачи

3. С – он отвечает на вопросы экзаменатора

Следовательно исходное высказывание можно записать логической формулой:  .

 

 

Задача III.

Для булевой функции найти методом преобразования минимальную ДНФ. По таблице истинности построить СКНФ. По минимальной ДНФ построить релейно-контактную схему.

 

Решение.

 

Используя свойства логических операций, методом преобразований получим минимальную ДНФ:

 

 меняем знак

соотношение эквивалентности для  импликации

закон де Моргана

коммутативность

 коммутативность

 идемпотентность

Составим таблицу истинности для данной функции.

Таблица функции

 

x	y	z
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

 

 

Построим СКНФ. Располагая таблицей истинности функции, запишем  основные дизъюнкции:

 

x	y	z		основные дизъюнкции
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

 

Следовательно, СКНФ функции  имеет вид:

- минимальная ДНФ совпадает с СКНФ.

 

По минимальной ДНФ  построим релейно-контактную схему (рис.6).

 

 

 

 

 

Рис. 6. Релейно-контактная схема реализации переключательной функции  с реле-повторителями сигналов датчиков.

 

 

Задача IV.

Орграф задан своей  матрицей смежности. Следует:

 а) нарисовать орграф;

 б) найти полустепени и степени вершин;

 в) записать матрицу  инцидентности;

 

 

 

Решение.

 

1.  В матрице смежности строкам и столбцам соответствуют все вершины графа

v_j, а элемент δ _{k l}, стоящий на пересечении k -й и l -й вершин ( k -й строки и l -го столбца):

   – в случае неографа (неориентированного графа) равен числу рёбер, соединяющих эти вершины;

   – в случае орграфа (ориентированного графа) равен числу рёбер с началом в k -й вершине и концом в l -й.

 

Матрица смежности рассматриваемого графа соответствует графическому представлению орграфа (рис.7).

 

 

 

 

 

Рис. 7

 

 

2. Локальная степень (или просто степень) deg (v) вершины – число рёбер, инцидентных вершине  v .

Ребро в орграфе называется дугой (дуга – ориентированное ребро). Для вершин орграфа определяются две локальные степени:

  – полустепень захода   degⁱⁿ(v) или d⁺ – число дуг, входящих в v ;

   – полустепень  исхода  deg^out(v) или d^-  – число дуг, выходящих из  v .

Петля даёт вклад, равный 1, в обе эти степени. Сумма полустепеней вершины даёт степень вершины.

 

Полустепени и степени  вершин орграфа:

 

вершина
	1	2	3
	3	3	6
	1	2	3
	2	2	4
	3	1	4
	1	1	2

 

( – полустепень захода,  – полустепень исхода,  +   – степень вершины)

 

 

3. В матрице инцидентности строкам соответствуют вершины v_i  , а столбцам рёбра e_j графа, а элемент ε_ij, находящийся на пересечении i -й строки и j -го столбца:

– в случае орграфа:

 

 

Обозначим дуги орграфа  и составим таблицу инцидентности  вершин и рёбер графа.

 

Рис. 8

 

 

вершина\дуга	(1,3)	(1,5)	(2,2)	(2,4)	(2,5)	(3,2)	(3,4)	(4,2)	(4,6)	(5,5)	(6,1)
v1	–1	–1	0	0	0	0	0	0	0	0	1
v2	0	0	2	–1	–1	1	0	1	0	0	0
v3	1	0	0	0	0	–1	–1	0	0	0	0
v4	0	0	0	1	0	0	1	–1	–1	0	0
v5	0	1	0	0	1	0	0	0	0	2	0
v6	0	0	0	0	0	0	0	0	1	0	–1

 

Следовательно, матрица инцидентности орграфа: