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

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

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

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

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

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

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

Вариант 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)}