Курсовая работа по «Математической логике и теории алгоритмов»
Автор: sidoleg80 • Июнь 27, 2021 • Курсовая работа • 2,275 Слов (10 Страниц) • 523 Просмотры
Санкт-Петербургский государственный
электротехнический университет «ЛЭТИ» имени В.И. Ульянова (Ленина)
Кафедра Алгоритмический Математики
Курсовая работа
по дисциплине
«Математическая логика и теория алгоритмов»
Вариант 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)}
...