ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1354
Скачиваний: 1
28
Множество всех самодвойственных функций обозначим через
S
.
Из определения самодвойственности следует, что функция са-
модвойственна тогда и только тогда, когда на каждой паре противопо-
ложных наборов она принимает противоположные значения.
Лемма (о несамодвойственной функции).
Если функция
f
(
x
1
, x
2
, . . . , x
n
)
несамодвойственна, то подставляя в неё вместо пе-
ременных
x
1
, x
2
, . . . , x
n
x
или
¯
x
, можно получить простейшую неса-
модвойственную функцию – константу.
Упражнения
8.1.
Является ли функция
g
двойственной к функции
f
, если
а)
f
=
x
→
y,
g
=
y
→
x
;
б)
f
=
xy
∨
xz
∨
yz,
g
=
xy
⊕
xz
⊕
yz
;
в)
f
=
x
⊕
y
⊕
z,
g
=
x
⊕
y
⊕
z
;
г)
f
=
x
¯
yz
∨
x
(
y
↔
z
)
,
g
(
x, y, z
) = (01101101)
;
д)
f
=
x
⊕
y,
g
=
x
↔
y
.
8.2.
Пусть значения функции
f
(
x
1
, x
2
, . . . , x
n
)
образуют согласно таб-
лице истинности набор
(
α
1
, α
2
, . . . , α
2
n
)
. Доказать, что функция
f
∗
(
x
1
, x
2
, . . . , x
n
)
задается вектором
( ¯
α
2
n
,
¯
α
2
n
−
1
, . . . ,
¯
α
2
,
¯
α
1
)
.
8.3.
Выразить в виде формул функции, двойственные к элементарным
булевым функциям.
8.4.
Пользуясь принципом двойственности, построить формулу, реали-
зующую функцию, двойственную к функции
f
. Полученное выра-
жение упростить (записав его в виде днф или в виде полинома Же-
галкина)
а)
f
=
xy
∨
yz
∨
xt
∨
zt
;
б)
f
=
x
·
1
∨
y
(
zt
∨
0)
∨
xyz
;
в)
f
= (
x
↔
y
)
⊕
((
x
↓
y
)
|
(¯
x
↔
yz
))
;
г)
f
= (¯
x
∨
y
∨
(
y
¯
z
⊕
1))
→
1
.
8.5.
Самодвойственна ли функция
f
?
а)
f
=
xy
∨
yz
∨
xz
;
б)
f
=
¬
((
x
→
y
)
→
xz
)
→
(
y
→
z
)
;
в)
f
= (
x
∨
y
∨
z
)
t
∨
xyz
;
29
г)
f
= (0001001001100111)
;
д)
f
=
x
1
⊕
x
2
⊕
. . .
⊕
x
2
m
+1
⊕
σ
, где
σ
=
{
0
,
1
}
.
8.6.
Доказать, что если
f
(
x
1
, x
2
, . . . , x
n
)
– самодвойственная функция,
то мощность её множества истинности равна
2
n
−
1
.
8.7.
Из самодвойственной функции
f
с помощью подстановки на места
независимых переменных
x
и
¯
x
получить константу:
а)
f
= (01101001)
;
б)
f
= (
x
∨
¯
y
∨
z
)
t
∨
¯
xyz
;
в)
f
= (
x
↓
y
)
→
(
x
⊕
z
)
;
г)
f
=
xy
∨
xz
∨
yt
∨
zt
.
§9.
Линейность и класс линейных функций
Булева функция
f
(
x
1
, x
2
, . . . , x
n
)
называется линейной, если сте-
пень её полинома Жегалкина не превосходит 1, другими словами, если
она представима в виде
f
(
x
1
, x
2
, . . . , x
n
) =
a
0
⊕
a
1
x
1
⊕
a
2
x
2
⊕
. . .
⊕
a
n
x
n
,
где
a
i
∈ {
0
,
1
}
,
0
≤
i
≤
n
. Множество всех линейных функций обознача-
ется
L
, а множество всех линейных функций, зависящих от переменных
x
1
, x
2
, . . . , x
n
– через
L
n
.
Класс
L
линейных функций замкнут. Мощность множества
L
n
рав-
на
2
n
+1
. Функция
f
∈
/L
называется нелинейной.
Лемма (о нелинейной функции).
Если
f
(
x
1
, x
2
, . . . , x
n
)
нели-
нейная функция, то подставляя на места её переменных
x
1
, x
2
, . . . , x
n
функции
0
,
1
, x, y,
¯
x,
¯
y
получим либо
xy
, либо
x
|
y
.
Упражнения
9.1.
Разлагая функцию
f
в полином Жегалкина, выяснить, является
ли она линейной.
а)
f
(
x, y, z
) = (
xy
∨
xz
)
⊕
z
;
б)
f
(
x, y
) =
xy
(
x
⊕
y
)
;
в)
f
(
x, y, z, u
) =
xy
∨
yz
∨
zu
∨
xu
;
г)
f
(
x, y, z
) = (
x
→
y
)(
y
→
x
)
↔
z
.
30
9.2.
Наборы
(
α
1
, . . . , α
i
−
1
, α
i
, α
i
+1
, . . . , α
n
)
и
(
α
1
, . . . , α
i
−
1
,
¯
α
i
, α
i
+1
, . . . ,
α
n
)
являются соседними (см. определение на стр. 3). Доказать, что
если функция на любых двух соседних наборах принимает проти-
воположные значения, то она линейна.
9.3.
Доказать, что если
f
(
x
1
, x
2
, . . . , x
n
)
– линейная функция отличная
от константы, то мощность её множества истинности равна
2
n
−
1
.
9.4.
Выяснить, является ли линейной функция
f
:
а)
f
(
x, y, z, u
) = (1010101001101000)
;
б)
f
(
x, y, z, u
) = (1001011010010110)
;
в)
f
(
x, y, z, u
) = (1001011001101001)
;
г)
f
(
x, y, z, u
) = (0110100110100101)
.
9.5.
Выяснить, можно ли из функции
f
с помощью подстановки на ме-
ста её переменных функций
0
,
1
, x, y,
¯
x,
¯
y
получить
xy
.
а)
f
(
x, y, z
) = (11101000)
;
б)
f
(
x, y, z
) = (01111111)
;
в)
f
(
x, y, z
) = (10011001)
;
г)
f
(
x
1
, x
2
, . . . , x
n
) = (
x
1
→
x
2
)(
x
2
→
x
1
)
⊕
(
x
2
→
x
3
)(
x
3
→
x
2
)
⊕
⊕
. . .
⊕
(
x
n
−
1
→
x
n
)(
x
n
→
x
n
−
1
)
.
§10.
Классы функций, сохраняющих константы
Говорят, что функция
f
(
x
1
, x
2
, . . . , x
n
)
сохраняет константу 0
(константу
1),
если
f
(0
,
0
, . . . ,
0)
=
0
(соответственно,
если
f
(1
,
1
, . . . ,
1) = 1
). Множество всех булевых функций, сохраняющих кон-
станту 0, обозначается через
T
0
, а сохраняющих 1 –
T
1
. Множество всех
булевых функций, зависящих от переменных
x
1
, x
2
, . . . , x
n
и сохраняю-
щих константу 0 (константу 1) будем обозначать
T
0
n
(соответственно
T
1
n
). Мощность классов
T
0
n
и
T
1
n
совпадают и равны
2
2
n
−
1
. Каждое
из множеств
T
0
, T
1
является замкнутым в Б классом.
Упражнения
10.1.
Выяснить, каким из множеств
T
0
∪
T
1
, T
1
\
T
0
принадлежат пере-
численные ниже функции:
а)
((
x
∨
y
)
→
(
x
|
yz
))
↓
((
y
↔
z
)
→
x
)
;
б)
(
xy
→
z
)
|
((
x
→
y
)
↓
(
z
⊕
¯
xy
))
;
31
в)
(
x
→
y
)(
y
↓
z
)
∨
(
z
→
y
)
.
10.2.
Выяснить, при каких
n
функция
f
(
x
1
, x
2
, . . . , x
n
)
принадлежит
множеству
T
1
\
T
0
:
а)
f
(
x
1
, x
2
, . . . , x
n
) =
x
1
⊕
x
2
⊕
. . .
⊕
x
n
⊕
1
;
б)
f
(
x
1
, x
2
, . . . , x
n
) = (
. . .
((
x
1
→
x
2
)
→
x
3
)
→
. . .
→
x
n
)
;
в)
f
(
x
1
, x
2
, . . . , x
n
) = 1
⊕
⃝
∑
1
≤
i
1
<i
2
<i
3
≤
n
x
i
1
x
i
2
x
i
3
.
10.3.
Подсчитать
число
функций,
зависящих
от
переменных
x
1
, x
2
, . . . , x
n
, в каждом из следующих множеств:
a)
T
0
∩
T
1
;
е)
T
1
∩
S
;
б)
T
0
∪
T
1
;
ж)
T
0
\
S
;
в)
T
0
∩
L
;
з)
L
∩
S
∩
T
1
;
г)
T
1
∪
L
;
и)
S
∩
(
T
0
∪
T
1
)
;
д)
L
\
(
T
0
∩
T
1
)
;
к)
S
\
(
T
0
∪
T
1
)
.
10.4.
Найти функцию
φ
(
x
) =
f
(
x, x, . . . , x
)
, если
а)
f
(
x
1
, x
2
, . . . , x
n
)
∈
T
1
\
T
0
;
б)
f
(
x
1
, x
2
, . . . , x
n
)
∈
L
\
(
T
1
∩
S
)
;
в)
f
(
x
1
, x
2
, . . . , x
n
)
∈
S
\
T
0
.
§11.
Монотонность и класс монотонных функций
Булева функция
f
(
x
1
, x
2
, . . . , x
n
)
называется монотонной, если для
любых двух наборов
(
α
1
, α
2
, . . . , α
n
)
и
(
β
1
, β
2
, . . . , β
n
)
из
E
n
таких, что
α
1
≤
β
1
, α
2
≤
β
2
, . . . , α
n
≤
β
n
имеет место неравенство
f
(
α
1
, α
2
, . . . , α
n
)
≤
f
(
β
1
, β
2
, . . . , β
n
)
.
В противном случае функция
f
(
x
1
, x
2
, . . . , x
n
)
называется немонотон-
ной.
Множество всех монотонных булевых функций обозначается через
M
, а множество всех монотонных функций, зависящих от переменных
x
1
, x
2
, . . . , x
n
– через
M
n
. Множество
M
является замкнутым в Б клас-
сом.
Лемма (о немонотонной функции)
:
если
f
∈
/ M
, то, подстав-
ляя на места её переменных функции
0
,
1
, x
, можно получить про-
стейшую немонотонную функцию
¯
x
.
32
Вершина
(
α
1
, α
2
, . . . , α
n
)
∈
E
n
называется нижней едини-
цей
(верхним
нулем)
монотонной
функции
f
(
x
1
, x
2
, . . . , x
n
)
,
ес-
ли
f
(
α
1
, α
2
, . . . , α
n
)
=
1
(соответственно
f
(
α
1
, α
2
, . . . , α
n
)
=
0
)
и
для
всякой
вершины
(
β
1
, β
2
, . . . , β
n
)
из
неравенств
β
1
≤
α
1
, β
2
≤
α
2
, . . . , β
n
≤
α
n
вытекает
f
(
β
1
, β
2
, . . . , β
n
) = 0
(соответственно из
α
1
≤
β
1
, α
2
≤
β
2
, . . . , α
n
≤
β
n
вытекает
f
(
β
1
, β
2
, . . . , β
n
) = 1
).
Упражнения
11.1.
Какие из перечисленных ниже функций является монотонными?
а)
x
→
(
x
→
y
)
;
б)
x
→
(
y
→
x
)
;
в)
xy
(
x
⊕
y
)
;
г)
xy
⊕
yz
⊕
zx
⊕
z
;
д)
f
(
x, y, z
) = (00110111)
;
е)
f
(
x, y, z
) = (01100111)
;
ж)
f
(
x, y, z, u
) = (0000000010111111)
;
з)
f
(
x, y, z, u
) = (0001010101010111)
.
11.2.
Доказать, что для каждой монотонной функции
f
, отличной от
константы, существует днф и кнф, не содержащие отрицаний пере-
менных и реализующие функцию
f
.
11.3.
Сколько существует монотонных функций
f
(
x, y, z
)
таких, что
f
(0
,
1
,
1) =
f
(1
,
0
,
1) = 1
, f
(0
,
0
,
1) = 0
. Сколько таких функций
принадлежит множеству
M
\
S
?
11.4.
Показать, что если функция
f
(
x
1
, x
2
, . . . , x
n
)
немонотонна,
то существуют такие два набора
(
α
1
, . . . , α
i
−
1
,
0
, α
i
+1
, . . . , α
n
)
и
(
α
1
, . . . , α
i
−
1
,
1
, α
i
+1
, . . . , α
n
)
такие, что
f
(
α
1
, . . . , α
i
−
1
,
0
, α
i
+1
, . . . , α
n
)
> f
(
α
1
, . . . , α
i
−
1
,
1
, α
i
+1
, . . . , α
n
)
.
11.5.
Показать, что не существует монотонных самодвойственных функ-
ций, имеющих ровно две нижние единицы.
11.6.
Пусть
m
(
n
)
– число монотонных функций, зависящих от перемен-
ных
x
1
, x
2
, . . . , x
n
. Показать, что
m
(1) = 3
, m
(2) = 6
, m
(3) = 20
.