ВУЗ:
Составители:
Рубрика:
34
а)
[P
2
]=P
2
;
б) замыканием множества },{
⊕
1 будет класс L всех линейных
функций, т.е. функций, имеющих вид
,...),...,(
nn110n1
xxxxf
α
α
α
⊕
⊕
⊕
=
где
α
i
={0,1}, i= n0, .
Определение.
Класс F называется функционально замкнутым,
если [F]=F.
Примеры функционально замкнутых классов:
а) P
2
;
б) класс L замкнут, т.к. линейная комбинация линейных
выражений является линейным выражением.
Определение
(полноты в терминах замыкания и замкнутых
классов). F - полная систем, если [F]=P
2
.
Основные замкнутые классы.
Класс Т
0
.
Обозначим через T
0
класс всех логических функций f(x
1
,…,x
n
),
сохраняющих константу 0, т.е. функций таких, для которых
выполняется равенство f(0,…,0)=0.
Заметим, что если f
∈
T
0
, a f
′
– функция, равная f (т.е.
отличающаяся некоторым множеством фиктивных переменных),
то и f
′∈
T
0
.
Далее, функции 0, x, x&y, x
∨
y, x
⊕
y принадлежат классу T
0
, а
функции 1,
x не входят в Т
0
.
Поскольку таблица для функций f из класса T
0
в первой строке
содержит значение 0, то в Т
0
содержится ровно
n
2
2
2
1
)( булевых
функций, зависящих от переменных х
1
,…,х
n
.
Покажем, что T
0
-замкнутый класс. Так как T
0
содержит
тождественную функцию (в противном случае необходимо было
бы показать, что x
i
=f(f
1
,…,f
n
)), то для обоснования замкнутости
достаточно показать, что функция
Φ
:
Φ
=f(f
1
,…,f
n
)
принадлежит T
0
, если f,f
1
,…,f
n
принадлежат T
0
. Это следует
из цепочки равенств
Φ
(0,…,0)=f(f
1
(0,…,0),…,f
n
(0,…,0))=f(0,…,0)=0.
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
