Кнопка меню
ИНФОРМАТИКА
подготовка к ЕГЭ
Задачи

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

Алгебра логики - это математический аппарат, который позволяет производить алгебраические действия над логическими высказываниями. Алгебру логики также называют булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего основные ее методы в 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 + x ⋅ \overline{y} \)

Решение:

Переменные Промежуточные операции Значение выражения
\( x \) \( y \) \( \overline{x} \) \( \overline{y} \) \( \overline{x}⋅y \) \( x⋅\overline{y} \) \( \overline{x}⋅y + x⋅\overline{y} \)
0 0 1 1 0 0 0
0 1 1 0 1 0 1
1 0 0 1 0 1 1
1 1 0 0 0 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

 

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