ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1351
Скачиваний: 1
33
§12.
Полнота и замкнутые классы. Критерий Поста
Система (множество булевых функций) называется полной в Б , ес-
ли её замыкание совпадает с множеством всех булевых функций.
Система булевых функций называется базисом, если она полна и
любая её подсистема не является полной в Б .
Теорема (критерий Поста).
Для того, чтобы система булевых
функций
F
=
{
f
1
, f
2
, . . .
}
была полной в Б , необходимо и достаточно,
чтобы она целиком не содержалась ни в одном из замкнутых классов
T
0
, T
1
, S, M, L
.
Задача 1.
Дана булева функция
f
. Исследовать её принадлеж-
ность каждому из классов
T
0
, T
1
, S, M, L
.
Алгоритм решения задачи о принадлежности функции
f
классам
T
0
, T
1
, S, M, L
:
– построить таблицу истинности функции
f
;
– если значение функции в первой строке таблицы равно 0
(
f
(0
,
0
, . . . ,
0) = 0
), то
f
∈
T
0
, иначе
f
∈
/ T
0
;
– если значение функции в последней строке таблицы равно 1
(
f
(1
,
1
, . . . ,
1) = 1
), то
f
∈
T
1
, иначе
f
∈
/ T
1
;
– если
в
таблице
истинности
можно
указать
пару
проти-
воположных
наборов
(
α
1
, α
2
, . . . , α
n
)
и
( ¯
α
1
,
¯
α
2
, . . . ,
¯
α
n
)
,
на
которых
функция
f
принимает
одинаковые
значения
(
f
(
α
1
, α
2
, . . . , α
n
) =
f
( ¯
α
1
,
¯
α
2
, . . . ,
¯
α
n
)
), то
f
∈
/ S
, иначе
f
∈
S
;
– если в таблице истинности можно указать наборы
(
α
1
, α
2
, . . . , α
n
)
и
(
β
1
, β
2
, . . . , β
n
)
, такие, что
α
1
≤
β
1
, α
2
≤
β
2
, . . . , α
n
≤
β
n
и
f
(
α
1
, α
2
, . . . , α
n
) = 1
, f
(
β
1
, β
2
, . . . , β
n
) = 0
, то
f
∈
/ M
, иначе
f
∈
M
;
– для проверки принадлежности функции
f
классу
L
нужно по-
строить её полином Жегалкина; если степень ПЖ не превосходит 1
(
a
12
=
a
13
=
. . .
=
a
12
...n
=0
), то
f
∈
L
, иначе
f
∈
/ L
.
Задача 2.
Дана система булевых функций
F
=
{
f
1
, f
2
, . . .
}
. Иссле-
довать полноту этой системы функций и, если она полна, выделить из
неё базис.
Алгоритм исследования полноты системы булевых функций:
– построить таблицу, число строк в которой равно числу функций в
F
, а число столбцов равно 5 по числу основных замкнутых классов;
34
– проверить принадлежность функции
f
1
классу
T
0
и поставить на
пересечении соответствующих
f
1
и
T
0
строки и столбца знак "
+
",
если
f
1
∈
T
0
, и знак "
−
", если
f
1
∈
/ T
0
;
– если на предыдущем шаге в результате исследования получен знак
"
+
", то продолжить исследование по "вертикали"проверить при-
надлежность функции
f
2
классу
T
0
и т.д., если же на предыдущем
шаге получен знак "
−
", то продолжать исследования по горизон-
тали – проверить принадлежность функции
f
1
классу
T
1
и т.д.;
– исследование заканчивается, если выполнено одно из двух условий:
1) в каждом столбе таблицы стоит по крайней мере один знак "
−
",
либо 2) в одном из столбцов таблицы стоят знаки "
+
".
В первом случае система функций
F
целиком не содержится ни в
одном из из классов и, согласно критерию Поста, является полной, во
втором случае она целиком содержится в одном из классов и потому не
является полной.
Для выделения базиса из полной системы функций нужно упорядо-
чить по числу функций множество подсистем системы
F
:
{
f
1
}
,
{
f
2
}
, . . . ,
{
f
1
, f
2
}
, . . .
(12
.
1)
и, начиная с первой, исследовать их на полноту. Первая из полных в
последовательности (12.1) систем будем базисом на множестве всех бу-
левых функций.
Пример 1.
Для функции
f
= (
x
∧
¯
y
)
→
(
x
⊕
z
)
определить её
принадлежность каждому из классов
T
0
, T
1
, S, M, L
.
Построим таблицу истинности:
x y z
¯
y x
∧
¯
y x
⊕
z
(
x
∧
¯
y
)
→
(
x
⊕
z
)
0
0 0 1
0
0
1
0
0 1 1
0
1
1
0
1 0 0
0
0
1
0
1 1 0
0
1
1
1
0 0 1
1
1
1
1
0 1 1
1
0
0
1
1 0 0
0
1
1
1
1 1 0
0
0
1
Из анализа построенной таблицы следует:
f
∈
/ T
0
,
так как
f
(0
,
0
,
0) = 1;
f
∈
T
1
,
так как
f
(1
,
1
,
1) = 1;
35
f
∈
/ S,
так как
f
(1
,
1
,
0) =
f
(0
,
0
,
1);
f
∈
/ M,
так как
f
(0
,
0
,
0) = 1
, f
(1
,
0
,
1) = 0
.
Для определения принадлежности функции
f
классу
L
, построим
ПЖ. Система уравнений для неопределенных коэффициентов имеет вид:
a
0
=
1
a
0
⊕
a
3
=
1
a
0
⊕
a
2
=
1
a
0
⊕
a
1
=
1
a
0
⊕
a
2
⊕
a
3
⊕
a
23
=
1
a
0
⊕
a
1
⊕
a
2
⊕
a
12
=
1
a
0
⊕
a
1
⊕
a
3
⊕
a
13
=
0
a
0
⊕
a
1
⊕
a
2
⊕
a
3
⊕
a
12
⊕
a
13
⊕
a
23
⊕
a
123
= 1,
откуда находим:
a
1
=
a
2
=
a
3
=
a
12
=
a
23
= 0
, a
0
=
a
13
=
a
123
= 1
;
ПЖ
=
xyz
⊕
xz
⊕
1
. Следовательно,
f
∈
/ L
.
Пример 2.
Исследовать полноту системы функций
F
=
{
¯
x
⊕
y
;
x
∧
yz
;
y
→
¯
x
}
и, если она полна, выделить базис.
В соответствии с сформулированным выше алгоритмом решение со-
стоит из следующих шагов:
f
1
(0
,
0) = ¯
0
⊕
0 = 1
,
⇒
f
1
∈
/ T
0
;
f
1
(1
,
1) = ¯
1
⊕
1 = 1
,
⇒
f
1
∈
T
1
;
f
2
(1
,
1) = 1
∧
1 = 1
,
⇒
f
2
∈
T
1
;
f
3
(1
,
1) = 1
→
¯
1 = 0
,
⇒
f
3
∈
/ T
1
.
Построим таблицу истинности функции
f
3
:
x y
¯
x y
→
¯
x
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
0
Из таблицы следует
f
3
(0
,
1) =
f
3
(1
,
0)
, поэтому функция
f
3
∈
/ S
.
Далее
f
3
(0
,
0) = 1
,
f
3
(1
,
1) = 0
, поэтому функция
f
3
∈
/ M
.
Построим полином Жегалкина для функции
f
3
:
f
3
(
x, y
) =
y
→
¯
x
= ¯
y
∨
¯
x
= (
x
∧
y
) =
xy
⊕
1 =
ПЖ
,
откуда следует
f
3
∈
/ L
, так как степень полинома Жегалкина равна 2.
По результатам исследований построим таблицу
36
Классы функций
T
0
T
1
S
M
L
f
1
= ¯
x
⊕
y
−
+
f
2
=
x
∧
yz
+
f
3
=
y
→
¯
x
− − − −
В каждом столбце таблицы стоит знак "
−
", откуда следует, что
данная система является полной. Каждая из функций
f
1
и
f
2
и обе
они вместе не могут быть базисом в Б , так как принадлежат классу
T
1
.
Функция
f
3
является базисом, так как в дополнение к проделанному
анализу
f
3
(0
,
0) = 1
и
f
3
∈
/ T
0
.
Ответ:
система
F
полная; функция
{
f
3
}
является базисом на мно-
жестве всех булевых функций.
Задачи и упражнения
12.1.
Исследовать принадлежность функции
f
классам
T
0
, T
1
, S, M, L
.
а)
f
= (
x
→
y
)
→
z
;
б)
f
= (
x
|
y
)
→
(
x
⊕
z
)
;
в)
f
=
¬
(
x
↔
y
)
↔
z
;
г)
f
= (
xy
→
¯
z
)
∨
x
;
д)
f
= (
xyz
⊕
x
)
|
z
;
е)
f
= (
x
∨
y
∨
¯
z
)
⊕
¯
x
;
ж)
f
= (
x
↔
y
)
↔
zy
.
12.2.
Исследовать полноту системы булевых функций
F
и, если она
полна, построить базис:
а)
F
=
{
(
x
⊕
y
)
∨
¯
z
;
x
↔
y
; ¯
xyz
}
;
б)
F
=
{
xy
↔
¯
z
;
x
⊕
y
⊕
z
; ¯
xy
}
;
в)
F
=
{
x
⊕
(
y
→
z
); ¯
x
∨
yz
;
xy
}
;
г)
F
=
{
(
x
|
y
)
⊕
z
;
x
→
(¯
y
→
z
);
x
↔
y
}
;
д)
F
=
{
(
x
↓
z
)
∨
¯
y
; (
x
→
y
)
→
¯
z
;
x
∨
y
}
;
е)
F
=
{
¯
x
⊕
(
y
∨
z
); (
x
|
y
)
|
¯
x
; ¯
x
↔
¯
y
}
;
ж)
F
=
{
xy
→
¯
z
;
xy
⊕
z
⊕
1; 1
}
.
37
§13. Построение минимальных и кратчайших дизъюнктивных
нормальных форм
1.
Постановка задачи.
Сднф, которая строится по таблице ис-
тинности булевой функции (см. стр. 15) зачастую оказывается весьма
сложной, так как она содержит достаточно много элементарных конъ-
юнкций и литералов. Используя метод эквивалентных преобразований,
можно из сднф построить днф, реализующую данную функцию и со-
держащую значительно меньше и элементарных конъюнкций и лите-
ралов. Так для функции
f
(
x, y, z
)
, заданной набором своих значений
(01101110)
, сднф
= ¯
x
¯
yz
∨ ∨
¯
xy
¯
z
∨
x
¯
y
¯
z
∨
x
¯
yz
∨
xy
¯
z
; после элементарных
преобразований получаем днф
= ¯
y
¯
z
∨
x
¯
y
∨
¯
yz
. Если в первой из формул
мы имеем 15 литералов и 5 элементарных конъюнкций, то во второй – 6
литералов и 3 элементарных конъюнкции.
С целью уточнения проблемы минимизации и формулировки алго-
ритмов е¨
е решения введем следующие определения.
Определение
1.
Переменная
x
i
, i
=
1
, . . . , n
, называется
фиктивной переменной булевой функции
f
(
x
1
, x
2
, . . . , x
n
)
, если значе-
ние функции не зависит от значения этой переменной, т.е. для любых
наборов значений переменных
x
1
, x
2
, . . . , x
i
−
1
, x
i
+1
, . . . , x
n
имеем
f
(
x
1
, x
2
, , x
i
−
1
,
1
, x
i
+1
, . . . , x
n
) =
f
(
x
1
, x
2
, . . . , x
i
−
1
,
1
, x
i
+1
, . . . , x
n
)
.
Wеременная
x
i
, которая не является фиктивной для функции
f
,
называется существенной переменной данной функции; в этом случае
говорят, что функция
f
существенно зависит от переменной
x
i
.
Определение 2.
Булеву функцию
g
называют импликантой бу-
левой функции
f
, если для любых наборов
(
α
6
, α
2
, . . . , α
n
)
∈
E
n
значений переменных, от которых зависят эти функциy, из равенства
g
(
α
1
, α
2
, . . . , α
n
) = 1
следует равенство
f
(
α
1
, α
2
, . . . , α
n
) = 1
, другими
словами,
N
g
⊆
N
f
(см. стр. 5 настоящего пособия).
Если сднф реализует функцию
f
, то любая е¨
е элементарная конъ-
юнкция будет импликантой
f
. Следует отметить, что если
g
1
и
g
2
им-
пликанты
f
, то их дизъюнкция также является импликантой
f
. Дей-
ствительно, если
N
g
1
⊆
N
f
и
N
g
2
⊆
N
f
, то
N
g
1
∨
g
2
⊆
N
f
. Последнее
означает, что функция
g
0
∨
g
2
– импликанта
f
.
Определение 3.
Днф называется минимальной, если она содержит
наименьшее число литералов среди всех днф, реализующих функцию
f
.
Отметим, что число литералов в днф равно сумме рангов всех е¨
е
элементарных конъюнкций.
Пример 1.
Днф
xyz
∨
x
¯
yz
∨
xy
¯
z
∨
x
¯
y
¯
z
не является минимальной,
так как е¨
е можно преобразовать к эквивалентной днф, не содержащей