Алгебра логики

Огастес де Морган
Огастес де Морган — математик, чьим именем названы законы де Моргана

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

В этой главе мы рассматриваем именно алгебраические преобразования логических выражений. Эти преобразования во многом похожи на преобразования обычных алгебраических выражений, поэтому для простоты будем использовать такую запись:

  • \(\overline A\) — отрицание, то есть НЕ \(A\);
  • \(A \cdot B\) — логическое И;
  • \(A + B\) — логическое ИЛИ.
Закон Для операции И Для операции ИЛИ
Двойного отрицания \(\overline{\overline A} = A\)
Исключённого третьего \(A \cdot \overline A = 0\) \(A + \overline A = 1\)
Операции с константами \(A \cdot 1 = A\), \(A \cdot 0 = 0\) \(A + 1 = 1\), \(A + 0 = A\)
Повторения \(A \cdot A = A\) \(A + A = A\)
Переместительный \(A \cdot B = B \cdot A\) \(A + B = B + A\)
Сочетательный \(A \cdot (B \cdot C) = (A \cdot B) \cdot C\) \(A + (B + C) = (A + B) + C\)
Распределительный \(A + B \cdot C = (A + B) \cdot (A + C)\) \(A \cdot (B + C) = A \cdot B + A \cdot C\)
Поглощения \(A + A \cdot B = A\) \(A \cdot (A + B) = A\)
де Моргана \(\overline{A \cdot B} = \overline A + \overline B\) \(\overline{A + B} = \overline A \cdot \overline B\)

Законы алгебры логики

Закон двойного отрицания означает, что операция НЕ обратима: если применить её два раза, логическое значение не изменится.

Закон исключённого третьего опирается на то, что в классической двузначной логике любое выражение либо истинно, либо ложно. Поэтому \(A\) и \(\overline A\) не могут быть истинны одновременно, но одно из них обязательно истинно. Значит, \(A \cdot \overline A = 0\), а \(A + \overline A = 1\). Равенство \(A \cdot \overline A = 0\) часто также называют законом противоречия.

Операции с константами и закон повторения легко проверяются по таблицам истинности операций И и ИЛИ.

Переместительный и сочетательный законы выглядят вполне привычно, так же как и в арифметике. Вообще аналогия с обычной алгеброй здесь часто оказывается полезной. Нужно только помнить, что в логике \(1 + 1 = 1\), а не \(2\).

Распределительный закон для операции ИЛИ — это обычное раскрытие скобок: \(A \cdot (B + C) = A \cdot B + A \cdot C\). А вот равенство \(A + B \cdot C = (A + B) \cdot (A + C)\) выглядит менее привычно: в алгебре чисел оно вообще неверно. Поэтому полезно отдельно увидеть, как оно доказывается.

Доказательство удобно начать с правой части.

\[ (A + B)\cdot(A + C) = A\cdot A + A\cdot C + B\cdot A + B\cdot C = A + A\cdot C + A\cdot B + B\cdot C = A + B\cdot C \]

В последнем переходе использованы закон повторения и закон поглощения: \(A \cdot A = A\), \(A + A \cdot C = A\), \(A + A \cdot B = A\).

Из распределительного закона следует ещё одно полезное тождество.

\[ A + \overline A \cdot B = (A + \overline A)\cdot(A + B) = A + B \]

Равенство доказано. По ходу доказательства мы фактически использовали и закон поглощения: \(A + A \cdot C = A\) и \(A + A \cdot B = A\).

Законы де Моргана позволяют раскрывать отрицание сложных выражений. Эти правила названы в честь шотландского математика и логика Огастеса (Августа) де Моргана.

Важно заметить, что при таком преобразовании не просто «общее» отрицание переходит на отдельные выражения. Одновременно меняется и сама операция:

  • И заменяется на ИЛИ;
  • ИЛИ заменяется на И.

С помощью этих законов можно шаг за шагом сокращать сложные логические выражения.

Доказательство равносильности по таблице истинности

Законы выше можно доказать через таблицы истинности.

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

Разберём это на примере первого закона де Моргана: \(\overline{(A + B)} = \overline A \cdot \overline B\).

Для этого нужно для всех возможных комбинаций значений \(A\) и \(B\) вычислить левую и правую части равенства и сравнить результаты. Чтобы не делать всё сразу в уме, удобно добавить промежуточные столбцы. Сначала вычислим \(A + B\) и \(\overline{(A + B)}\). Затем отдельно найдём \(\overline A\), \(\overline B\) и \(\overline A \cdot \overline B\).

\(A\) \(B\) \(A + B\) \(\overline{(A + B)}\) \(\overline A\) \(\overline B\) \(\overline A \cdot \overline B\)
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Нас интересуют именно столбцы \(\overline{(A + B)}\) и \(\overline A \cdot \overline B\). Они совпадают для всех строк. Значит, эти выражения равносильны. Точно так же доказывается и второе равенство: \(\overline{(A \cdot B)} = \overline A + \overline B\).

Задачи для тренировки: доказательство по таблице истинности

1. Докажите по таблице истинности закон двойного отрицания:

\[ \overline{\overline A} = A \]

Ответ

\(A\) \(\overline A\) \(\overline{\overline A}\)
0 1 0
1 0 1

Столбцы \(A\) и \(\overline{\overline A}\) совпадают, значит равенство доказано.

2. Докажите по таблице истинности закон исключённого третьего:

\[ A \cdot \overline A = 0, \qquad A + \overline A = 1 \]

Ответ

\(A\) \(\overline A\) \(A \cdot \overline A\) \(A + \overline A\)
0 1 0 1
1 0 0 1

В столбце \(A \cdot \overline A\) во всех строках стоит \(0\). Значит, при любых значениях \(A\) выражение \(A \cdot \overline A\) равно \(0\).

В столбце \(A + \overline A\) во всех строках стоит \(1\). Значит, при любых значениях \(A\) выражение \(A + \overline A\) равно \(1\).

3. Докажите по таблице истинности законы операций с константами:

a) \(A \cdot 1 = A\)

b) \(A \cdot 0 = 0\)

c) \(A + 1 = 1\)

d) \(A + 0 = A\)

Ответ

\(A\) \(A \cdot 1\) \(A \cdot 0\) \(A + 1\) \(A + 0\)
0 0 0 1 0
1 1 0 1 1

a) Столбцы \(A\) и \(A \cdot 1\) совпадают.

b) В столбце \(A \cdot 0\) во всех строках стоит \(0\). Значит, при любом \(A\) выражение \(A \cdot 0\) равно \(0\).

c) В столбце \(A + 1\) во всех строках стоит \(1\). Значит, при любом \(A\) выражение \(A + 1\) равно \(1\).

d) Столбцы \(A\) и \(A + 0\) совпадают.

4. Докажите по таблице истинности закон повторения:

\[ A \cdot A = A, \qquad A + A = A \]

Ответ

\(A\) \(A \cdot A\) \(A + A\)
0 0 0
1 1 1

Оба полученных столбца совпадают со столбцом \(A\), значит оба равенства доказаны.

5. Докажите по таблице истинности переместительный закон:

\[ A \cdot B = B \cdot A, \qquad A + B = B + A \]

Ответ

\(A\) \(B\) \(A \cdot B\) \(B \cdot A\) \(A + B\) \(B + A\)
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 0 1 1
1 1 1 1 1 1

Столбцы \(A \cdot B\) и \(B \cdot A\) совпадают. Столбцы \(A + B\) и \(B + A\) тоже совпадают. Значит, переместительный закон доказан.

6. Докажите по таблице истинности сочетательный закон:

\[ A \cdot (B \cdot C) = (A \cdot B) \cdot C, \qquad A + (B + C) = (A + B) + C \]

Ответ

Для операции И:

\(A\) \(B\) \(C\) \(B \cdot C\) \(A \cdot (B \cdot C)\) \(A \cdot B\) \((A \cdot B) \cdot C\)
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
1 1 0 0 0 1 0
1 1 1 1 1 1 1

Столбцы \(A \cdot (B \cdot C)\) и \((A \cdot B) \cdot C\) совпадают.

Для операции ИЛИ:

\(A\) \(B\) \(C\) \(B + C\) \(A + (B + C)\) \(A + B\) \((A + B) + C\)
0 0 0 0 0 0 0
0 0 1 1 1 0 1
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1

Столбцы \(A + (B + C)\) и \((A + B) + C\) тоже совпадают. Значит, сочетательный закон доказан.

7. Докажите по таблице истинности распределительный закон:

\[ A \cdot (B + C) = A \cdot B + A \cdot C, \qquad A + B \cdot C = (A + B) \cdot (A + C) \]

Ответ

Для первого равенства:

\(A\) \(B\) \(C\) \(B + C\) \(A \cdot (B + C)\) \(A \cdot B\) \(A \cdot C\) \(A \cdot B + A \cdot C\)
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1

Столбцы \(A \cdot (B + C)\) и \(A \cdot B + A \cdot C\) совпадают.

Для второго равенства:

\(A\) \(B\) \(C\) \(B \cdot C\) \(A + B \cdot C\) \(A + B\) \(A + C\) \((A + B) \cdot (A + C)\)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1

Столбцы \(A + B \cdot C\) и \((A + B) \cdot (A + C)\) тоже совпадают. Значит, распределительный закон доказан.

8. Докажите по таблице истинности закон поглощения:

\[ A + A \cdot B = A, \qquad A \cdot (A + B) = A \]

Ответ

\(A\) \(B\) \(A \cdot B\) \(A + A \cdot B\) \(A + B\) \(A \cdot (A + B)\)
0 0 0 0 0 0
0 1 0 0 1 0
1 0 0 1 1 1
1 1 1 1 1 1

Столбец \(A + A \cdot B\) совпадает со столбцом \(A\). Столбец \(A \cdot (A + B)\) тоже совпадает со столбцом \(A\). Значит, закон поглощения доказан.

9. Докажите по таблице истинности законы де Моргана:

\[ \overline{(A + B)} = \overline A \cdot \overline B, \qquad \overline{(A \cdot B)} = \overline A + \overline B \]

Ответ

Для первого равенства:

\(A\) \(B\) \(A + B\) \(\overline{(A + B)}\) \(\overline A\) \(\overline B\) \(\overline A \cdot \overline B\)
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Столбцы \(\overline{(A + B)}\) и \(\overline A \cdot \overline B\) совпадают.

Для второго равенства:

\(A\) \(B\) \(A \cdot B\) \(\overline{(A \cdot B)}\) \(\overline A\) \(\overline B\) \(\overline A + \overline B\)
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

Столбцы \(\overline{(A \cdot B)}\) и \(\overline A + \overline B\) тоже совпадают. Значит, законы де Моргана доказаны.

Упрощение логических выражений

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

Задача: упростите выражение.

\[ X = \overline A \cdot B + \overline A \cdot C + \overline B \cdot C \]

Решение:

Заметим, что по закону исключённого третьего \(B + \overline B = 1\). Значит, второе слагаемое можно записать так.

\[ \overline A \cdot C = \overline A \cdot (B + \overline B)\cdot C = \overline A \cdot B \cdot C + \overline A \cdot \overline B \cdot C \]

Подставим это в исходное выражение.

\[ X = \overline A \cdot B + \overline A \cdot B \cdot C + \overline A \cdot \overline B \cdot C + \overline B \cdot C = \overline A \cdot B \cdot (1 + C) + (\overline A + 1)\cdot \overline B \cdot C = \overline A \cdot B + \overline B \cdot C \]

Такой приём иногда помогает увидеть более короткую форму выражения.

Для упрощения логических выражений удобно придерживаться такой последовательности действий.

  1. Если в выражении есть отрицания сложных частей, раскрыть их по законам де Моргана так, чтобы отрицание осталось только у отдельных переменных.
  2. Вынести общие множители, раскрыть скобки и применить другие законы алгебры логики.

Ниже приведён более подробный пример, в котором последовательно используются несколько разных законов.

Задача: упростите выражение.

\[ (A + \overline B)\cdot \overline{(A + B)}\cdot(\overline A + C) \]

Решение:

Сначала раскроем отрицание суммы по закону де Моргана.

\[ (A + \overline B)\cdot \overline A \cdot \overline B \cdot (\overline A + C) \]

Теперь упростим выражение по шагам.

\[ (A + \overline B)\cdot \overline A \cdot \overline B \cdot (\overline A + C) = (A\cdot \overline A + \overline B\cdot \overline A)\cdot \overline B \cdot (\overline A + C) = \overline B\cdot \overline A \cdot \overline B \cdot (\overline A + C) = \overline A \cdot \overline B \cdot (\overline A + C) = \overline A \cdot \overline B \]

Здесь последовательно использованы:

  • закон де Моргана: \(\overline{(A + B)} = \overline A \cdot \overline B\);
  • распределительный закон: \((A + \overline B)\cdot \overline A = A\cdot \overline A + \overline B\cdot \overline A\);
  • закон противоречия: \(A\cdot \overline A = 0\), поэтому этот член исчезает;
  • переместительный закон и закон повторения: \(\overline B\cdot \overline A \cdot \overline B = \overline A \cdot \overline B\);
  • закон поглощения: \(\overline A \cdot (\overline A + C) = \overline A\).
Задачи для тренировки: упрощение логических выражений

1. Упростите выражение:

\[ (A + B)\cdot(\overline A + \overline B) \]

Ответ

\[ (A + B)\cdot(\overline A + \overline B) = A \cdot \overline A + A \cdot \overline B + \overline A \cdot B + B \cdot \overline B \]
\[ = A \cdot \overline B + \overline A \cdot B \]

Слагаемые \(A \cdot \overline A\) и \(B \cdot \overline B\) исчезают по закону противоречия.

2. Упростите выражение:

\[ \overline{(A + \overline B)} + \overline{(A + B)} + A \cdot B \]

Ответ

\[ \overline{(A + \overline B)} = \overline A \cdot B, \qquad \overline{(A + B)} = \overline A \cdot \overline B \]
\[ \overline A \cdot B + \overline A \cdot \overline B + A \cdot B = \overline A \cdot (B + \overline B) + A \cdot B = \overline A + A \cdot B = \overline A + B \]

Сначала раскрыли отрицания, затем применили закон исключённого третьего и поглощение.

3. Упростите выражение:

\[ A + \overline{(A + B)} + \overline A \cdot B \]

Ответ

\[ A + \overline{(A + B)} + \overline A \cdot B = A + \overline A \cdot \overline B + \overline A \cdot B \]
\[ = A + \overline A \cdot (\overline B + B) = A + \overline A = 1 \]

Здесь использованы закон де Моргана и два раза закон исключённого третьего.

4. Упростите выражение:

\[ A + \overline A \cdot B + \overline A \cdot C \]

Ответ

\[ A + \overline A \cdot B + \overline A \cdot C = A + \overline A \cdot (B + C) \]
\[ = (A + \overline A)\cdot(A + B + C) = A + B + C \]

Сначала вынесли \(\overline A\), затем применили распределительный закон и закон исключённого третьего.

5. Упростите выражение:

\[ A \cdot B + \overline A \cdot C + B \cdot C \]

Ответ

Представим \(B \cdot C\) так:

\[ (A + \overline A)\cdot B \cdot C = A \cdot B \cdot C + \overline A \cdot B \cdot C \]

Тогда

\[ A \cdot B + \overline A \cdot C + B \cdot C = A \cdot B + \overline A \cdot C + A \cdot B \cdot C + \overline A \cdot B \cdot C \]
\[ = A \cdot B + \overline A \cdot C \]

Здесь пришлось сначала временно сделать запись длиннее, а потом применить поглощение.

Синтез логических выражений

До этого момента мы в основном разбирали уже готовые логические выражения: строили для них таблицы истинности, упрощали их и преобразовывали. Это задача анализа.

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

Рассмотрим сначала простейший пример: восстановим формулу для двух переменных по готовой таблице истинности.

Задача: восстановите формулу по этой таблице истинности.

\(A\) \(B\) \(X\)
0 0 1
0 1 1
1 0 0
1 1 1

Решение:

Способ 1. По строкам, где \(X = 1\).

Выделим все строки, в которых функция равна \(1\). Для каждой такой строки составим произведение, истинное только в этом случае:

  • если переменная в строке равна \(0\), она входит в произведение с отрицанием;
  • если переменная равна \(1\), она входит без отрицания.

Для этой таблицы получаем:

  • первая строка: \(\overline A \cdot \overline B\);
  • вторая строка: \(\overline A \cdot B\);
  • четвёртая строка: \(A \cdot B\).

Складывая эти выражения, получаем

\[ X = \overline A \cdot \overline B + \overline A \cdot B + A \cdot B \]

Упростим.

\[ X = \overline A \cdot (\overline B + B) + A \cdot B = \overline A + A \cdot B = (\overline A + A)\cdot(\overline A + B) = \overline A + B \]

Так мы получили формулу, заданную этой таблицей истинности.

Способ 2. По строкам, где \(X = 0\).

Если в таблице нулей меньше, чем единиц, удобнее сначала построить выражение для \(\overline X\), а потом применить отрицание.

Здесь \(X = 0\) только в одной строке, при \(A = 1\) и \(B = 0\). Поэтому

\[ \overline X = A \cdot \overline B \]

Тогда

\[ X = \overline{A \cdot \overline B} = \overline A + B \]

Это тот же ответ, но путь оказался короче.

Рассмотрим более сложный пример с тремя переменными.

Задача: восстановите формулу функции трёх переменных по этой таблице истинности.

\(A\) \(B\) \(C\) \(X\)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Решение:

Способ 1.

По строкам, где \(X = 1\), получаем

\[ X = \overline A \cdot \overline B \cdot \overline C + \overline A \cdot \overline B \cdot C + \overline A \cdot B \cdot \overline C + \overline A \cdot B \cdot C + A \cdot \overline B \cdot C + A \cdot B \cdot C \]

Упростим это выражение.

\[ \begin{aligned} X &= \overline A \cdot \overline B \cdot (\overline C + C) + \overline A \cdot B \cdot (\overline C + C) \\ &\quad + A \cdot C \cdot (\overline B + B) \\ &= \overline A \cdot \overline B + \overline A \cdot B + A \cdot C \\ &= \overline A \cdot (\overline B + B) + A \cdot C \\ &= \overline A + A \cdot C \\ &= (\overline A + A)\cdot(\overline A + C) \\ &= \overline A + C \end{aligned} \]

Способ 2.

В этой таблице нулей меньше, чем единиц, поэтому удобно сначала найти \(\overline X\).

\[ \overline X = A \cdot \overline B \cdot \overline C + A \cdot B \cdot \overline C = A \cdot \overline C \cdot (\overline B + B) = A \cdot \overline C \]

Тогда

\[ X = \overline{A \cdot \overline C} = \overline A + C \]

Этот способ проще, потому что в столбце \(X\) нулей действительно меньше, чем единиц.

Ответ в обоих способах совпал:

\[ X = \overline A + C \]
Задачи для тренировки: синтез логических выражений

1. Постройте выражения для логических функций двух переменных.

a)

\(A\) \(B\) \(X\)
0 0 0
0 1 1
1 0 0
1 1 1

Ответ

\[ X = \overline A \cdot B + A \cdot B = B \cdot (\overline A + A) = B \]

b)

\(A\) \(B\) \(X\)
0 0 1
0 1 0
1 0 1
1 1 1

Ответ

\[ X = \overline{\overline A \cdot B} = A + \overline B \]

c)

\(A\) \(B\) \(X\)
0 0 0
0 1 1
1 0 0
1 1 0

Ответ

\[ X = \overline A \cdot B \]

d)

\(A\) \(B\) \(X\)
0 0 0
0 1 0
1 0 1
1 1 0

Ответ

\[ X = A \cdot \overline B \]

2. Постройте выражения для логических функций трёх переменных.

a)

\(A\) \(B\) \(C\) \(X\)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

Ответ

\[ X = \overline A \cdot \overline B \cdot C + \overline A \cdot B \cdot \overline C + \overline A \cdot B \cdot C + A \cdot B \cdot \overline C \]
\[ X = \overline A \cdot B + \overline A \cdot \overline B \cdot C + A \cdot B \cdot \overline C = \overline A \cdot (B + C) + A \cdot B \cdot \overline C \]

b)

\(A\) \(B\) \(C\) \(X\)
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

Ответ

\[ X = \overline A \cdot \overline B \cdot \overline C + A \cdot \overline B \cdot \overline C + A \cdot B \cdot \overline C + A \cdot B \cdot C \]
\[ X = \overline B \cdot \overline C + A \cdot B \]

c)

\(A\) \(B\) \(C\) \(X\)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

Ответ

\[ X = \overline A \cdot \overline B \cdot \overline C + \overline A \cdot \overline B \cdot C + \overline A \cdot B \cdot \overline C + A \cdot B \cdot \overline C \]
\[ X = \overline A \cdot \overline B + B \cdot \overline C \]

По материалам:
1. К. Ю. Поляков, Е. А. Еремин. Учебник информатики для 10–11 классов. Углубленный уровень.