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

UptoLike

ВУЗ: 

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

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

Рубрика: 

21
на этом наборе в 0 по правилу:
, если 0,
, если 1 .
i
ii
i
ii
x
x
x
α
α=
=
α=
Все остальные конституенты 0 на данном наборе обращаются в 1.
Например, для функции набору (0, 1, 0) соответствует конституента 0:
123
xxx
∨∨
.
Образуя дизъюнкцию конституент 0, соответствующих всем набо-
рам, на которых функция обращается в 0, получим СКНФ, равную дан-
ной функции.
Пример. Представим параллельно алгоритмы получения СДНФ и
СКНФ для функции, заданной следующей таблицей истинности:
Получение СДНФ: Получение СКНФ:
1. По правилам, определенным выше, рядом со строками, где f(x, y) = 1,
записать конституенты 1, а где f(x, y) = 0, записать конституенты 0.
2. Все полученные выражения для конституент связать операцией:
дизъюнкции для СДНФ: конъюнкции для СКНФ:
xу
х
у
∨
(
)(
)
x уху∨⋅∨
Покажем, что полученные по двум алгоритмам СДНФ и СКНФ экви-
валентны. Преобразуем СКНФ по правилам булевой алгебры:
(
)( )
.
x уху хххухууухуху∨⋅∨= ∨ ∨∨ = ∨
Рекомендуется использовать тот из двух алгоритмов, в котором меньше
конституент, а затем упростить формулу, используя булевы операции.
Эквивалентные преобразования и минимизация формул базируются
на следующих теоремах, вытекающих из теорем 1 и 2.
Теорема 3 (о представлении булевой функции формулой). Любая
булева функция может быть представлена в виде формулы булевой ал-
гебры, т.е. как суперпозиция конъюнкции, дизъюнкции и отрицания.
Действительно, в качестве формулы, представляющей любую булеву
функцию f(x
1
, x
2
, . . . , x
n
) можно выбрать ее СДНФ.
Теорема 4 (об эквивалентных формулах). С помощью соотноше-
ний (1 – 16) всякую формулу булевой функции можно преобразовать в
любую другую, эквивалентную ей, т. е. представляющей ту же самую
булеву функцию.
Преобразовать формулу А в эквивалентную ей формулу В всегда мож-
но через СДНФ F, которая в силу теоремы 2 будет общей для формул А
и В, но на практике этот способ оказывается громоздким.

Страницы