ВУЗ:
Составители:
Рубрика:
36
Лемма (о несамодвойственной функции).
Если f(x
1
,…,x
n
)
∉
S, то
из нее путем подстановки функций x и
x
можно получить
несамодвойственную функцию одной переменной, т.е. константу.
Доказательство.
Т.к. f
∉
S то найдется набор (
α
1
,…,
α
n
)
такой, что
),...,(f),...,(f
n1n1
α
α
α
α
=
.
Рассмотрим функции
n,1i,x)x(
i
i
==
α
ϕ
и положим
))x(),...,x((f)x(
n1
ϕ
ϕ
ϕ
= .
Тогда имеем
)1())1(),...,1((f)1,...,1(f),...,(f
),...,(f)0,...,0(f))0(),...,0((f)0(
n1n1
n1n1
n
1
n
1
ϕϕϕαα
ααϕϕϕ
α
α
αα
====
====
что и требовалось доказать.
Класс М
Определение.
Для двух наборов ),...,(
~
n1
α
α
α
=
и
),...,(
~
n1
βββ
= выполнено отношение предшествования
βα
~
~
≺ ,
если
nn11
,...,
β
α
β
α
≤
≤
.
Например, )1,0,1,1()1,0,1,0(
≺ .
Очевидно, что если
βα
~
~
≺ и
γβ
~
~
≺ , то
γ
α
~
~
≺ . При этом не
любые пары наборов находятся в отношении предшествования.
Например, наборы (0,1) и (1,0) в таком отношении не находятся.
Таким образом, множество всех двоичных наборов длины n по
отношению к операции предшествования
≺ является частично
упорядоченным.
Определение.
Функция f(x
1
,…,x
n
) называется монотонной,
если для любых двух наборов
α
~
и
β
~
, таких, что
βα
~
~
≺ имеет
место
)
~
(f)
~
(f
βα
≤ .
Заметим, что функция, равная монотонной функции, также
является монотонной.
Монотонными функциями являются 0, 1, x, x&y, x
∨
y.
Обозначим через M множество всех монотонных функций.
Покажем, что класс M замкнут. Так как M содержит
тождественную функцию, то достаточно показать, что функция
Φ
:
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
