Дискретная математика. Элементы теории задачи и упражнения. Часть 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
=
,
относительно которых известно, что первая система полна в Б и каждая ее
функция является суперпозицией функций второй системы. Тогда вторая
система также является полной. 
                                           102
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________


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 ,...},
относительно которых известно, что первая система полна в Б и каждая ее
функция является суперпозицией функций второй системы. Тогда вторая
система также является полной.

Страницы