Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

Курсовая работа по «Математической логике и теории алгоритмов»

Автор:   •  Июнь 27, 2021  •  Курсовая работа  •  2,275 Слов (10 Страниц)  •  438 Просмотры

Страница 1 из 10

Санкт-Петербургский государственный 

электротехнический университет «ЛЭТИ» имени В.И. Ульянова (Ленина) 

Кафедра Алгоритмический Математики

 

 

 

 

 

 

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

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

«Математическая логика и теория алгоритмов» 

 

 

 

Вариант 2

 

 

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

2020г.

2.2. Второй вариант

1. Отношение задано на множестве целых чисел {53, 43, 54, 42, 44, 60, 50, 20}. Для каждого из следующих отношений:

i. проверить, является ли отношение рефлексивным, симметричным, антисимметричным (строгим, нестрогим), транзитивным;

ii. построить матрицы и графы этих отношений;

iii. определить, являются ли эти отношения отношениями эквивалентности, частичного порядка, линейного порядка;

iv. для отношений эквивалентности построить классы эквивалентности;

v. для отношений частичного порядка применить алгоритм топологической сортировки и получить отношение строгого порядка;

vi. построить транзитивные замыкания всех отношений.

xGy каждая из цифр числа x больше цифры числа y , стоящей в соответствующем разряде;

xSy ⇔ ⏐x - y< 5.

Отношение R называется рефлексивным, если для любого х  Х имеет место хRх. Главная диагональ его матрицы содержит только единицы.

Отношение называется антирефлексивным, если ни для какого х  X не выполняется хRх. Главная диагональ его матрицы содержит только нули.

Другими словами:

Отношение R на X рефлексивно, если для любого х  Х пара (x, x)  R.

Отношение R на X антирефлексивно, если для любого х  Х пара (x, x)  R.

Отношение R называется симметричным, если для пары (x, y)  X2 из xRy следует yRx (иначе говоря, для любой пары R либо в обе стороны, либо не выполняется вообще). Матрица симметричного отношения симметрична относительно главной диагонали: cij = cji для любых  i и j.

Отношение R называют антисимметричным, если из xiRxj и xjRxi следует, что xi = xj.

Другими словами:

Отношение R на X симметрично, если для любой пары [pic 1] из условия (x, y)  R следует (y, x)  R.

Отношение R на X антисимметрично, если из условий (x, y)  R и (y, x)  R следует x = y.

Отношение R на X транзитивно, если для любых двух пар [pic 2] и [pic 3] из условий (x, y)  R и (y, z)  R следует (x, z)  R.

Отношение называется отношением эквивалентности (сходства), если оно рефлексивно, симметрично и транзитивно.

Отношение называется отношением порядка, если оно антисимметрично и транзитивно.

Отношение называется отношением нестрогого (частичного) порядка, если оно антисимметрично, транзитивно и рефлексивно.

Отношение R X называется отношением линейного порядка тогда и только тогда, когда:

1) R является отношением частичного порядка;

2)  x, y  X: xRy  yRx.

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

Запишем отношения:

G = {(53,42), (53,20), (43,20), (54,43), (54,42), (54,20), (42,20), (44,20)}

...

Скачать:   txt (26.5 Kb)   pdf (251.7 Kb)   docx (1.1 Mb)  
Продолжить читать еще 9 страниц(ы) »
Доступно только на Essays.club