Всякое бесконечное множество эквивалентно некоторому своему собственному подмножеству.

Это свойство можно принять за определение бесконечного множества.

Два эквивалентных между собой множества (М~N) называют равномощными или говорят, что они имеют одинаковую мощность. Таким образом, мощность это то общее, что присуще всем эквивалентным между собой множествам. Для конечных множеств понятие мощности совпадает с понятием числа элементов. Мощность множества натуральных чисел, а, следовательно, и любого счетного множества обозначается À₀ (читается: “алеф нуль”). Мощность всех действительных чисел отрезка [0,1] и всех эквивалентных ему множеств называют континуальной или говорят, что эти множества имеют мощность континуума. Эта мощность обозначается символом с (или символом À).

Для конечных множеств, кроме понятия равенства мощностей имеются понятия «больше» и «меньше». Выясним, можно ли эти понятия распространить на бесконечные множества?

Для произвольных множеств А и В обозначим через m(A) и m(B) их мощности. Если А эквивалентно В, то по определению m(A)=m(B). Если А эквивалентно некоторому подмножеству В₁ÌВ, а при этом в А нет подмножества, эквивалентного В, то естественно считать, что m(A)<m(B). Однако логически, кроме указанных возможностей, есть еще две:

а) ВÉВ₁~ А, АÉ А₁~ В;

б) А и В не эквивалентны и ни в одном из них нет подмножеств, эквивалентных другому множеству.

В случае а) множества А и В оказываются эквивалентными друг другу, т.е. m(A)=m(B) . Это утверждает следующая теорема.

Теорема 2. (Кантора – Бернштейна). Пусть А и В два произвольных множества. Если в А имеется подмножество А₁, эквивалентное В, а в В имеется подмножество В₁, эквивалентное А, то А и В эквивалентны между собой.

Случай б), который означал бы существование несравнимых между собой мощностей, на самом деле невозможен.

Таким образом, мощности любых двух множеств А и В или совпадают m(A)=m(B), или удовлетворяют одному из двух неравенств:

m(A) m(B) , m(A)> m(B).

В связи с тем, что мощности можно сравнивать, возникают следующие вопросы: 1) существуют ли мощности, промежуточные между мощностью «самого маленького» из бесконечных множеств – счетного множества и мощностью континуума; 2) существуют ли множества, мощность которых больше, чем мощность континуум; 3) вообще, существует ли «наивысшая» мощность? Оказывается, верна следующая теорема.

Теорема 3. Пусть М – некоторое множество и S(М) – множество всех подмножеств множества М. Тогда мощность S(М) больше мощности самого множества М.

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

2. ОТНОШЕНИЯ

2.1. Понятие отношения

Пусть даны два множества А и В. Рассмотрим множество всевозможных пар вида (a, b), таких, что аÎA, bÎB. Мы получили новое множество, элементы которого имеют иную, чем элементы множеств А и В, природу. Например, таким образом устроены обозначения клеток шахматной доски, декартовы координаты точек плоскости.

Определение 1 Множество А´В = {(а,b)| aÎA, bÎB} – всех упорядоченных пар элементов множеств А и В называется прямым или декартовым произведениеммножеств А и В.

Областью значений бинарного отношения R называется множество E(R) = {b| (a, b)ÎR}, т.е. множество E(R) составляют вторые компоненты (координаты) всех пар, входящих в R (Е(R)ÍВ).

Каждое отношение – это множество и может быть обозначено прописной буквой (что мы и делали до сих пор). Но часто, используя строчные греческие буквы, например r, s и t, бинарные отношения обозначают следующим образом:

а) (a,b)Îr (пара (a,b) находится в r);

b) arb (элемент a связан с b отношением r).

Первое из обозначений естественно для теории множеств, а второе связано с общепринятыми обозначениями известных в математике отношений, например, равенства (a=b) или порядка (a<b).

Для любых бинарных отношений между множествами A и B обычным образом определены теоретико-множественные операции объединения, пересечения и т. д. Новыми для бинарных отношений будут следующие понятия.

Определение 5 Пусть R – бинарное отношение (RÍА´В). Тогда обратным отношением для отношения R называется отношение R^–1 на В´А, заданное равенством R^–1 = {(b,a)| (a,b)ÎR}.

Ясно, что D(R^–1) = Е(R) и Е(R^–1) = D(R).

Определение 6 Композицией или произведением двух бинарных отношений R₁ÍА´В и R₂ÍА´С называется отношение, которое обозначается и состоит из пар (a,c) таких, что aÎA, cÎC и существует bÎB с условием (a,b)ÎR₁ и (b,c)ÎR₂ .

Очевидно, что является бинарным отношением на А´С.

Для любых бинарных отношений выполняются следующие свойства:

1) (R^–1)^–1=R;

2)( )^–1=R₁ ^–1 R₂^–1.

Упражнение 1. Доказать свойства 1) и 2).

2.3. Способы заданий бинарных отношений

Рассмотрим способы заданий бинарных отношений, отличные от тех, которые указаны в первом разделе для произвольных множеств. В основе новых способов заданий бинарных отношений лежит особая структура их элементов.

Пусть r ÍА´В и A={а₁, а₂, ..., а_n}, B={b₁, b₂, …, b_m}. Отношению r поставим в соответствие матрицу С=(с_ij) размерности n´m (i=1,2, ..., n; j=1, 2, ..., m), в которой с_ij=1 тогда и только тогда, когда (а_i,b_j )Îr, в остальных случаях с_ij=0. Такая матрица полностью определяет бинарное отношение r и называется матрицей бинарного отношения r. Если rÍА², то матрица отношения будет квадратной. Такой способ задания отношений позволяет действия над отношениями моделировать операциями над соответствующими бинарными матрицами, т.е. матрицами, у которых любой элемент либо 0, либо 1.

Для наглядности используют графический способ задания бинарного отношения r на множестве А={а₁, а₂, ..., а_n}. Он состоит в том, что элементы множества А изображаются точками. При этом две точки а_i и а_j соединяются направленной дугой тогда и только тогда, когда (а_i,а_j)Îr. Существуют графические способы представления бинарных отношений между различными множествами.

Еще один способ задания бинарного отношения r на множестве А={а₁, а₂, ..., а_n} связан с понятием фактор–множества. Для каждого элемента а_i множества А определяется подмножество А_i всех тех элементов из А, которые находятся с ним в данном отношении, т.е. А_i={x| xÎA и (a_i,х)Îr} (иногда его называют образом элемента а_i). Совокупность таких подмножеств А_i (i = 1,2,...,n) называется фактор–-множеством множества А по отношению r и обозначается А/r. Если в одну строку выписать все элементы множества А , а во второй строке под каждым из них – соответствующие элементы (образы) фактор–множества А/r, то очевидно, что отношение r будет полностью задано.

Пример 2. Пусть на множестве А={а₁=2, а₂=3, а₃=4, а₄=6, а₅=12}, бинарное отношение s определено следующим образом: элемент a множества A находится в отношении s с элементом b ((a,b)Îs) тогда и только тогда, когда a делит b, и а меньше b. Задать это отношение всеми возможными способами.

В задаче отношение s как множество определено с помощью характеристического свойства.

1. Зададим отношение s перечислением его элементов:

s = {(2,4), (2,6), (2,12), (3,6), (3,12), (4,12)}.

2. Составим матрицу отношения s:

С_s = .

3. На рисунке 4 изображено одно из возможных графических заданий отношения s.

12 3

· ·

· · ·

4 2 6

Рис. 4.

4. Зададим отношение s с помощью фактор–множества А/s:

2 3 4 6 12

{4, 6, 12} {6, 12} {12} {12} Æ.

Очевидно, что по рисунку 4, например, можно задать отношение перечислением, записать его матрицу, перейти к фактор–множеству, и наоборот.

2.4. Свойства бинарных отношений.

Очевидно, что, изучая отношения в самом общем виде, нельзя получить много содержательной информации, так как они представляют собой просто подмножества прямого произведения множеств. С другой стороны можно выделить ряд специальных свойств, которыми обладают хорошо известные в математике отношения, например, отношение равенства и отношение порядка. Рассмотрим некоторые из основных свойств, которыми могут быть наделены отношения.

Определение 7 Пусть q – бинарное отношение на множестве А. Тогда:

(1) q рефлексивно, если (а,а)Î q (или в других обозначениях: аqа) для всех аÎА;

(2) q симметрично, если из (а,b)Îq следует, что (b,a)Îq (иначе: аq b Þ bq a);

(3) q транзитивно, если из (а,b)Îq и (b,c)Îq следует, что (a,c)Îq (иначе: аqb и bqc Þ aqc);

(4) q антисимметрично, если из (а,b)Îq и (b,a)Îq следует, что a=b (иначе: аq b и bq a Þ a=b).

Пример 3. Отношение включения (Í) на множестве всех подмножеств некоторого множества А является бинарным отношением, причем оно рефлексивно (ХÍХ), транзитивно (ХÍY и YÍZ Þ XÍZ) и антисимметрично (ХÍY и YÍX Û X=Y).

Пример 4. Отношение «меньше» (<) на множестве натуральных чисел, очевидно, обладает свойством транзитивности, но не является ни рефлексивным, ни симметричным.

Заметим, что свойства симметричности и антисимметричности не являются взаимоисключающими. Легко проверить, что для любого множества А отношение I_А является и симметричным, и антисимметричным. Приведем пример отношения, которое не является ни симметричным, ни антисимметричным. Пусть s отношение, которое определено на множестве Р всех людей следующим образом: хsу Û х – брат у. Для семьи, в которой два братьа p и q и сестра r, имеем: ps r, но не rs p, т.е. отношение s не является симметричным. Это отношение также не является антисимметричным, так как ps q и qs p, хотя, p и q различны.

Эти свойства довольно просто описать при графическом задании отношения:

а) отношение рефлексивно тогда и только тогда, когда для каждой точки существует стрелка, которая начинается и заканчивается в этой точке (петля);

б) отношение симметрично тогда и только тогда, когда для каждой стрелки, соединяющей две точки, существует стрелка, которая соединяет эти точки в обратном направлении;

в) отношение транзитивно тогда и только тогда, когда для каждой пары точек х и у, связанных последовательностью стрелок, идущих от х к а₁, от а₁ к а₂, ..., от а_n-1 к а_n, от а_n к у, существует также стрелка от х к у;

г) отношение антисимметрично тогда и только тогда, когда не существует двух различных точек, связанных парой противоположно направленных стрелок.

Если С_s=(с_ij)_{n´ n} – матрица бинарного отношения s на множестве А, то отношение s:

а) рефлексивно Û с_ii=1 для всех i;

б) симметрично Û с_ij=1 Þ с_ji=1;

в) транзитивно Û с_ij=1 и с_jk=1 Þ с_ik=1;

г) антисимметрично Û с_ij=с_ji=1 Þ i=j.

В частности, для отношения s из примера 3 по матрице С_s, легко заключить что оно обладает только свойством транзитивности.

2.5. Отношение эквивалентности

Определение 8 Бинарное отношение q на множеств А называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Если q – отношение эквивалентности на множестве А, то классом эквивалентности, порожденным элементом а, называется подмножество множества А, состоящее из тех элементов bÎА, для которых aq b .

Класс эквивалентности, порожденный элементом а, обозначается через [a] или С_а. По определению имеем: [a]={b| bÎA и aq b}.

Пример 5. Отношение равенства на множестве целых чисел, очевидно, есть отношение эквивалентности. При этом каждый класс эквивалентности состоит из одного элемента, т.е. для любого целого числа х [x]={x}.

Пример 6. Отношение подобия на множестве всех треугольников является отношением эквивалентности. Каждый класс эквивалентности представляет собой множество подобных между собой треугольников.

Пример 7. Покажем, что отношение сравнения по модулю натурального числа n на множестве целых чисел Z: хºy(mod n) тогда и только тогда, когда х–у делится на n, есть отношение эквивалентности. Это отношение рефлексивно на Z, так как для любого хÎZ х–x=0, и, следовательно, делится на n. Если х–у делится на n, то и у–х делится на n, это означает симметричность отношения. Это отношение транзитивно, так как если х–у делится на n, то для некоторого целого r имеем х–у rn, а если у–z делится на n, то для некоторого целого q имеем у–z=qn. Складывая эти два равенства, получаем: x–z=(r+q)n, т.е. x–z делится на n, так как (r+q)–целое число.

Данное отношение порождает следующие классы эквивалентности: вместе с любым целым числом а в этом же классе эквивалентности содержатся все числа вида а+kn, где k – целое число. Очевидно, что числа 0, 1, 2, ... , n–1 порождают различные классы эквивалентности: [0], [1], [2], ... , [n–1]. Они называются классами вычетов по модулю n. Поскольку любое целое число а можно представить в виде а=qn+r, где 0£r<n, то все остальные классы эквивалентности совпадают с указанными выше.

Пример 8. Отношением эквивалентности на множестве всех студентов университета, очевидно, является отношение принадлежности одной учебной группе. Классом эквивалентности в этом случае является множество студентов одной группы.

Для любого отношения эквивалентности q на множестве А справедливы следующие утверждения:

· Если аÎА, то аÎ[a] (т.е. каждый элемент множества А принадлежит порожденному им классу эквивалентности).

· Если а, bÎА и aq b, то [а]=[b] (т.е. класс эквивалентности порождается любым своим элементом).

Справедливость первого утверждения следует из свойства рефлексивности отношения q : аq а и, следовательно, аÎ[a] .Докажем второе утверждение. Пусть сÎ[b]. Тогда bq c и в силу транзитивности отношения q, аq с, т.е. сÎ[a]. Отсюда [b]Í[a] . Аналогично в силу симметричности q можно показать, что [а]Í[b], а значит, [а]=[b].

Из приведенных выше утверждений следует, что любое отношение эквивалентности q на множестве А позволяет представить это множество в виде объединения попарно непересекающихся подмножеств – классов эквивалентности. Действительно, каждый элемент а из А лежит в порожденном им классе [a]. При этом любые два класса эквивалентности либо не пересекаются, либо совпадают. Предположим, что два различных класса эквивалентности пересекаются, т.е. существует такой элемент с, что cÎ[a]Ç[b].Это означает, что аq с, и bq с, следовательно [a]=[c], [b]=[c]. Откуда, [a]=[b]. Такое представление множества А имеет специальное название.

Определение 9 Разбиением множества А называется совокупность попарно непересекающихся подмножеств А_k таких, что каждый элемент множества А принадлежит одному и только одному из этих подмножеств, т.е.

АÈА_k, kÎK и А_iÇА_j=Æпри i¹j.

Итак, выше нами фактически установлена

Теорема 1. Всякое отношение эквивалентности определяет разбиение множества на классы эквивалентности относительно этого отношения.

С другой стороны справедлива обратная теорема.

Теорема 2. Всякое разбиение множества А определяет на нем отношение эквивалентности q : аq b тогда и только тогда, когда a и b принадлежат одному подмножеству разбиения.

Действительно, отношение q, очевидно, рефлексивно и симметрично. Докажем транзитивность. Пусть aq b и bq c, тогда a, bÎA₁, b,cÎA₂, где A₁ и A₂ – подмножества из разбиения множества А. Поскольку bÎA₁, bÎA₂, то A₁=A₂.

Если отношение эквивалентности задано матрицей, то с помощью перестановки строк (столбцов) матрицу отношения можно привести к такому виду, что около главной диагонали расположены подматрицы (клетки), состоящие из единиц, остальные элементы матрицы равны нулю. Каждая такая подматрица (клетка) соответствует классу эквивалентности.

Пример 9. Бинарное отношение t на множестве А={a₁,a₂,a₃,a₄,a₅} задано матрицей

С_t= .

Показать, что t отношение эквивалентности, указать соответствующее ему разбиение множества А.

Матрица С_t имеет клеточную структуру. Рассмотрим соответствующее ей разбиение множества А: , где . Согласно теореме 2 данное разбиение задает отношение эквивалентности, которое, как легко видеть, совпадает с отношением t.

2.6. Отношение порядка. Упорядоченные множества.

Определение 9 Бинарное отношение j, заданное на множестве А, называется отношением порядка, если оно обладает свойствами:

1) рефлексивности (для любого аÎА аj а);

2) транзитивности (если ajb и bjc , то ajc;

3) антисимметричности (если ajb и bja, то a = b).

Отношение порядка играет важную роль в математике, для него принято специальное обозначение « £ ». В этих обозначениях свойства рефлексивности, транзитивности и антисимметричности записываются следующим образом:

1) а£а для всех а;

2) если a£b и b£c, то a£c;

3) если a£b и b£a, то а = а.

Запись a£b означает, что пара (a,b) принадлежит отношению порядка j ((a,b)Îj Í A´A). При этом говорят, что элемент а меньше либо равен (не превосходит) b или, что он содержится в b. Отношение j^–1, обратное к отношению порядка j (аj^–1bÛbja), само является отношением порядка. Порядок (£)^–1 называют двойственным к порядку £ и обозначают символом ³. Будем писать a<b, если a£b и а¹ b. Таким образом, мы задали отношение строгого порядка, которое обладает только свойством транзитивности.

Определение 10 Частично упорядоченным множеством называется множество, на котором задано отношение порядка.

Таким образом, частично упорядоченное множество определяется двумя объектами: самим множеством А и определенным на нем отношением порядка j – < А, j >. При этом на одном и том же множестве порядок можно задать различными способами, т. е. получить различные частично упорядоченные множества. В частности, таким образом получается так называемое двойственное частично упорядоченное множество <А, j^–1>.

Пример 10. Множество натуральных чисел N с обычным отношением порядка £ (a£bÛb–a³0) является частично упорядоченным множеством: < N , £>.

Пример 11. Легко убедиться, что бинарное отношение j, которое задано на множестве натуральных чисел N следующим образом: ajb Û b делится на а без остатка, удовлетворяет условиям 1)–3) определения 9, т.е. является отношением порядка. Следовательно, < N, j > – частично упорядоченное множество.

Пример 12. Рассмотрим множество М = {a,b,c,0,1}. Бинарное отношение R на нем зададим перечислением пар: R = {(0,0), (0,a), (0,b), (0,1), (a,a), (a,1), (b,b), (b,1), (c,c), (c,1), (1,1)}. Свойства рефлексивности, транзитивности и антисимметричности выполняются (проверьте), следовательно, это отношение порядка. Система <М,R> является частично упорядоченным множеством.

Отметим, что в примерах 9 и 10 мы имеем дело с одним и тем же множеством N, но с различными частично упорядоченными множествами.

С другой стороны, если на множестве А = {2,4,6,10,60} отношение порядка определено также, как в примере 10, то достаточно очевидно, что это частично упорядоченное множество устроено (ведет себя) также, как и множество в примере 12 в смысле отношения порядка. Фактически, если переобозначить элементы множества А: 2«0, 4«a, 6«b, 10«c, 60«1, то получим упорядоченное множество из примера 11. Такое переобозначение можно сделать не единственным образом, но суть его состоит в том, что мы нашли взаимно однозначное соответствие между множествами А и М, причем такое, которое «сохраняет» отношение порядка. Таким образом, мы приходим к понятию изоморфизма упорядоченных множеств.

Пусть А и А¢ – два частично упорядоченных множества и g – взаимно однозначное отображение А на А¢. Отображение g называется сохраняющим порядок, если из того, что a £ b (a, bÎ A), следует, что g(a) £ g(b).

Определение 11 Взаимно однозначное отображение g частично упорядоченного множества А на А¢ называется изоморфизмом, а сами частично упорядоченные множества А и А¢ изоморфными, если g(a)£g(b) тогда и только тогда, когда a£b (a, bÎA).

Пусть А – частично упорядоченное множество из примера 9, а А¢ – из примера 10. Взаимно однозначное отображение g, которое каждому натуральному числу n ставит в соответствие его само (g(n) = n), будет сохранять порядок, но не будет изоморфизмом. Действительно, если m делится на n без остатка (n£m (n, mÎA)), то очевидно, что m–n = g(m)–g(п)³0, т.е. g(n)£g(m), следовательно g сохраняет порядок. Однако, отображение g не является изоморфизмом частично упорядоченных множеств примеров 9 и 10 хотя бы в силу того, что в частично упорядоченном множестве А не любая пара его элементов сравнима (например, m = 5, n = 3), а в множестве А¢ любая пара элементов сравнима, так как для любых натуральных чисел m и n либо m £ n, либо n £ m.

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

Рассмотрим частные случаи упорядоченных множеств.

Определение 12 Частично упорядоченное множество < А,£ > называется линейно упорядоченным, если в нем сравнимы любые два элемента, т.е. для любых a и b из А либо a£ b, либо b£ a.

В примере 9 множество линейно упорядочено, а в примерах 10 и 11 множества таковыми не являются. В условиях примера 10 натуральное число 2 несравнимо с любым натуральным нечетным числом. В примере 11 – несравнимы между собой элементы a, b, c.

Любое подмножество линейно упорядоченного множества само является таковым.

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

Введем еще более узкое, но весьма важное понятие полной упорядоченности. Для этого определим минимальный элемент частично упорядоченного множества. Элемент а частично упорядоченного множества А называется минимальным (наименьшим), если из b£а следует, что b=a. По аналогии элемент с частично упорядоченного множества А называется максимальным (наибольшим), если из с£b следует, что b c.

Определение 13 Линейно упорядоченное множество называется вполне упорядоченным, если любое его непустое подмножество имеет минимальный (наименьший) элемент.

Множество всех рациональных чисел по отношению к естественному порядку является линейно упорядоченным, но не вполне упорядоченным, так как в нем нет минимального (и максимального) элемента.

Множество всех рациональных чисел отрезка [0,1] (с естественным отношением порядка) имеет минимальный элемент – 0 и максимальный элемент – 1, но не является вполне упорядоченным множеством, так как, например, его подмножество положительных рациональных чисел наименьшего элемента не имеет.

Множество натуральных чисел N (с естественным отношением порядка) не имеет наибольшего элемента, но имеет наименьший элемент – 1. В силу того, что любое его непустое подмножество обладает наименьшим элементом, N является не только линейно упорядоченным, но и вполне упорядоченным множеством.

Ясно, что всякое (непустое) подмножество вполне упорядоченного множества само вполне упорядочено.

Частично упорядоченные множества можно изобразить графически (как бинарное отношение), но поскольку любое отношение порядка рефлексивно и транзитивно, то из соответствующей диаграммы удаляют все петли и транзитивно замыкающие дуги. Такие диаграммы, задающие частично упорядоченные множества, называются диаграммами Хассе. Диаграммы Хассе известны с конца XIX века, их применяли в генеалогии для задания родства.

Пример 13. Пусть А = {1,2,3,5,30}. Рассмотрим два упорядоченных множества: <A; £ > и < А; j >. В первом задан естественный порядок, а во втором – aj bÛ b делится на а без остатка. Изобразим соответствующие им диаграммы Хассе.

· 30

· 5

· 3

· 2

· 1

Рис. 5а.

· 30

2 · 3· ·5

· 1

Рис. 5б.

Очевидно, что эти два частично упорядоченных множества неизоморфны. Множество, изображенное на рисунке 5а, линейно (и даже вполне) упорядочено, а множество на рисунке 5б не является линейно упорядоченным.

2.7. Функции и отображения.

Определение 14Функцией из А в В называется однозначное бинарное отношение fÍ А´В, т.е. если (a,b)Î f и (a,с)Îf, то b=c (aÎA; b,cÎB).

Поскольку, любая функция являются бинарным отношением, т.е. множеством, то, применяя интуитивный принцип объемности, получаем: две функции f и g равны (f=g), если они состоят из одних и тех же элементов. Область определения и область значения функции обозначаются и определяются так же как для бинарного отношения.

Если f – функция из Х в Y, то вместо (x,y)Îf привычно пишут у=f(x) и говорят, что у – значение, соответствующее аргументу х, или у – образ элемента х при отображении f. При этом х называют прообразом элемента у. Функцию f из X в Y (fÍX´Y) называют одноместной или функцией одной переменной. Это понятие можно обобщить на случай функции нескольких переменных следующим образом.

Функция f из Хⁿ в Y (fÎ Хⁿ´Y) называется n-местной функцией из Х в Y или функцией n переменных и обозначается у = f(х₁, x₂, ..., x_n).

Определение 15 Функция fÍА´В, у которой область определения D_f совпадает с множеством А, называется отображением множества А в множество В или всюду определенной функцией. Если при этом область значений Е_f совпадает с В (Е_f =B), то f –отображение А на множество В.

Иногда говорят, что отображение f устанавливает однозначное соответствие между множествами А и В. Отображение обозначают: f: А®В или .

Пусть f – отображение множества М в множество В. Совокупность всех элементов из М, образом которых является данный элемент b Î В, называется прообразом (или, точнее, полным прообразом) элемента b и обозначается f^–1(b), т.е. f^–1(b)={m| mÎM и f(m)=b}.

Если АÍМ, то образом множества А при отображении f называется множество f(A)={x| xÎB, x=f(a) для всех аÎА}, т.е. совокупность образов всех элементов множества А. В свою очередь для каждого подмножества C из B множество f ^–1(C)={m| m=f^–1(c) для всех cÎC} называется прообразом множества C, т.е. f^–1(C) – совокупность всех тех элементов из М, образы которых принадлежат C. Если ни один элемент c из C не имеет прообраза, то полный прообраз f ^–1(C)=Æ.

Сформулируем основные самые общие свойства отображений.

Теорема 3. Прообраз объединения двух множеств равен объединению их прообразов:

f ^–1(АÈВ) = f ^–1(А)È f ^–1(В).

Прообраз пересечения двух множеств равен пересечению их прообразов:

f ^–1(АÇВ) = f ^–1(А)Çf ^–1(В).

Теорема 3 остается в силе для объединений и пересечений любого (конечного или бесконечного) числа множеств.

Теорема 4.Образ объединения двух множеств равен объединению их образов:

f (АÈВ) = f (А)Èf (В).

Утверждение аналогичное теореме 4 для пересечений не имеет места, т.е. в общем случае образ объединения двух множеств не совпадает с пересечением их образов.

Например, если отображение f – это проектирование плоскости на ось Ох, то множество А = {0£ х£1, у=0} и множество В={0£х£1, у=1} не пересекаются (АÇВ = Æ), а их образы, очевидно, совпадают (f(A) = f(B)).

2.8. Операции. Понятие алгебры.

Рассмотрим важный частный случай отображений – операции.

Определение 15 Отображение f из А в A называется операцией на множестве А.

В этом случае f(a)ÎA и операцию f называют унарной.

На множестве действительных чисел Rпримерамиунарных операций являются:

1) операция нахождения обратного числа: f =x^–1, x ¹ 0, или в других обозначениях: f ={(x,x^–1)| xÎR, x ¹ 0};

2) операция нахождения противоположного числа: f(x)=–x, или иначе: f ={(x,–x)| xÎR};

3) операция f ={(x,0)| xÎR}, которая любое действительное число х отображает в 0.

Определение 16 Отображение из Аⁿ в А называется n-местной (n-арной)операцией на множестве А.

В случае n=2 операция называется бинарной, а при n=3 – тернарной. На множестве векторов трехмерного пространства R₃векторное умножение векторов – бинарная операция, а двойное векторное произведение – тернарная.

Операции сложения и умножения действительных чисел являются бинарными на множестве действительных чисел R. Например, операция сложения: f = {((x,y),x+y)| x, yÎR}.

Определение 17 Алгеброй называется совокупность двух множеств: некоторого множества А и множества F – операций, определенных на А.

Алгебры принято обозначать готическими буквами: Á, Â и т.д. Для алгебры Â =<А, F> множество А называется носителем алгебры, а множество F ее сигнатурой.

Пример 14. Множество натуральных чисел N c определенными на нем бинарными операциями сложения (+), умножения (´) является алгебрoй: <N; +, ´>. Сигнатура этой алгебры состоит из двух бинарных операций: F = {+, ´}.

Алгебры отличаются одна от другой носителями, сигнатурами и, наконец, свойствами, которыми обладают операции в этой алгебре.

Множество всех подмножеств (булеан) некоторого множества М с определенными на нем бинарными операциями объединения, пересечения и унарной операцией дополнения является алгеброй:

Â_K = <S(М); È, Ç, ¢>.

Иногда считают, что сигнатура данной алгебры кроме указанных трех операций содержит две нульарны (0-арные) операции: выделено пустое множество Æ и само множество М. Как мы видели в 1.4. эти операции удовлетворяют определенным свойствам (1–9).

Алгебра Â_K = <S(М); È, Ç, ¢,Æ, М> называется алгеброй Кантора. Существуют алгебры с другими носителями, на которых определены две бинарные, одна унарная операция и выделены два элемента, причем для них справедливы свойства (1–9) алгебры Кантора. Рассматривая все такие алгебры, мы приходим к понятию абстрактной булевой алгебры. Алгебры Буля находят широкое применение в прикладных задачах.

Определение 20 Булевой алгеброй называется непустое множество В с двумя бинарными операциями Ú, Ù, двумя отмеченными элементами 0, I и одной унарной операцией`, причем для любых a ,b, cÎB выполняются следующие равенства:

(А1) аÚb = bÚa,

аÙb = bÙa (коммутативность);

(A2) aÚ(bÚc) = (aÚb)Úc,

aÚ(bÚc) = (aÚb)Úc (ассоциативность);

(A3): аÚ(bÙc) = (aÚb)Ù(aÚc),

аÙ(bÚc) = (aÙb)Ú(aÙc) (дистрибутивность);

(A4): aÙa = a,

aÚa = a (идемпотентность);

(А5): аÙ(аÚb) = a,

аÚ(аÙb) = a (поглощение);

(А6): аÙ0 = 0, аÚ0 = а,

аÙI = а, аÚI= I (универсальные границы);

(А7): аÙ =0, aÚ =0 (дополнение);

(А8): = a (двойное дополнение или инволютивность);

(А9): ,

(законы де Моргана).

Отметим, что это определение носит аксиоматический характер. Мы считаем заданными пять операций на множестве В (две бинарные: Ú и Ù, одна унарная` , и две нульарные: 0, I) и перечисляем 19 тождеств, сгруппированные в девять аксиом (постулатов). Алгебра считается булевой алгеброй тогда и только тогда, когда она имеет такой набор операций (сигнатуру) и в ней выполняются все выписанные аксиомы. Очевидно, что способ обозначения операций не играет роли. Операции Ú и Ù называют соответственно булевой суммой, или объединением, и булевым произведением, или пересечением.

Абстрактная булева алгебра может быть задана другим списком аксиом. В частности приведенный выше набор аксиом является избыточным, т.е. некоторые аксиомы можно исключить, так как они являются следствием других. В нашем случае, например, аксиомы А1, А8, А9 следуют из остальных шести. С другой стороны список аксиом можно пополнить следствиями из них. Например, в любой булевой алгебре справедливы тождества:

аÙ(bÚ(aÙc)) = (aÙb)Ú(aÙc),

аÚ(bÙ(aÚc)) = (aÚb)Ù(aÚc),

которые называются законами модулярности и могут быть получены из аксиом А1 – А5. Действительно, пользуясь последовательно аксиомами А3, А2, А5 и А3, получаем

аÙ(bÚ(aÙc)) = аÙ((bÚa)Ù(bÚc)) = (аÙ(bÚa))Ù(bÚc) =

= аÙ(bÚc) = (аÙb)Ú(aÙc).

Очевидно, что доказательство второго закона модулярности получается из доказательства первого заменой каждого символа Ù на символ Ú и наоборот. Последнее замечание является частным случаем, более общего принципа двойственности, который можно сформулировать следующим образом:

любое утверждение верное в булевой алгебре, в формулировке которого встречаются только операции Ù, Ú и , остается справедливым, если в его формулировке всюду заменить Ù на Ú, и наоборот.

Это следует из того, что при такой замене множество аксиом А1 – А9 в целом не изменяется. Поэтому любое доказательство превращается в доказательство двойственного утверждения.

Изоморфизмоммежду алгебрами Â₁ =<А₁, F₁ >и Â₂=<А₂, F₂ >называется взаимно однозначное соответствие jмежду элементами носителей и сигнатур такое, что

f_m(a_1,..., a_n) = a Û j(f_m)(j(a₁)..., j(a_n))= j(a),

гдеa₁, ..., a_n, aÎА₁, f_mÎF₁, j(a₁), ..., j(a_n), j(a)ÎA₂, j(f_m)ÎF₂.

При этом алгебры Â₁ и Â₂ называются изоморфными. Все законы алгебры Â₁ справедливы и в изоморфной ей алгебре Â₂.

Алгебру Кантора Â_K = < S(М); È, Ç,` >, очевидно, можно рассматривать как модель (интерпретацию) булевой алгебры, считая, что Ç«Ù, È«Ú, Æ«0, M«I. Более того, любую конечную булеву алгебру можно рассматривать как алгебру Кантора для некоторого конечного множества М.

Теорема 5. Любая конечная булева алгебра изоморфна алгебре всех подмножеств некоторого множества.

3. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

3.1. Моделирование высказываний

Согласно одному из самых распространенных определений, логика есть анализ методов рассуждений. Изучая эти методы, логика интересуется в первую очередь формой, а не содержанием доводов в том или ином рассуждении. Логика не интересует истинность или ложность отдельных посылок или заключений, он лишь желает знать, вытекает ли истинность заключения из истинности посылок. Одна из основных задач логики – систематическая формализация и катологизация правильных способов рассуждений.

Математическая логика, как любая другая математическая дисциплина предметом своего изучения имеет математическую модель, в данном случае – модель человеческих рассуждений и правил умозаключений.

В содержательной логике под высказыванием понимается законченная мысль. Это может быть некоторое предложение, о котором имеет смысл говорить истинно оно или ложно, или несколько предложений, связанных между собой определенным образом. Таким образом, можно выделить элементарные высказывания (первокирпичики) и более сложные высказывания, которые по определенным правилам строятся из элементарных высказываний.

В математической логике элементарные высказывания моделируются элементами некоторого произвольного (непустого) множества М. Будем называть М множеством элементарных высказываний, а его элементы – элементарными высказываниями, и обозначать, как это принято в математической логике, большими латинскими буквами (иногда с индексами). При анализе способов построения сложных высказываний в разговорной речи можно выделить основные связки: «не», «и», «или», «если ..., то...», «тогда и только тогда» и др. В математической модели им соответствует некоторое множество, элементы которого называются логическими (пропозициональными) связками. Множество логических связок включает в себя следующие связки:

– отрицание («не»),

& – конъюнкция («и»),

Ú – дизъюнкция («или»),

® – импликация («если ..., то ...»),

º – эквивалентность («тогда и только тогда»).

Кроме того, в математической логике используются и другие связки в частности, " – квантор всеобщности («каждый», «любой», «всякий»), $ - квантор существования («существует», «найдется»). Множество элементарных высказываний и множество логических связок никогда не пересекаются.

Заметим, что в литературе встречаются другие обозначения логических связок. Например, конъюнкцию обозначают «Ù», импликацию – «É», а эквивалентность – «~».

Формализуем правила построения сложных высказываний из элементарных высказываний. Из множества элементарных высказываний М с помощью множества логических связок построим новое множество Ф, которое будем называть множеством логических формул. Правило построения множества Ф состоит из 3-х условий (такой способ определения называют индуктивным).

Определение 1 Множество Ф является множеством логических формул, если выполняются следующие условия:

1) всякое элементарное высказывание есть формула, т.е. М Í Ф;

2) если F₁ и F₂ – формулы (F₁,F₂ÎФ), то (ØF₁), (F₁&F₂), (F₁ÚF₂),

(F₁ -®F₂), (F₁ ºF₂) – формулы;

3) других формул нет.

Пример 1. Записать в виде логической формулы следующее предложение: «если целое число не делится на два, то оно нечетное».

Введем обозначения для элементарных высказываний: А – «целое число делится на два», В – «оно (целое число) нечетное». Тогда сложное предложение описывается формулой: ((ØА)®В). При составлении формулы мы точно следовали определению 1. Действительно, так как А и В –элементарные высказывания, то они формулы (условие 1) определения 1, следовательно по условию 2) формулами являются выражения (ØА) и ((ØА)®В). Однако, записи (ØА®В), (ØА)®В нельзя назвать формулами, согласно определению 1, так как в первой не заключено в скобки высказывание (ØА), а во второй – целиком все высказывание ((ØА)®В). Это противоречит условию 3) определения 1.

Данный пример показывает, что при записи логических формул нужно соблюдать формальные правила, сформулированные в определении 1. Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Кроме того, можно опускать внешние скобки.

Например, формула F = (A®(Ø(СÚ(A&B)))), учитывая принятые соглашения, может быть записана следующим образом

F = A®(Ø(СÚA&B)).

3.2. Таблицы истинности

Рассмотрим высказывания с точки зрения их истинностных значений. В содержательной логике под высказыванием подразумевается повествовательное предложение, о котором можно определенно сказать истинно оно или ложно. Например, предложение «квадрат является ромбом» – высказывание, причем истинное, а предложение «рассмотрим множество всех функций» высказыванием не является, так как нельзя с определенностью утверждать, истинно оно или ложно. Таким образом, в нашей математической модели каждое элементарное высказывание нужно рассматривать как переменную величину (пропозиционную переменную), которая принимает только два значения «истина» и «ложь». Значение «истина» принято обозначать через единицу 1, а «ложь» – через ноль 0. Итак, всякое элементарное высказывание (пропозиционная переменная) формально может принимать одно из значений: 1 или 0.

Формулы логики высказываний, которые мы определили выше, являются высказываниям и, следовательно, тоже должны принимать одно из истинностных значений. Для формул, которые являются таковыми по условию 1) (элементарные высказывания), мы уже приняли соглашения. Чтобы определить истинностное значение любой формулы, которая не является элементарным высказыванием, нужно, прежде всего, определить значения формул: (ØА), (А&В), (А ÚВ), (А ®В), (А ºВ) в зависимости от значений входящих в них элементарных высказываний. Это делается с помощью так называемых таблиц истинности.

Таблица истинности.

Таблица 1.

Из определения формулы следует, что с помощью таблицы истинности можно определить истинностные значения любой формулы. Ясно, что, если формула содержит n элементарных высказываний, то она имеет 2ⁿ значений, т.е. таблица истинности этой формулы содержит 2ⁿ строк. Рассмотрим пример построения таблицы истинности для логической формулы.

Пример 2. Найти истинностные значения формулы

F=((AºB)®((ØA)&B)).

Убедимся, что F формула. По определению 1 (условие 2) высказывания (ØA), (A ºB) являются формулами. Тогда в силу этого же условия формулами являются ((ØA)&B) и F = ((AºB)®((ØA)&B)). Рассмотренные нами выше составные части формулы F, которые сами являются формулами, называются подформулами формулы F.

Для нахождения всех истинностных значений формулы F последовательно найдем значения всех подформул. Представим эти вычисления в виде общей таблицы истинности.

Таблица 2.

Логические связки: отрицание, конъюнкцию, дизъюнкцию, импликацию, эквивалентность можно рассматривать как функции, которые определены на двухэлементном множестве В={0,1} со значениями в этом же множестве. Их называют логическими (булевыми) функциями или операциями. Операция отрицания – унарная, а все остальные – бинарные. Таблицу истинности для каждой из операций можно рассматривать как определение этой операции.

3.3. Равносильные формулы

Рассмотрим таблицы истинности для двух формул F=A®B и Н=(ØA)ÚB.

Таблица 3.

Из таблицы 3 видно, что при всех наборах значений элементарных высказываний А и В формулы F и Н принимают одинаковые значения.

Определение 2 Две логические формулы F и H называются равносильными, если они принимают одинаковые значения на любом наборе значений входящих в них элементарных высказываний.

Тот факт, что формулы F и H равносильны, обозначают F = H.

Таким образом, с помощью таблицы 3 установлена равносильность

A®B = (ØA)ÚB (1)

Среди всех логических формул особый интерес представляют такие, которые истинны уже в силу одной только своей функционально‑истинностной структуры. Такую формулу можно рассматривать как модель логического закона.

Определение 3 Формула А называется тавтологией (тождественно- истинной формулой), если при любых значениях входящих в нее переменных она принимает значение «истина» (А = 1).

С помощью таблицы истинности тавтологию можно определить как формулу, для которой соответствующий ей в таблице истинности столбец целиком состоит из 1. Таким образом, построение таблицы истинности это эффективная процедура для решения вопроса о том, является ли данная формула тавтологией.

Из таблицы истинности для импликации легко следует, что при любых значениях логической переменной А формула А®А принимает значение 1, т.е. является тавтологией.

Из определения конъюнкции легко получаем, что формула A&(ØA) всегда принимает значение 0 («ложь»). Тогда формула Ø(A&(ØA)) принимает только одно значение – 1 («истина»), т.е. является тавтологией.

Мы встретились с формулой A&(ØA), которая всегда принимает ложное значение. Такие формулы называют тождественно-ложными формулами (противоречиями). Очевидно, что формула А является тавтологией тогда и только тогда, когда формула (ØA) – противоречие.

Сформулируем несколько утверждений общего характера о тавтологиях.

1. Если А, (А®В) – тавтологии, то тавтологией является В.

Рассмотрим формулы Ф₁ =С&A и Ф₂ = (ØС)ÚА. Заменим в формуле F примера 3 пропозиционную переменную А на Ф