3.3 Основные законы алгебры логики
В булевой алгебре функции, принимающие одинаковые значения при одинаковых наборах входящих в них переменных называются равносильными. Замена логической функции другой, ей равносильной, называется равносильным преобразованием данной формулы.
Для проведения тождественных преобразований логических выражений используют основные законы математической логики:
– переместительный закон:
X V Y = Y V X,
X & Y = Y & X;
– сочетательный закон:
( X V Y ) V Z = X V (Y V Z ),
( X & Y ) & Z = X & ( Y & Z );
– распределительный закон:
( X V Y ) & Z = ( X & Z ) V ( Y & Z ),
( X & Y ) V Z = ( X V Z ) & ( Y V Z );
– законы де Моргана:
¬ ( X V Y ) = ¬ X & ¬ Y,
¬ ( X & Y ) = ¬ X V ¬ Y;
– закон идемпотентности:
X V X = X,
X & X = X;
– закон поглощения:
( X & Y ) V X = X,
( X V Y ) & X = X;
– закон склеивания:
( X & Y ) V ( ¬ X & Y ) = Y,
( X V Y ) & ( ¬ X V Y ) = Y;
– правило операции переменной с ее инверсией:
¬ X V X = 1,
¬ X & X = 0;
– правило операции с константами:
X V 0 = X,
X V 1 = 1,
X & 0 = 0,
X & 1 = X;
– закон двойного отрицания:
¬ ¬ X = X.
Преобразование логических функций
Равносильные преобразования логических функций имеют то же назначение, что и преобразования функций в обычной алгебре. Они служат для упрощения функций или приведения их к определённому виду путем использования основных законов алгебры и устранением логических связок и используя правила: XY = ( X Y ) & ( Y X ), X Y = X V Y.
Пример 3.3.1. Упростить выражение ¬(A & B) ¬B. Для упрощения будем применять последовательность законов из таблицы 3.3.1.
Таблица 3.3.1 – Упрощение выражения ¬(A & B) ¬B.
№ п/п |
Применяемый закон (правило) |
Результат преобразования |
1 |
закон де Моргана ¬(A & B) = ¬A V ¬B |
¬A V ¬B V ¬B |
2 |
закон идемпотентности ¬B V ¬B= ¬B |
¬A V ¬B |
Пример 3.3.2. Упростить выражение ¬(¬B & C C). Для упрощения будем применять последовательность законов из таблицы 3.3.2.
Таблица 3.3.2 – Упрощение выражения ¬(¬B & C C).
№ п/п |
Применяемый закон (правило) |
Результат преобразования |
1 |
закон поглощения ¬B & C C = C |
¬(С) |
2 |
убираем скобки |
¬(С)= ¬С |
Пример 3.3.3. Упростить выражение¬( ¬A & С) (B & ¬С). Для упрощения будем применять последовательность законов из таблицы 3.3.3.
Таблица 3.3.3 – Упрощение выражения ¬( ¬A & С) (B & ¬С).
№ п/п |
Применяемый закон (правило) |
Результат преобразования |
1 |
закон де Моргана ¬( ¬A & С) = ¬¬A V ¬C |
¬¬A V ¬C (B & ¬С) |
2 |
закон двойного отрицания ¬¬A= A |
A V ¬C (B & ¬С) |
3 |
закон поглощения ¬С (B & ¬С) = ¬С |
A V ¬С |
Пример 3.3.4 Упростить логическую функцию ¬(x v y)&(x&¬y). Для упрощения будем применять последовательность законов из таблицы 3.3.4.
Таблица 3.3.4 – Упрощение выражения ¬(x v y)&(x&¬y).
№ п/п |
Применяемый закон (правило) |
Результат преобразования |
1 |
закон де Моргана ¬(x v y)= ¬x&¬y |
¬x&¬y&(x&¬y) |
2 |
убираем скобки |
¬x&¬y&x&¬y |
3 |
сочетательный закон ¬x&¬y&x&¬y = ¬x&x&¬y&¬y |
¬x&x&¬y&¬y |
4 |
правило операций переменной с её инверсией ¬x&x=0 |
0&¬y&¬y |
5 |
закон идемпотентности ¬y&¬y = ¬y |
0&¬y |
6 |
правило операций с константами 0&¬y =0 |
0 |
Пример 3.3.5 Упростить логическую функцию ¬(x → y) & x. Для упрощения будем применять последовательность законов из таблицы 3.3.5.
Таблица 3.3.5 – Упрощение выражения ¬(x → y) & x.
№ п/п |
Применяемый закон (правило) |
Результат преобразования |
1 |
устраняем логическую связку x y = x V y |
¬( ¬x V y ) & x |
2 |
закон де Моргана ¬( ¬x V y ) = x&y |
x&¬y&x |
3 |
закон идемпотентности x&x = x |
x&¬y |