ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1352
Скачиваний: 1
23
– удалим лишение слагаемые, так как
u
⊕
u
= 0
.
Пример 1.
Построить ПЖ для функции
(
x
→
¯
y
)
∧
(
z
⊕
¯
x
)
с ис-
пользованием таблицы истинности.
Построим таблицу истинности для данной функции:
x y z
¯
x
¯
y x
→
¯
y z
⊕
¯
x
(
x
→
¯
y
)
∧
(
z
⊕
¯
x
)
0
0 0 1
1
1
1
1
0
0 1 1
1
1
0
0
0
1 0 1
0
1
1
1
0
1 1 1
0
1
0
0
1
0 0 0
1
1
0
0
1
0 1 0
1
1
1
1
1
1 0 0
0
0
0
0
1
1 1 0
0
0
1
0
Для построения полинома Жегалкина используем его пред-
ставление
(6.3).
Составим
систему
уравнений
для
неизвестных
a
0
, a
1
, a
2
, . . . , a
123
:
a
0
=
1
a
0
⊕
a
3
=
0
a
0
⊕
a
2
=
1
a
0
⊕
a
1
=
0
a
0
⊕
a
2
⊕
a
3
⊕
a
23
=
0
a
0
⊕
a
1
⊕
a
2
⊕
a
12
=
0
a
0
⊕
a
1
⊕
a
3
⊕
a
13
=
1
a
0
⊕
a
1
⊕
a
2
⊕
a
3
⊕
a
12
⊕
a
13
⊕
a
23
⊕
a
123
= 0.
Решая эту систему уравнений "сверху вниз", находим:
a
2
=
a
23
=
=
a
12
=
a
13
= 0
,
a
0
=
a
1
=
a
3
=
a
123
= 1
. Подставляя найденные
коэффициенты в (6.3), получим
P
(
x, y, z
) = 1
⊕
x
⊕
z
⊕
xyz.
Пример 2.
Построить ПЖ для функции
(
x
→
¯
y
)
∧
(
z
⊕
¯
x
)
методом
эквивалентных преобразований.
(
x
→
¯
y
)
∧
(
z
⊕
¯
x
) = (¯
x
∨
¯
y
)
∧
(
z
⊕
x
⊕
1) =
= (
x
∧
y
)
∧
(
z
⊕
x
⊕
1) = (
xy
⊕
1)(
z
⊕
x
⊕
1) =
xyz
⊕
x
⊕
z
⊕
1
.
Сравнивая результаты, полученные в примерах 1 и 2, можно ещё
раз убедиться в единственности представления формулы в виде ПЖ.
24
Задачи и упражнения
6.1.
Построить полиномы Жегалкина для функций:
а)
(
x
⊕
y
)
→
yz
;
б)
f
= (01101100)
;
в)
((¯
x
→
¯
y
)
↔
z
)
|
xyz
;
г)
f
= (0100110000110010)
.
6.2.
Построить ПЖ методом эквивалентных преобразований для следу-
ющих формул алгебры высказываний:
а)
(¯
x
→
y
)(¯
x
⊕
y
)(
x
↔
y
)(
y
|
x
)
;
б)
((
x
→
y
)
∨
¯
z
)
↔
(
x
∨
(
y
→
¯
z
))
;
в)
(
x
1
∨
x
2
)
→
(
x
3
∨
x
4
)
;
г)
((
x
⊕
z
)
→
y
)
∨
((¯
x
|
y
)
∨
¯
y
)
;
д)
(
y
↔
z
)(
z
↔
¯
x
)(
x
∨
y
)
;
е)
(
x
1
|
x
2
)
→
(
x
3
|
x
4
)
.
6.3.
Построить полиномы для функций:
а)
f
(
x, y, z
) = (
x
|
y
)
↓
z
;
б)
f
(
x, y, z
) = (
x
→
y
)(
x
↓
z
)
;
в)
f
(
x, y, z
) = ((
x
→
y
)
∨
z
)
|
x
.
6.4.
Всякую булеву функцию можно записать в виде полинома, исполь-
зуя обычные арифметические операции умножения, сложения и вы-
читания. Для этого достаточно выразить
f
через конъюнкцию и
отрицание, а затем заменить формулу вида
¯
A
на
1
−
A
и раскрыть
скобки. Выразить с помощью арифметических операций следующие
функции:
а)
f
(
x, y, z
) =
x
⊕
y
;
б)
f
(
x, y, z
) = (
x
→
y
)
→
z
;
в)
f
(
x, y, z
) = (10000001)
.
6.5.
На скольких наборах из
E
n
обращается в единицу полином
P
(
x
1
, x
2
, . . . , x
n
)
:
а)
P
(
x
1
, x
2
, . . . , x
n
) =
x
1
. . . x
k
⊕
x
k
+1
. . . x
n
;
б)
P
(
x
1
, x
2
, . . . , x
n
) = 1
⊕
x
1
⊕
x
1
x
2
⊕
. . .
⊕
x
1
x
2
. . . x
n
.
25
6.6.
Показать, что если в совершенной днф знак
∨
везде заменить на
знак
⊕
, то получится формула, эквивалентная исходной. Справед-
ливо ли аналогичное утверждение для произвольной днф?
Производной булевой функции
f
(
x
1
, x
2
, . . . , x
n
)
по совокупности пере-
менных
x
i
1
, x
i
2
, . . . , x
i
k
(или булевой разностью называется функция)
∂f
(
x
1
, x
2
, . . . , x
n
)
∂
(
x
i
1
, x
i
2
, . . . , x
i
k
)
=
f
(
x
1
, . . . ,
¯
x
i
1
. . . ,
¯
x
i
k
, . . . , x
n
)
⊕
⊕
f
(
x
1
, . . . , x
i
1
. . . , x
i
k
, . . . , x
n
)
.
6.7.
Доказать следующие свойства производной:
а)
d
dx
j
(
df
(
x
1
, x
2
, . . . , x
n
)
dx
i
)
=
d
dx
i
(
df
(
x
1
, x
2
, . . . , x
n
)
dx
j
)
;
б)
∂f
(
x
1
, x
2
, . . . , x
n
)
∂
(
x
i
1
, x
i
2
, . . . , x
i
k
)
=
∂
¯
f
(
x
1
, x
2
, . . . , x
n
)
∂
(
x
i
1
, x
i
2
, . . . , x
i
k
)
;
в)
∂
(
f
(
x
1
, x
2
, . . . , x
n
)
⊕
g
(
x
1
, x
2
, . . . , x
n
))
∂
(
x
i
1
, x
i
2
, . . . , x
i
k
)
=
∂f
(
x
1
, x
2
, . . . , x
n
)
∂
(
x
i
1
, x
i
2
, . . . , x
i
k
)
⊕
⊕
∂g
(
x
1
, x
2
, . . . , x
n
)
∂
(
x
i
1
, x
i
2
, . . . , x
i
k
)
;
г)
d
(
f
(
x
1
, x
2
, . . . , x
n
)
∨
g
(
x
1
, x
2
, . . . , x
n
))
dx
i
=
f
(
x
1
, x
2
, . . . , x
n
)
∗
∗
dg
(
x
1
, x
2
, . . . , x
n
)
dx
i
⊕
g
(
x
1
, x
2
, . . . , x
n
)
df
(
x
1
, x
2
, . . . , x
n
)
dx
i
⊕
⊕
df
(
x
1
, x
2
, . . . , x
n
)
dx
i
·
dg
(
x
1
, x
2
, . . . , x
n
)
dx
i
;
д)
d
(
f
(
x
1
, x
2
, . . . , x
n
)
·
g
(
x
1
, x
2
, . . . , x
n
))
dx
i
=
f
(
x
1
, x
2
, . . . , x
n
)
∗
∗
dg
(
x
1
, x
2
, . . . , x
n
)
dx
i
+
g
(
x
1
, x
2
, . . . , x
n
)
df
(
x
1
, x
2
, . . . , x
n
)
dx
i
+
+
df
(
x
1
, x
2
, . . . , x
n
)
dx
i
·
dg
(
x
1
, x
2
, . . . , x
n
)
dx
i
;
е)
df
(
x
1
, x
2
, . . . , x
n
)
dx
i
= 0
тогда и только тогда, когда
x
i
не входит
явно в полином Жегалкина
f
(
x
1
, x
2
, . . . , x
n
)
;
ж)
если
f
(
x
1
, x
2
, . . . , x
n
)
=
x
1
g
(
x
2
, . . . , x
n
) +
h
(
x
2
, . . . , x
n
)
, то
df
(
x
1
, x
2
, . . . , x
n
)
dx
1
=
g
(
x
2
, . . . , x
n
)
.
6.8.
Если
g
(
x
1
, x
2
, . . . , x
m
)
и
h
(
x
m
+1
, . . . , x
n
)
– булевы функции и
1
≤
j
≤
m
для всех
j
= 1
, . . . , k
, то
26
а)
∂
(
g
+
h
)
∂
(
x
i
1
, . . . , x
i
k
)
=
∂g
∂
(
x
i
1
, . . . , x
i
k
)
;
б)
∂
(
g
∧
h
)
∂
(
x
i
1
, . . . , x
i
k
)
=
h
∂g
∂
(
x
i
1
, . . . , x
i
k
)
;
в)
∂
(
g
∨
gh
)
∂
(
x
i
1
, . . . , x
i
k
)
= ¯
h
∂g
∂
(
x
i
1
, . . . , x
i
k
)
.
§7.
Операция замыкания. Замкнутые классы
Обозначим Б – множество всех булевых функций. Пусть
Φ
⊆
Б
множество функций (или логических связок). Суперпозицией функций
из
Φ
называется всякая функция
F
, которую можно реализовать фор-
мулой над множеством
Φ
.
Пусть
M
– некоторые подмножество множества Б . Замыканием
[
M
]
множества
M
называется совокупность всех функций из Б , явля-
ющихся суперпозициями функций из
M
.
Операция получения множества
[
M
]
из
M
называется операцией
замыкания. Множество
M
называется функционально замкнутым клас-
сом (короче замкнутым классом), если
[
M
] =
M
.
Пусть
M
– замкнутый класс в Б . Подмножество
P
из
M
называ-
ется функционально полной системой в
M
, если
[
P
] =
M
. Множество
P
функций из
M
называется неприводимой системой, если замыкание
любого собственного подмножества
P
′
из
P
отлично от замыкания все-
го множества
P
, т.е.
[
P
′
]
⊆
[
P
]
и
[
P
′
]
̸
= [
P
]
. Неприводимая, полная в
замкнутом классе
M
система называется базисом класса
M
.
Упражнения
7.1.
Обосновать следующие свойства замыкания:
а)
[ [
M
] ] = [
M
]
;
б)
если
M
1
⊆
M
2
, то
[
M
1
]
⊆
[
M
2
]
;
в)
[
M
1
∪
M
2
]
⊇
[
M
1
]
∪
[
M
2
]
;
г)
[
∅
] =
∅
.
7.2.
Вытекает ли соотношение г) из соотношений а), б), в)?
7.3.
Выяснить какие из отношений
⊃
,
⊂
,
⊇
,
⊆
,
=
,
⊃
⊂
/
выполняется для
множеств
K
1
⊆
Б и
K
2
⊆
Б (отношение
⊃
⊂
/
означает, что ни одно
из отношений
K
1
и
K
2
не выполняется)
27
а)
K
1
= [
M
1
∩
M
2
]
,
K
2
= [
M
1
]
∩
[
M
2
]
;
б)
K
1
= [
M
1
\
M
2
]
,
K
2
= [
M
1
]
\
[
M
2
]
;
в)
K
1
= [
M
1
∪
(
M
2
∩
M
3
)]
,
K
2
= [
M
1
∪
M
2
]
∩
[
M
1
∪
M
3
]
;
г)
K
1
= [
M
1
∩
(
M
2
∪
M
3
)]
,
K
2
= [
M
1
∩
M
2
]
∪
[
M
1
∩
M
3
]
;
д)
K
1
= [
M
1
\
(
M
1
∩
M
2
)]
,
K
2
= [
M
1
]
\
[
M
1
∩
M
2
]
.
7.4.
Из системы
P
, полной для замкнутого класса
M
= [
P
]
, выделить
базис
а)
P
=
{
0
,
1
, x,
¯
x
}
;
б)
P
=
{
1
, x
⊕
y
⊕
z
⊕
1
}
;
в)
P
=
{
x
∨
y, xyz, x
∨
yz,
(
x
∨
y
)
z
}
;
г)
P
=
{
x
∨
y
∨
z, xyz,
(
x
→
y
)
→
z,
(
x
∨
y
)
z
}
;
д)
P
=
{
xy, x
∨
y, x
→
y, x
⊕
y
⊕
z
}
.
§8.
Двойственность и класс самодвойственных функций
Функция
g
(
x
1
, x
2
, . . . , x
n
)
называется двойственной к функции
f
(
x
1
, x
2
, . . . , x
n
)
, если
g
(
x
1
, x
2
, . . . , x
n
) = ¯
f
(¯
x
1
,
¯
x
2
, . . . ,
¯
x
n
)
.
По определению, функцией, двойственной к константе 0, является
константа 1 и, наоборот, константа 0 является функцией, двойственной
к константе 1. Функция, двойственная к функции
f
(
x
1
, x
2
, . . . , x
n
)
, обо-
значается
f
∗
(
x
1
, x
2
, . . . , x
n
)
. Итак,
f
∗
(
x
1
, x
2
, . . . , x
n
) = ¯
f
(¯
x
1
,
¯
x
2
, . . . ,
¯
x
n
)
.
(8
.
1)
f
∗∗
(
x
1
, x
2
, . . . , x
n
) =
f
(
x
1
, x
2
, . . . , x
n
)
.
Справедливо следующее утверждение, называемое принципом
двойственности.
Если
Φ(
x
1
, x
2
, . . . , x
n
)
=
f
(
f
1
(
x
1
, x
2
, . . . , x
n
)
, . . . ,
f
m
(
x
1
, x
2
, . . . , x
n
))
, то
Φ
∗
(
x
1
, x
2
, . . . , x
n
)
=
f
∗
(
f
∗
1
(
x
1
, x
2
, . . . , x
n
)
, . . . ,
f
∗
m
(
x
1
, x
2
, . . . , x
n
))
.
Пусть
M
– некоторое множество булевых функций,
M
⊆
Б . Че-
рез
M
∗
обозначим множество всех булевых функций, двойственных к
функциям из множества
M
. Множество
M
∗
называется двойственным
к множеству
M
. Если
M
∗
=
M
, то множество
M
называется самодвой-
ственным.
Функция
f
(
x
1
, x
2
, . . . , x
n
)
называется самодвойственной, если она
совпадает со своей двойственной
f
∗
(
x
1
, x
2
, . . . , x
n
) =
f
(
x
1
, x
2
, . . . , x
n
)
.