Булева алгебра и теория множеств

Лекция

Всякая алгебра, содержащая две бинарные и одну унар­ную операции, называется булевой, если ее операции удов­летворяют соотношениям (4.14) - (4.23).

Примеры булевых алгебр:

(P₂, &, Ú, ù) - булева алгебра логических функций с опера­циями конъюнкции, дизъюнкции и отрицания;

(P₂(m), &,Ú, ù) - булева алгебра логических функций m переменных, являющаяся под алгеброй алгебры

(Р₂; &, Ú, ù), Р₂ (m) Ì Р₂;

((U); Ç, È, ù) - булева алгебра множеств над U с опе­рациями пересечения, объединения и дополнения;

(b(U¢); Ç, È, ù) - булева алгебра множеств над

U¢, U¢ Ì U, являющаяся подалгеброй алгебры

(b(U); Ç, È, ù);

(В_п; &, Ú, ù) - булева алгебра двоичных векторов длины n с покомпонентными (поразрядными) логическими операци­ями над двоичными векторами, определенными следующим образом.

Для любых векторов a = (a ₁,a₂,…, a_n)

и b = (b₁, b₂,…, b_n):

а) a & b = (a₁ & b₁, a₂ & b₂,..., a_n & b_n),

где a_i & b_i = 1, если a_i = b_i = 1 и a_i & b_i, = 0 в любом другом случае;

б) a Ú b = (a₁ Ú b₁, a₂ Ú b₂,..., a_nÚ b_n),

где, если a_i Ú b_i, = 0, если a_i = b_i = 0 и a_i & b_i, = 1

в любом другом случае;

в)

где = 0, если , = 1 и = 1 в противном случае.

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