Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

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

Определение 2.26. Отображение / из А в А называется операцией на множестве А. В этом случае /(a) G Л и операцию / называют унарной.

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

  • 1) операция нахождения обратного числа: f(x)=x~1, х^О, или в других обозначениях: / = {(х, х~1) ? R, х ^ 0};
  • 2) операция нахождения противоположного числа: f(x) = —х, или иначе: /= {(ж, — ж)|жеМ};
  • 3) операция f = {(x, 0)|жеМ}, которая любое действительное число х отображает в 0.

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

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

Операции сложения и умножения действительных чисел являются бинарными на множестве действительных чисел М. Например, операция сложения: / = {((ж, у), х + у)х, у Е И).

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

Алгебры принято обозначать готическими буквами: 3- 91 и т. д. Для алгебры 9= (A: F) множество А называется носителем, алгебры, а множество F ее сигнатурой.

Например, множество натуральных чисел N с двумя бинарными операциями сложения (+), умножения (х) является алгеброй: 91 = — (N; +, х). Сигнатура этой алгебры: F={-f, х}.

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

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

Алгебра 9к= U, П, ", 0, М) называется алгеброй Кантора.

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

Определение 2.29. Булевой алгеброй называется непустое множество В с двумя бинарными операциями V, Л, двумя отмеченными элементами О, I и одной унарной операцией - , причем для любых а, 6, cdB выполняются следующие равенства:

А1 аVb = bVа, aAb—bAа (коммутативность);

А2 а V (6 V с) = (а V 6) V с, (ассоциативность);

a A(b А с) = (a Ab) А с

АЗ а V (6 Л с) = V Ь) Л V с), (дистрибутивность):

а Л (6 V с) = (а Л 6) V (а Л с)

А4 аЛа = а, аVа = а (идемпотентность);

А о а Л (а V Ь) = а, а V (а ЛЪ) = а (поглощение);

А6 а Л 0 = 0, а V 0 = а, о Л1 = а, а V1 = 1 (законы нуля и единицы);

А7 аЛа = (). а V а = /

А8 а = а (двойное дополнение или

инволютивность);

А9 а A b=аV 6, а V Ь — а ЛЬ (законы де Моргана).

Отметим, что это определение носит аксиоматический характер. Мы считаем заданными пять операций на множестве В (две бинарные:

V и Л, одна унарная " , и две нульарные: 0, I) и перечисляем 19 тождеств, сгруппированные в девять аксиом (постулатов). Алгебра считается булевой алгеброй тогда и только тогда, когда она имеет такой набор операций (сигнатуру) и в ней выполняются все выписанные аксиомы. Очевидно, что способ обозначения операций не играет роли. Операции

V и Л называют соответственно булевой суммой, или объединением, и булевым произведением, или пересечением.

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

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

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

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

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

Определение 2.30. Изоморфизмом алгебр = (А, б) и 9П = = (А‘2-!Ь) называется взаимно однозначное соответствие у между элементами носителей и сигнатур такое, что

где аи ..., an, aeAh fmeFb уДаД, ..., у?(ап), ср(а)еА2, y?(/m)GF2. При этом алгебры 9 и 942 называются изоморфными.

Все законы алгебры 9Д справедливы и в изоморфной ей алгебре 9В.

Алгебру Кантора 9l# = (S'(M); U, П, “ , 0, М), очевидно, можно рассматривать как модель (интерпретацию) абстрактной булевой алгебры, считая, что П^Л, U^V, 0<->О, М «->/. Более того, любую конечную булеву алгебру можно рассматривать как алгебру Кантора для некоторого конечного множества М.

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>