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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

51
Пользуясь этой теоремой, можно доказать полноту еще ряда
функциональных систем и тем самым расширить список примеров полных
систем.
4. Системы
{
}
yxxG
Ú
=
,
1
и
{
}
yxxG
Ù
=
,
2
являются полными.
Из равенств
yxyx Ù=Ú и yxyx Ú=Ù
следует, что в качестве системы
F
можно использовать множество
функций в примере 1.
5. Система
{
}
yxG |
=
полна, так как
(
)
(
)
yxyxyxxxx |||;|
=
Ù
=
,
и в качестве
F
можно взять систему функций
{
}
yxx
Ù
, из примера 4.
На множестве
булевых функций справедлив следующий кри-
терий полноты.
Теорема Поста:
Система
{
}
,...,
21
ffF
=
полна тогда и только тогда, когда она
целиком не содержится ни в одном из замкнутых классов
0
T ,
1
T ,
S
,
M
,
L
.
Применение критерия полноты
Чтобы исследовать полноту системы функций
{
}
,...,
21
ffF
=
, удобно
построить следующую таблицу.
В ней столько строк, сколько функций в данной системе F . В каждую
клетку этой таблицы, стоящей на пересечении столбца, соответствующего
одному из классов, и строки, соответствующей функции
i
f , заносится знак
«+», если
i
f принадлежит этому классу, и знак «–» в противном случае.
В силу критерия Поста для полноты системы F=
{
}
,...,
21
ff необхо-
димо и достаточно, чтобы хотя бы в одной клетке каждого столбца стоял
знак «–».
классы
функции
0
T
1
T
S
M
L
1
f
2
f
3
f
… 
        Пользуясь этой теоремой, можно доказать полноту еще ряда
функциональных систем и тем самым расширить список примеров полных
систем.
     4. Системы G1 � �x , x � y� и G 2 � �x , x � y� являются полными.
        Из равенств
                          x� y� x� y и x� y� x� y
     следует, что в качестве системы F можно использовать множество
     функций в примере 1.
     5. Система G � �x | y� полна, так как
                        x � x | x; x � y � � x | y � | � x | y � ,
     и в качестве F можно взять систему функций �x , x � y� из примера 4.

       На множестве Б булевых функций справедлив следующий кри-
терий полноты.
       Теорема Поста:
       Система F � � f 1 , f 2 ,...� полна тогда и только тогда, когда она
целиком не содержится ни в одном из замкнутых классов T0 , T1 , S ,
M , L.

                     Применение критерия полноты

     Чтобы исследовать полноту системы функций F � � f 1 , f 2 ,...�, удобно
построить следующую таблицу.

                     классы
                              T0      T1      S     M       L
         функции
                f1
                f2
                f3
               …

В ней столько строк, сколько функций в данной системе F . В каждую
клетку этой таблицы, стоящей на пересечении столбца, соответствующего
одному из классов, и строки, соответствующей функции f i , заносится знак
«+», если f i принадлежит этому классу, и знак «–» в противном случае.
      В силу критерия Поста для полноты системы F= � f 1 , f 2 ,...� необхо-
димо и достаточно, чтобы хотя бы в одной клетке каждого столбца стоял
знак «–».

                                    51

Страницы