07.1. Алгебраические системы. Булевы алгебры

Определение 7.1. Множество M с заданными на нём операциями и отношениями называется алгебраической системой. При этом M называется Основным множеством системы, а множество символов, используемых для обозначения определённых на M операций и отношений называется Сигнатурой алгебраической системы.

Алгебраическую систему с основным множеством M и сигнатурой , состоящий из символов операций FI арностей NI и отношений RJ арностей MJ, обозначают в виде M(), или подробнее M(). При этом набор натуральных чисел <N1, …, NK; M1, …, ML> называется типом алгебраической системы M(). Если на алгебраической системе определены только операции, то она называется Алгеброй. Если на алгебраической системе только отношения, то она называется Моделью.

Пример 7.2. N(+, *; =, <) — алгебраическая система.

Пример 7.3. N(+, *) — алгебра.

Пример 7.4. N(+, <) — модель.

Пример 7.5. Алгебрами являются полугруппы, группы, кольца, поля и т. д.

В математической логике особую роль играют так называемые булевы алгебры.

Определение 7.6. Булевой алгеброй называется множество B с двумя бинарными операциями «», «», и одной унарной операцией «¢» и двумя нуль-арными операциями (т. е. выделенными элементами) 0, 1, удовлетворяющими условиям (при любых ):

1. ,

2. ,

3. ,

4. ,

5. ,

6. ,

7. ,

8. ,

9. ,

10. ,

11. ,

12. .

Несложно показать, что Из условий 1-12 следуют равенства:

, , , ,

, .

Например, выведем из условий 1-12 равенство :

.

Элементы 0 и 1 булевой алгебры B называют её нулём и единицей. Иногда их обозначают в виде 0B и 1B.

Пример 7.7. Пусть 2M — обозначение множества всех подмножеств множества M,  — бинарная операция пересечения множеств,  — бинарная операция объединения множеств. Для A  M обозначим A¢ = M\A, A¢ — дополнение множества A. «¢» — унарная операция, и M – нуль-арные операции, играющие роль 0 и 1. Тогда 2M(, , , M) — булева алгебра.

Пример 7.8. Пусть M — множество всех положительных делителей числа M, равного произведению некоторых различных простых чисел. Определим операции «», «» и «¢» следующим образом: для любых M положим , , . Число 1 M играет Роль нуль-арной операции 0. Число M M играет роль нуль-арной операции 1. Тогда M(, , ¢, 1, M) — булева алгебра.

Определение 7.9. Пусть  — бинарное отношение на на M. Бинарное отношение на множестве M называется Отношением частичного порядка (или просто отношением порядка), если оно рефлексивно, транзитивно, антисимметрично. Отношение частичного порядка r на М называется отношением линейного порядка, если для любых X, X¢ Î M либо XR X¢, либо X¢r X. Отношение порядка обозначается через «». Если и , то пишут .

Множество M с заданным на нём отношением частичного или линейного порядка «» называется, соответственно, частично или линейно упорядоченным множеством.

В некоторых случаях при изучении частично упорядоченных множеств используются их геометрические изображения — диаграммы. При построении диаграмм частично упорядоченного множества M() различные элементы из M отождествляются с различными точками плоскости так, что:

Точка Лежит левее (или ниже) точки , если ;

Точка соединяется отрезком с отличной от неё точкой , если и не существует точки , отличной от A, B, удовлетворяющей условию (в этом случае говорят, что B непосредственно следует за a или a непосредственно предшествует B).

Пример 7.10. M = 2{1, 2, 3}.

Положим для любых A, B  M, . Тогда диаграмма для M() представляется рис.7.1.

Рис.7.1

Пример 7.11. M = {}.

Положим A  B «натуральное число A» «натурального числа B». Тогда диаграмма для M() имеет вид, показанный на рис.7.2.

1	2	3	N – 1	N

Рис.7.2

Пример 7.12. M = {1, 2, 3, 4, 5, 6}.

Положим A  B A | B для любых A, B M. Тогда диаграмма для M() имеет вид (рис.7.3).

Рис.7.3

Интересно отметить Связь булевых алгебр с частично упорядоченными множествами.

Пусть B — произвольная булева алгебра. Для произвольных элементов A, B  B положим A  B  A B = B.

Из условий 6.4.2 следует, соответственно, что так определённое отношение «» на B рефлексивно, антисимметрично и транзитивно. В итоге имеем частично упорядоченное множество B(). Диаграмма для B() называется диаграммой Булевой алгебры B. Таким образом на рис.7.1 изображена диаграмма булевой алгебры всех надмножеств множества {1, 2, 3}.

< Предыдущая		Следующая >