Дизъюнктивные и конъюнктивные нормальные формы
Элементарной конъюнкцией или конъюнктом называется конъюнкция литер.
Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.
Пример. Формулы и - дизъюнкты, формулы и - конъюнкты, а является одновременно и дизъюнктом, и конъюнктом.
Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).
Пример. Формула — ДНФ, формула — КНФ, а формула является одновременно КНФ и ДНФ.
1. Любая формула эквивалентна некоторой ДНФ.
2. Любая формула эквивалентна некоторой КНФ.
Алгоритм приведения формулы к ДНФ.
1. Выразить все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалентности
и определения операций:
штрих Шеффера (антиконъюнкция) ,
стрелки Пирса (антидизъюнкция)
сумма по модулю два (антиэквивалентность) .
2. Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания по правилу
3. Используя закон дистрибутивности
преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций. В результате применения пп. 1-3 получается ДНФ данной формулы.
Пример 6. Привести к ДНФ формулу .
Решение. Выразим логические операции и через , и :
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
Используя закон дистрибутивности, приводим формулу к ДНФ:
Приведение формулы к КНФ производится аналогично приведению ее к ДНФ, только вместо п. 3 применяется пункт
3'. Используя закон дистрибутивности
, преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.
Пример 6. Привести к КНФ формулу ,
Решение. Преобразуем формулу φ к формуле, не содержащей :
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания: φ
По закону дистрибутивности получаем, что формула φ эквивалентна формуле
Упростим полученную формулу:
1) используем закон дистрибутивности
2) используем закон эквивалентность φ φ0
3) используем закон поглощения
Таким образом, формула φ из примера 6.1.1 эквивалентными преобразованиями приводится к формуле (являющейся одновременно ДНФ и КНФ формулы φ).
Построить таблицу истинности
Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).
Совершенные ДНФ (СДНФ) и КНФ (СКНФ).
Пусть (x1. xn) — набор логических переменных, Δ = (δ1. δп) — набор нулей и единиц.
Конституентой единицы набора Δ называется конъюнкт K 1 (δ1 . δп) = .
Конституентой нуля набора Δ называется дизъюнкт K 0 (δ1 … δп) = .
Отметим, что K 1 (δ1 . δп) = 1, а K 0 (δ1 … δп) = 0 тогда и только тогда, когда х1 = δ1, х2 = δ2, хn = δn.
Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых.
Совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых.
Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная хi из набора входит ровно один раз, причем входит либо сама хi, либо ее отрицание .
Пример. Формула есть конституента единицы К 1 (1,0,1).
Формула есть конституента нуля К 0 (0,0,1).
Формула — СДНФ.
Формула — СКНФ.
Формула не является СДНФ.
Первая теорема Шеннона
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле φ, предварительно рассмотрим разложения булевой функции f(x1, х2,. xп) по k; переменным (для определенности по x1, х2,. xk) — разложения Шеннона.
Теорема (первая теорема Шеннона). Любая булева функция f(x1, х2,. xп) представима в виде разложения Шеннона:
Доказательство. Прежде всего, заметим, что . Подставим произвольно вместо первых k переменных их значения: . Тогда левая часть доказываемой формулы равна Правая часть представляет собой дизъюнкцию 2 k конъюнкций вида , которые этой подстановкой разбиваются на два класса. К первому классу относится конъюнкция, у которой набор (δ1, δ2,. δk) совпадает с набором :
Эта конъюнкция равна левой части формулы. Ко второму классу относится 2 k -1 конъюнкций, у каждой из которых хотя бы в одной переменной xi, выполнено условие . Следовательно, каждая из них равна нулю. Используя закон , получаем, что левая и правая части формул равны при любой подстановке переменныхx1, x2. xn.
Вторая теорема Шеннона
В силу принципа двойственности для булевых алгебр справедлива
Теорема 6.4.3 (вторая теорема Шеннона). Любая булева функция f(x1, х2,. xп) представима в виде разложения Шеннона:
В предельном случае, когда k = n, для булевой функции f(x1, х2,. xп), не равной нулю, получаем ее представление в виде совершенной ДНФ:
Аналогично для булевой функции f(x1, х2,. xп), не равной единице, получаем ее представление в виде совершенной КНФ:
Приведенные формулы позволяют сформулировать следующую теорему о функциональной полноте.
Функциональная полнота
Теорема (о функциональной полноте). Для любой булевой функции f найдется формула φ, представляющая функцию f. Если f ≠ 0, то существует представляющая ее формула φ, находящаяся в СДНФ:
и такое представление единственно с точностью до порядка следования конституент единицы. Если f ≠ 1, то существует приставляющая ее формула φ, находящаяся в СКНФ:
и такое представление единственно с точностью до порядка следования конституент нуля.
Пример.
Найти СДНФ и СКНФ функции f(x,y,z), заданной следующей таблицей истинности:
f(x,y,z)
Решение. По теореме о функциональной полноте СДНФ имеет вид , а СКНФ — . Для нахождения СДНФ и СКНФ исходной формулы φ составляется ее таблица истинности, а затем по ней строится требуемая совершенная нормальная форма. По СДНФ φ1 для функции f, можно составить ее таблицу истинности и по ней найти СКНФ φ2.
Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.
Алгоритм нахождения СДНФ.
Для нахождения СДНФ данную формулу нужно привести сначала к ДНФ, а затем преобразовать ее конъюнкты в конституенты единицы с помощью следующих действий:
а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то нужно удалить этот конъюнкт из ДНФ;
б) если в конъюнкт одна и та же литера х δ входит несколько раз, то удалить все литеры х δ , кроме одной;
в) если в некоторый конъюнкт не входит переменная y, то этот конъюнкт заменить на эквивалентную формулу применяя закон дистрибутивности, привести полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляется соответствующую формулу вида ;
г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставить только одну из них. В результате получается СДНФ.
Пример. Найдем СДНФ для ДНФ .
Решение. Имеем φ
Алгоритм приведения КНФ к СКНФ аналогичен вышеизложенному описанию алгоритма приведения ДНФ к СДНФ.
Минимизация булевых функций в классе ДНФ
Вхождение переменной – это место, которое переменная занимает в формуле. Каждая формула имеет конечное число вхождений переменных. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных.
Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза.
Пример 6.6.1. Формула — элементарное произведение, а формула элементарным произведением не является.
Формула φ(x1, x2,…,xп) называется импликантой формулы ψ(x1, x2,…,xп), если φ — элементарное произведение и φ ψ
φ, т. е. для соответствующих формулам φ и ψ функций fφ и fψ справедливо неравенство fφ ≤ fψ. Формула φ(x1, x2,…,xп) называется импликантой функции f, если φ — импликанта совершенной ДНФ, представляющей функцию f.
Импликанта φ(x1, x2,…,xп) = формулы ψ называется простой, если после отбрасывания любой литеры из φ не получается формула, являющаяся импликантой формулы ψ.
Пример 6.6.2. Найти все импликанты и простые импликанты для формулы
φ (х,у) = х → у.
Всего имеется 8 элементарных произведений с переменными х и у. Ниже приведены их таблицы истинности: