Главная >> Информатика 10 класс. Босова

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

Основные законы алгебры логики

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

Приведём основные законы алгебры логики.

1. Переместительные (коммутативные) законы:

2. Сочетательные (ассоциативные) законы:

3. Распределительные (дистрибутивные) законы:

4. Законы идемпотентности (отсутствия степеней и коэффициентов):

5. Закон противоречия:

6. Закон исключённого третьего:

7. Закон двойного отрицания:

8. Законы работы с константами:

9. Законы де Моргана:

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

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение

Последовательно применим дистрибутивный закон и закон исключённого третьего:

Пример 2.

Аналогичные законы выполняются для операций объединения, пересечения и дополнения множеств. Например:

Пробуйте самостоятельно доказать один из этих законов с помощью кругов Эйлера.

Пример 3.

На числовой прямой даны отрезки В = [2; 12] и С = [7; 18]. Каким должен быть отрезок А, чтобы предикат становился истинным высказыванием при любых значениях х.

Преобразуем исходное выражение, избавившись от импликации:

А, В и С — множества. Для них можем записать:

Известно, что

Будем считать, что Тогда причём это минимально возможное множество А.

Множество В — это отрезок [2; 12].

Множество — это промежутки ]-∞; 7[ и ]18; +∞[.

Пересечением этих множеств будет служить промежуток [2; 7[. В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.

Чему равна минимальная длина отрезка А? Укажите ещё несколько вариантов множества А.

Пример 4.

Для какого наименьшего неотрицательного целого десятичного числа а выражение

тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

Прежде всего, вспомним, что представляет собой поразрядная конъюнкция двух целых десятичных чисел, например 27 и 22.

27 = 11011₂, 22 = 10110₂.
27 & 22 = 11011 & 10110 = 10010₂ = 18₁₀.

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

Окончание >>>