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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
99
Говорят , что набор
(
)
n
α
α
α
...,,
~
1
=
предшествует набору
(
)
n
βββ ...,,
~
1
= и
пишут βα
~
~
p , если ni
ii
,...,, 1
=
≤
β
α
. Функция
(
)
Бxxf
n
∈
...,,
1
называет -
ся монотонной, если
(
)
(
)
βα
~
~
ff ≤ при βα
~
~
p .
Функции
xy
y
x
x
∨
1
0
являются монотонными, тогда как
yxyxyxyxyxx ~,,,|,, ⊕→↓ не принадлежат классу
M
.
Справедливо утверждение (лемма о немонотонной функции):
Если
M
f
∉
, то, подставляя на места ее переменных
x
1
0
, можно
получить функцию
x
. 
                                           99
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
                                                                      ~
 Говорят, что набор α~ =(α 1 , ...,α n ) предшествует набору β =(β1 , ..., βn ) и
            ~
пишут α~  β , если α i ≤βi , i =1,..., n . Функция f ( x 1 , ..., x n ) ∈Б называет-
                                    ~
                                     ( )
ся монотонной, если f (α~ ) ≤ f β при α~  β .
                                                ~
      Функции x, 0, 1, x ∨ y, xy являются монотонными, тогда как
x , x ↓ y , x | y, x → y , x ⊕ y , x ~ y не принадлежат классу M .
       Справедливо утверждение (лемма о немонотонной функции):
       Если f ∉M , то, подставляя на места ее переменных 0, 1, x , можно
получить функцию x .

Страницы