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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
103
Пользуясь этой теоремой, можно доказать полноту еще ряда
функциональных систем и тем самым расширить список примеров полных
систем.
4. Системы
{
}
yxxG
∨
=
,
1
и
{
}
yxxG
∧
=
,
2
являются полными. Из
равенств
yxyx ∧=∨ и yxyx ∨=∧
следует , что в качестве системы
F
можно использовать множество
функций в примере 1.
5. Система
{
}
yxG |
=
полна, так как
(
)
(
)
yxyxyxxxx |||;|
=
∧
=
и в качестве
F
можно взять систему функций
{
}
yxx
∧
, из примера
4.
На множестве
Б
булевых функций справедлив следующий кри -
терий полноты.
Теорема Поста:
Система
{
}
,...,
21
ffF
=
полна тогда и только тогда , когда она
целиком не содержится ни в одном из замкнутых классов
0
T ,
1
T ,
S
,
,
L
.
Применение критерия полноты
Чтобы исследовать полноту системы функций
{
}
,...,
21
ffF
=
, удобно
построить следующую таблицу ,
в которой столько строк, сколько функций в данной системе F . В каждую
клетку этой таблицы, стоящей на пересечении столбца , соответствующего
одному из классов, и строки, соответствующей функции
i
f , заносится знак
«+», если
i
f
принадлежит этому классу , и знак «-» в противном случае.
классы
функции
0
T
1
T
S
L
1
f
2
f
3
f
… 
                                           103
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
        Пользуясь этой теоремой, можно доказать полноту еще ряда
функциональных систем и тем самым расширить список примеров полных
систем.
     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.

         На множестве Б булевых функций справедлив следующий кри-

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

терий полноты.
       Теорема Поста:
       Система F ={f 1 , f 2 ,...} полна тогда и только тогда, когда она
целиком не содержится ни в одном из замкнутых классов T0 , T1 , S ,
M , L.

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

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

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

Страницы