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

Вариант 1.

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

U= {-15,-14,-13,-12,-11};

A= {-15,-14,-12} ;B= {-14,-12,-11} ;C= {-15,-11} ;D= {-12}.

а) A∪ C̅ ;б) (A∩C)̅ ;в) (B∪C)(AD);г) (UC)∩A;д) (D̅∩C̅)̅.

Решение.

Диаграммы Эйлера-Венна будем представлять в виде прямоугольников. Универсальному множеству поставим в соответствие прямоугольник. Каждому множеству, входящему в универсальное множество, поставим в соответствие половину площади универсального множества, как и дополнению этого множества.

Клеточки, принадлежащие некоторому множеству, будем помечать 1.

а) C̅ =UC= {-14,-13,-12} ; A∪ C̅ = {-15,-14,-13,-12}.

C̅ C

A̅ 1 0

A 1 0

С̅

C̅ C

A̅ 1 0

A 1 1

A∪ С̅

б) A∩C= {-14,-12} ; (A∩C)̅ =U(A∩C)={-15,-13,-11}.

C̅ C

A̅ 0 0

A 0 1

A∩C

C̅ C

A̅ 1 1

A 1 0

(A∩C)̅



в) B∪C= {-15,-14,-12,-11} ; AD= {-15,-14};

(B∪C) (AD) = {-12,-11}.

C̅ D̅ C̅ D CD C D̅

A̅ B̅ 0 0 1 1

A̅ B 1 1 1 1

AB 1 1 1 1

A B̅ 0 0 1 1

B∪C

C̅ D̅ C̅ D CD C D̅

A̅ B̅ 0 0 0 0

A̅ B 0 0 0 0

AB 1 0 0 1

A B̅ 1 0 0 1

AD

C̅ D̅ C̅ D CD C D̅

A̅ B̅ 0 0 1 1

A̅ B 1 1 1 1

AB 0 1 1 0

A B̅ 0 0 1 0

(B∪C) (AD)

г) (UC) ∩A= {-14,-12}.



C̅ C

A̅ 0 0

A 1 0

A∩ С̅

д) D̅ =UD= {-15,-14,-13,-11} ; (D̅∩C̅)̅ =D∪C= {-15,-12,-11}.

D̅ D

C̅ 1 0

C 1 0

D̅

D̅ D

C̅ 0 1

C 1 1

D∪C

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

“Если оперативная память правильно установлена в контрольный компьютер, и он при запуске не выдает ошибки при проверке оперативной памяти, то оперативная память исправна”.

Решение.

Введем обозначения для высказываний:

A = «Оперативная память правильно установлена в контрольный компьютер»;

B = «Контрольный компьютер при запуске не выдает ошибки при проверке оперативной памяти»;

C = «Оперативная память исправна».

Искомая логическая формула имеет вид:

A⋀B→C.

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

f (x,y,z) = (z→x) → ((y⋁z)̅→x).

Решение.

Имеем:

z→x= z̅⋁x.

(y⋁z)̅→x=y⋁z⋁x.

f (x,y,z) = x̅z⋁x⋁y⋁z=x⋁y⋁z.

Произошла операция поглощения: x̅ z⋁z=z, получена минимальная ДНФ.

Строим таблицу истинности:

x y z f(x,y,z)

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 1

Запишем СКНФ функции:

f (x,y,z)=x⋁y⋁z.

Релейно-контактная схема, реализации функции, имеет вид:

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

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

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

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

A (G̅) = (█(0 1 0 0 1 0@1 0 1 0 0 1@0 0 1 0 0 0@1 0 0 1 0 0@0 0 1 1 0 0@0 0 0 0 1 0))

Решение.

а) Орграф на плоскости имеет вид:

б) Находим полустепени и степени вершин.

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

deg_+ (1) =2; deg_+ (2) =3; deg_+ (3) =1; deg_+ (4)=2;

deg_+ (5) =2; deg_+ (6)=1.

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

deg_- (1) =2; deg_- (2) =1; deg_- (3) =3; deg_- (4)=2;

deg_- (5) =2; deg_- (6)=1.

Степень любой вершины орграфа равна сумме полустепеней для этой вершины: deg 〖(v)〗 = deg_+ (v) + deg_- (v). Имеем:

deg 〖(1)〗 =2+2=4; deg 〖(2)〗 =3+1=4; deg 〖(3)〗=1+3=4;

deg 〖(4)〗 =2+2=4; deg 〖(5)〗 =2+2=4; deg 〖(6)〗=1+1=2.

Сумма всех степеней орграфа равна 22. Разделив это число на 2, получим 11 - число ребер орграфа.

в) Построим матрицу инцидентности орграфа.

Это матрица размера n×m, где n - число вершин, m - число дуг орграфа. Элементы b_(ij) матрицы вычисляют по правилу: b_(ij) =-1, если дуга a_j входит в вершину v_i ; b_(ij) =1, если дуга a_j выходит из вершины v_i ; b_(ij) =2, если дуга a_j есть петля вершины v_i ; b_(ij) =0, если a_j и v_i не инцидентны.

a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 a_9 a_(10) a_(11)

1 -1 1 0 -1 1 0 0 0 0 0 0

2 1 -1 1 0 0 0 0 0 1 0 0

3 0 0 0 0 0 0 0 -1 -1 2 0

4 0 0 0 1 0 0 -1 0 0 0 2

5 0 0 0 0 -1 -1 1 1 0 0 0

6 0 0 -1 0 0 1 0 0 0 0 0