lec02

Имеем множество из двух элементов – {0,1}. На нем введем три операции:

0 0 = 0

Дизъюнкция (по смыслу – логическое сложение): 1 0 = 0 1 = 1

1 1 = 1

0 0 = 0

Конъюнкция (по смыслу – логическое умножение): 1 0 = 0 1 = 0

1 1 = 1

Отрицание: 0 = 1

1 = 0

12

Операции с булевыми векторами.

Рассмотрим векторы в булевой алгебре Вn:

= (α1, α2, … αi, … αn); = ( 1, 2, … i, … n)

Логической суммой (сложением) двух булевых векторов и , называется вектор: , полученный покоординатным логическим сложением элементов соответствующих векторов – αi и i 1≤i≤n, αi , i .

(α1 1; α2 2; … αi i, …; αn n)

13

Операции с булевыми векторами.

Логическим умножением двух булевых векторов и называется вектор: (или ∩ ), полученный покоординатным логическим умножением элементов соответствующих векторов – αi и i 1≤i≤n, αi , i .

(α1 1; α2 2 ; … αi i, … ; αn n)

Логическое отрицание булева вектора получается из первоначального вектора покоординатным отрицанием элементов αi:

α (α1, α2, … α , … α ).

14

Теорема о принадлежности булевого куба булевым алгебрам.

Теорема 2.2. При таком определении операции булев куб Вn становится булевой алгеброй. При этом роль соответственно нуля и единицы играют вектора

0 = (0, 0, …, 0); 1 = (1, 1, …,1);

Доказательство. Достигается проверкой всех аксиом булевой алгебры.

15

Теорема 2.3. (о взаимно однозначном соответствии между подмножествами и их характеристическими векторами).

Объединению подмножеств отвечает логическая сумма их характеристических векторов:

S T αS αT

Пересечению отвечает логическое произведение:

S T αS ∩ αT

дополнению соответствует отрицание характеристического вектора:

S αS

18

Доказательство:

Пусть

αT = ( 1, 2, … i, … n), αS = (α1, α2, … αi, … αn).

1) Покажем верность первого соответствия (для )

S T (α1 1, α2 2, … αi i … , αn n)

Вообще i-й элемент (αi i) характеристического вектора αS T соответствует прообразам αi и i из S и T, и равен 1, если его прообраз (для αi либо i) лежит либо в S, либо в T, соответственно, а это и есть логическая сумма (по свойствам введенных операций).

19

2) Покажем верность второго соответствия (для ∩)

S T (α1 ∩ 1, α2 ∩ 2, … αi ∩ i … , αn ∩ n)

i-й элемент (αi ∩ i) характеристического вектора αS∩T соответствует прообразам αi и i из S и T, соответственно, и равен 1, если его прообразы (как для αi так и i) лежат в S и в T, соответственно, а это и есть логическое произведение.

3) Покажем верность соответствия (для отрицания).

S (α1, α2, … α , … α ).

20