Множества и отношения. Алгебра множеств.Отображения и соответствия. Отношения и операции. Элементы математической логики (Избранные лекции), страница 3

Можно сказать, чтосоответствие — это многозначное отображение, при которого одному значению x может соответствовать несколько (или ни одного) значений y. Нетрудно сформулировать эквивалентноеопределение соответствия F : X → Y как отображения F : X → 2Y , при котором каждому элементу x ∈ X в соответствие ставится некоторое подмножество y ∈ 2Y (иначе y ⊂ Y ).Основная операция над отображениями — композиция отображений. Она без измененийпереносится на соответствия. Композицией G ◦ F соответствий F : X → Y и G: Y → Zназывается множествоÌÃÒÓÌÃÒÓЗамечание 14.3.

Данное определение соответствия (отображения) приводит к тому, чтос этим понятием сливается другое понятие — график соответствия (отображения).Это понятие появляется как прямое обобщение понятия графика функции действительного переменного. Но если график функции действительного переменного — ее удобное графическоепредставление, то абстрактное понятие графика соответствия ничего не добавляет к самомупонятию соответствия.ÌÃÒÓÔÍ-12ÌÃÒÓ31ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14.

МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓ• рефлексивные x ρ x (т.е. ∀x(x, x) ∈ ρ) и иррефлексивные x ρ y ⇒ x 6= y (т.е.∀x(x, x) ∈/ ρ);• симметричные x ρ y ⇒ y ρ x и антисимметричные x ρ y, y ρ x ⇒ x = y;• транзитивные x ρ y, y ρ z ⇒ x ρ z.Рефлексивное, антисимметричное, транзитивное отношение называется порядком (отношением порядка). Пример — отношение неравенства a 6 b на множестве действительных чисел(естественный порядок на множестве действительных чисел).Иррефлексивное, антисимметричное, транзитивное отношение называется строгим порядком. Пример — отношение строго неравенства a < b на множестве действительных чисел.ÔÍ-12• рефлесивное idA ⊂ ρ, иррефлексивное idA ∩ρ = ∅;• симметричное ρ−1 = ρ, антисимметричное ρ−1 ∩ ρ ⊂ idA ;• транзитивное ρ2 ⊂ ρ (здесь ρ2 = ρ ◦ ρ).ÌÃÒÓМожно также выделить нерефлексивные отношения, которые не относятся ни к рефлексивным, ни к иррефлексивным, и несимметричные отношения, которые не относятсяни к симметричным, ни к антисимметричным отношениям.Указанные виды отношений можно определить, используя операции композиции и обратногоотношения (в этих операциях отношение интерпретируется как соответствие):ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓБинарное отношение арности n на множестве A — это любое подмножество n-й декартовой степени An множества A.Отношения служат для описания связей между группами объектов.

Например, отношениекомпланарности трех векторов можно интерпретировать как подмножество в (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ÌÃÒÓВысказывания.