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

UptoLike

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

17
Таким образом, область определения булевой функции
(
)
n
x,...,x,xf
21
есть
(
)
n
EFD = , множество значений
(
)
EfR = , где мощ-
ность
(
)
(
)
.fR,fD
n
22 ==
Булева функция может быть задана при помощи:
1. описания;
2. таблицы истинности;
3. формулы алгебры высказываний;
4. множества истинности
(
)
(
)
{
}
1
2121
==
nnf
,...,,f,...,,fE
aaaaaa
;
5. набора значений;
6. функциональной схемы.
Рассмотрим пример, на котором проиллюстрируем указанные спосо-
бы задания булевых функций.
Пример. Пусть булева функция
(
)
321
x,x,xf принимает значений 1
на наборах
(
)
321
aaa
,, , в которых большинство нулей, а на остальных на-
борах ее значение равно 0.
Описанная функция может быть задана с помощью таблицы истин-
ности (рис. 1):
В случае
n
переменных булева функция )x,...,x,x(f
n21
задается таб-
лицей, содержащей
n
2 строк, т.к.
n
n
n
EE 2== . В дальнейшем всегда бу-
дем располагать наборы в таблице истинности так, как показано на рис. 2.
1
x
2
x
3
x )x,x,x(f
321
x
2
x
1-n
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
a
a
a
21
в
таблице истинности всякая булева функция однозначно задается набором
своих значений. В нашем примере этот набор имеет вид
).
(
f
0
0
0
1
0
1
1
1
=
Заметим, что множество истинности
f
E , задающее функцию
)x,...,x,x(f
n21
, представляет собой
n
-местное отношение
j
на множе-
стве
E
. Оно задает булеву функцию по правилу: