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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

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
=
,
относительно которых известно, что первая система полна в Б и каждая ее
функция является суперпозицией функций второй системы. Тогда вторая
система также является полной.
50 
16. Сколько существует таких монотонных функций f � x , y, z � , что
    f �0,1,1� � f �1,0,1� � 1, f �0,0,1� � 0 ? Сколько таких функций принадле-
   жит множеству M \ S ?

17. Показать, что если f � M , то f * � M .
18. Показать, что замкнутые классы T0 , T1 , S , M , L попарно различны.



             8. ПОЛНОТА СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ

      Для всякой булевой функции существует представление в виде
дизъюнктивной или конъюнктивной нормальных форм. Отсюда следует,
что всякая функция f � Б может быть выражена в виде формулы через
элементарные функции: отрицание x , дизъюнкцию x � y и конъюнкцию
x � y . В связи с этим возникает вопрос: существуют ли другие системы
булевых функций, которые обладают таким же свойством? Ответом на
этот вопрос являются приводимые ниже понятия и теоремы.
      Система булевых функций F � � f 1 , f 2 , ..., f S , ...� называется полной,
если любая булева функция может быть записана в виде формулы через
функции этой системы, другими словами, является суперпозицией функ-
ций из системы F .
      Из этого определения следует, что система F полна, если �F � � F .
Рассмотрим примеры полных систем:
      1. Система F � �x , x � y , x � y� представляет собой полную систему.
      2. Система F � �x � y , x & y , 0, 1� также полна, так как любая булева
         функция представима в виде полинома Жегалкина.
      3. Множество Б всех булевых функций также образует полную сис-
         тему, так как �Б � � Б .
      Ясно, что не всякая система является полной. Например, система
�x � y, x & y� не является полной. Следующая теорема позволяет сводить
вопрос о полноте одних систем к вопросу о полноте других систем.

        Теорема (о полноте двух систем):
        Пусть даны две системы функций
                     F � � f 1 , f 2 ,...� и G � �g1 , g 2 ,...� ,
относительно которых известно, что первая система полна в Б и каждая ее
функция является суперпозицией функций второй системы. Тогда вторая
система также является полной.


                                        50

Страницы