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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
72
3)
(
)
(
)
.xyxf
→
→
=
7. Построить двойственные функции для всех элементарных булевых
функций.
8. Доказать или опровергнуть равенство двух функций, используя прин-
цип двойственности:
1)
(
)
,zyxf
⊕
→
=
(
)
(
)
;yxyx
→
⊕
→
=
ϕ
2)
(
)
;zyxf
→
→
=
(
)
(
)
;yxyx
→
→
→
=
ϕ
3)
(
)
;zyxf
↔
=
xz
xy
↔
=
ϕ
4)
(
)
;zyxf
⊕
=
xz
xy
⊕
=
ϕ
5)
(
)
;zyxf
∨
⊕
=
(
)
(
)
.zxyx
⊕
∨
⊕
=
ϕ
9. Доказать, что
(
)
1
≡
yxf , , если:
1)
(
)
(
)
;xyyxf
→
∨
→
=
2)
(
)
(
)
;yxyxf ↔↔⊕=
3)
(
)
;| yxxyf ↔=
4)
(
)
.yxyxf ↓↔∨= .
5.2 Дизъюнктивные и конъюнктивные нормальные формы
Пусть
x
- булева переменная.
Введем обозначение:
σ
σ
σ
∨
=
xxx , где параметр
{
}
., 10
∈
σ
Оче-
видно, что ,
если,x
если,x
x
=
=
=
0
1
σ
σ
σ
т.е. .xx,xx ==
01
Легко видеть, что
1
=
σ
x тогда и только тогда, когда
σ
=
x
.
Пусть
n
x,...,x,x
21
- булевы переменные .
Определение. Формулы алгебры логики вида:
n
n
iii
x&...&x&x
σ
σσ
2
2
1
1
и
n
n
iii
x...xx
σ
σσ
∨∨∨
2
2
1
1
,
где
{
}
n...,,,i
k
21
∈
,
{
}
10 ,
k
∈
σ
, называются соответственно элементарной
конъюнкцией (э.к.) и элементарной дизъюнкцией (э.д.) на множестве
булевых переменных
{
}
n
x,...,x,x
21
. 
                                                    72
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
            3) f =(( x → y ) → x ).

7. Построить двойственные функции для всех элементарных булевых
   функций.




8. Доказать или опровергнуть равенство двух функций, используя прин-
   цип двойственности:
         1) f = x → ( y ⊕ z ), ϕ =( x → y ) ⊕ ( x → y );
         2) f = x → ( y → z ); ϕ =( x → y ) → ( x → y );
         3) f =x ( y ↔ z ); ϕ = xy ↔ xz;
         4) f = x ( y ⊕ z ); ϕ =xy ⊕ xz;
         5) f = x ⊕ ( y ∨ z ); ϕ =( x ⊕ y ) ∨ ( x ⊕ z ).

9. Доказать, что f ( x , y ) ≡1 ,если:
         1) f =( x → y ) ∨ ( y → x );
            2) f =( x ⊕ y ) ↔ x ↔ y ; (         )
            3) f = xy ↔ ( x | y );
            4) f = x ∨ y ↔ (x ↓ y ). .



       5.2 Дизъюнктивные и конъюнктивные нормальные формы

     Пусть x - булева переменная.
     Введем обозначение: x σ = x ⋅ σ ∨ x ⋅σ , где параметр σ ∈{0 ,1}. Оче-
                �x , если σ =1
видно, что x σ =�                     , т.е. x 1 = x , x 0 = x .
                �x , если σ =0
     Легко видеть, что x σ =1 тогда и только тогда, когда x =σ .
     Пусть x1 , x 2 , ... , x n - булевы переменные.

       Определение. Формулы алгебры логики вида:
                x iσ11 & x iσ2 2 & ... & x iσnn и x σi1 1 ∨ x σi 22 ∨ ... ∨ x σi nn ,
где i k ∈{1, 2 , ..., n}, σ k ∈{0,1}, называются соответственно элементарной
конъюнкцией (э.к.) и элементарной дизъюнкцией (э.д.) на множестве
булевых переменных {x1 , x 2 , ... , x n }.

Страницы