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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
69
(
)
(
)
(
)
(
)
(
)
()()()()
.xxxxxxxxxxxx
fxxxfxxxfxxxfxxx
fxxxfxxxfxxxfxxxx,x,xf
321321321321
1
3
1
2
1
1
0
3
1
2
1
1
1
3
0
2
1
1
0
3
0
2
1
1
1
3
1
2
0
1
0
3
1
2
0
1
1
3
0
2
0
1
0
3
0
2
0
1321
111011101001
110010100000
∨∨∨=
=∨∨∨∨
∨∨∨∨=
Такое представление называется нормальной формой, речь о которой
пойдет в следующих двух параграфах.
Всякая формула алгебры логики есть булева функция. Тождественно
истинная и тождественно ложная формулы есть постоянные функции. Их
множества значений соответственно состоят только из единиц или только
из нулей.
Булевы функции вида
,xf =
1
,y&xf
=
4
xf
=
7
,
y
,xf =
2
,yxf
→
=
5
,yxf ↓=
8
yxf
∨
=
3
, ,yxf
↔
=
6
yxf
=
9
называются элементарными.
Булевы функции от
n
переменных называются равными, если они
принимают одинаковые значения на соответствующих одинаковых набо -
рах переменных , в них входящих. Равные функции реализуются равно-
сильными формулами. Например,
(
)
.xxxxxxxx,xf 1
121212121
⊕
⊕
=
∨
=
→
=
Равносильность формул доказывается:
1. С помощью таблиц истинности;
2. Методом эквивалентных (равносильных ) преобразований.
Существует еще один способ доказательства равносильности фор-
мул, основанный на применении так называемого принципа двойственно-
сти.
Булева функция
(
)
n
x,,xf K
1
∗
называется двойственной к функции
(
)
n
x,,xf K
1
, если
(
)
(
)
nn
x,,xfx,,xf KK
11
=
∗
. Так, функция
(
)
yxyxf &, =
∗
, двойственна к
(
)
yxyxf
∨
=
,
:
(
)
y&xy&xyxy,xf ==∨=
∗
. 
                                                        69
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
f ( x1 , x 2 , x 3 )= x 10 x 20 x 30 f (0 0 0 ) ∨ x10 x 20 x 31 f (0 01) ∨ x10 x 12 x 30 f (01 0 ) ∨ x10 x 12 x 13 f (0 11) ∨
                     ∨ x11 x 20 x 30 f (10 0 ) ∨ x11 x 20 x 13 f (1 01) ∨ x11 x 12 x 30 f (11 0 ) ∨ x11 x 12 x 31 f (111) =
                      = x 1 x 2 x 3 ∨ x1 x 2 x 3 ∨ x1 x 2 x 3 ∨ x1 x 2 x 3 .

      Такое представление называется нормальной формой, речь о которой
пойдет в следующих двух параграфах.
      Всякая формула алгебры логики есть булева функция. Тождественно
истинная и тождественно ложная формулы есть постоянные функции. Их
множества значений соответственно состоят только из единиц или только
из нулей.
      Булевы функции вида

f1 = x ,                       f 4 =x & y ,                     f 7 =x � y ,
 f 2 =x ,                      f5 =x → y ,                      f8 =x ↓ y,
 f3 =x ∨ y ,                   f6 =x ↔ y ,                      f 9 =x ⊕ y
называются элементарными.
        Булевы функции от n переменных называются равными, если они
принимают одинаковые значения на соответствующих одинаковых набо-
рах переменных, в них входящих. Равные функции реализуются равно-
сильными формулами. Например,
                f ( x1 , x 2 ) = x1 → x 2 = x1 ∨ x 2 = x1 x 2 ⊕ x1 ⊕ 1.
        Равносильность формул доказывается:
1. С помощью таблиц истинности;
2. Методом эквивалентных (равносильных) преобразований.
       Существует еще один способ доказательства равносильности фор-

мул, основанный на применении так называемого принципа двойственно-

сти.

        Булева функция f ∗(x1 , , x n ) называется двойственной к функции

f ( x1 , , x n ), если f ∗(x1 , , x n ) = f (x1 , , x n ). Так, функция

f ∗( x, y ) = x & y , двойственна к f (x , y ) =x ∨ y :

f ∗(x , y ) = x ∨ y = x & y = x & y .

Страницы