Реферат: Конспект лекций по дискретной математике
6) Принципиально существует другой способ получения ККНФ:
а) составляется КДНФ, но не для самой, а для ее отрицания.
б) берется отрицание над полученной КДНФ, которое снимается с применением закона двойственности.
_ _ _ = ------------ ----- ---- _ _
y=x1 x2 Úx1 x2 , y=y=x1 x2 Úx1 x2 =x1 x2 x1 x2 =( x1 Úx2 )(x1 Úx2 )
Разнообразие двоичных алгебр
В связи с тем, что любую сколь угодно сложную Булеву функцию можно представить в канонических формах, то есть записать ее с помощью операций отрицания, конъюнкции и дизъюнкции эта система Булевых операций обладает свойством функциональной полноты, т.е. образует так называемый базис. Естественно предположить, что система Булевых операций является не единственной, с помощью которой можно образовать некоторый базис.
В принципе любую из базовых функций можно отождествить соответствующей операцией и на основе совокупности этих операций построить двоичные алгебры, отличные от Булевой. К наиболее распространенным двоичным алгебрам относятся: алгебра Жигалкина (Å, &); алгебра Вебба (Пирса) (¯); алгебра Шеффера ( | ). В каждой из этих алгебр действуют собственные законы. Естественно существуют взаимно однозначные переходы от операций одного базиса к операциям другого.
Числовое представление Булевых функций
Для любой Булевой функции можно предложить две числовые формы, основанные на перечислении десятичных эквивалентов наборов аргументов на которых функция принимает значение единицы (нуля).
f3 (x)=
(0,2,6,7) - от этой числовой формы легко перейти к КДНФ путем замены каждого из наборов в перечислении конституенты единицы.
_ _ _ _ _ _ _ _ _ _ _
y=x1 x2 x3 Úx1 x2 x3 Úx1 x2 x3 Úx1 x2 x3 =x1 x3 (x2 Úx2 )Úx1 x2 (x3 Úx3 )=x1 x3 Úx1 x2 (ДНФ)
f3 (x)=
&(1,3,4,5)
_ _ _ _ _ _
y=(x1 Úx2 Úx3 ) (x1 Úx2 Úx3 ) (x1 Úx2 Úx3 ) (x1 Úx2 Úx3 ) (*)
Преобразование произвольной аналитической формы Булевой функции в нормальную
В Булевой алгебре в виде теоремы доказывается следующее утверждение: существует единый конструктивный подход, позволяющий преобразовать аналитическое выражение Булевой алгебры в произвольной форме к нормальной форме.
Пример:
_ _ _ _ _ _
y=f4 (x)=(x1 x2 Úx2 x3 )(x1 |x4 )=(x1 x2 Úx2 x3 )(x1 x4 )=(x1 x2 Úx2 x3 )(x1 Úx4 )=
_ _ _ _ _ _ _ _ _ _
=x1 x2 Úx1 x2 x4 Úx1 x2 x3 Úx2 x3 x4= x1 x2 Úx1 x2 x3 Úx2 x3 x4 =x1 (x2 Úx2 x3 )Úx2 x3 x4 =
_ _ _ _
=x1 (x2 Úx3 ) Úx2 x3 x4 =x1 x2 Úx1 x3 Úx2 x3 x4 (КДНФ)
Замечания:
1) В общем случае любая Булева функция может иметь несколько КДНФ, отличающихся либо количеством термов, либо количеством букв в этих термах.
2) При построении комбинационной схемы, реализующей данную функцию по ее нормальной форме предпочтительней та, которая обладает наименьшим числом термов и наименьшим количеством букв в этих термах.
3) По сравнению со схемой, построенной по ДНФ, схема, построенная по скобочной форме (*), является более предпочтительной т.к. при одном и том же числе логических элементов (И, ИЛИ) содержат меньшее число входов (9 вместо 10).
Задача преобразования нормальной формы Булевой функции в скобочной форме называют задачей фактеризации.
4) Сущность конструктивного подхода при получении ДНФ состоит в следуюшем:
а) преобразование операций не-Булевого базиса к операциям Булевого базиса (см. последние строки таблицы)