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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
74
Шаг 1.Формулу преобразовать так, чтобы в ней были только опера -
ции
, & и ;
Шаг 2. Добиться с помощью законов де Моргана, чтобы знак отри -
цания стоял лишь над отдельными переменными;
Шаг 3. Раскрыть скобки по 1-му дистрибутивному закону
(
)
ACABCBA
=
при построении ДНФ и по 2-му дистрибутивному за -
кону
(
)
(
)
CABABCA
=
при построении КНФ .
Способ 2. (С использованием таблицы истинности ).
Шаг 1. Пусть функция
(
)
n
x,...,x,xf
21
задана таблицей или набором
своих значений. Воспользоваться разложением функции по переменным
n
x,...,x,x
21
:
(
)
()
(
)
(
)
nn
,...,,
n
,...,f&x&...&x&xx,...,x,xf
n
n
σσ
σσσ
σσσ
12121
21
21
∨= ()
при построении ДНФ и
(
)
()
(
)
(
)
nnn
fxxxxxxf
n
n
σσ
σσσ
σσσ
,...,...&,...,,
,...,,
12121
21
21
∨= (∗∗)
при построении КНФ .
Шаг 2. Полученные формулы по возможности упростить с помощью
основных равносильностей алгебры логики высказываний.
()()()
()
()
()()
()
.д.ти;baabba;bababa
;a;bababa
;babab&ab&ababa
;abbaabbaabbaba
;aa,a&a
;
b
a
b
a
====↓
==⊕
===⊕
===↔
=∨=
=
11
10
Пример 1. Методом эквивалентных преобразований для
функции
(
)
(
)
yzyxz,y,xf
=
построить ДНФ и КНФ .
Решение. Применяя основные равносильности и 1-ый дистрибутив-
ный закон , строим ДНФ :
()()() ()()
()()
.yzyxxy
yzxyyyxxyxyzxyyx
yzxyyxyzyxyzyxz,y,xf
∨=
==∨=
==∨↔=⊕=