🗊Презентация Элементы математической логики. Отношения

Элементы математической логики Отношения

Унарные отношения Отношения – один из способов задания взаимосвязей между элементами множества. Унарные (одноместные) отношения отражают наличие какого-то определенного признака R у элементов множества М. Пример. М – множество студентов гр.08АСУ; R – «быть светловолосым» R={Гуничев, Хомутинникова, Смирнов, Федотова, Баранов} Унарным отношением R на множестве М называется подмножество R множества М, состоящее из элементов множества М, обладающих свойством R, т.е. а R и RМ.

Бинарные (двухместные отношения) используются для определения каких-либо взаимосвязей, которыми характеризуются пары элементов во множестве М. Бинарные (двухместные отношения) используются для определения каких-либо взаимосвязей, которыми характеризуются пары элементов во множестве М. Например, М-множество людей, отношение R- «жить в одном городе», R = {(Иванов, Сидоров), (Смит, Джонсон), …} Все пары (a,b) элементов из М, между которыми имеет место отношение R, образуют подмножество пар из множества всех возможных пар элементов М  М = М2, называемое бинарным отношением R, т.е. (a,b)R, при этом R М  М.

n-местное отношение

Пример. Пусть . Рассмотрим отношение R A  A , R- множество всех пар (x,y), в которых y делится на x и x не больше 5. Пример. Пусть . Рассмотрим отношение R A  A , R- множество всех пар (x,y), в которых y делится на x и x не больше 5. Т.е. }. Перечислим все такие пары: Т.о. мы задали отношение R A  A

Область определения и область значений Область определения D(x) - это множество значений x, таких, что пара (x,y) принадлежит отношению R: Область значений это множество значений y, таких, что пара (x,y) принадлежит отношению R:

Область определения и область значений Пример. Для отношения рассмотренного в предыдущем примере, область определения и область значений будут соответственно равны: и

Способы задания отношений

Способы задания отношений

Пример. R ={(1,5), (2,4), (3,6), (6,2)} на R Х2, Пример. R ={(1,5), (2,4), (3,6), (6,2)} на R Х2, Х = {1,2,3,4,5,6}

Способы задания отношений

Способы задания отношений Матрица отношения будет иметь вид:

Способы задания отношений

Способы задания отношений

Способы задания отношений

Способы задания отношений Рассмотрим подробнее графический способ задания отношений. Графические методы задания отношения: Координатный метод; Линейно-координатный метод; Линейный метод; Графовый метод.

Координатный метод Координатный метод

Линейно-координатный метод Линейно-координатный метод

Линейный метод Линейный метод Используя параллельные вертикальные линии для D и R получаем диаграммы, в которых стрелки не требуются в принципе, так как мы двигаемся слева направо:

Графовый метод Графовый метод Элементы множества, на котором строится отношение, представлены вершинами графа, а сами отношения - дугами графа. Так как точки в областях D и R одни и те же, их можно объединить.

Задача. По матрице представить отношение списком, графически Задача. По матрице представить отношение списком, графически

Пример. Пусть Пример. Пусть Определено на множестве Зададим списком: Свойства отношения R: рефлексивно, так как х/х=1 для хN несимметрично, поскольку, например, 2 - делитель 4, а 4 не является делителем 2; антисимметрично, так как если x/y R и y/x R, то х=у. транзитивно, так как (2, 4) и (4, 8) влечет (2, 8);

Пример. На булеане множества М={1, 2, 3} задано отношение R – «являться собственным подмножеством». Задать списком, матрицей, графически. Определить его свойства. Пример. На булеане множества М={1, 2, 3} задано отношение R – «являться собственным подмножеством». Задать списком, матрицей, графически. Определить его свойства. Решение. 1)(М)={, {1}, {2}, {3},{1,2}, {1,3}, {2,3}, {1,2,3}}

Свойства отношения R – «быть собственным подмножеством»: Свойства отношения R – «быть собственным подмножеством»: Не является рефлексивным Антирефлексивно, так как любое множество не является своим собственным подмножеством Не является симметричным, так как, например, {1}{1,2}, но {1,2}{1} антисимметрично, так как для любых множеств А и В из того, что АВ и ВА следует А=В. Является транзитивным, так как, если АВ и ВС, то АС

Пример. R Пример. R Задать всеми способами и определить свойства отношения R. N={1,2,3,4,5,6,7,8,9} Решение. Списком: Графически:

Матрица отношения «иметь общий делитель» Матрица отношения «иметь общий делитель»

Свойства отношения R- «иметь общий делитель»: Свойства отношения R- «иметь общий делитель»: нерефлексивно, так как выполняется аRа аR, кроме а=1; Не антирефлексивно; симметрично, так как если пара (а, b) имеет общий делитель, то и пара (b, а) тоже имеет общий делитель; не антисимметрично; не транзитивно, так как, например, 2 и 6 имеют общий делитель, 6 и 9 имеют общий делитель, но 2 и 9 не имеют общий делитель, т.е. (2,6)R, (6,9)R (2,9)R .

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

5) На диаграмме графового представления транзитивного отношения для каждой пары узлов a и c, связанных последовательностью стрелок от a к b и от b к c существуют также стрелки от a к c. 5) На диаграмме графового представления транзитивного отношения для каждой пары узлов a и c, связанных последовательностью стрелок от a к b и от b к c существуют также стрелки от a к c.

Отношения эквивалентности и порядка

Отношение эквивалентности Определение: Отношение эквивалентности– это бинарное отношение на множестве Х, удовлетворяющее следующим условиям: Рефлексивность (xRx) Симметричность (xRy & yRx) Транзитивность (xRy & yRz → xRz)

Отношение эквивалентности Пример. R- «быть равным» на множестве натуральных чисел. Свойства: Рефлексивно, т.к. а=а, аN; Симметрично, т.к. если а=b, то и b=а, а, bN; Транзитивно, т.к. если а=b и b=с, то и а=с, а, b, сN. Т.к. отношение R- «быть равным» на множестве натуральных чисел рефлексивно, симметрично и транзитивно, следовательно, оно является отношением эквивалентности.

Отношение эквивалентности Примеры отношений эквивалентности: Отношение «быть равным», «иметь один и тот же остаток от деления на конкретное число»

Отношение толерантности Определение: Отношением толерантности (или просто толерантностью) на множестве X называется бинарное отношение, удовлетворяющее свойствам рефлексивности (xRx) и симметричности (xRy & yRx), но не обязательно являющееся транзитивным.

Отношение толерантности Отношения «быть другом», «быть знакомым», - отношения толерантности, так как они рефлексивны, симметричны, но не транзитивны. Отношение «иметь непустое пересечение» для множеств – отношение толерантности.

Отношения порядка

Отношение строгого порядка Определение: Отношение строгого порядка– это бинарное отношение на множестве Х, удовлетворяющее следующим условиям: Антирефлексивность (xRx) Антисимметричность (xRy → yRx) Транзитивность (xRy & yRz → xRz)

Отношение нестрогого порядка Определение: Отношение нестрогого порядка– это бинарное отношение на множестве Х, удовлетворяющее следующим условиям: Рефлексивность (xRx) Антисимметричность (xRy → yRx) Транзитивность (xRy & yRz → xRz)

Особые виды отношений

Задача 2. Дан граф некоторого отношения. Дополните его минимальным числом стрелок так, чтобы оно превратилось в эквивалентность. Задача 2. Дан граф некоторого отношения. Дополните его минимальным числом стрелок так, чтобы оно превратилось в эквивалентность.

Задача 3. Назовем два слова сходными, если они состоят из одинако­вого числа букв, причем либо совпадают, либо отличаются лишь одной буквой. Например, КИТ-КОТ. Определить вид отношения. Задача 3. Назовем два слова сходными, если они состоят из одинако­вого числа букв, причем либо совпадают, либо отличаются лишь одной буквой. Например, КИТ-КОТ. Определить вид отношения. Задача 4. Папки в файловой системе компьютера вложены друг в друга, образуя ветвящуюся структуру. Определить вид отношения «вложенности».

Использованные источники Спирина М. С., Спирин П. А. Дискретная математика: Учебник для студентов учр. Среднего проф. Образования.- М.:Издат. Центр «Академия», 2014. Москинова Г. И. Дискретная математика: Учебное пособие,-М.:Логос, 2012 Игошин В.И. Задачник-практикум по математической логике. – М.: Издательский центр “Академия”, 2013. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Издательский центр “Академия”, 2013. window.edu.ru›resource/315/24315 edu.ru›modules.php alleng.ru›d/math/math163.htm Чащина Е.А. Комплект КОС учебной дисциплины ЕН.02. Элементы математической логики основной образовательной программы (ОПОП). – ГБОУ СПО «Прокопьевский политехнический техникум»