Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 23 стр.

UptoLike

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

23
(
)
( )( )
( )( )( )
.zxzyyxzxK
,zyyxzxK
,yxzxK
ÚÚÚ=
ÚÚ=
Ú
=
3
2
1
Рассмотрим два способа построения ДНФ и КНФ.
Способ 1. (Метод эквивалентных преобразований). Пусть булева
функция
(
)
n
x,...,x,xf
21
задана формулой. Алгоритм построения ДНФ и
КНФ состоит в следующем:
Шаг 1. Формулу преобразовать так, чтобы в ней были только опера-
ции
Ú
, & и ù.
Шаг 2. Добиться с помощью законов де Моргана, чтобы знак отри-
цания стоял лишь над отдельными переменными.
Шаг 3. Раскрыть скобки по 1-му дистрибутивному закону
ABC

при построении ДНФ и по 2-му дистрибутивному
закону
(
)
(
)
CABABCA
Ú
Ú
=
Ú
при построении КНФ.
Способ 2. (С использованием таблицы истинности).
Шаг 1. Пусть функция
(
)
n
x,...,x,xf
21
задана таблицей или набором
своих значений. Воспользоваться разложением функции по переменным
n
x,...,x,x
21
:
(
)
( )
(
)
(
)
nn
,...,,
n
,...,f&x&...&x&xx,...,x,xf
n
n
ss
s
ss
sss
12121
21
21
Ú= (*)
при построении ДНФ и
(
)
( )
(
)
(
)
n
n
n
n
n
fxxxxxxf
s
s
sss
sss
,...,...&,...,,
1
2
2
1
1
,...,
2
,
1
21
Ú
Ú
Ú
Ú
=
(**)
при построении КНФ.
Шаг 2. Полученные формулы по возможности упростить с помощью
основных равносильностей алгебры логики высказываний.
( )( ) ( )
( )
( )
( ) ( )
( )
.д.ти;baabba;bababa
;a;bababa
;babab&ab&ababa
;abbaabbaabbaba
;aa,a&a
;
b
a
b
a
Ú==½=Ú=¯
=ÚÚ=Å
ÚÚ=Ú=«=Å
Ú=ÚÚ=®®=«
=Ú=
Ú
=
®
11
10
Пример 1. Методом эквивалентных преобразований для функции
(
)
(
)
yzyxz,y,xf
®
Å
=
построить ДНФ и КНФ.