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

Лекция №7

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

Алгебраическую систему с основным множеством M и сигнатурой , состоящий из символов операций f_i арностей n_i и отношений R_j арностей m_j , обозначают в виде M(), или подробнее M(). При этом набор натуральных чисел <n₁, …, n_k; m₁, … ,m_l> называется типом алгебраической системы M().

Если на алгебраической системе определены только операции, то она называется алгеброй.

Если на алгебраической системе только отношения, то она называется моделью.

Пример 7.1.2: N(+,*;=,<) – алгебраическая система;

Пример 7.1.3: N(+,*) – алгебра;

Пример 7.1.4: N(+,<) – модель.

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

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

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

1.,

2. ,

3. ,

4. ,

5. ,

6. ,

7. ,

8. ,

9. ,

10. ,

11. ,

12. .

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

, , , , , .

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

.

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

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

Пример 7.1.8: Пусть M – множество всех положительных делителей числа m, равного произведению некоторых различных простых чисел. Определим операции «», «» и «’» следующим образом: для любых M положим , , .

Число 1 M играет роль нуль-арной операции 0.

Число m M играет роль нуль-арной операции 1.

Тогда M(,,’,1,m) - булева алгебра.

Определение 7.1.9: Пусть - бинарное отношение на на M. Бинарное отношение на множестве M называется отношением частичного порядка (или просто отношением порядка), если оно рефлексивно, транзитивно, антисимметрично. Связное отношение частичного порядка называется линейным порядком. Отношение порядка обозначается через «». Если и , то пишут .

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

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

1. точка лежит левее (или ниже) точки если ;

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

Пример 7.1.10: M = 2^{1,2,3}

Положим для любых A,B M, .

Тогда диаграмма для M() представляется следующим рисунком:

 

 

Рисунок 7.1.11.

Пример 7.1.12: M={}.

n

n-1

Положим ab «натуральное число a» «натурального числа b». Тогда диаграмма для M() имеет следующий вид:

 

Рисунок 7.1.13.

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

Положим aba | b для любых a, b M. Тогда диаграмма для M() имеет следующий вид:

 

 

Рисунок 7.1.15.

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

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

abab=b.

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

Таким образом на рисунке 7.1.11 изображена диаграмма булевой алгебры всех надмножеств множества {1,2,3}.