ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1348
Скачиваний: 1
18
Применим теперь для построения сднф и скнф метод эквивалентных
преобразований
(
x
⊕
yz
)
|
(
y
→
zx
) =
¬
(
x
⊕
yz
)
∨ ¬
(
y
→
zx
) = (
x
↔
yz
)
∨ ¬
(¯
y
∨
zx
) =
=
xyz
∨
¯
x yz
∨
yzx
=
xyz
∨
¯
x
(¯
y
∨
¯
z
)
∨
y
(¯
z
∨
¯
x
) =
xyz
∨
¯
x
¯
y
∨
¯
x
¯
z
∨
y
¯
z
∨
y
¯
x
=
мы получили дизъюнктивную нормальную форму; продолжим преобра-
зования, используя (5.3)-(5.4)
=
xyz
∨
¯
x
¯
y
¯
z
∨
¯
x
¯
yz
∨
¯
xy
¯
z
∨
¯
x
¯
y
¯
z
∨
xy
¯
z
∨
¯
xy
¯
z
∨
¯
xyz
∨
¯
xy
¯
z
=
=
xyz
∨
¯
x
¯
y
¯
z
∨
¯
x
¯
yz
∨
¯
xy
¯
z
∨
xy
¯
z
∨
¯
xyz
−
сднф
.
Построим скнф
xyz
∨
¯
x yz
∨
yzx
= ¯
x yz
∨
(
xyz
∨
yzx
) = ¯
x
(¯
y
∨
¯
z
)
∨
y
(
xz
∨
xz
) = ¯
x
(¯
y
∨
¯
z
)
∨
y
=
= (¯
x
∨
y
)(¯
y
∨
¯
z
∨
y
) = ¯
x
∨
y
−
кнф
;
на основании (5.6) имеем
f
= ¯
x
∨
y
= (¯
x
∨
y
∨
z
)(¯
x
∨
y
∨
¯
z
)
−
скнф
.
Пример 2.
Построить сднф и скнф, реализующих функцию
(
x
∨
¯
yz
)
↓
(
xy
→
¯
z
)
.
Построим таблицу истинности.
x y z
¯
y
¯
z
¯
yz x
∨
¯
yz xy xy
→
¯
z
(
x
∨
¯
yz
)
↓
(
xy
→
¯
z
)
0
0 0 1 1
0
0
0
1
0
0
0 1 1 0
1
1
0
1
0
0
1 0 0 1
0
0
0
1
0
0
1 1 0 0
0
0
0
1
0
1
0 0 1 1
0
1
0
1
0
1
0 1 1 0
1
1
0
1
0
1
1 0 0 1
0
1
1
1
0
1
1 1 0 0
0
1
1
0
0
Исследуемая функция является противоречием, так как на всех на-
борах принимает значение 0. Она не имеет реализующей её сднф, а скнф
состоит из восьми сомножителей и имеет следующий вид
f
= (
x
∨
y
∨
z
)(¯
x
∨
y
∨
z
)(
x
∨
¯
y
∨
z
)(
x
∨
y
∨
¯
z
)(¯
x
∨
¯
y
∨
z
)(¯
x
∨
y
∨
¯
z
)(
x
∨
¯
y
∨
¯
z
)(¯
x
∨
¯
y
∨
¯
z
)
.
Методом эквивалентных преобразований скнф для тождественно
ложной функции можно получить используя (5.7) следующем образом:
0 =
x
¯
x
= (
x
∨
y
)(
x
∨
¯
y
)(¯
x
∨
¯
y
)(¯
x
∨
¯
y
) =
= (
x
∨
y
∨
z
)(¯
x
∨
y
∨
z
)(
x
∨
¯
y
∨
z
)(
x
∨
y
∨
¯
z
)(¯
x
∨
¯
y
∨
z
)(¯
x
∨
y
∨
¯
z
)(
x
∨
¯
y
∨
¯
z
)(¯
x
∨
¯
y
∨
¯
z
)
.
19
Задачи и упражнения
5.1.
Построить сднф и скнф для следующих функций (для функций,
заданных формулами, предварительно построить таблицы истинно-
сти):
а)
(
x
⊕
y
)
→
yz
;
б)
f
= (01101100)
;
в)
((¯
x
→
¯
y
)
↔
z
)
|
xyz
;
г)
f
= (0100110000110010)
;
д)
(¯
x
→
y
)(¯
x
⊕
y
)(
x
↔
y
)(
y
|
x
)
;
е)
(
x
⊕
y
)
→
(
z
∨
¯
x
)
;
ж)
(¯
x
|
z
)
↔
(
y
¯
z
)
;
и)
(
x
↔
¯
z
)
↓
(
x
→
y
)
;
к)
(
xy
→
¯
z
)
⊕
¯
x
;
л)
¬
(
xyz
)
→
(¯
x
|
¯
y
)
;
м)
(
x
→
¯
z
)
⊕
(
x
∨
y
)
;
н)
¯
x
↔
(
x
∨
yz
)
.
5.2.
Преобразовать заданные днф в совершенные:
а)
xy
∨
y
¯
z
∨
¯
x
¯
y
;
б)
x
1
∨
x
2
x
3
∨
x
1
x
2
x
4
;
в)
x
∨
¯
x
¯
y
¯
z
∨
xy
;
г)
xy
∨
xyz
∨
y
∨
¯
xy
;
д)
x
1
x
2
∨
x
2
x
3
∨
¯
x
3
x
1
.
5.3.
Преобразовать заданные кнф в совершенные:
а)
(¯
x
∨
y
)(
z
∨
y
)
z
;
б)
(
u
∨
v
)(
u
∨
¯
v
∨
w
)(¯
u
∨
v
)
;
в)
(
x
1
∨
x
2
)(
x
2
∨
x
3
)(
x
3
∨
x
4
)
;
г)
(¯
x
∨
¯
y
)(
x
∨
z
)
y
;
д)
(
x
1
∨
x
2
)(
x
1
∨
x
3
∨
¯
x
4
)
.
5.4.
Построить сднф и скнф следующих функций при помощи эквива-
лентных преобразований:
а)
((
x
→
y
)
∨
¯
z
)
↔
(
x
∨
(
y
→
¯
z
))
;
20
б)
(
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
)
.
5.5.
Построить формулу функции от трех переменных, которая прини-
мает значение 1 в том и только в том случае, когда равно две пере-
менные равны нулю.
5.6.
Построить формулу функции от трех переменных, которая прини-
мает такое же значение, как и большинство (или меньшинство) пе-
ременных.
5.7.
Доказать, что функция от
n
переменных
f
(
x
1
, x
2
, . . . , x
n
) = 1
тогда
и только тогда, когда её сднф содержит
2
n
попарно не эквивалент-
ных элементарных конъюнкций.
5.8.
Доказать, что функция от
n
переменных
f
(
x
1
, x
2
, . . . , x
n
) = 0
тогда
и только тогда, когда её скнф содержит
2
n
попарно не эквивалент-
ных элементарных дизъюнкций.
5.9.
По скнф формулы
U
построить
а)
сднф двойственной формулы
U
∗
;
б)
скнф формулы
¯
U
;
в)
сднф формулы
¯
U
.
5.10.
По сднф формулы
U
и сднф формулы
V
построить
а)
скнф и сднф формулы
U ∨ V
;
б)
скнф и сднф формулы
U ∧ V
;
в)
скнф и сднф формулы
U → V
.
5.11.
Найти длину совершенной днф функции
f
(
x
1
, x
2
, . . . , x
n
)
:
а)
f
(
x
1
, x
2
, . . . , x
n
) =
x
1
⊕
x
2
⊕
. . .
⊕
x
n
;
б)
f
(
x
1
, x
2
, . . . , x
n
) = (
x
1
∨
x
2
∨
. . .
∨
x
n
)(¯
x
1
∨
¯
x
2
∨
. . .
∨
¯
x
n
)
;
в)
f
(
x
1
, x
2
, . . . , x
n
) = (
x
1
∨
x
2
∨
x
3
)(
x
1
∨
x
2
∨
x
3
)
⊕
x
4
⊕
x
5
⊕
. . .
⊕
x
n
.
21
§6.
Полином Жегалкина
Определение.
Пусть
x
1
, x
2
, . . . , x
n
– булевы переменные. Монотон-
ной конъюнкцией, составленной из переменных
x
1
, x
2
, . . . , x
n
, называет-
ся элементарная конъюнкция вида
K
M
=
x
i
1
x
i
2
. . . x
i
r
,
(6
.
1)
где
{
i
1
, i
2
, . . . , i
r
} ⊆ {
1
,
2
, . . . , n
}
, число
r
– ранг монотонной конъюнк-
ции.
Из определения следует, что число монотонных конъюнкций, состав-
ленных из переменных
x
1
, x
2
, . . . , x
n
, равно числу подмножеств множе-
ства
{
1
,
2
, . . . , n
}
, а именно
2
2
n
.
При
n
= 3
мы имеем следующие монотонные конъюнкции, состав-
ленные из переменных
x, y, z
:
1;
x
;
y
;
z
;
xy
;
xz
;
yz
;
xyz
.
Определение.
Полиномом Жегалкина (ПЖ) от переменных
x
1
, x
2
, . . . , x
n
называется сумма по модулю 2 различных монотонных
конъюнкций, составленных из этих переменных:
P
(
x
1
, x
2
, . . . , x
n
) =
K
M
1
⊕
K
M
2
⊕
. . .
⊕
K
M
l
,
(6
.
2)
где
0
≤
l
≤
2
2
n
.
Наибольший из рангов элементарных конъюнкций, входящих в по-
лином Жегалкина, называется его степенью.
В случае 3-х переменных имеем:
P
(
x, y, z
) =
a
0
⊕
a
1
x
⊕
a
2
y
⊕
a
3
z
⊕
a
12
xy
⊕
a
13
xz
⊕
a
23
yz
⊕
a
123
xyz,
(6
.
3)
здесь
a
0
, a
1
, a
2
, a
3
, a
12
, a
13
, a
23
, a
123
– коэффициенты полинома
P
(
x, y, z
)
,
каждый из которых принимает одно из двух значений 0 или 1.
В случае
n
-переменных
x
1
, x
2
, . . . , x
n
полином
P
(
x
1
, x
2
, . . . , x
n
)
мо-
жет быть записан в виде
P
(
x
1
, x
2
, . . . , x
n
) =
⃝
∑
{
i
1
,i
2
,...,i
s
}⊆{
1
,
2
,...,n
}
a
i
1
i
2
... i
s
x
i
1
x
i
2
. . . x
i
s
,
(6
.
4)
где
a
i
1
i
2
... i
s
∈ {
0
,
1
}
– коэффициенты полинома Жегалкина.
Каждый полином Жегалкина однозначно задается набором своих
коэффициентов
(
a
0
, a
1
, a
12
, a
13
, a
23
, a
123
, . . . , a
i
1
i
2
... i
s
, . . . , a
12
...n
)
.
(6
.
5)
Длина этого набора равна
2
n
, состоит он из нулей и единиц. Отсюда сле-
дует, что число полиномов Жегалкина от
n
переменных равно
¯
A
n
2
= 2
2
n
и совпадает с числом булевых функций от
n
переменных.
22
Теорема.
Для каждой булевой функции существует и единствен-
но до порядка слагаемых её представление в виде полинома Жегалкина
f
(
x
1
, x
2
, . . . , x
n
) =
⃝
∑
{
i
1
,i
2
,...,i
s
}⊆{
1
,
2
,...,n
}
a
i
1
i
2
... i
s
x
i
1
x
i
2
. . . x
i
s
.
Алгоритм построения ПЖ методом неопределенных коэффициентов.
– построить таблицу истинности данной функции
f
;
– записать общий вид полинома Жегалкина (см. (6.3));
– исходя из того, что данная функция и её ПЖ принима-
ют одинаковые значения на всевозможных наборах перемен-
ных, в них входящих, составим систему уравнений для коэф-
фициентов
a
0
, a
1
, a
2
, . . . , a
12
...n
. В случае трех переменных имеем:
a
0
=
f
(0
,
0
,
0)
a
0
⊕
a
1
=
f
(1
,
0
,
0)
a
0
⊕
a
2
=
f
(0
,
1
,
0)
a
0
⊕
a
3
=
f
(0
,
0
,
1)
a
0
⊕
a
1
⊕
a
2
⊕
a
12
=
f
(1
,
1
,
0)
a
0
⊕
a
1
⊕
a
3
⊕
a
13
=
f
(1
,
0
,
1)
a
0
⊕
a
2
⊕
a
3
⊕
a
23
=
f
(0
,
1
,
1)
a
0
⊕
a
1
⊕
a
2
⊕
a
3
⊕
a
12
⊕
a
13
⊕
a
23
⊕
a
123
=
f
(1
,
1
,
1)
Решаем
эту
систему
"сверху
вниз";
найденные
коэффициенты
a
0
, a
1
, a
2
, . . . , a
123
подставляем в формулу (6.3) и получаем ПЖ за-
данной функции
f
.
Алгоритм построения ПЖ методом эквивалентных преобразований.
Этот
метод
применяется
в
том
случае,
когда
функция
f
(
x
1
, x
2
, . . . , x
n
)
задана в виде формулы алгебры логики.
– предварительно выразим данную функцию через
∨
,
∧
,
¬
при помо-
щи равносильностей (4.5)-(4.11);
– выразим
∨
через
∧
и
¬
:
x
∨
y
= ¯
x
∧
¯
y
;
– в полученном выражении проведем преобразования, выразив опера-
цию
¬
через
⊕
:
¯
u
=
u
⊕
1;
– раскроем скобки в полученном выражении:
w
(
u
⊕
v
) =
wu
⊕
wv
;