Эквивалентные преобразования

Теория:

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

Основные эквивалентные соотношения в булевой алгебре:

1) Ассоциативность конъюнкции и дизъюнкции

а) ;

б) .

2) Коммутативность конъюнкции и дизъюнкции

а) ;

б) .

3) Дистрибутивность конъюнкции относительно дизъюнкции

4) Дистрибутивность дизъюнкции относительно конъюнкции

5) Идемпотентность

а) ;

б) .

6) Закон двойного отрицания

7) Свойства констант 0 и 1

а) ; б) ; в) ;

г) ; д) ; е) .

8) Правила де Моргана

а) ; б) .

9) Закон противоречия

10) Закон исключенного третьего

Могут использоваться и некоторые другие соотношения, которые могут быть выведены из основных:

11) Поглощение

а) ; б) .

12) Склеивание

13) Обобщенное склеивание

а) ;

б) .

Задача 2. Упростить булеву формулу:

Решение:

Проведем следующие преобразования:

используя выражение 11 получим:

используя выражение 13,б получим:

используя выражение 3 получим:

используя выражение 10 получим:

используя выражение 7,а получим:

В результате преобразований получена простая дизъюнкция.

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

Таблица истинности

Задача 3. Упростить булеву формулу:

Решение:

используя выражение 3 получим:

используя выражение 9 получим:

используя выражения 7,б,г получим:

используя выражение 5,а получим:

используя выражение 11 получим:

В результате преобразований получена простая конъюнкция.

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

Таблица истинности

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

2.3. Дизъюнктивная и конъюнктивная нормальные формы

Теория:

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Всякая конъюнкция элементарных дизъюнкция называется конъюнктивной нормальной формой (КНФ).

Любую логическую функцию, не равную тождественно единице, можно представить в ДНФ.

Любую логическую функцию, не равную тождественно нулю, можно представить в КНФ.

Процедура приведения к ДНФ:

1. Все отрицания «спустить» до переменных с помощью формул (6) и (8).

2. Раскрыть скобки с помощью (1), (3), (4).

3. Удалить лишние конъюнкции и повторения в конъюнкциях с помощью (5), (9), (10).

4. Удалить константы с помощью (7).

Задача 4.Привести к ДНФ формулу

Решение.

раскрываем скобки (3)

правило де Моргана (8,б)

правила (9, 7,б, 8,а)

правила (8,а и 8,б, 6)

раскрываем скобки

правило (5,а)

применяем обобщенное склеивание (13,а),

введя обозначения , получим

раскрываем скобки и правило (9, 5,а)

выносим за скобки

правило обобщенного склеивания (13,б)

раскрываем скобки

Теория:

Процедура приведения ДНФ к КНФ:

Пусть ДНФ F имеет вид

, где k₁, k₂, …, k_m – элементарные конъюнкции.

1. Применить к F правило двойного отрицания

и привести к ДНФ , где – элементарные конъюнкции. Тогда:

2. С помощью правила де Моргана освободиться от второго отрицания и преобразовать отрицания элементарных конъюнкций в элементарные дизъюнкции . Тогда:

Задача 5. Привести формулу к КНФ

Решение:

вводим двойное отрицание

правило де Моргана (8,б)

правило де Моргана (8,а)

раскрываем скобки и правило (5, 9)

правило склеивания (12)

правило де Моргана (8,б)

Теория:

Способ перехода от табличного задания логических функций к булевой формуле.

Процедура перехода к СДНФ:

а) для каждого набора значений переменных , на котором функция равна 1, выписываются конъюнкции всех переменных;

б) над теми переменными, которые на этом наборе равны 0, ставятся отрицания;

в) все такие конъюнкции соединяются знаками дизъюнкции.

Полученная таким образом формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции .

Процедура перехода к СКНФ:

а) для каждого набора значений переменных , на котором функция равна 0, выписываются дизъюнкции всех переменных;

б) над теми переменными, которые на этом наборе равны 1, ставятся отрицания;

в) все такие дизъюнкции соединяются знаками конъюнкции.

Полученная таким образом формула называется совершенной конъюнктивной нормальной формой (СКНФ) логической функции .

Задача 6. Логическую функцию трех переменных представить булевой формулой в виде СДНФ и СКНФ:

Решение:

Построим таблицу истинности последовательно в соответствии с шагами построения формулы

						конъюнкции	дизъюнкции

Таким образом, СДНФ будет выглядеть следующим образом:

а СКНФ имеет вид:

Задача 7. Показать справедливость представления следующей бинарной логической операции:

Решение:

Составим таблицу истинности для правой и левой сторон равенства:

правая часть: левая часть:

Из таблиц видно, что столбцы результирующих формул правой и левой частей равенства совпадают, также совпадают и СДНФ правой и левой сторон уравнения. Таким образом, справедливость предложенной формулы подтверждается.