ВУЗ:
Составители:
Рубрика:
Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
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
∨∨=
=∨∨∨∨=∨∨∨=
=∨→→=∨↔=→⊕=
74 Операция замыкания. Основные замкнутые классы. __________________________________________________________________________________________ Шаг 1.Формулу преобразовать так, чтобы в ней были только опера- ции ∨ , & и �; Шаг 2. Добиться с помощью законов де Моргана, чтобы знак отри- цания стоял лишь над отдельными переменными; Шаг 3. Раскрыть скобки по 1-му дистрибутивному закону A(B ∨ C ) = AB ∨ AC при построении ДНФ и по 2-му дистрибутивному за- кону A ∨ BC =( A ∨ B )( A ∨ C ) при построении КНФ. Способ 2. (С использованием таблицы истинности). Шаг 1. Пусть функция f ( x1 , x 2 , ... , x n ) задана таблицей или набором своих значений. Воспользоваться разложением функции по переменным x1 , x 2 , ... , x n : f ( x1 , x 2 , ... , x n ) = ∨ (x (σ1 ,σ 2 ,...,σ n ) σ1 1 & x 2σ 2 & ... & x σn n & f (σ 1 ,...,σ n )) (∗) при построении ДНФ и f ( x1 , x 2 , ..., x n ) = & (σ 1 ,σ 2 ,...,σ n ) (x σ1 1 ∨ x σ2 ∨ ... ∨ x nσ ∨ f (σ 1 ,..., σ n )) 2 n (∗∗) при построении КНФ. Шаг 2. Полученные формулы по возможности упростить с помощью основных равносильностей алгебры логики высказываний. a → b =a ∨ b ; a & a =0 , a ∨ a =1; a ↔ b =(a → b )(b → a ) =(a ∨ b )(b ∨ a ) =a b ∨ ab ; ( a ⊕ b =a ↔ b = a & b ∨ (a & b ) =(a ∨ b ) a ∨ b ; ) ( ) a ⊕ b =a b ∨ ab ; a ∨ 1 =1; a ↓ b =a ∨ b =a b ; a�b =ab =a ∨ b ; и т .д . Пример 1. Методом эквивалентных преобразований для функции f ( x , y , z ) =( x ⊕ y ) → yz построить ДНФ и КНФ. Решение. Применяя основные равносильности и 1-ый дистрибутив- ный закон, строим ДНФ: f ( x , y , z ) =( x ⊕ y ) → yz =( x ↔ y ) ∨ yz =( x → y )( y → x ) ∨ yz = =( x ∨ y )( y ∨ x ) ∨ yz = x y ∨ xx ∨ yy ∨ xy ∨ yz = = xy ∨ x y ∨ yz .
Страницы
- « первая
- ‹ предыдущая
- …
- 26
- 27
- 28
- 29
- 30
- …
- следующая ›
- последняя »