Булева алгебра. Функциональная полнота

Определение.Алгеброй над множеством логических функций с двумя бинарными операциями, обозначаемыми как логическое умножение ‘ & ‘ и логическое сложение ’v ’ и одной унарной операцией (отрицанием)

'Ø ‘называется булевой алгеброй.

Будем обозначать ее символом S_B. Рассмотрим свойства булевой алгебры.

1. Замкнутость

 

для " A и B Î S_B

A v B Î S_B

A & B Î S_B

 

2. Коммутативность

 

A & B = B & A

A v B = B v A

 

3. Ассоциативность

 

A v ( B v C) = (A v B) v C

 

4. Дистрибутивность

 

A & ( B v C) = (A & B) v (A & C)

A v ( B & C) = (A v B) & (A v C)

 

5. Идемпотентность

 

A v A = A & A = A.

 

6. Булева алгебра содержит элементы 0,1 такие, что для всякого

элемента A Î S_B справедливо:

A v 0 = A, A v 1 = 1

A & 0 = 0, A & 1 = A.

 

7.Для каждого элемента A Î S_B существует элемент , такой что

 

A v =1

A & =0.

 

8.Закон поглощения

 

A & (A v B) = A v A & B = A.

 

9.Закон Де Моргана

 

Ø (A v B ) = ØA & ØB

Ø (A & B ) = ØA v ØB.

Определение. Система функций f₁, f₂... f_n Î S_B называется полной, если любая функция j из S_B представима в виде суперпозиции функций f₁, f₂... f_n.

 

Определение.Система функций f₁, f₂... f_n Î S_B , являющаяся полной, называется базисом.

Определение.Минимальным базисом называется базис, для которого удаление хотя бы одной из функций f_i превращает систему функций в неполную.

Можно показать, что системы функций { &, Ø} и { Ú, Ø} - полные. Система функций { &, Ø, Ú} является полной, но избыточной, так как она сохраняет свойства полноты и при удалении из нее & или Ú. За не избыточность системы функций { &, Ø} и { Ú, Ø} приходится платить избыточностью формул (повышением сложности функций).

 

Определение. Алгебра над множеством логических функций с двумя бинарными операциями & и Å называется алгеброй Жегалкина.