Основные положения и теоремы алгебры логики

Порядок выполнения логических операций

Если в выражении скобок нет, то первой выполняется инверсия, второй – логическое умножение, а затем все остальные операции по порядку слева направо. Если черта (знак инверсии) стоит над совокупностью аргументов и знаков, то инверсия выполняется в последнюю очередь. Если в выражении имеются скобки, то как и в обычной алгебре, сначала выполняют действия в скобках.

В процессе преобразования функции используют теоремы алгебры логики.

Основные теоремы для одной переменной следуют из определения функции и имеют вид

1 - x v 0 = x; 2 - x v 1 = 1; 3 - x v x = x;

4 - x v = 1; 5 - x Ù 0 = 0; 6 - x Ù 1 = x;

7 - x Ù x = x; 8 - x Ù = 0; 9 - = x

Проверить теоремы можно подстановкой х = 0 и х = 1.

Одним из основных положений в алгебре логики является принцип двойственности (теорема де Моргана).

Запишем таблицы истинности операций "ИЛИ" и "И", расположив строчки "И" в обратном (сверху вниз) порядке:

"ИЛИ" "И"

0 v 0 = 0 1 Ù 1 = 1

0 v 1 = 1 1 Ù 0 = 0

1 v 0 = 1 0 Ù 1 = 0

1 v 1 = 1 0 Ù 0 = 0

Сравнив построчно операции "ИЛИ" и "И", можно заметить, что если заменить в строках "ИЛИ" и "И" все 0 на 1, а все 1 на 0 и знаки дизъюнкции на знаки конъюнкций, то значение функций поменяется местами: строка "ИЛИ" превращается в строку "И" и наоборот. В этом и состоит принцип двойственности, который алгебраически записывается в следующем виде:

для двух переменных:

_______ __ __ _______ __ __

а) x1 v x2 = x1 Ù x2 или б) x1 Ù x2 = x1 v x2

при любом числе переменных:

______________ __ __ __

а) x1 v x2 v x3v... = x1 Ù x2 Ù x3...

____________ __ __ __

б) x1 Ù x2 Ù x3... = x1 v x2 v x3...

Необходимо отметить, что эти теоремы (как и последующие) остаются справедливыми и для случая, если под х понимать не только одно переменное, но и целое выражение.

Теоремы для двух и более переменных

10. Переместительный закон:

а) х1 v х2 = х2v х1;

б) х1 Ù х2 = х2 Ù х1.

Переместительный закон означает, что выходной сигнал в логических элементах не зависит от того, к какому входу подведен тот или иной сигнал.

11. Сочетательный закон:

а) х1 v х2 vх3 = х1 v (х2 v х3) = (х1 v х2) v х3;

б) х1 Ù х2 Ù х3 = х1 Ù (х2 Ù х3) = (х1 Ù х2) Ù х3.

12. Распределительный закон:

а) х1 Ù (х2 vх3) = х1 Ù х2 v х1 Ù х3;

б) х1 v х2 Ù х3 = (х1 v х2) Ù (х1 v х3).

Теоремы 10, 11, 12а очевидны и совпадают с правилами обычной алгебры, а 12б требуют доказательства.

Используя принцип двойственности, запишем 12а в следующем виде (заменяя все переменные на их отрицания, а знаки сложения и умножения друг на друга):

_ _ _ _ _ _ _

х1 v х2 Ù х3 = (х1 v х2) Ù (х1 v х3). (5.5)

_ _ _

Обозначив х1 = z1; х2 = z2; х3 = z3 и подставив в (5.5),

получим z1 v z2 Ù z3 = (z1 v z2) Ù (z1 v z3), а это и есть 12б

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

а) х1 v х1 Ù х2 = х1; б) х1 Ù (х1 v х2) = х1.

Доказательство 13а. Выносим х1 за скобки:

х1 Ú х1 Ù х2 = х1 Ù (1 v х2).

Используя теоремы 2 и 6 - 1 v х2 = 1, х1 ^ 1 = х1,

Получаем х1 v х1 Ù х2 = х1.

13б следует из принципа двойственности.

14. Закон склеивания:

__ __

а) х1 Ù х2 v х1 Ù х2 = х2; (х1 v х2) Ù (х1 v х2) = х2

Доказательство 14а. Выносим х2 за скобки и, используя теоремы 4 и 6, запишем:

__ __

х1 Ù х2 v х1 Ù х2 = х2(х1 v х1) = х2 Ù 1.

14б следует из принципа двойственности

15. Закон обобщенного склеивания:

__ __

а) (х1 v х2) Ù х2 = х1 Ù х2; б) х1 Ù х2 v х2 = х1 v х2

Упрощение (минимизация) булевых функций производится на основании теорем 1-15 и принципа двойственности. Наиболее эффективными приемами являются вынесение общих членов за скобки, применение двойного отрицания, законов поглощения и склеивания. Рассмотрим простейший пример минимизации:

__ __

F(x1, x2) = x1 Ù x2 v x1 Ù x2 v x1 Ù x2.

Выносим х1 за скобки и, используя теоремы 4 и 15б, получим

__ __ __

F(x1, x2) = x1 Ù x2 v x1 Ù (х2 v х2) = х2 Ù х1 v х1 = x1 v x2.

Схемы неупрощенного и упрощенного выражений и таблица истинности приведены на рисунке 5.7

X1	X2	Y

а б в

а – функция до преобразования; б после преобразования;

в – таблица истинности

Рисунок 5.7 – Пример упрощения логической функции