Научная литература
booksshare.net -> Добавить материал -> Математика -> Мальцев А.И. -> "Алгебраические системы" -> 5

Алгебраические системы - Мальцев А.И.

Мальцев А.И. Алгебраические системы — Наука, 1970. — 392 c.
Скачать (прямая ссылка): algebraicheskiesistemi1970.djvu
Предыдущая << 1 .. 2 3 4 < 5 > 6 7 8 9 10 11 .. 133 >> Следующая


x[\{y®z) = {x[\y)@{x(\z). (2)

Система, состоящая из совокупности U всех подмножеств некоторого множества U ж операций f] > называется кольцом Буля подмножеств множества U. Помимо законов коммутативности и ассоциативности (Б02 и Б03) операции П і закона дистрибутивности (2), в кольце Буля выполнены также следующие тождества:

х@х=0, х@0=х, = y ©.т,

(X@y)®z = x@(y®z),

легко вытекающие из тождеств Б1 — Б7 и формулы (1), определяющей разностную сумму множеств.

Отметим еще, что в алгебре Буля отношение включения подмножеств A s В равносильно каждому из равенств

А[]В = В, AftB = A.

Ясно также, что включение А <= В равносильно двойственному включению В' s А'.

Естественно было бы спросить себя, исчерпывают ли тождества Б1 — Б7 и их формальные следствия все вообще тождества, которые связывают операции U , D5' на произвольной алгебре подмножеств? Ответ на этот вопрос положительный и будет дан ниже (см. пп. 5.2 и 7.1).

1.2. Отношения. Декартовым произведением множеств А и B1 символически А X В, называется совокупность всех пар вида (а, Ь), где а ? А, Ь?В. Например, если А = {1, 2}, В = {4, 5}, то AxB= {(1, 4), (1, 5), (2, 4), (2, 5)}. Далее,

BxA = {(4, 1), (4, 2), (5, 1), (5, 2)},

AxA = {(1, 1), (1, 2), (2, 1), (2, 2)}. ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ-

17

Ясно, что если множества А, В конечные и А содержит т элементов, а В — п элементов, то произведение А X В содержит тп пар.

Всякое подмножество а декартова произведения AxB произвольных множеств А, В называется отношением, определенным на паре множеств А, В. Если (а, Ъ) ? а, то говорят, что элемент а находится в отношении а к элементу Ь или что отношение а для а, Ъ истинно. Вместо (а, Ь) ? а пишут также aab или а (а, Ь).

Отношение, заданное на паре множеств A1 А, называется бинарным отношением, заданным на множестве А.

Поскольку отношения, заданные на фиксированной паре множеств А, В, суть подмножества множества А X В, то совокупность всех этих отношений образует алгебру Буля относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных a Qr A1 Ъ ? В

a (a U ?) b <?=> aab или o?&,

а (а П ?) Ъ <?=> aab и a?&,

aa'b не aab.

Поэтому часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, отношение равенства =, определенное на множестве натуральных чисел N, можно понимать как совокупность всех «диагональных» пар: (0,0), (1,1), . . . Дополнение этого отношения есть отношение неравенства ф. Отношение порядка <С есть совокупность пар (а, Ь), у которых а < Ь. Отношение совпадает с объединением <U—» а пересечение <С П = пусто, т. е. представляет собою всюду ложное отношение. Объединение U > является, напротив, всюду истинным отношением.

Помимо операций |J, f|, ' важное значение имеют еще две операции над отношениями — обращение и умножение отношений, определяемые следующим образом.

Если а — отношение, определенное на паре множеств A, B1 то обратным отношением (символически а-1) называется отношение а-1, определенное на паре В, А и состоящее

2 А. И. Мальцев - 18

0ЙІЦЙЕ rtOHHflltf

[Ґл . 1

из тех пар (Ъ, а), для которых (а, Ъ) ? а, т. е.

bar1 а <=> aab. Например, если <С — отношение порядка, то а -с-1 Ъ <=> Ь<, а <=> а > Ъ,

и потому <-1 = >.

Пусть теперь отношение а задано на паре множеств А, В и отношение ? задано на паре множеств В, С. Произведением a? отношений a, ? называется отношение, определенное на паре множеств А, С и такое, что a(a?)c (a ? А, с ? С) истинно тогда и только тогда, когда в В найдется элемент х, для которого истинны аах и афс. Если же отношение а определено на паре множеств А, В, отношение ? определено на паре С, D и В Ф С, то произведение a? считается не определенным.

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

Рассмотрим несколько примеров. Введем обозначения:

aa = a2, a2a = a3, ... (1)

Посмотрим, что выражают отношения <С2, <L3, • ¦ где <С — отношение порядка на множестве натуральных чисел N. Согласно определению, а<C2 Ъ истинно тогда и только тогда, когда для некоторого натурального х истинны а <С X и X <С Ъ. Для существования такого х необходимо и достаточно, чтобы а + 1 <С Ъ. Следовательно,

а <С2 Ъ <=>а+ 1 <&,

a<3&<=>a + 2<&, (2)

Аналогично

а (< •>) Ъ <=> Эх (а С х & х > Ъ) -?=> Зж (х > max (а, Ь)).

(3) ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ

19

Здесь Эх— символ выражения «существует такое х, что», а &—символ для союза и. Переставив в (3) сомножители

< и >, получим

а (> • <) b <=> Эх (а >¦ X & х •< Ъ) <=> Эх (х -< min (а, Ь)).

(4)

Бинарные отношения а, ?, определенные на каком-нибудь множестве А, называются перестановочными, если a? = ?a. Формулы (3), (4) показывают, что отношения
Предыдущая << 1 .. 2 3 4 < 5 > 6 7 8 9 10 11 .. 133 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed