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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
102
16. Сколько существует таких монотонных функций
(
)
zyxf ,, , что
(
)
(
)
,,,,, 1101110
=
=
ff
(
)
0100
=
,,f ? Сколько таких функций принадле-
жит множеству
S
M
\
?
17. Показать, что если
M
f
, то
.
M
f
18. Показать, что замкнутые классы LMSTT ,,,,
10
попарно различны.
8. ПОЛНОТА СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ
Для всякой булевой функции существует представление в виде
дизъюнктивной или конъюнктивной нормальных форм . Отсюда следует ,
что всякая функция
Б
f
может быть выражена в виде формулы через
элементарные функции: отрицание
x
, дизъюнкцию
y
x
и конъюнкцию
y
x
. В связи с этим возникает вопрос: существуют ли другие системы
булевых функций, которые обладают таким же свойством? Ответом на
этот вопрос являются приводимые ниже понятия и теоремы.
Система булевых функций
{
}
...,...,,,
S
fffF
21
=
называется полной,
если любая булева функция может быть записана в виде формулы через
функции этой системы, другими словами, является суперпозицией функ-
ций из системы
F
.
Из этого определения следует, что система
F
полна, если
[
]
FF
=
.
Рассмотрим примеры полных систем :
1. Система
{
}
yxyxxF
=
,, представляет собой полную систему.
2. Система
{
10 ,,&, yxyxF
=
также полна, так как любая булева
функция представима в виде полинома Жегалкина;
3. Множество
Б
всех булевых функций также образует полную
систему, так как
[
]
ББ
=
.
Ясно, что не всякая система является полной. Например, система
{
yxyx &,
не является полной. Следующая теорема позволяет сводить
вопрос о полноте одних систем к вопросу о полноте других систем.
Теорема (о полноте двух систем ):
Пусть даны две системы функций
{
}
,...,
21
ffF
=
и
{
}
,...,
21
ggG
=
,
относительно которых известно, что первая система полна в Б и каждая ее
функция является суперпозицией функций второй системы. Тогда вторая
система также является полной.