Дискретная математика. Прокушев Л.А. - 21 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

19
возникает двойственность свойств дизъюнкции и конъюнкции. Выпол-
нив в приведенных определениях подобные замены, получим соответ-
ствующие определения для конъюнктивной нормальной формы. Напри-
мер, для функции f(x
1
, x
2
, x
3
) элементарная дизъюнкция получается из
элементарной конъюнкции инвертированием переменных и заменой
операции конъюнкции на дизъюнкцию:
элементарная конъюнкция: элементарная дизъюнкция:
12
хх
12
хх
∨
конституента 1: конституента 0:
123
хх х
123
хх х∨∨
Конъюнктивной нормальной формой (КНФ) называется конъюнкция
различных элементарных дизъюнкций:
12 13
()().
хх хх∨⋅∨
Совершенной КНФ (СКНФ) называется КНФ, состоящая только из
конституент 0:
123 123
()().
хх х хх х∨∨ ⋅ ∨∨
Осуществляя такую замену, можно автоматически для любого выве-
денного впоследствии свойства (соотношения) получить двойственное
ему свойство. Поэтому ограничимся рассмотрением утверждений лишь
для ДНФ.
Теорема 1 (о приведении формулы к СДНФ). С помощью соотноше-
ний (1–16) любая формула булевой алгебры может быть приведена к СДНФ.
Пример. Преобразовать формулу
(,,)
f x y z x yz xyz
=∨ ∨
к СДНФ.
На основании соотношений (8, 9) приведем формулу к виду:
(,,) ( )( ) ( ) .f x y z x y y z z yz x x xyz
=∨ ∨∨ ∨∨
Используя соотношения (4, 1, 2, 3), последовательно придем к сле-
дующей формуле:
(,,) ( )( )
.
xyz xyz xyz xyz xyz xyz xyz
xyz xyz xyz xyz xyz xyz
=∨ ∨∨∨∨=
=∨∨∨∨∨∨=
=∨∨∨∨∨
Полученная СДНФ эквивалентна исходной формуле и все выпол-
ненные шаги обратимы, т. е. от СДНФ с помощью соотношений (1–16)
можно перейти к исходной формуле.

Страницы