Просолупов Е.В. Конспект курса: Основы дискретной математики

Подождите немного. Документ загружается.

2.1.8 Функции, сохраняющие ноль

Определение 2.1.21 . Пусть f(x

, ..., x

) ∈ P

. f называют

функцией, сохраняющей ноль, если f(0, ..., 0) = 0.

Множество всех функций сохраняющих 0 обозначим T

= {f(x

, ..., x

) | f ∈ P

, f(0, ..., 0) = 0}.

Утверждение 2.1.15 . Класс функций T

замкнут.

Доказательство. Рассмотрим суперпозицию ранга 1 от функций из T

a) Пусть f(x

, ..., x

) ∈ T

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y) = f(x

, ..., x

j−1

, y, x

j+1

, ..., x

Тогда g(0, ..., 0) = f(0, ..., 0) = 0. Следовательно,

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y) ∈ T

b) Пусть f(x

, ..., x

) ∈ T

и h(y

, ..., y

) ∈ T

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y

, ..., y

) =

= f(x

, ..., x

j−1

, h(y

, ..., y

), x

j+1

, ..., x

Тогда

g(0, ..., 0) = f(0, ..., 0, h(0, ..., 0), 0, ..., 0) = f(0, ..., 0, 0, 0, ..., 0) = 0.

Получаем, что g(x

, ..., x

j−1

, x

j+1

, ..., x

, y

, ..., y

) ∈ T

Таким образом, [T

] = T

Замечание 2.1.15 . Тождественная фукнция f(x) = x лежит в

классе T

. Функция отрицания f(x) = x не лежит в T

. Таким образом,

6= ∅ и T

6= P

2.1.9 Функции, сохраняющие единицу

Замечание 2.1.16 . Рассуждения этого пункта повторяют

содержание предыдущего с точностью до замены 0 на 1

111

Определение 2.1.22 . Пусть f(x

, ..., x

) ∈ P

. f называют

функцией, сохраняющей единицу, если f(1, ..., 1) = 1.

Множество всех функций сохраняющих 1 обозначим T

= {f(x

, ..., x

) | f ∈ P

, f(1, ..., 1) = 1}.

Утверждение 2.1.16 . Класс функций T

замкнут.

Доказательство. Доказательство полностью эквивалентно

доказательству утверждения 2.1.15.

Замечание 2.1.17 . Тождественная фукнция f(x) = x лежит в

классе T

. Функция отрицания f(x) = x не лежит в T

. Таким образом,

6= ∅ и T

6= P

2.1.10 Двойственность

Определение 2.1.23 . Пусть f(x

, ..., x

) ∈ P

. Двойственной

функцией к функции f называется f

∗

, ..., x

) = f(x

, ..., x

Пример 2.1.17 . Пусть f(x, y, z) = xy ∨ z. Тогда f

∗

(x, y, z) =

x · y ∨ z = x · y ∨ z.

Пример 2.1.18 . Пусть функция f(x, y, z) задана таблицей. Тогда,

чтобы получить двойственную функцию, нужно перевернуть и

инвертировать столбец значений:

x y z f(x, y, z) f

∗

(x, y, z)

112

Определение 2.1.24 . Функция f(x

, ..., x

) ∈ P

— самодвойственная,

если f

∗

, ..., x

) = f(x

, ..., x

Обозначим за S множество всех самодвойственных функций:

S = {f | f(x

, ..., x

) ∈ P

, f

∗

, ..., x

) = f(x

, ..., x

)}.

Пример 2.1.19 . Пусть f = x ∨ y, f

∗

= x ∨ y = xy. f 6= f

∗

и,

следовательно, f

∗

не является самодвойственной.

Пример 2.1.20 . Пусть f — функция голосования:

f(x, y, z) = xy ∨ xz ∨ yz.

∗

(x, y, z) = x · y ∨ x · z ∨ y · z = x · y · x · z · y · z =

= (x ∨ y)(x ∨ z)(y ∨ z) = (x ∨ xz ∨ xy ∨ yz)(y ∨ z) =

xy ∨ xz ∨ xyz ∨ xz ∨ xy ∨ xyz ∨ yz ∨ yz = xy ∨ xz ∨ yz ∨ xyz =

= xy ∨ xz ∨ yz = f(x, y, z).

Функция голосования — самодвойственная.

Рассмотрим табличный вид функции голосования:

x y z f(x, y, z)

Можно видеть, что нижняя половина столбца значений повторяет

перевернутую и инвертированную верхнюю. Это верно для любой

самодвойственной функции.

113

Утверждение 2.1.17 (Принцип двойственности).

Пусть формула U = f(U

, ..., U

) реализует фукнцию F (x

, ..., x

), где U

— формулы, реализующие f

, ..., x

), i = 1, n. Пусть U

∗

— формулы

реализующие f

∗

, i = 1, n. Тогда формула U

∗

= f

∗

, ..., U

∗

) реализует

функцию F

∗

, ..., x

Доказательство.

F (x

, ..., x

) = f(f

, ..., x

), ..., f

, ..., x

)).

Тогда, по определению двойственной функции

∗

, ..., x

) = f(f

, ..., x

), ..., f

, ..., x

)) =

= f(f

, ..., x

), ..., f

, ..., x

)) =

= f(f

∗

, ..., x

), ..., f

∗

, ..., x

)) =

= f

∗

, ..., x

), ..., f

∗

, ..., x

)).

С другой стороны, формула f

∗

, ..., U

∗

) реализует функцию

∗

, ..., x

), ..., f

∗

, ..., x

)) =

= f

∗

, ..., x

), ..., f

∗

, ..., x

)).

Таким образом, один из способов задать функцию F

∗

, ..., x

)

формулой имеет вид U

∗

= f

∗

, ..., U

∗

Пример 2.1.21 . Пусть,

F (x, y, z) = (x ≡ y) ⊃ (y | z) = f(f

(x, y), f

(y, z)).

∗

(x, y) =(x ⊃ y)

∗

= x ⊃ y = x ∨ y = xy.

∗

(x, y) =(x ≡ y)

∗

= x ≡ y = x ≡ y = x ⊕ y.

∗

(x, y) =(x | y)

∗

= x | y = x ∨ y = x ∧ y = x ↓ y.

Тогда по утверждению 2.1.17 f

∗

(x, y, z) будет иметь вид

∗

(x, y, z) = f

∗

(x, y), f

∗

(y, z)) = (x ⊕ y) ∧ (y ↓ z).

114

Действительно,

∗

(x, y, z) = ¬((x ≡ y) ⊃ (y | z)) = ¬((x ≡ y) ∨ (y ∨ z)) =

= (x ≡ y) ∧ (y ∨ z) = (x ⊕ y) ∧ (y ↓ z).

Следствие 2.1.18 . Пусть f(x

, ..., x

) задана формулой U над

множеством фукнций {0, 1, ¬, ∨, ∧}. Тогда f

∗

, ..., x

) задается

формулой, полученной из U заменой: нулей на единицы, единиц на нули,

конъюнкций на дизъюнкции, дизъюнкций на конъюнкции.

Доказательство. Пусть f = ¬f

. Это значит, что f = f

), где

(x) = x. Тогда f

∗

= x = x = f

. Следовательно

∗

= f

∗

) = f

∗

) = ¬f

∗

Пусть f = f

∨ f

. Другими словами, f = f

, f

), f

(x, y) = x ∨ y.

Тогда f

∗

= x ∨ y = x ∧ y и

∗

= f

∗

, f

∗

) = f

∗

∧ f

∗

Пусть f = f

∧ f

. Другими словами, f = f

, f

), f

(x, y) = x ∧ y.

Тогда f

∗

= x ∧ y = x ∨ y и

∗

= f

∗

, f

∗

) = f

∗

∨ f

∗

Пусть f = 0. Тогдa f

∗

= 1.

Пусть f = 1. Тогда f

∗

= 0.

Пусть f = x. Тогда f

∗

= x = x = f.

Пример 2.1.22 . Пусть, f(x, y, z) = 0 ∧ x ∧ y ∨ 1 ∧ y ∧ z. Тогда,

∗

(x, y, z) = f(x, y, z) = ¬(0 ∧ x ∧ y ∨ 1 ∧ y ∧ z) =

= (0 ∧ x ∧ y) ∧ (1 ∧ y ∧ z) = (1 ∨ x ∨ y) ∧ (0 ∨ y ∨ z).

Пример подтверждает утверждение 2.1.18.

Пример 2.1.23 . Пусть, f(x, y, z) = (0 ∨ x)(y ∨ xz). Тогда

∗

(x, y, z) = ¬((0 ∨ x)(y ∨ x ∧ z)) = ¬(1 ∧ x)(y ∨ x ∧ z)) =

= (1 ∧ x) ∨ (y ∨ x ∧ z)) = (1 ∧ x) ∨ ( y ∧ (x ∨ z))).

Пример подтверждает утверждение 2.1.18.

115

Утверждение 2.1.19 . Класс функций S замкнут.

Доказательство. Рассмотрим суперпозицию ранга 1 от функций из S.

a) Пусть f(x

, ..., x

) ∈ S и

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y) = f(x

, ..., x

j−1

, y, x

j+1

, ..., x

Тогда

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y) = f(x

, ..., x

j−1

, y, x

j+1

, ..., x

) =

= f

∗

, ..., x

j−1

, y, x

j+1

, ..., x

) = f(x

, ..., x

j−1

, y, x

j+1

, ..., x

) =

= g(x

, ..., x

j−1

, x

j+1

, ..., x

, y).

Следоваетльно g(x

, ..., x

j−1

, x

j+1

, ..., x

, y) ∈ S.

b) Пусть f(x

, ..., x

) ∈ S и h(y

, ..., y

) ∈ S и

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y

, ..., y

) =

= f(x

, ..., x

j−1

, h(y

, ..., y

), x

j+1

, ..., x

Тогда

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y

, ..., y

) =

= f(x

, ..., x

j−1

, h(y

, ..., y

), x

j+1

, ..., x

) =

= f(x

, ..., x

j−1

, h(y

, ..., y

), x

j+1

, ..., x

) =

= f(x

, ..., x

j−1

, h

∗

, ..., y

), x

j+1

, ..., x

) =

= f

∗

, ..., x

j−1

, h

∗

, ..., y

), x

j+1

, ..., x

) =

= f(x

, ..., x

j−1

, h(y

, ..., y

), x

j+1

, ..., x

) =

= g(x

, ..., x

j−1

, x

j+1

, ..., x

, y

, ..., y

)

Получаем, что g(x

, ..., x

j−1

, x

j+1

, ..., x

, y

, ..., y

) ∈ S.

Таким образом, [S] = S.

Замечание 2.1.18 . Тождественная фукнция f(x) = x лежит в

классе S. Конъюнкция f(x) = x ∧ y не лежит в S. Таким образом,

S 6= ∅ и S 6= P

116

Лемма 2.1.20 (О несамодвойственной функции). Пусть

f(x

, ..., x

) /∈ S. Тогда, подставляя в f вместо аргументов x и x можно

получить константу.

Доказательство. Пусть (α

, ..., α

), α

∈ {0, 1}, такой набор, что

f(α

, ..., α

) = f(α

, ..., α

). Такой набор обязан существовать в силу

несамодвойственности функции f.

Рассмотрим функцию ϕ(x) = f(x

, ..., x

). Тогда

ϕ(0) = f(0

, ..., 0

) = f(α

, ..., α

) = f(α

, ..., α

) =

= f(α

, ..., α

) = f(1

, ..., 1

) = ϕ(1).

Следовательно ϕ(x) — константа.

Пример 2.1.24 (получение константы из несамодвойственной

функции). Пусть f(x, y, z) = x ⊃ (y ⊕ z). Это несамодвойствен-

ная функция, поскольку

f(0, 1, 0) = 0 ⊃ (1 ⊕ 0) = 1 = 1 ⊃ (0 ⊕ 1) = f(1, 0, 1).

Тогда ϕ(x) = f(x, x, x) — константа. Действительно,

ϕ(x) = x ⊃ (x ⊕ x) = x ⊃ 1 = 1.

2.1.11 Монотонность

Определение 2.1.25 . Пусть eα

= (α

, ..., α

= (β

, ..., β

, β

∈ {0, 1}, i = 1, n.

Говорят, что набор eα

предшествует набору

(набор

следует

после набора eα

) и пишут eα

, если

≤ β

, α

≤ β

, ..., α

≤ β

Будем говорить, что eα

строго предшествует

и обозначать

eα

≺

, если eα

и eα

Будем говорить, что eα

непосредственно предшествует

обозначать eα

≺

, если если eα

≺

и не существует набора eγ

такого, что eα

≺ eγ

≺

117

Замечание 2.1.19 . ¹, ≺ — отношения частичного порядка.

Определение 2.1.26 . Пусть f(x

, ..., x

) ∈ P

. Функция f

называется монотонной, если

eα

=⇒ f(eα

) ≤ f(

Класс всех монотонных функций будем обозначать M.

Пример 2.1.25 . Функция x является монотонной. Функция x — не

монотонна.

Утверждение 2.1.21 . Класс функций M замкнут.

Доказательство. Рассмотрим суперпозицию ранга 1 от функций из M.

a) Пусть f(x

, ..., x

) ∈ M и

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y) = f(x

, ..., x

j−1

, y, x

j+1

, ..., x

Тогда монотонность g непосредственно следует из монотонности функции

b) Пусть f(x

, ..., x

) ∈ M и h(y

, ..., y

) ∈ M и

g(x

, ..., x

j−1

, x

j+1

, ..., x

, y

, ..., y

) =

= f(x

, ..., x

j−1

, h(y

, ..., y

), x

j+1

, ..., x

Пусть eα

n+m−1

. Тогда, в частности,

(α

, ..., α

n+m−1

) ¹ (β

, ..., β

n+m−1

Поскольку h монотонна, то

h(α

, ..., α

n+m−1

) ≤ h(β

, ..., β

n+m−1

)

и, следовательно,

(α

, ..., α

j−1

, h(α

, ..., α

n+m−1

), α

, ..., α

n−1

) ¹

¹ (β

, ..., β

j−1

, h(β

, ..., β

n+m−1

), β

, ..., β

n−1

118

Таким образом, из монотонности f следует, что

g(eα

n+m−1

) = f(α

, ..., α

j−1

, h(α

, ..., α

n+m−1

), α

, ..., α

n−1

) ≤

≤ f(β

, ..., β

j−1

, h(β

, ..., β

n+m−1

), β

, ..., β

n−1

) = g(

n+m−1

Получаем, что g(x

, ..., x

j−1

, x

j+1

, ..., x

, y

, ..., y

) ∈ M.

Таким образом, [M] = M.

Замечание 2.1.20 . Тождественная фукнция f(x) = x лежит в

классе M. Функция отрицания f(x) = x не лежит в M. Таким образом,

M 6= ∅ и M 6= P

Лемма 2.1.22 (О немонотонной функции). Пусть

f(x

, ..., x

) /∈ M. Тогда, подставляя в f вместо аргументов 0, 1,

x можно получить x.

Доказательство. Так как f /∈ M, существуют два набора eα

, такие

что eα

и f(eα

) > f(

). Очевидно, что f(eα

) = 1 и f(

) = 0.

Пусть eα

отличен от

в t позициях.

a) Пусть t = 1. Тогда eα

≺

для некоторого i верно, что

eα

= (α

, ..., α

i−1

, 0, α

i+1

, ..., α

)

= (α

, ..., α

i−1

, 1, α

i+1

, ..., α

Определим функцию ϕ(x) следующим образом:

ϕ(x) = f(α

, ..., α

i−1

, x, α

i+1

, ..., α

Тогда:

ϕ(0) = f(α

, ..., α

i−1

, 0, α

i+1

, ..., α

) = 1

ϕ(1) = f(α

, ..., α

i−1

, 1, α

i+1

, ..., α

) = 0.

То есть ϕ(x) = x, что и требовалось доказать.

b) Пусть теперь t > 1. В этом случае построим последовательность

наборов

eα

= eγ

(0) ≺ eγ

(1) ≺ ... ≺ eγ

(t − 1) ≺ eγ

(t) =

119

где каждая пара наборов eγ

(i − 1) и eγ

(i) отличаются только в одной

позиции, i = 1, t. Это не трудно сделать, последовательно заменяя

каждую позицию, в которой наборы eα

различаются с нуля на

единицу. Поскольку f(eα

) = 1 и f(

) = 0, найдется такое k, что

eγ

(k − 1) = 1 и eγ

(i) = 0. Такая ситуация возвращает нас к пункту

a) доказательства.

Пример 2.1.26 (Построение x с помощью немонотонной функ-

ции). Пусть f(x, y, z) = x ⊃ (y ⊕ z). Эта функция немонотонна, так

как

f(0, 0, 0) = 0 ⊃ (0 ⊕ 0) = 1 > 0 = 1 ⊃ (1 ⊕ 1) = f(1, 1, 1).

Рассмотрим последовательность наборов

(0, 0, 0) ≺ (0, 0, 1) ≺ (0, 1, 1) ≺ (1, 1, 1)

и значения функции f на этих наборах

1 = f(0, 0, 0) = f(0, 0, 1) = f(0, 1, 1) > f(1, 1, 1) = 0.

Тогда ϕ(x) = f(x, 1, 1) = x. Действительно,

ϕ(x) = x ⊃ (1 ⊕ 1) = x ⊃ 0 = x.

2.1.12 Линейность

Определение 2.1.27 . Пусть f(x

, ..., x

) ∈ P

. Функция f —

линейная, если ее полином Жегалкина имеет вид

f(x

, ..., x

) = α

⊕ α

⊕ ... ⊕ α

Обозначим L — класс всех линейных функций.

Пример 2.1.27 . x — линейная функция. Функция x ∨ y не является

линейной.

Утверждение 2.1.23 . Класс функций L замкнут.

120