Понедельник, Июль 5th, 2010

МЛОИ

Рассмотренная в § 1 настоящей главы теория множеств также является алгеброй в указанном выше смысле. Это алгебра множеств, объектами которой являются множества, а определенными и замкнутыми на этих объектах являются операции объединения, пересечения, дополнения.
Точно так же, рассмотренная в § 2 настоящей главы логика высказываний является алгеброй. Это алгебра высказываний, объектами которой являются высказывания, а определенными и замкнутыми на этих объектах являются операции дизъюнкции, конъюнкции и отрицания.
Две последние алгебры принадлежат к особому типу алгебр, называемых булевыми.2)
Булева алгебра представляет собой множество объектов (любой, но одинаковой, природы) с двумя «особыми» объектами («константами») — «единица» (I) и «нуль» (О), и двумя замкнутыми на множестве объектов операциями «сложения» (+) и «умножения» (?), обладающими следующими свойствами:
коммутативность + и ?:
A+B=B+A, A?B=B?A;
ассоциативность + и ?:
A+(B+C)=(A+B)+C, A?(B?C)=(A?B) ?C;
дистрибутивность + относительно ? и ? относительно +:
A+(B?C)=(A+B) ?(A+C), A?(B+C)=(A?B)+(A?C);
идемпотентность + и ?:
A+A=A, A?A=A.
Кроме того, «особые» объекты («константы») I и O обладают следующими свойствами:
A+O=A, A+I=I, A?I=A, A?O=O.

С точки зрения этого определения алгебра множеств является булевой алгеброй, в которой роль «сложения» играет операция объединения множеств (), роль «умножения» – операция пересечения множеств (), роль константы «нуль» – пустое множество (?), роль «единицы» — универсальное множество (U). Легко проверить, что все указанные выше свойства операций и констант булевой алгебры здесь выполняются.
Алгебра высказываний также является булевой алгеброй. В ней роль «сложения» играет операция дизъюнкции (?), роль «умножения» – операция конъюнкции (&), роль “нуля” – логическая константа Л, роль “единицы” – логическая константа И. И опять-таки легко проверить, что все указанные выше свойства операций и констант булевой алгебры выполняются.
Аналогично можно убедиться в том, что «алгебра переключательных схем» также является булевой: «сложению» будет соответствовать параллельное соединение контактов, «умножению» – последовательное соединение, константе «нуль» – всегда разомкнутый контакт, «единице» – всегда замкнутый контакт. 3)

В заключение приведем пример еще одной булевой алгебры – «алгебры максимумов и минимумов». Примем в качестве объектов (элементов) нашей алгебры, например, множество всех чисел отрезка [0,1], т.е. 0?х?1. В качестве операции «сложения» будем рассматривать операцию взятия максимального из двух чисел x и y и обозначать ее max (x,y), в качестве операции «умножения» — операцию взятия минимального из двух чисел x и y и обозначать ее min (x,y). В качестве константы «нуль» примем минимальное число из рассматриваемого отрезка, то есть число 0, а в качестве «единицы» – максимальное число из рассматриваемого отрезка – 1.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Категория: Лекции