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

Пример 2. Возьмём соотношение 8а и подставим вместо переменной выражение . Получим: . Здесь в обеих частях стоят формулы, неэквивалентные исходным формулам, но эквивалентные между собой. Если же в правой части нового соотношения формулу заменить формулой , эквивалентной ей в силу соотношения 8а и затем заменить на (согласно 6), то получим . Причём все формулы в полученной цепи преобразований являются эквивалентными:

.

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

В булевой алгебре принято опускать скобки в следующих двух случаях: а) при последовательном выполнении нескольких конъюнкций или дизъюнкций; б) если они являются внешними скобками у конъюнкции. Оба соглашения совершенно аналогичны общепринятому опусканию скобок для операции умножения в арифметических выражениях.

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

а) Поглощение: 1) и 2) . Докажем данное равенство подробно, используя для доказательства соотношения 3, 7а и 7в.

.

Далее будем опускать доказательства приводимых равенств, которые при желании можно получить из соотношений 1 – 10 и уже доказанных равенств.

б) Склеивание: .

в) Обобщённое склеивание: .

г) .

Одним из главных видов упрощения формул является приведение их к дизъюнктивной нормальной форме (ДНФ).

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

Заметим, что СДНФ является частным случаем ДНФ.

Приведение формулы к ДНФ выполняется так. Сначала с помощью соотношений 6 и 8 все отрицания “спускаются” до переменных. Затем раскрываются скобки. После этого с помощью соотношений 5, 9 и 10 удаляются лишние конъюнкции и повторения переменных в конъюнкциях. Наконец, с помощью соотношений 7а – 7е удаляются лишние константы. При этом необходимо помнить, что ДНФ данной формулы может быть не единственной.

Пример 3. Привести к ДНФ формулу .

Решение:

. В итоге получили дизъюнкцию элементарных конъюнкций, то есть ДНФ.

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

Теорема 8.3. Для любых двух эквивалентных формул и существует эквивалентное преобразование в и наоборот с помощью соотношений 1 – 10.

Аналогично понятию ДНФ определяется понятие конъюнктивной нормальной формы (КНФ), то есть КНФ есть конъюнкция элементарных дизъюнкций. Переход от КНФ к ДНФ и обратно всегда осуществим (обычно, с помощью формул Де Моргана).

Пример 4. Привести формулу к КНФ.

Заменим исходную формулу её двойным отрицанием, а затем применим соотношения 8.

.