ВУЗ:
Составители:
Рубрика:
35
Класс Т
1
Обозначим через T
1
класс всех логических функций f(x
1
,…,x
n
),
сохраняющих константу 1, т.е. функций, для которых выполнено
равенство f(1,…,1) =1.
Очевидно, что класс Т
1
вместе с любой функцией содержит и
любую равную ей функцию. Легко видеть, что функции 1, x, x&y,
x
∨
y принадлежат классу T
1
, а функции 0 и
x
не входят в T
1
.
Аналогично предыдущему показывается, что T
1
содержит
n
2
2
2
1
)( , функций, зависящих от n переменных, и является
замкнутым классом.
Замечание.
Класс T
1
состоит из функций, двойственных
функциям из класса T
0
.
Класс S
Обозначим через S класс всех самодвойственных функций f
из
P
2
, т.е. таких, что f
*
=f.
Как и выше, можно проверить, что добавление равных функций
не выводит за пределы класса S. Очевидно, что функции х,
x –
самодвойственны.
Из определения самодвойственной функции:
),...,(),...,(
n1n1
xxfxxf =
,
следует, что на противоположных наборах
),...,(
n1
α
α
и
),...,(
n1
αα
самодвойственная функция принимает
противоположные значения. Следовательно, самодвойственная
функция полностью определяется своими значениями на первой
половине строк. Поэтому число всех самодвойственных функций,
зависящих от переменных x
1
,…,x
n
, равно
1n
2
2
−
.
Докажем, что класс S замкнут. Поскольку класс S содержит
тождественную функцию, то достаточно показать, что функция
Φ
:
Φ
=f(f
1
,…,f
n
)
является самодвойственной, если f, f
1
,…,f
n
-
самодвойственны. Это проверяется непосредственно
ΦΦ
===
∗∗∗∗
),,(),,(
n1n1
ffffff …… .
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
