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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
68
1
x
2
x
3
x
)x,x,x(f
321
1
x
2
x
1n
x
n
x )x,...,x,x(f
n21
0 0 0 1 0 0
0 0
),,...,,(f 0000
0 0 1 1 0 0
0 1
),,...,,(f 1000
0 1 0 1 0 0
1 0
),,...,,(f 0100
0 1 1 0 0 0
1 1
),,...,,(f 1100
1 0 0 1
1 0 1 0 1 1
0 1
),,...,,(f 1011
1 1 0 0 1 1
1 0
),,...,,(f 0111
1 1 1 0 1 1
1 1
),,...,,(f 1111
Рис. 1
Рис. 2
При фиксированном порядке расположения наборов )...,,,(
n
α
α
α
21
в
таблице истинности всякая булева функция однозначно задается набором
своих значений. В нашем примере этот набор имеет вид
).
(
f
=
Заметим, что множество истинности
f
E , задающее функцию
)x,...,x,x(f
n21
, представляет собой
n
-местное отношение
ϕ
на множе-
стве
E
. Оно задает булеву функцию по правилу :
()
(
)
()
=
.,...,,åñëè,
,...,,åñëè,
,...,,f
n
n
n
ϕααα
ϕααα
ααα
21
21
21
0
1
И наоборот, булева функция )x,...,x,x(f
n21
однозначно определяет
множество истинности
(
)
(
)
}
1
2121
==
nnf
,...,,f,...,,fE αααααα .
В случае описанного выше примера
(
)
(
)
(
)
(
)
.,,,E
f
001010100000
=
Имеет место
Теорема. Всякая булева функция представима в виде формулы алгебры
логики через операции
&
,
и , и это представление таково:
(
)
()
(
)
(
)
nmmm
,...,
n
x...,,x,,...,,f&x&...&x&xx...,,xf
m
m
121211
21
1
+
= σσσ
σσσ
σσ
,
где
(
)
m
,...,,
σ
σ
σ
21
различные двоичные наборы значений пе -
ременных
iin
xx,nm,x...,,x
i
=≤≤
σ
1
1
, если 1
=
i
σ
,
ii
xx
i
=
σ
, если 0
=
i
σ
,
m
...,
,
i
=
.
Приведенная выше в примере функция
(
)
321
x,x,xf представима
формулой: