Лекция № 9. Булевы алгебры.

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

1. Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

Введём обозначения: . Пусть параметр, равный 0 или 1. Тогда , если , и , если .

Теорема 8.1. Всякая логическая функция может быть представлена в следующем виде:

,

где , а дизъюнкция берётся по всем наборам значений переменных .

Равенство (1) называется разложением по переменным . Формула (1) достаточно громоздка на вид, однако её несложно использовать при небольших значениях и . Например, при значениях , разложение (1) имеет вид:

.

Практический смысл такого разложения очевиден: оно позволяет заменять функцию нескольких переменных суперпозицией конечного числа функций с меньшим количеством переменных. Особенно важен частный случай , когда разложение производится по всем переменным. При этом все переменные в правой части равенства (1) получают фиксированные значения, и функции в конъюнкциях правой части становятся равными 0 или 1, что даёт:

,

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

Пример 1. Составить СДНФ для функции, заданной таблицей:

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

Получим: .

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

.

Единственная функция, которая не имеет СДНФ – это константа .

Формулы, содержащие кроме переменных и скобок, только знаки дизъюнкции, конъюнкции и отрицания, будем называть булевыми формулами.

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

1. Булева алгебра функций.

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

Определение. Булевой алгеброй логических функций называется алгебра вида , основным множеством которой является всё множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание.

Замечание. На практике мы имеем дело не самими функциями, а с представляющими их формулами, то есть с алгеброй формул, которая значительно шире, поскольку каждую функцию представляет бесконечное множество формул. Чтобы “синхронизировать” их алгебре формул придаётся следующий вид. Элементами алгебры формул объявляются не сами формулы, а классы эквивалентности формул, то есть классы формул, представляющих одну и ту же функцию. Определённая таким образом, алгебра формул называется алгеброй Линденбаума - Тарского. Она изоморфна булевой алгебре функций.

Теперь рассмотрим основные свойства булевых операций (частично уже знакомые по теме “Элементы математической логики”).

1. Ассоциативность: а) ; б) .

2. Коммутативность: а) ; б) .

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

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

.

5. Идемпотентность: а) ; б) .

6. Двойное отрицание: .

7. Свойства констант: а) ; б) ; в) ; г) ; д) ; е) .

8. Правила де Моргана: а) ; б) . Очень важные соотношения, которые часто будут использоваться в дальнейшем. С их помощью (а также с помощью соотношения 6) дизъюнкция заменяется конъюнкцией и наоборот.

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

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

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

При подстановке формулы вместо переменной всевхождения данной переменной в исходное соотношение должны быть одновременно заменены формулой .

Правило подстановки позволяет получать из соотношений 1 – 10 новые эквивалентные соотношения. Заметим, что равенство означает в данном контексте, что формулы и описывают одну и ту же логическую функцию. Следовательно, если какая-то формула содержит в качестве подформулы, то замена её на не изменит значения формулы . Это утверждение представляет собой правило замены подформул, которое позволяет, используя эквивалентные соотношения, получать формулы, эквивалентные данной. Практическое применение описанных правил будет рассмотрено ниже.

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

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

Пример 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.

.