Курсовая работа: Дискретная математика и математическая логика

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

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

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

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

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

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

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

Студентка

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

Владивосток 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

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

а)

F(0, 0)= =1

F(0, 1)= = 1

F(1,0)= =0

F(1,1)= =1

б)

F(0, 0, 0)= = 1

F(0, 0, 1)= = 1

F(0, 1, 0)= = 1

F(1, 0, 0)= = 0

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)

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

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

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

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

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

2)

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

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

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

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

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

3)

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

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

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

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

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

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

Задание №4

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

a) (1111 1100 0011 0011)