Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Дальневосточный федеральный университет»

ИНЖЕНЕРНАЯ ШКОЛА

Кафедра Системы радиосвязи и радиодоступа

Курсовая работа

Дискретная математика и математическая логика

Студентка

Э.В. Прощенок

Владивосток 2018 г



Введение

Дискретную математику можно определить как науку, изучающую конечные множества. При таком определении она становится всепроникающей -- трудно представить себе раздел математики, не связанный с конечными множествами, -- и необъятной. Поэтому всякий курс дискретной математики, как начальный, так и более сложный, поневоле ограничивается какими-то аспектами этой науки. Выбор излагаемых аспектов обычно опирается на решение людей, которые составляют программу курса. В этом курсе мы рассматривали такие темы, как «Метод математической индукции», «Теория множеств», «Функции», «Теория графов», «Математическая логика».



Задание №1

Задать два отношения R ? АЧВ (R ? АЧА)

1. Отношение порядка (частичного (строгого или нестрогого), линейного). Указать экстремальные элементы.

2. Отношение эквивалентности, разбить на классы эквивалентности.

Определение. R ? АЧА есть отношение частичного порядка, если оно рефлексивно, антисимметрично, транзитивно.

R={ (x, y) | x ? y}

Рефлексивно: любой х ? R; х ? х

Определение. Отношение порядка R ? АЧА называется рефлексивным, если для любого а ? А: (а;а) ? R. На любом числовом множестве: « = », « ? ».

Антисимметрично: х ? у и y ? x <=> x = y

Определение. Отношение порядка R ? АЧА называется антисимметричным, если любые a, b ? A следует a - b, из того, что (a, b) ? R и (b, a) ? R. На числовом множестве: « ? », x < y, x > y, x = y: на графе все стрелки, есть петли.

Транзитивно:x ? y, z > y => x < z

Определение. Отношение порядка R ? АЧА называется транзитивным, если любые a, b, c ? A из того, что (a, b) ? R и (b, c) ? R следует, что (a, с) ? R. На числовом множестве: « = », « ? », « < »; a < b, b < c следует, что a > c.

P(A) = { X | X?A }

На Р(А) отношение R = { (X, Y): X ? Y }

Рефлексивно: любой X ? P(A) : Х ? Х

Антисиммметрично: любой Х, Y ? P(A) : Х ? Y и Y ? X <=> X = Y

Транзитивно: любой X, Y, Z ? P(A): Х ? Y и Y ? Z => X ? Z

Определение. Множество А называется строго частично упорядоченным множеством, если оно антирефлексивно, антисимметрично и транзитивно.

Определение. Отношение порядка R ? АЧА называется антирефлексивным, если любое а ? А: (а, а) не принадлежит А. На числовом множестве: « < », « > ». На графе ни одной петли.

Определение. Если в частично упорядоченном множестве А все элементы сравнимы, то оно называется линейно - упорядоченное множество (естественный порядок). Нестрогий: x ? y или x ? y , строгий: x < y или x > y или x = y.

Определение. Пусть дано частично упорядоченное множество А ( А, ?). Элемент а ? А называется максимальным элементом, если не существует b ? А: b > a. Элемент а называется минимальным, если не существует b ? А: b < a.

Замечание. Максимального или минимального элемента частично упорядоченного множества может не быть или один, или несколько.

Определение. Пусть дано частично упорядоченное множество А ( А, ?). Элемент а ? А называется наибольшим, любое b ? А: a ? b. Элемент а называется наименьшим, если любое b ? А: b ? a.

Пример.

А = {1, 2, 3, 4}

P(A) = {(1,1)(2,2)(3,3)(4,4)(2,4)(3,1)(4,3)(2,3)(4,1)}

R = {(1,1)(2,2)(3,3)(4,4)(2,4)(3,1)(4,3)(2,3)(4,1)}

Данное отношение на множестве является отношением частичного порядка.

Рефлексивность: (1,1)(2,2)(3,3)(4,4)

Антисимметричность (нет симметричных элементов)

Транзитивность: (2,4)(4,3)?(2,3); (4,3)(3,1)?(4,1); (2,4)(4,4)?(2,4); (3,1)(1,1)?(3,1); (4,3)(4,4)?(4,3)

Экстремальные элементы

Максимальный элемент: 4

Минимальный элемент: 1

Определение. Отношение R ? АЧА называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности на множестве А разбивает это множество на подмножества (классы эквивалентности), элементы которых эквиваленты друг другу и не эквиваленты друг другу элементам других подмножеств.

А = {12, 14, 15, 16, 27, 28, 37}

R = {(12, 12)(14, 14)(15, 15)(16, 16)(27, 27)(28, 28)(37, 37)(12, 14)(12, 16) (14, 16)(15, 27)(14, 12)(27, 15)(16, 12)(16, 14)}

(12, 12) … (37, 37) - рефлексивность

(12, 14)(14, 12), (12,16)(16,12), (14,16)(16,14),(15,27)(27,15) - симметричность

(12, 16)(16, 12) ?(12, 12); (12,14)(14,12)?(12,12); (14,16)(16,14)?(14,14), (15,27)(27,15)?(15,15), (14,12)(12,14)?(14,14), (16,12)(12,16)?(16,16), (27,15)(15,27)?(27,27) - транзитивность

[12] = {12, 14, 16}

[14] = {12, 14, 16}

[15] = {15, 27, 28}

[16] = {12, 14, 16}

[27] = {15, 27, 28}

[28] = {15, 27, 28}

[37] = {37}

[12] = [14] = [16] = {12, 14, 16}

[15] = [27] = [28] = {15, 27, 28}

[37] = {37}



[A]R = {{12, 14, 16}, {15, 27, 28}, {37}}

Задание №2

Построить таблицы истинности для высказываний (проверить аналитически).

а)

А	В		АВ		В
0	0	1	0	1	1	1	1
0	1	1	0	1	1	1	1
1	0	0	0	1	0	1	0
1	1	0	1	0	1	1	1

F(0, 0)= =1

F(0, 1)= = 1

F(1,0)= =0

F(1,1)= =1

б)

А	В	С		В	AC	АС			BC
0	0	0	1	0	0	1	0	0	0
0	0	1	0	0	0	1	0	0	0
0	1	0	1	1	0	0	1	1	0
0	1	1	0	0	0	1	0	0	1
1	0	0	1	0	0	1	0	0	0
1	0	1	0	0	1	0	1	0	0
1	1	0	1	1	0	0	1	1	0
1	1	1	0	0	1	0	1	1	1



F(0, 0, 0)= = 1

F(0, 0, 1)= = 1

F(0, 1, 0)= = 1

F(1, 0, 0)= = 0

ВС		В		AB
0	1	0	0	0	1	0
0	0	0	0	0	1	0
1	1	1	1	0	1	1
1	0	0	0	0	1	1
0	1	0	1	0	1	0
0	0	0	1	0	1	0
1	1	1	1	1	0	1

1
1
1
0
1
1
1
1

F(0, 1, 1)= = 1

F(1, 0, 1)= = 1

F(1, 1, 0)= = 1

F(1, 1, 1)= = 1



Задание №3

Проверить, является ли система

а) полной,

б) базисом (если нет, дополнить до базиса).

Замыканием над множеством булевой функции М = {f1, f2, … ,fn} называется множество всех булевых функций, представляемых формулами над М. Обозначается [M]. эквивалентность множество булевой функция

Класс функций, сохраняющих 0 (Т0)

Булева функция сохраняет 0, если на нулевом наборе она принимает значение 0. Множество всех функций, сохраняющих 0, образует замкнутый класс 0. Замечание. ДНФ (СДНФ) сохраняет 0, если в нее не входит конъюнкция, в которой все переменные взяты с отрицанием.

Класс функций, сохраняющих 1 (Т1)

Булева функция сохраняет 1, если на единичном наборе она принимает значение 1. Множество функций, сохраняющих 1, образует замкнутый класс Т1. Замечание. ДНФ (СДНФ) сохраняет 1, если в нее входит конъюнкция, в которой все переменные без отрицания.

Класс самодвойственных функций (S)

Булева функция f*называется двойственной к булевой функции f, если она построена следующим образом . Булева функция называется самодвойственной, если она совпадает с двойственной f = f*.

Класс монотонных функций (М)

Булева функция называется монотонной, если при любом возрастании наборов значение функции не убывает. Замечание. ДНФ (СДНФ) являются монотонной, если в ней отсутствуют отрицания.

Класс линейных функций (L)

Многочлен Жегалкина - выражение, в котором нет отрицаний и конъюнкций переменных, связанных операцией сложение по модулю два(). Линейный многочлен Жегалкина - выражение вида с0с1х1с2х2…cnxn, где с1, c2, …cn - числа, коэффициенты многочлена Жегалкина. Булева функция называется линейной, если ее можно представить линейным многочленом Жегалкина. Множество всех линейным функций образует замкнутый класс [L]

Множество булевых функций А = {f1, f2, …, fn} называется полной системой в Р2, если любую функцию алгебры логики можно представить формулой над А. Теорема Поста о полноте: система булевых функций А = {f1, f2, …, fn} является полной в Р2 тогда и только тогда, когда она не содержится целиком ни в одной из замкнутых классов (T0, T1, L, M, S).Система булевых функций называется базисом, если 1) [A] = P2; 2) для любой из функций системы [A\f] ?P2, т.е. при удалении любой функции системы, система перестает быть полной.

1)

x	y	,
0	0	1
0	1	0
1	0	0
1	1	1

, следовательно ;

, следовательно ;

, следовательно ;

, следовательно ;

, следовательно .

2)

x	y	f2(x, y)
0	0	1
0	1	1
1	0	1
1	1	0

, следовательно ;

, следовательно ;

, следовательно ;

, следовательно ;

, следовательно .

3)

x	f3(x)
0	1
1	0

, следовательно ;

, следовательно ;

, следовательно ;

, следовательно ;

, следовательно .

,	,	,	,	,	,
,	-	+	-	-	+
x|y	-	-	-	-	-
,	-	-	+	-	+

Таким образом, система полная, но не является базисом. Функция f2(x, y) = х|y является базисом.



Задание №4

Найти сокращённую ДНФ булевой функции f(x1, x2, x3, x4), заданной вектором своих значений (методом Квайна и с помощью карт Карно). Найти минимальную ДНФ.

a) (1111 1100 0011 0011)

x1	x2	x3	x4	f(x1, x2, x3, x4)
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

СДНФ: V V V V V V V V V

Сокращенная ДНФ: V V V V V V

V V

Таблица Квайна



,	+		+
	+			+
,	+		+			+
	+			+				+
,
,			+		+	+
,				+	+			+
,						+
,								+

Минимальная ДНФ: V V

Ядро: V

Карта Карно

	00	01	11	10
00	+(2)	+(2)	+(1)	+(1)
01	+(1)	+(1)
11			+(1)	+(1)
10			+(1)	+(1)

Минимальная ДНФ: V V

Ядро: V

б) (1001 1110 0111 0000)

x1	x2	x3	x4	f(x1, x2, x3, x4)
0	0	0	0	1
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	0

СДНФ: V V V V V V V V

Сокращенная ДНФ: V V V V V

Таблица Квайна

	+	+	+
				+	+	+

Ядро: V V V V V

Минимальная ДНФ: : V V V V V

Карта Карно

,	00	01	11	10
00	+(1)		+(1)
01	+(3)	+(1)		+(1)
11
10		+(1)	+(3)	+(1)

Ядро: V V V V V

Минимальная ДНФ: V V V V V

Задание №5

Найти максимальный поток в сети. Пропускная способность дуги указана над дугой. Пропускная способность указана над вершиной. Указать минимальный разрез.

Сеть - ориентированный граф с весовой функцией и выделенными вершинами. Поток в сети называется максимальным, если он больше любого возможного потока. Пропускная способность - положительное число, соответствующее каждому ребру. Минимальный разрез - разрез, имеющий наименьшую пропускную способность среди всех разрезов.



1 поток	2 поток	3 поток
S (+?)	S (+?)	S (+?)
x1 (+S; 12)	x1 (+S; 6)	x1 (+S; 1)
x2 (+x1; 6)	x2 -	x2 -
x3 (+x1; 7)	x3 (+x1; 6)	x3 (+x1; 1)
x4 (+x2; 6)	x4 -	x4 -
x5 (+x3; 7)	x5 (+x3; 6)	x5 (+x3; 1)
x6 (+x4; 6)	x6 -	x6 -
x7 (+x5; 6)	x7 (+x5; 5)	x7 (+x5; 1)
x8 (+x6; 6)	x8 (+x5; 5)	x8 (+x5; 1)
x9 (+x7; 5)	x9 (+x7; 5)	x9 -
x10 (+x8; 6)	x10 (+x9; 5)	x10 (+x8; 1)
t (+x10; 6)	t (+x10; 5)	t (+x10; 1)

1 путь: t ? x10 ? x8 ? x6 ? x4 ? x2 ? x1 ? S |6

2 путь: t ? x10 ? x9 ? x7 ? x5 ? x3 ? x1 ? S |5

3 путь: t ? x10 ? x8 ? x5 ? x3 ? x1 ? S |1

Минимальный разрез {S; x1} = 12

Максимальный поток в сети = 12



Заключение

Математика стала частью нашей культуры. Человек не может считать себя широко образованным, не имея представления о современной математике, ее роли в повседневной жизни, науке.

В настоящее время курс «Дискретная математика» всё чаще вводится в программы подготовки не только математиков, инженеров, программистов, но даже юристов. Интерес к этой дисциплине не случаен, так как потребность в знаниях этой области математики объясняется широким кругом применения. Это электроника и информатика, вопросы оптимизации и принятия решения и т. д. В данном курсе мы познакомились лишь с небольшой частью всей дисциплины. За ее рамками остается довольно большой и интересный материал.

Размещено на Allbest.ru

...