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

Алгебра логики - это математический аппарат, который позволяет производить алгебраические действия над логическими высказываниями. Алгебру логики также называют булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего основные ее методы в XIX веке.

Логическое высказывание - это утверждение, которое может быть либо истинным, либо ложным. Примеры высказываний: "Этот автомобиль черного цвета", "3 меньше 5". Противоречивое утверждение не может быть логическим высказыванием, например "Данное утверждение ложно". Логические высказывания обычно обозначаются латинскими буквами. В алгебре логики определены три основных логических операций с высказываниями и законы для выполнения этих операций. Действия с логическими высказываниями записываются в виде логических выражений.

Итак, для любого логического высказывания возможны два значения:

ИСТИНА - в некоторых языках програмирования обозначается как True, в формулах и таблицах используется 1

ЛОЖЬ - в некоторых языках програмирования обозначается как False, в формулах и таблицах используется 0

Любую логическую функцию можно представить в виде выражения или в виде таблицы истинности. В таблице истинности в столбцах указаны значения аргументов (переменных, операндов) и значение функции. Количество строк в таблице определяется количеством переменных и равно 2N, где N - количество перменных.

Основные логические операции:

1. Логическое отрицание (Инверсия). Обозначается \( ¬A \), not A, НЕ А, в записи на черновике удобно использовать \( \overline{A} \)

Выражение \( \overline{A} \) истинно тогда, когда \( A \) ложно и ложно, когда \( A \) истинно.

Таблица истинности операции логического отрицания:

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

2. Логическое умножение (Конъюнкция). Обозначается \( A \)  \( B \) ,  \( A \) and \( B \), \( A \) И \( B \), \( A \) \( B \), в записи на черновике удобно использовать \( A ⋅ B\)

Выражение \( A ⋅ B\) истинно тогда и только тогда, когда оба высказывания \( A \) и \( B \) истинны.

Таблица истинности операции логического умножения:

\( A \) \( B \) \( A ⋅ B \)
0 0 0
0 1 0
1 0 0
1 1 1

3. Логическое сложение (Дизъюнкция). Обозначается \( A \) ∨ \( B \) ,  \( A \) or \( B \), \( A \) ИЛИ \( B \), \( A \) \( B \), в записи на черновике удобно использовать \( A + B\)

Выражение \( A + B\) ложно тогда и только тогда, когда оба высказывания \( A \) и \( B \) ложны.

Таблица истинности операции логического сложения:

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

Остальные операции алгебры логики можно выразить основными операциями. Перечислим их:

4. Исключающее ИЛИ. Обозначается \( A \) XOR \( B \) ,  \( A \)  \( B \)

Выражение  \( A \) ⊕ \( B \) истинно тогда и только тогда, когда высказывания \( A \) и \( B \) не равны.

Таблица истинности операции исключающего ИЛИ:

\( A \) \( B \) \( A \) ⊕ \( B \)
0 0 0
0 1 1
1 0 1
1 1 0

Исключающее ИЛИ можно выразить: \( \overline{A} ⋅ B + A ⋅ \overline{B} \) 

5. Логическое следование (Импликация). Обозначается \( A \)  \( B \) ,  \( A \)  \( B \)

Выражение  \( A \) → \( B \) ложно тогда и только тогда, когда высказывание \( A \) истинно, а \( B \) ложно.

Таблица истинности операции логического следования:

\( A \) \( B \) \( A \) → \( B \)
0 0 1
0 1 1
1 0 0
1 1 1

Логическое следование можно выразить: \( \overline{A} + B \) 

6. Эквивалентность (Равносильность). Обозначается \( A \)  \( B \) ,  \( A \) ~ \( B \),  \( A \)  \( B \)

Выражение  \( A \) ≡ \( B \) истинно тогда и только тогда, когда высказывания \( A \) и \( B \) совпадают.

Таблица истинности операции эквивалентность:

\( A \) \( B \) \( A \) ≡ \( B \)
0 0 1
0 1 0
1 0 0
1 1 1

Эквивалентность можно выразить: \( (\overline{A} + B) ⋅ (A + \overline{B}) \)

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

  1. логическое отрицание
  2. логическое умножение
  3. логическое сложение
  4. исключающее ИЛИ
  5. логическое следование
  6. эквивалентность

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

 

Исключение констант \( 1 + A = 1 \)
\( 0 ⋅ A = 0 \)
\( 0 + A = A \)
\( 1 ⋅ A = A \)
Идемпотентность \( A + A = A \)
\( A ⋅ A = A \)
Закон исключения третьего \( A + \overline{A} = 1 \)
Закон непротиворечивости \( A ⋅ \overline{A} = 0 \)
Закон отрицания \( \overline{\overline{A}} = A \)
Закон коммутативности \( A + B = B + A \)
\( A ⋅ B = B ⋅ A \)
Закон ассоциативности \( A + B + C = A + (B + C)\)
\( A ⋅ B ⋅ C = A ⋅ (B ⋅ C)\)
Закон дистрибутивности \( A ⋅ (B + C) = A ⋅ B + A ⋅ C \)
\( A + (B ⋅ C) = (A + B) ⋅ (A + C) \)
Правило де Моргана \( \overline{(A + B)} = \overline{A} ⋅ \overline{B}\)
\( \overline{(A ⋅ B)} = \overline{A} + \overline{B}\)
Закон поглощения \( A + A ⋅ B = A\)
\( A ⋅ (A + B) = A\)
Закон склеивания \( A ⋅ B + \overline{A} ⋅ B = B \)
\( (A + B) ⋅ (\overline{A} + B) = B \)

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

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

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

Рассмотрим несколько примеров:

 

1.   \( \overline{(x ⋅ \overline{x}) } ⋅ (y + \overline{y}) = \)   первый множитель - по закону непротиворечивости,
    \( =  \overline{0}  ⋅  1 = 1 ⋅ 1 = 1 \)   а второй множитель по закону исключения третьего
 
2.   \( \overline{(x + y)} ⋅ (x ⋅ \overline{y}) = \)   правило де Моргана
    \( = \overline{x} ⋅ \overline{y} ⋅ (x ⋅ \overline{y}) = \)   ассоциативный закон
    \(= \overline{x} ⋅ x ⋅ \overline{y} ⋅ \overline{y} = \)   закон непротиворечивости
    \(= 0 ⋅ \overline{y} ⋅ \overline{y} = 0 \)    
 
3.       Докажем закон склеивания преобразованием выражения
    \( (x + y) ⋅ (\overline{x} + y) = \)   закон дистрибутивности
    \( = x ⋅ \overline{x} + y ⋅ \overline{x} + x ⋅ y + y ⋅ y = \)   закон дистрибутивности для второго и третьего слагаемых
    \( = 0 + y ⋅ (\overline{x} + x) + y = \)   исключение констант
    \( = y ⋅ 1 + y = y \)    
 
4.   \( \overline{(x ⋅ y + \overline{z})} = \)   правило де Моргана
    \( = \overline{(x ⋅ y)} ⋅ \overline{\overline{z}} = \)   правило де Моргана и двойное отрицание
    \( = (\overline{x} + \overline{y}) ⋅ z \)    
 
5.   \( (x + y) ⋅ (\overline{x} + y) ⋅ (\overline{x} + \overline{y}) = \)   повторяем второй множитель
    \( = (x + y) ⋅ (\overline{x} + y) ⋅ (\overline{x} + y) ⋅ (\overline{x} + \overline{y}) = \)   закон склеивания для двух пар множителей
    \( = y ⋅ \overline{x} \)    

 

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

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

Для того, чтобы построить таблицу истинности выражения нужно:

Задача: Построить таблицу истинности для логического выражения \(  \overline{x} ⋅ y  + \overline{x + y} \)

Решение: 

Переменные Промежуточные операции Значение выражения
\( x \) \( y \) \( \overline{x} \) \( \overline{x} ⋅ y \) \( x + y \) \( \overline{x + y} \) \( \overline{x} ⋅ y  + \overline{x + y} \)
0 0 1 0 0 1 1
0 1 1 1 1 0 1
1 0 0 0 1 0 0
1 1 0 0 1 0 0

 

Построение формулы логической функции по таблице истинности

Строится формула следующим образом:

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

Дизъюнктивная нормальная форма называется совершенной, если все конъюкции в ней состоят из одного и того же набора переменных, каждый из которых входит в конъюнкцию один раз.

Задача: Дана полная таблица истинности некоторой функции. Построить формулу функции по этой таблице.

\( x \) \( y \) \( z \) \( F \)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

 1. Удаляем строки со значением функции равным 0

\( x \) \( y \) \( z \) \( F \)
0 1 0 1
1 0 0 1
1 0 1 1
1 1 1 1

2. Составляем конъюнкции для каждой строки

\( x \) \( y \) \( z \) \( F \) Конъюнкция
0 1 0 1 \( \overline{x} ⋅ y ⋅ \overline{z} \)
1 0 0 1 \( x ⋅ \overline{y} ⋅ \overline{z} \)
1 0 1 1 \( x ⋅ \overline{y} ⋅ z \)
1 1 1 1 \( x ⋅ y ⋅ z \)

3. Объединяем все конъюнкции дизъюнкцией:

\( F(x,y,z) = \overline{x} ⋅ y ⋅ \overline{z} + x ⋅ \overline{y} ⋅ \overline{z} + x ⋅ \overline{y} ⋅ z + x ⋅ y ⋅ z \)

 

 Разбор некоторых задач

 

Задача: Для какого из указанных \( X \) истинно высказывание \( ¬((X > 2) → (X > 3)) \)?

1) 1     2) 2    3) 3    4) 4

Решение: 

Введем обозначения \( (X > 2) - A, (X > 3) - B \), перепишем логическое выражение в удобной нам форме и упростим его, преобразовав импликацию и применив правило де Моргана:

\( \overline{(A → B)} = \overline{\overline{A} + B} = \overline{\overline{A}} ⋅ \overline{B} = A ⋅ \overline{B} \).   Полученное выражение истинно, когда истинны оба множителя, то есть:

\( \begin{cases}A = 1 \\ \overline{B} = 1 \end{cases} \)    или    \( \begin{cases}X > 2 \\ X ≤ 3 \end{cases} \) , заметим, что утверждение \( (X ≤ 3) \) противоположно утверждению \( (X > 3) \)

Системе неравенств удовлетворяет \( X = 3 \). Ответ: вариант 3.

 

Задача: Символом  \( F \)  обозначено одно из указанных ниже логических выражений от трех аргументов \( X, Y, Z \) . Дан фрагмент истинности выражения  \( F \) :

\( X \) \( Y \) \( Z \) \( F \)
1 0 0 1
0 0 0 1
1 1 1 0

Какое выражение соответствует \( F \)?

1)  \( ¬X ∧ ¬Y ∧ ¬Z \)     2) \( X ∧ Y ∧ Z \)     3) \( X ∨ Y ∨ Z \)     4) \( ¬X ∨ ¬Y ∨ ¬Z \)

Решение:  Для удобства перепишем выражения в удобной форме:

1)  \( \overline{X} ⋅ \overline{Y} ⋅ \overline{Z} \)     2) \( X ⋅ Y ⋅ Z \)     3) \( X + Y + Z \)     4) \( \overline{X} + \overline{Y} + \overline{Z} \)

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

Но можно сразу отвергнуть выражение 2, потому что коньюнкция переменных \( X, Y, Z \) при их значениях равным 1 должно быть истинно, а по таблице ложно. Выражение 3 также следует отвергнуть, так как дизъюнкция переменных \( X, Y, Z \) при их значениях равным 0 должно быть ложным, а по таблице истинно.

Значение первого выражения на первом же наборе данных таблицы не совпадает с табличным:

\( \overline{X} ⋅ \overline{Y} ⋅ \overline{Z} \) = \( \overline{1} ⋅ \overline{0} ⋅ \overline{0}  = 0 ⋅ 1 ⋅ 1 = 0\)

Остается только выражение 4. Для подтверждения вычислим все значения выражения на наборах данных таблицы:

\( \overline{X} + \overline{Y} + \overline{Z} \) = \( \overline{1} + \overline{0} + \overline{0}  = 0 + 1 + 1 = 1\)

\( \overline{X} + \overline{Y} + \overline{Z} \) = \( \overline{0} + \overline{0} + \overline{0}  = 1 + 1 + 1 = 1\)

\( \overline{X} + \overline{Y} + \overline{Z} \) = \( \overline{1} + \overline{1} + \overline{1}  = 0 + 0 + 0 = 0\)

Ответ: 4.

 

Задача: Какое из приведенных имен соответствует условию:

(Первая буква согласная) ∨ (Вторая буква гласная) → (В слове 4 буквы)

1) МИХАИЛ     2) ГРИГОРИЙ     3) ЕВГЕНИЙ     4) ИОЛАНТА ?

Решение: Обозначим высказывания: 

(Первая буква согласная) - A
(Вторая буква гласная)  - B
(В слове 4 буквы) - C

Тогда выражение будет получит вид: \( A + B → C \). 

Преобразуем его: \( A + B → C = \overline{(A + B)} + C  = \overline{A} ⋅ \overline{B} + C \) 

Условие задачи будет выглядеть: \( \overline{A} ⋅ \overline{B} + C = 1\). Но так как во всех приведенных именах больше четырех букв, то  \( C = 0 \)  и условие принимает вид \( \overline{A} ⋅ \overline{B} = 1\), то есть:

\( \begin{cases}\overline{A} = 1 \\ \overline{B} = 1 \end{cases} \)    или    \( \begin{cases} \text{(Первая буква гласная)} \\ \text{(Вторая буква согласная)} \end{cases} \)

Заметим, что оба утверждения противоположны исходным. Этим условиям отвечает только вариант 3.

 

Задача: Каково наименьшее натуральное число \( X\), при котором истинно высказывание:

\( (X^{2} < 80) → ((X + 1)^{2} > 80)  \) ?

Решение:  Обозначим \( (X^{2} < 80) \) - A, \( ((X + 1)^{2} > 80)  \) - B, тогда получим условие задачи в виде:

\( A → B  \), преобразовываем: \( \overline{A} + B \). Полученное выражение истинно, когда истинно одно из слагаемых. Рассмотрим оба случая:

  1. \( X^{2} ≥ 80 \). В задаче речь идет о натуральных числах, поэтому отрицательные значения не рассматриваем: \( X ≥ 4\sqrt{5} \). Ближайшее натуральное число 9, поэтому \( X ≥ 9 \)
  2. \( (X + 1)^{2} > 80 \),    \( X + 1 > 4\sqrt{5} \),   \( X > 4\sqrt{5} - 1 \),   \( X ≥ 8\).

 Получается, что высказывание истинно при  \( X ≥ 9 \) или  при \( X ≥ 8 \). Наименьшее число 8.

 

Задача: Укажите значения переменных \( K, L, M, N \), при которых ложно логическое выражение:

\( (¬K ∨ M) → (¬L ∨ M ∨ N) \)

Ответ запишите в виде строки их четырех символов - значений переменных \( K, L, M, N \) (в указанном порядке). Так, например, строка 1101 соответствует тому, что \( K = 1, L = 1, M = 0, N = 1 \)

Решение: Надо решить уравнение \( (\overline{K} + M) → (\overline{L} + M + N) = 0\). Преобразовываем:

\( \overline{(\overline{K} + M)} + (\overline{L} + M + N) = 0\),  \( (K ⋅ \overline{M}) + (\overline{L} + M + N) = 0\), оба выражения в скобках должны быть ложны, поэтому получаем систему уравнений:

\( \begin{cases}\overline{L} + M + N = 0\\ K ⋅ \overline{M} = 0 \end{cases} \) 

Чтобы дизъюнкция была бы ложной, должны быть ложны все переменные, поэтому из первого уравнения получаем, что \( L = 1, M = 0, N = 0 \). Подставляем \( M = 0\) во второе: \(K ⋅ \overline{0} = 0 \), \(K ⋅ 1 = 0 \), получаем \( K = 0\)

Записываем значения переменных в указанном порядке: 0100

 

Задачи для самостоятельного решения