10. Операторные и бинарные программы.

Операторные программы.

Реализованы непосредственно по булевой формуле, используя выходную ячейку для запоминания промежуточных результатов. Так как в них используются логические битовые операции и не применяются условные переходы. Поэтому все команды в таких программах вне

зависимости от входных наборов всегда выполняются последовательно, и

в общем случае в них используются дополнительные ячейки памяти для

423 запоминания промежуточных результатов. Это приводит к увеличению

числа команд по сравнению со случаем, когда запоминания не требуется.

Бинарные программы.

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

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

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

• называется булевой алгеброй. Будем обозначать ее символом _B.

Рассмотрим свойства булевой алгебры.

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

для  A и B  _B

A v B  _B

A & B  _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  _B справедливо:

A v 0 = A, A v 1 = 1

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

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

A v =1

A & =0.

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

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

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

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

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

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

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

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

Свойства алгебры Жегалкина

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

x  y = y  x

x & y = y & x

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

x & (y  z)= x & y  z & x