Решение Пример 1

Пример 1.

Теорема 4.

Теорема 3.

Для булевых алгебр логических функций, множеств, дво­ичных векторов справедливы следующие теоремы.

Если | U | = n, то булева алгебра множеств (b(U¢); Ç, È, ù) изоморфна булевой алгебре двоичных векторов

(В_п; &, Ú, ù).

Если | U | = 2 ^m то булева алгебра множеств (В_п; &, Ú, ù)

изоморфна булевой алгебре функций (P₂, &, Ú, ù).

Взаимный изоморфизм данных булевых алгебр, таким образом, выполняется, если

| U | = n = 2 ^m (4.28)

В этом случае |b(U)| = | В_п | = |P₂(m)|

и между множе­ствами |b(U)|, и |P₂(m)| устанавливается взаимно однознач­ное соответствие.

Изоморфизм булевых алгебр широко используется в ком­пьютерных вычислениях, например вместо выполнения опе­раций над множествами или логическими функциями ис­пользуют их изоморфные аналоги - легко реализуемые на компьютере поразрядные операции над двоичными векто­рами.

Представить соотношения (4.14) - (4.23) для булевой алгебры множеств.

Пусть множества А, В, С Í U.

Основные эквивалентные соотношения (за­коны) в булевой алгебре множеств (b (U); Ç, È, ù)

Ассоциативность пересечения и объединения:

а) A Ç (B Ç C) = (A Ç B) Ç C = A Ç B Ç C; (4.29)

б) (A Ç B) È C = (A È B) È C = A È B È C.

Коммутативность пересечения и объединения:

а) A Ç B = B Ç A;

б) A È B = B È A (4.30)

Дистрибутивность пересечения относительно объединения:

A Ç (B È C) = (A Ç B) È (A Ç С). (4.31)

Дистрибутивность объединения относительно пересече­ния:

A È (B Ç C) = (A È B) Ç (A È С) (4.32)

Идемпотентность:

а) A Ç A = A

б) A È A = A (4.33)

Закон двойного “отрицания”:

. (4.34)

Свойства универсального U и пустого Æ множеств:

а) A Ç U = A,

в) AÈ U = U

д) ; (4.35)

б) A Ç Æ = A;

г) A È Æ = А;

е) .

Дата добавления: 2014-01-14