WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 11 |
Московский Государственный университет им. М.В. Ломоносова Факультет Вычислительной математики и кибернетики С.И. Гуров Упорядоченные множества и универсальная алгебра (вводный курс) учебное пособие Электронная версия Москва 2005 УДК 512 (075.8) В пособии рассмотрены основные понятия и теоремы булевой алгебры, отношений множеств, причем особое внимание уделено частично упорядоченным множествам и решёткам. Изучаются свойства модулярных и дистрибутивных решёток и решёток с дополнениями. Указанным разделам посвящены две первые главы. Заключительная третья глава посвящена универсальной алгебре. Вводится понятие алгебраической системы, рассматриваются различные типы таких систем и доказываются основные теоремы об их изоморфизме и гомоморфизме. Пособие есть результат существенной переработки и дополнения вышедшего в 2002 г. в Издательском отделе ф-та ВМиК МГУ пособия Элементы теории упорядоченных множеств и универсальной алгебры. В ходе его подготовки были, в частности, упрощены формулировки многих теорем и определений, добавлены новые разделы и исправлены замеченные неточности. Пособие предназначено для студентов, изучающих соответствующие разделы алгебры и может быть использовано при самообразовании.

Данное электронная версия отличается от брошюры Гуров С.И. Упорядоченные множества и универсальная алгебра (вводный курс): Учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ, 2004 г. 104 с. тем, что в ней исправлены замеченные опечатки и неточности, сделаны добавления и уточнения, а также изменено форматирование на более удобное для распечатки.

Подготовлено при поддержке Intel Technologies, Inc.

© С.И. Гуров, 2005.

Оглавление 1 Булевы алгебры. Отношения и соответствия.................. 4 1.1 Булева алгебра как алгебраическая система.............. 4 1.1.1 Определение булевой алгебры. Алгебраические системы.. 4 1.1.2 Алгебры множеств....................... 1.1.3 Изоморфизмы булевых алгебр................. 1.1.4 Теорема Стоуна......................... 1.2 Декартово произведение множеств. Отношения. Однородные отношения.................................... 1.2.1 Основные определения..................... 1.2.2 Псевдообращение и произведение соответствий....... 1.2.3 Однородные отношения.................... 1.3 Отношение эквивалентности и его свойства.............. 1.3.1 Классы эквивалентности.................... 1.3.2 Устойчивость эквивалентности................ 1.4 Соответствия и отображения....................... 1.4.1 Основные типы соответствий................. 1.4.2 Отображения........................... 1.4.3 Основные свойства отображений............... 2 Порядки и решётки................................ 2.1 Отношение порядка............................ 2.1.1 Предпорядки и порядки.................... 2.1.2 Частично упорядоченные множества............. 2.1.3 Изотонные отображения и порядковые идеалы....... 2.1.4 Вполне упорядоченные множества и смежные вопросы.. 2.2 Алгебраические решётки......................... 2.2.1 Решёточно упорядоченные множества и решётки...... 2.2.2 Основные свойства решёток.................. 2.3 Специальные виды решёток....................... 2.3.1 Модулярные решётки...................... 2.3.2 Дистрибутивные решётки................... 2.3.3 Решётки с дополнениями.................... 2.4 Булевы алгебры (продолжение)..................... 2.4.1 Безатомные булевы алгебры. Булевы гомоморфизмы, кольца и структуры......................... 2.4.2 Булевы идеалы и фильтры................... 3 Алгебраические системы............................. 3.1 Модели и алгебры............................. 3.1.1 Основные определения..................... 3.1.2 Подсистемы и прямое произведение алгебраических систем 3.2 Гомоморфизмы алгебраических систем................. 3.2.1 Согласованность отображений АС с операциями и отношениями............................... 3.2.2 Типы гомоморфизмов АС................... 3.3 Конгруэнции и гомоморфные системы................. 3.3.1 Конгруэнции и фактор-системы................ 3.3.2 Теоремы о гомоморфизмах и изоморфизмах АС...... 3.4 Многоосновные системы......................... Список литературы................................... 1 Булевы алгебры. Отношения и соответствия 1.1 Булева алгебра как алгебраическая система 1.1.1 Определение булевой алгебры. Алгебраические системы Определение 1.1. Булевой алгеброй B называется содержащее по крайней мере два элемента нуль (o ) и единица ( ) множество B с заданными на нём бинарными операциями объединения ( ), пересечения ( ) и унарной операцией дополнения ( ). При этом для любых x, y и z из B выполняются следующие законы (аксиомы) булевой алгебры:

Com : x y = y x Com : x y = y x Dtr1 : (x y) z = (x z) (y z) Dtr2 : (x y) z = (x z) (y z) o : x o = x : x = x Cmp : x x = Isl : x x = o Inv : (x ) = x : = o o : o = DeM1 : (x y) = x y DeM2 : (x y) = x y : x = o : x o = o Ass : x (y z) = (x y) z Ass : x (y z) = (x y) z Id : x x = x Id : x x = x Abs1 : x (x y) = x Abs2 : x (x y) = x Множество B называется носителем булевой алгебры B.

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

Законы o,, и o описывают свойства особых элементов o и (в частности, o = ) по отношению к объединению и пересечению, а, o их взаимную дополнитель ность. Законы Cmp и Isl постулируют полноту и обособленность дополнения (это основные законы, описывающие свойства дополнения), а Inv его инволютивность. Взаимные свойства бинарных операций и дополнения описываются законами Де Моргана (DeM1 и DeM2 ).

Введённые операции называют абстрактными, поскольку ни они сами, ни носитель, на котором они определены никак не конкретизируются, и никаких иных требований, кроме удовлетворения вышеприведённым законам, к ним не предъявляется. В приложениях элементы носителя B (или просто элементы булевой алгебры) интерпретируются как подмножества некоторых множеств, события, высказывания, сигналы и т.д.

Следствием очевидной самодвойственности законов булевой алгебры является важный Принцип двойственности (для булевой алгебры). Любое утверждение, истинное в булевой алгебре, остаётся истинным, если в нём произвести замены символов, o и/или x x, где x имя элемента булевой алгебры.

Последнее замечание важно: если им пренебречь, то, например, из DeM1 можно получить неверное равенство x y = x y вместо верного (x y ) = x y.

Нетрудно обнаружить, что приведённая система из 21-ой аксиом избыточна.

Inv. Инволютивность дополнения есть прямое следствие симметричности его основных свойств Cmp и Isl.

DeM1 и DeM2. Используя законы дистрибутивности, ассоциативности, свойства дополнения и единицы показывается, что для любых x, y B (x y) (x y ) = и (x y) (x y ) = o.

Это означает, что x y дополнение к x y, т.е. выведен закон DeM1. Выводимость DeM2 следует из принципа двойственности.

Id и Id. Законы идемпотентности вытекают из законов поглощения. Действительно, для любого x B имеет место Abs1 Absx x = x (x (x x)) = x.

Идемпотентность пересечения следует из только что доказанного по принципу двойственности.

Избыточность системы аксиом обычно не является помехой в практической работе.

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

Вопрос о неизбыточной системе аксиом для булевой алгебры оказался не таким простым, как могло бы показаться на первый взгляд. В ходе его исследования был обнаружен ряд интересных фактов, и с некоторыми из них мы встретимся в п. 2.3. Здесь же отметим восходящую к работе Э. Хантингтона1 часто используемую систему, содержащую только первые восемь из приведенных выше аксиом. Однако и указанная совокупность не является независимой: можно показать, что каждый из законов o, выводим из остальных семи. Единственная известная на сегодняшний день (2005 г.) безызбыточная самодвойственная система аксиом булевой алгебры содержит пары законов поглощения, дистрибутивности и основных свойств операции дополнения.

Булева алгебра является примером алгебраической системы (АС), точнее, частного случая АС алгебры. Произвольная АС A задается парой множеств A и A, т.е.

A = A, A. Здесь A носитель, а A сигнатура АС. Носитель АС есть некоторое непустое множество. В зависимости от его мощности различают конечные и бесконечные АС. Сигнатура A алгебры с носителем A есть упорядоченная совокупность символов операций и особых элементов из A. Если результат некоторой операции над элементами множества всегда лежит в этом множестве, то говорят, что множество устойчиво относительно данной операции, а операция устойчива на данном множестве. В определении алгебры требуется, чтобы все операции были устойчивы на её носителе.

В случае булевой алгебры с носителем B имеем B =,,, o,, и свойства указанных операций и выделенных элементов носителя описываются указанными выше законами. Если рассматриваются АС заданной сигнатуры, то, стремясь к краткости, для её обозначения часто используют просто символ носителя. Мы будем так поступать, когда это не приводит к недоразумениям.

1.1.2 Алгебры множеств Рассмотрим непустое множество A и произвольную совокупность S(A) его подмножеств, устойчивую относительно операций их объединения ( ), пересечения ( ) и дополнения ( ) до A. Множество всех подмножеств (булеан) A будем обозначать P(A).

Huntington E.V. Sets of independent postulates for algebra of logic. Amer. Math. Soc., 1904, 5, p.

288-309.

Понятно, что S(A) P(A). Алгебраическая система S(A),,,,, A называется алгеброй или полем множеств. Алгебру множеств с носителем P(A) будем называть тотальной (над A ), а с двухэлементным носителем {A, } тривиальной алгебрами множеств.

Нетрудно показать, что имеет место Теорема 1.1. Всякая алгебра множеств есть булева алгебра.

Доказательство. Достаточно убедиться, что в алгебре множеств произведены подста новки,,, A, o.

Законы коммутативности, o, и Cmp, Isl описывают элементарные свойства теоретико-множественных операций.

В силу принципа двойственности достаточно доказать справедливость для алгебры множеств первого закона дистрибутивности: (x y) z = (x z) (y z) для любых подмножеств x, y, z из S(A). Для этого рассмотрим произвольный элемент a (x y) z.

Ясно, что a z, и либо a x, либо x y. В первом случае a x z, а во втором a y z. Следовательно, в любом случае a x z или a y z, что эквивалентно a (x z) (y z). Справедливость второго дистрибутивного закона будет следовать отсюда по принципу двойственности.

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

Замечание. Проверку соотношений Dtr1, Dtr2 и им подобных легче всего проводить, используя известные читателю диаграммы Эйлера-Венна2, в которых множество A изображается прямоугольником, а его подмножества различными кругами или овалами общего положения в этом прямоугольнике. При этом объединению элементов соответствует объединение, а пересечению общая часть фигур, связанных с данными элементами.

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

В большинстве практических случаев (когда рассматриваемая булева алгебра изоморфна некоторой алгебре множеств см. ниже определения и теорему1.9 о представлении) для доказательств булевых равенств можно ограничиться рассмотрением “правильно построенных” диаграмм Эйлера-Венна.

Определение 1.2. Пусть дана система множеств X = {X1,..., Xn}. Составляющие { s1,..., sk} = S данной системы множеств задаются следующим индуктивным определением.

1 Составляющие {X1} суть X1 и X1.

2 Если S совокупность составляющих системы {X1,..., Xn-1}, то SXn и SXn составляющие системы {X1,..., Xn}.

Система множеств X называется независимой, если все её составляющие непусты.

Пример 2. Рассмотрим множество U = { a, b, c, d }.

См., например, Р. Фор, А. Кофман, М. Дение-Папен. Современная математика. М.: Мир, 1966.

1. Составляющими системы X1 = {a, b}, X2 = {b} суть {b},, {a}, {c, d} и, следовательно, данная система множеств не является независимой;

2. Составляющими системы X1 = {a, b}, X2 = {b, c}, суть {b}, {c}, {a}, {d}, и, следовательно, данная система множеств независима.

Для {0, 1} и множества X введём обозначение X: X есть X, если = 1 и X, если = 0.

Лемма 1.2. 1. Произвольная составляющая s S системы множеств j n {X1,..., Xn} представима в виде s = Xj, где j {0, 1}, и, следоваj=тельно, две составляющие либо совпадают, либо не пересекаются.

2. Независимая система из n множеств имеет 2n различных составляющих.

Доказательство. Доказательство п. 1) легко проводится по индукции. Утверждение 2) следует из 1).

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

Теорема 1.3 (Венна). Если булево равенство выполнено для некоторой независимой системы множеств, то оно справедливо для любой системы множеств.

Доказательство. Рассмотрим множество F, представимое некоторой булевой формулой над независимой системой множеств X = {X1,..., Xn} и s составляющая этой системы. Тогда либо s F, либо s F =. Первый случай имеет место если и только если x s x F. Это означает, что множество F может быть представлено в виде объединения F = s. Такое разложение останется справедливым и для завиxs xF симой системы множеств перестав, однако, быть единственным. Таким образом, если в независимой системе множеств две булевы теоретико-множественные формулы F1 и Fпредставляются в виде объединения одних и тех же составляющих, истинность x Fи x F2 будет одинакова в любой другой системе.

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

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

1.1.3 Изоморфизмы булевых алгебр Хотя алгебры множеств являются, как мы увидим, в определённом смысле, основными примерами булевых алгебр, последние ими не исчерпываются.

Пример 3. 1. Рассмотрим двоичное множество истинностных значений B = { 1, 0 } и сигнатуру B =,, ¬, 0, 1, состоящую из логических операций дизъюнкции, конъюнкции и отрицания, а также символов элементов B : логического нуля 0 ( ложь ) и логической единицы 1 ( истина ). Полученная АС B, B является, как нетрудно видеть, булевой алгеброй. Эта простая алгебра играет фундаментальную роль в логике. Она называется алгеброй логики или алгеброй высказываний. Заметим, что в логике Cmp и Isl называются соответственно законами исключенного третьего и непротиворечия.

2. АС Bn,,, ¬, 0, 1, где Bn булев n-мерный куб, 0 = (0,..., 0), 1 = (1,..., 1), а сигнатурные операции применяются к булевым векторам покомпонентно, называют булевой алгеброй n-мерных двоичных векторов.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 11 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.