Специальные бинарные отношения

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

Министерство образования и науки Российской Федерации

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

"Российский государственный профессионально-педагогический университет" в г. Советском

Кафедра профессионально-педагогического образования

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

Специальные бинарные отношения

по дисциплине

"Дискретная математика"

Вариант №6

Выполнил:

Апатова Е.С.

Советский

2014



Содержание

Задание №1

Задание №2

Задание №3

Задание №4

Задание №5

Задание №6

Задание №7

Задание №8

Задание №9

Задание №10

Задание №11

Задание №12

Задание №13

Список используемых источников



Задание №1

1. Пусть, , , . Найти

а) ; б), в).

Т.к. , то

а) ;

б)

в)

Если же

Тогда

а) ;

б)

в)



Задание №2

2. Является ли рефлексивным, антисимметричным и транзитивным отношение перпендикулярности на множестве прямых на плоскости?

1) Не является рефлексивным, т.к. прямая не может быть перпендикулярна сама себе

2) Не является антисимметричным, т.к. если одна прямая перпендикулярна второй, то вторая перпендикулярна первой

3) Не является транзитивным, т.к. если одна прямая перпендикулярна второй, а вторая перпендикулярна третьей, то первая и третья прямые параллельны, а не перпендикулярны

3. Какими свойствами обладают следующие бинарные отношения на множестве М:

a)

Рефлексивность:

Равенство верное, значит отношение рефлексивно

Симметричность:

на множестве М отношение симметрично

Транзитивность

Транзитивность установить однозначно нельзя

Ответ: рефлексивно и симметрично

b)

Рефлексивность

Равенство верно только для а=1 и а=0

Отношение не является рефлексивным и не является антирефлексивным

Симметричность:

Выполняется при а=1, и b=1 или b=-1, при а=b=0

Отношение не симметрично и не антисимметрично

Транзитивность

Транзитивность установить однозначно нельзя

Задание №3

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

М={a,b,c,d}

1) Линейное отношение

a-b-c-d

a-b-d-c

a-c-b-d

a-c-d-b

a-d-b-c

a-d-c-b

и тд

2) Дерево

И тд

3) "вилка"

и тд.

("и тд" - значит, что элементы могут быть переставлены в любой последовательности)

Задание №4

Найти значение выражения при , .

Если ,

Задание №5

Доказать логическое тождество .

Докажем графически с помощью диаграмм Эйлера

Левая и правая части тождества задают одну и ту же область, значит тождество верное

Задание №6

7. Записать в виде логического выражения следующие рассуждения:

а) "Неправильное употребление слов ведет за собой ошибки в области мысли и потом в практике жизни" (Д.И.Писарев).

a-правильное употребление слов

b-ошибки в области мысли

c- ошибки в практике жизни

б) У людей, переболевших в детстве корью, эта болезнь больше не повторяется, что обусловлено присутствием в крови соответствующих антител.

а- переболел в детстве

b - повторится

с - присутствуют антитела

Задание №7

Доказать, что выражение является тавтологией.

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

А	С	А>С	С>(А>С)
0	0	1	1
0	1	1	1
1	0	0	1
1	1	1	1

При любых А и С выражение истинно, следовательно является тавтологией

Задание №8

Областью определения предиката

""

является:

1) ; 2) ;

3) ; 4) .

Задание №9

Указать, какие из следующих предложений являются формулами логики предикатов:

1);

- явл. Формулой

2) ;

- явл формулой

3) ; - не явл формулой (операция дизъюнкции применена к свободной переменной и переменной связанной с квантором)

4) . - не явл. формулой квантор общности навешен к В не зависящей от х

Задание №10

Дан граф. Записать матрицу смежности графа.

Рис. 1 транзитивный перпендикулярность неизоморфность плоскость

Пронумеруем вершины графа

Составим матрицу смежности

Задание №11

Указать все цепи, связывающие вершины и в графе

А-1 А-2 А-3

А-1-В А-2-3 А-3-1

А-1-3 А-3-2

А-1-4 А-3-4

А-1-3-2 А-2-3-1 А-3-1-В

А-1-3-4 А-2-3-4 А-3-1-4

А-1-4-3 А-3-4-1

А-1-4-В А-3-4-В

А-1-4-5 А-3-4-5

А-1-3-4-В А-2-3-1-В

А-1-3-4-5 А-2-3-1-4 А-3-1-4-В

А-1-4-5-В А-2-3-4-1 А-3-1-4-5

А-2-3-4-В А-3-4-1-В

А-2-3-4-5 А-3-4-5-В

А-1-3-4-5-В А-2-3-1-4-В А-3-1-4-5-В

А-2-3-1-4-5

А-2-3-4-1-В

А-2-3-4-5-В

А-2-3-1-4-5-В

Выпишем найденные цепи от А к В и т.к. граф неориентированный, то запишем так же цепи от В к А:

А-1-В В-1-А

А-3-1-В В-1-3-А

А-1-4-В В-4-1-А

А-3-4-В В-4-3-А

А-1-3-4-В В-4-3-1-А

А-2-3-1-В В-1-3-2-А

А-3-1-4-В В-4-1-3-А

А-1-4-5-В В-5-4-1-А

А-2-3-4-В В-4-3-2-А

А-3-4-1-В В-1-4-3-А

А-3-4-5-В В-5-4-3-А

А-1-3-4-5-В В-5-4-3-1-А

А-2-3-1-4-В В-4-1-3-2-А

А-3-1-4-5-В В-5-4-1-3-А

А-2-3-4-1-В В-1-4-3-2-А

А-2-3-4-5-В В-5-4-3-2-А

А-2-3-1-4-5-В В-5-4-1-3-2-А

Задание №12

Найти число всех различных графов с 3 вершинами.

однонаправленных: всего 3 возможных ребра,

двунаправленных: каждое ребро может быть в ту или другую сторону,

в любом из этих графов может быть 0,1,2,3 петли у вершин, значит, число различных графов равно:

(8+64)*4=288

Задание №13

В городе 40 домов и 101 дорога, каждая из которых соединяет два дома, расположенные недалеко по соседству. Из любого дома можно проехать по дорогам к любому дому. Какое наибольшее количество дорог можно закрыть на ремонт так, чтобы по-прежнему от любого дома можно проехать к любому дому?

Должно остаться не менее

40-1=39 дорог, иначе граф не будет связным.

Изначально в городе101 дорога, поэтому можно закрыть на ремонт не более

101-39 = 62 дороги.



Список используемых источников

1.Электронные ресурсы

1.Дискретные случайные величины http://www.testent.ru/publ/studenty/vysshaja_matematika/diskretnye_sluchajnye_velichiny/35-1-0-1136

2. Специальные бинарные отношения. http://www.studfiles.ru/dir/cat14/subj266/file9094/view94415.html

3. Бинарные отношения. Отношения эквивалентности. http://mathprofi.ru/differencialnye_uravnenija_primery_reshenii.html

4. Дискретная математика. Алгоритмы http://rain.ifmo.ru/cat/view.php/theory/graph-general/enumeration-2005

5. Основные понятия теории графов http://www.urtt.ru/bib/dataindex/dm/glava_4~.htm

6.Цепи. Циклы. Связные графы. http://abc.vvsu.ru/Books/l_diskrmat3/page0007.asp

7.Понятие предикатов. http://primat.org/publ/spravochnye_materialy/matematicheskaja_logika_ponjatie_predikata/37-1-0-725

8.Тафтология http://dic.academic.ru/dic.nsf/enc_philosophy

9.Логический выражения. Тафтология. http://www.informikablog.ru/logika/logika-vyskazyvanij-logicheskie-vyrazheniya.html

10.Эквивалентность и порядок. Изоморфизмы. Отношение эквивалентности и порядка. http://www.intuit.ru/studies/courses/1034/144/lecture/3986?page=1

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