САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ им. проф. М.А. Бонч-Бруевича

ФАКУЛЬТЕТ ВЕЧЕРНЕГО И ЗАОЧНОГО ОБУЧЕНИЯ

Контрольная работа за 3 семестр

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

Имя: Михаил

Отчество: Владимирович

Курс: 2

Студ. билет №: 2010462

Группа №: АБ-03З

Дата сдачи работы: 03.06.2022

Санкт-Петербург

2022

Задача 1 Используя правила де Моргана, получить ДНФ и упростить ее: x ⋅ ¬x¬¬z ∨ ¬y¬¬z.

Решение.

x ⋅ ¬x¬¬z ∨ ¬y¬¬z = x ⋅ (¬x ∨¬¬z) ⋅ (¬y ∨¬¬z) =

x ⋅ (¬x ∨ z)⋅(¬y ∨ z) = (x ⋅ ¬x ∨ x ⋅z)⋅(¬y ∨ z) = x ⋅z⋅(¬y ∨ z) = x ⋅ ¬y ⋅z ∨ x ⋅z = x ⋅z

Задача 11. Даны две функции: f (x, y) = x +(x → y) ₁, f (x, y,z) = (x

y)↓ xz ₂. Требуется: а) для функции f (x, y) ₁составить таблицу истинности и найти по ней полином Жегалкина,  СДНФ, СКНФ. Упростить, если возможно, СДНФ; 

б) для функции f (x, y,z) ₂составить таблицу истинности и найти по ней полином Жегалкина,  СДНФ, СКНФ. По карте Карно получить минимальную ДНФ, нарисовать эквивалентную  РКС; 

в) составить таблицу Поста для системы функций f (x, y) ₁, f (x, y,z) ₂, проверить полноту  системы и выбрать базисы, если она полная. 

Решение.

а) Таблица истинности

x		y x → y	x + (x → y)
0		0 1	1
0		1 1	1
1		0 0	1
1		1 1	0

Полином Жегалкина f (x,y) = ∑ (x + ¬a₁)( y + ¬a₂)Получим f₁(x₁,y₁) = (x + 1)(y + 1) + (x + 1)y + x(y + 1) = x(y + 1) + (y + 1) +

---

+ (x + 1)y + x(y + 1) = (y + 1) + (x + 1)y = y +1+ xy + y =1+ xyСДНФ: f₁(x,y) = ¬x * ¬y v ¬x * y v x * ¬y => f₁(x,y) = ¬x v x * ¬yСКНФ: f₁ (x,y) = ¬x v ¬yб) Таблица истинности

x	y	Z	x y	¬x	¬xz	(x y) ↓ ¬xz
0	0	0	1	1	0	0
0	0	1	1	1	1	0
0	1	0	0	1	0	1
0	1	1	0	1	1	0
1	0	0	0	0	0	1
1	0	1	0	0	0	1
1	1	0	1	0	0	0
1	1	1	1	0	0	0

Полином Жегалкина f (x,y,z) = ∑ (x + ¬a₁) (y + ¬a₂) (z + ¬a₃)Тогда получим f₁ (x,y,z) = (x + 1)y(z + 1) + x(y + 1)(z + 1) + x(y + 1)z = = (x + 1)y(z + 1) + x(y + 1) = (xyz + yz + xy + y) + (xy + x) = xyz + yz + y + xСНДФ: f₂ (x,y,z) = ¬x * y * ¬z v x * ¬y *¬z v x * ¬y *zСКНФ: f (x,y,z) = (x^¬a1 v y^¬a2 v z^¬a3)Получим f (x, y, 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)Карта Карно:

yz  x	00	01	11	10
0	0	0	0	1
1	1	1	0	0

в) Для

---

того чтобы система функций была полна, необходимо и достаточно, чтобы она содержала: 

1) хотя бы одну функцию, не сохраняющую ноль; 

2) хотя бы одну функцию, не сохраняющую единицу; 

3) хотя бы одну несамодвойственную функцию; 

4) хотя бы одну нелинейную функцию; 

5) хотя бы одну немонотонную функцию. 
Таблица Поста: 

Функция	Функционально-замкнутые классы
	T0	T1	S	M	L
f  1	–	–	–	–	–
f 2	+	–	–	–	–

Задача 21. Составить для данного графа структурную матрицу. Найти: а) все простые пути из вершины i = 3в вершину j = 1; б) совокупность всех сечений между вершинами iи j.Составим структурную матрицу S = а) Вычеркиваем из матрицы 1-ую строчку и 3-ый столбец, получаем минор M(1,3):M(1,3) = = = ¬e_{12 ¬}e₃₂ v ¬e₁₂¬e₂₅ ¬e₃₅ v ¬e₁₂¬e₃₂ ¬e₄₅ ¬e₄₅Задача 31. Заданы сеть и начальный поток f:Требуется построить максимальный поток, считая вершину с номером 1 источником и  вершину с номером 4 стоком. Указать минимальное сечение, величина которого равна  максимальному потоку. Решение.Расставим пометки: 

---

Таким образом, поток можно увеличить на 3 единицы. Получим новый поток, на котором снова расставим пометки: Таким образом, поток можно увеличить на 4 единицы. Получим новый поток, на котором снова расставим пометки: Кроме источника можно пометить только одну вершину. Из множества помеченных вершин в множество непомеченных вершин идут только прямые насыщенные дуги 1-2, 1-4, 3-2, 3-4.  Эти три дуги образуют минимальное сечение, величина которого равна 16 единицам, и эта же величина равна величине потока. Таким образом, поток на последнем рисунке является максимальным.Задача 41. На множестве A = {1,2,3,4,5,6} задано отношение делимости: xRy тогда и только тогда, когда x делится на y. Для каждого отношения нужно: а) записать отношение R; б) построить матрицу смежности и граф отношения; в) проверить, является ли отношение рефлексивным, симметричным, транзитивным. Решение.

1. 
   R =
   

б) Матрица смежности А(¬G) = Граф отношения (петли не изображены, отношение - рефлексивное): в) проверить, является ли отношение рефлексивным, симметричным, транзитивным. Отношение R: рефлексивно, т.к. ∀a∈ A: aRa; не симметрично, т.к. ∀a,b∈ A: aRb ⇒ bRaне выполняется; транзитивно, т.к. ∀a,b,c∈ A:(aRb)∧(bRc)⇒ aRc . 

---

Смотрите также файлы

• Курсовая работа Студент 1 курса факультета таможенного дела Пономарева Ксения Евгеньевна Группы Тс2111.pptx

• При черепномозговой травме наиболее тяжелым повреждением является.docx

• Проблемный аспект.doc

• Буллезный пемфигоид на слизистой полости рта.pptx

• Открытый урок по изобразительному искусству во 2 классе Тема урока Живопись. Теплые и холодные цвета Учитель Ховалыг Д. М. ЭлдигХем, 2021.docx