FN_Alg14 (Лекции 2009), страница 3

Например, отношениекомпланарности трех векторов можно интерпретировать как подмножество в (V3 )3 , т.е. упорядоченных троек векторов, в которое попадают любые тройки компланарных векторов и непопадают тройки некомпланарных векторов. Абстрагируясь от способа описания отношения,мы как раз и приходим к понятию отношения как к некоторой совокупности кортежей.Наиболее распространенными являются отношения арности 2, или бинарные отношения. Бинарное отношение ρ ∈ A2 всегда можно интерпретировать как соответствие ρ: A → A.Иногда вообще отношения и соответствия отождествляют. В самом деле, соответствие ρ: A →→ B легко превратить в соответствие ρ: A ∪ B → A ∪ B, которое фактически есть бинарноеотношение. Использование разных терминов указывает на то, что один и тот же математический объект трактуется в разных смыслах: в первом случае как преобразование, трансформация(т.е.

некоторое действие), а во втором — как некоторая связь между объектами.Для бинарных соответствий вместо (x, y) ∈ ρ часто пишут x ρ y, причем в качестве символаотношения используют специальные знаки, например: x = y, x < y, A ⊂ B, x 6= y, m k n.Отношение на множестве A — ключевое понятие современной алгебры. Второе ключевоепонятие — операция. Операцией арности n на множестве A будем называть любое отображение P : An → A.

Наиболее простые операции: унарные (арности 1) и бинарные (арности 2).Унарные операции представляют собой произвольное отображение P : A → A. Пример унарнойоперации: унарный минус, означающий изменение знака числа. Бинарные операции: сложение,умножение, вычитание, деление, возведение в степень и т.п.Операция арности n обозначается как функция многих переменных f (x1 , . . . , xn ). Для бинарных операций можно выделить три формы записи: префиксную (как функцию двух переменных); инфиксную, в которой операцию часто обозначают специальным знаком (стандартныйспособ записи арифметических операций); постфиксную (знак операции ставится после операндов).Среди бинарных отношений выделяются те, которые имеют специальные свойства:ÔÍ-12ÔÍ-12Определения. Арность.

Бинарные отношения и операции. Способы обозначений операций иотношений. Виды бинарных отношений. Отношение эквивалентности и факторизация.ÌÃÒÓÌÃÒÓ14.3. Отношения и операцииÌÃÒÓÔÍ-12ÌÃÒÓ32ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓМножества Cx для различных элементов x ∈ A называются классами эквивалентности.

Множество всех классов эквивалентности называют фактор-множеством множестваAA по отношению эквивалентности ∼ и обозначают .∼Пример 14.1. Понятие равенства геометрических векторов вводит на множестве всех векторов отношение эквивалентности. Классы эквивалентности по этому отношению называютсвободными векторами, множество всех классов эквивалентности приводит к линейному пространству V3 .ÔÍ-12ÌÃÒÓÔÍ-12Описанная конструкция является математической интерпретацией агрегирования понятий.Например, понятие стул“ выделяет среди всех предметов мебели те, которые используются для”того, чтобы сидеть. С точки зрения математики стул“ — это совокупность всех предметов”мебели, предназначенных для того, чтобы сидеть.Задание отношения эквивалентности на множестве A приводит к разбиению этого множества на непересекающиеся классы эквивалентности.

И наоборот, любое разбиение множествана классы эквивалентностисвязано с некоторым отношением эквивалентности. В самом деле,Sпусть A = i∈I Ai и Ai ∩ Aj = ∅ при i 6= j. Рассмотрим отношение: x ρ y, если x и y принадлежат одному множеству Ai . нетрудно убедиться в том, что это отношение есть отношениеэквивалентности, причем классами эквивалентности по этому отношению будут множества Ai ,i ∈ I.Таким образом, факторизацию можно осуществить либо с помощью отношения эквивалентности, либо непосредственно задав разбиение множества на семейство попарно не пересекающихся подмножеств.Рассмотрим какое-либо отображение f : A → M множества A в множество M . Для любогоy ∈ M множество {x ∈ A: f (x) = y} называется полным прообразом элемента y.

Полныепрообразы различных элементов множества M либо не пересекаются, либо совпадают, т.е.задают разбиение множества A на попарно не пересекающиеся подмножества. Такое разбиениесоответствует отношению эквивалентности x ∼ y ⇔ f (x) = f (y) и может использоваться дляфакторизации множества A. Использование отображений — третий вариант факторизациимножеств.При факторизации множества с помощью отображения, всем элементам одного класса эквивалентности соответствует одно значение отображения, а элементам других классов соответствуют другие значения. В этом смысле значения отображения могут рассматриваться какобобщенная характеристика эквивалентных (неразличимых) элементов.ÌÃÒÓÔÍ-12ÌÃÒÓJ Покажем, что если y ∈ Cx , то Cy = Cx . Пусть z ∈ Cy . Тогда y ∼ z.

В то же время y ∈ Cx и,следовательно, x ∼ y. Из соотношений x ∼ y и y ∼ z в силу транзитивности получаем x ∼ z,т.е. z ∈ Cx . Итак, если z ∈ Cy , то z ∈ Cx , т.е. Cy ⊂ Cx .Пусть z ∈ Cx . Тогда x ∼ z и по-прежнему x ∼ y. С учетом симметричности и транзитивности заключаем, что y ∼ z, т.е. z ∈ Cy и C+ x ⊂ Cy .Мы показали, что если y ∈ Cx , то Cy = Cx . Пусть Cx1 ∩ Cx2 6= ∅ и z ∈ A принадлежитуказанному пересечению. Тогда Cx1 = Cz = Cx2 . IÔÍ-12ÔÍ-12Теорема 14.1.

Для любых x1 , x2 ∈ A имеем либо Cx1 = Cx2 , либо Cx1 ∩ Cx2 = ∅.ÌÃÒÓÌÃÒÓРефлексивное, симметричное, транзитивное отношение называется эквивалентностью(отношением эквивалентности). Пример: отношение коллинеарности векторов в V3 , отношениеравенства геометрических векторов.Выделяют и другие классы отношений.С отношением эквивалентности связана следующая распространенная в математике конструкция.Пусть на множестве A задано отношение эквивалентности ∼.

Для каждого x ∈ A сформируем множество Cx = {y ∈ A: x ∼ y}.ÌÃÒÓÔÍ-12ÌÃÒÓ33ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓВысказывание — это то или иное суждение, утверждение о протекающем процессе, свойствах объекта и т.п. Высказывание, строго говоря, как и множество — неопределимое понятие.Главным свойством высказываний является их истинность: каждое высказывание может бытьистинным или ложным.Высказывания можно объединять в более сложные с помощью логических связок. Логические связки можно рассматривать как операции, заданные на множестве (точнее, классе)всех высказываний.

Главной особенностью логических связок является то, что истинностьсложного, составного высказывания однозначно определяются истинностью исходных высказываний. Соединяя высказывания с помощью логических связок, можно получать весьма сложныевысказывания, об истинности которых нельзя сказать с лету“. Анализ таких высказываний —”одна из задач математической логики.Опишем употребляемые логические связки (табл. 14.1).Таблица 14.1ОперацияЛогическое или“”A∧BA⇒BA⇔BОтрицание¬AОписаниеистина, если хотя бы одно из высказыванийложноистина, если оба высказывания истинныистина, если A ложно или B истинноистина, если оба высказывания истинны илиоба ложныистина, если A ложноÌÃÒÓÔÍ-12Логическое или“ также называют дизъюнкцией, а логическое и“ — конъюнкцией.””При использовании логических связок действуют соглашения о приоритетах:• отрицание имеет более высокий приоритет, чем любые бинарные операции;• остальные логические связки имеют более низкий приоритет, чем алгебраические операции(арифметические, операции над векторами или множествами и т.п.);• дизъюнкция и конъюнкция имеют более высокий приоритет, чем импликация и эквиваленция;• дизъюнкция и конъюнкция, импликация и эквиваленция имеют одинаковый приоритет.Как и в алгебраических выражениях, порядок выполнения операций регулируется приоритетом и расставленными скобками.Наряду с обычными высказываниями используют и высказывания, содержащие переменные.

Они называются предикатами. Истинность таких высказываний зависит от того, какие значения приняли входящие в него переменные. Предикат можно рассматривать как некуювысказывательную форму, которая становится высказыванием, если все входящие в него переменные имеют конкретное значение. Каждая переменная может пробегать некоторое множествозначений, называемое областью значений переменной. Однако область значений переменной впредикате может быть и класс.ÔÍ-12Логическое и“”ИмпликацияЭквиваленцияОбозначениеA∨BÌÃÒÓÔÍ-12ÌÃÒÓВысказывания. Операции над высказываниями. Логические связки. Высказывания с переменными (предикаты). Алгебра предикатов.

Связь алгебры множеств и алгебры предикатов. Логическая интерпретация отношений.ÔÍ-12ÔÍ-1214.4. Элементы математической логикиÌÃÒÓÌÃÒÓВ каждом случае факторизации можно рассмотреть отображение Φ: A → 2A , которое каждому элементу x ∈ A ставит в соответствие его класс эквивалентности Cx . Такое отображениеназывают каноническим.

Каноническое отображение можно рассматривать как математическую реализацию идеи агрегирования: совокупности объектов с аналогичными свойствами всоответствие ставится один элемент, играющий роль символа, знака этой совокупности.ÌÃÒÓÔÍ-12ÌÃÒÓ34ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ35ÔÍ-12Различают предикаты одноместные, двуместные, трехместные и т.д. — по количеству входящих в предикат переменных. Предикат Множество A пустое“ — одноместный предикат,”областью значений переменной в котором является класс всех множеств.

Предикат x 6 y двуместный, а областью значений переменных может быть одна из числовых систем (множествоцелых чисел, рациональных чисел, действительных чисел).Предикаты так же, как и высказывания, можно соединять логическими связками (например,x > 0 ∧ x < 1).Предикат может задавать коллективизирующее свойство при описании множества с помощью свертки или выделения, например {x: x ∈ R ∧ |x − 1| < 2}. В действительности мы любой одноместный предикат можем использовать для описания класса или множества. Наоборот, если множество A определено, то предикат x ∈ A является логическим эквивалентомлюбого другого, описывающего коллективизирующее свойство.