Составители:
Рубрика:
25
является базисом. Однако, этот базис не является минимальным.
Действительно, на основании формул Моргана (5)
х
1
∨х
2
= х
1
⋅
х
2
,
х
1
⋅
х
2
= х
1
∨х
2
из базиса (6) можно удалить одну из функций - дизъюнкцию или конъюнкцию,
не нарушив его полноты. Таким образом, в качестве базиса можно взять любую
из следующих систем функций:
х, х
1
∨х
2
, или х , х
1
⋅
х
2
.
Каждый из этих базисов является минимальным, так как инверсия не может
быть выражена через дизъюнкцию или конъюнкцию.
Из приведенных рассуждений следует, что существует несколько
различных базисов. Выбор того или иного базиса определяется характером
рассматриваемой задачи.
Минимальные формы функции
На практике большое значение имеет задача нахождения так называемых
минимальных форм булевой функции. В общем виде она формулируется
следующим образом. Пусть задан некоторый базис f
1
,f
2
,...,f
m
, причем, каждой
функции f
i
, поставлено в соответствие некоторое число d
i
≥0 (i=1,2, ...,m),
называемое ее
весом.
Пусть далее для данной булевой функции f найдено
выражение через функции базиса, причем, каждая функция f
i
при написании
этого выражения ровно
ν
i
раз. Тогда величину
d
f
= ν
1
d
1
+ ν
2
d
2
+ ... + ν
m
d
m
(7)
называют весом полученного выражения
функции f в заданном базисе. Задача
минимизации формы функции f состоит в нахождении такого ее выражения
через функции базиса f
1
,f
2
,...,f
m
, которое имело бы минимальный вес d
f
(такое
выражение называется
минимальной формой
функции f).
В настоящее время эта задача в общем виде не решена даже для самых
простых базисов.
Рассмотрим частный случай этой задачи, когда задан базис
f
1
=х, f
2
= х
1
⋅ х
2
, f
3
= х
1
∨х
2
, (8)
причем положим d
1
=0, d
2
=d
3
=1.
В рассматриваемом базисе всякая булева функция f может быть
представлена в виде СДНФ. Сформулируем условие минимальности СДНФ
применительно к базису (8). Для этого введем еще два понятия.
Конъюнкция переменных х
1
,х
2
,...,х
r
, называется элементарной, если
каждая из этих переменных встречается в конъюнкции не более одного раза.
При этом число r (число переменных в конъюнкции) называется
рангом
конъюнкции. СДНФ, состоящая только из элементарных конъюнкций,
получила название
нормальной дизъюнктивной формы (ДНФ).
Найдем соотношение для веса ДНФ в базисе (8) через сумму рангов r
i
ее
конъюнктивных членов.
В соответствии с формулой (7) вес d
f
булевой функции в базисе (8)
вычисляется из соотношения
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
