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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
67
Переменная
x
, принимающая два значения, 0 или 1, называется бу-
левой переменной.
Пусть
{
}
10 ,E =
. Тогда
4434421
разn
n
E...EEE ×××= множество упорядоченных
двоичных наборов длины
n
:
(
)
{
}
.n,...,,,i,E,...,,E
in
n
321
21
=∈= αααα
Говорят , что задана булева функция
n
переменных
(
)
,x,...,x,xf
n21
если задан закон , по которому каждому двоичному набору
(
)
n
n
E,...,, ααα
21
ставится в соответствие 0 или 1: EE:f
n
.
Таким образом, область определения булевой функции
(
)
n
x,...,x,xf
21
есть
(
)
n
EFD =
, множество значений
(
)
EfR =
, где мощ -
ность
(
)
(
)
.fR,fD
n
22 ==
Булева функция может быть задана при помощи:
1. описания;
2. таблицы истинности;
3. формулы алгебры высказываний;
4. множества истинности
(
)
(
)
{
}
1
2121
==
nnf
,...,,f,...,,fE αααααα ;
5. набора значений;
6. функциональной схемы.
Рассмотрим пример, на котором проиллюстрируем указанные спосо-
бы задания булевых функций.
Пример. Пусть булева функция
(
)
321
x,x,xf принимает значений 1
на наборах
(
)
321
ααα ,, , в которых большинство нулей, а на остальных на-
борах ее значение равно 0.
Описанная функция может быть задана с помощью таблицы истин -
ности (рис. 1):
В случае
n
переменных булева функция )x,...,x,x(f
n21
задается
таблицей, содержащей
n
2 строк, т.к.
n
n
n
EE 2 == . В дальнейшем всегда
будем располагать наборы в таблице истинности так, как показано на
рис.2.