Контрольная работа: Булевы функции

Линейными являются булевы функции из табл. 6 - f0, f3 , f5 и т. д.

Прежде чем ввести понятие класса монотонных булевых функций, дадим следующее определение.

Определение. Двоичный набор не меньше двоичного набора , (т.е. ), если для каждой пары справедливо соотношение .

Так, набор 1011 ≥1010. Вместе с тем наборы 1011 и 0100 несравнимы в том смысле, что для них не выполняется ни соотношение , ни .

Определение. Булева функция f(x1,x2,...,xn) называется монотонной, если для любых двух наборов и таких, что имеет место неравенство ff()

Монотонными являются булевы функции f0, f1,f3 , f5 (из табл. 6) и т.д.

Приведем без доказательства две формулировки теоремы о функциональной полноте.

Теорема. Для того чтобы система Sбулевых функций была функционально полной, необходимо и достаточно, чтобы эта система содержала хотя бы одну булеву функцию, не сохраняющую константу 0, хотя бы одну булеву функцию, не сохраняющую константу 1, хотя бы одну несамодвойственную булеву функцию, хотя бы одну нелинейную булеву функцию и хотя бы одну немонотонную булеву функцию.

Система булевых функций является функционально полной тогда и только тогда, когда она целиком не содержится ни в одном из предполных классов. При помощи функционально полной системы можно реализовать булеву функцию любой степени сложности.

Рассмотрим примеры ФПСБФ. К таким ФПСБФ, наиболее распространенным в практике построения цифровых автоматов, следует отнести: (, НЕ); (,НЕ); (V, НЕ); (, НЕ), (,1); где символами V, , , НЕ, 1 обозначены булевы функции: «дизъюнкция», «конъюнкция», «сумма по mod2», «отрицание», «константа 1», соответственно.

7.Минимизация булевых функций

При проектировании цифровых автоматов широко используются методы минимизации булевых функций, позволяющие получать рекомендации для построения экономичных схем цифровых автоматов. Общая задача минимизации булевых функций может быть сформулирована следующим образом: найти аналитическое выражение заданной булевой функции в форме, содержащей минимально возможное число букв. Следует отметить, что в общей постановке данная задача пока не решена, однако достаточно хорошо исследована в классе дизъюнктивно-конъюнктивных нормальных форм.

Определение. Элементарной конъюнкцией называется конъюнкция конечного числа различных между собой булевых переменных, каждая из которых может иметь или не иметь отрицания.

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Определение. Минимальной дизъюнктивной нормальной формой булевой функции называется ДНФ, содержащая наименьшее число букв (по отношению ко всем другим ДНФ, представляющим заданную булеву функцию). Определение. Булева функция g(x1,x2,...,xn) называется импликантой булевой функции f1(x1,x2,...,xn), если для любого набора переменных, на котором g = 1, справедливо f = 1. Пример. Булева функция fзадана таблицей 8. Там же приведены все ее импликанты. При записи функции и ее импликант в СДНФ имеем

f= ÚÚ

g1=

g2=

g3=V=

g4=

g5=vv=

g6=vv

g7=ÚÚ

Определение. Импликанта gбулевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой функции f.

Из примера видно, что импликанты g3 и g5 являются простыми импликантами функции f. Другие импликанты не являются простыми, так как их части являются импликантами функции f, например g3 является частью g1. Приведем без доказательства два утверждения, полезные при получении минимальной ДНФ.

1. Дизъюнкция любого числа импликант булевой функции f также является импликантой этой функции.

2. Любая булева функция f эквивалентна дизъюнкции всех своих простых импликант. Такая форма представления булевой функции называется сокращенной ДНФ.

Перебор всех возможных импликант для булевой функции fиз рассмотренного примера дает возможность убедиться, что простых импликант всего две: g3 и g5. Следовательно, сокращенная ДНФ функции fимеет вид:

f= g3 Vg5 =V

Как видно из табл. 6.8., импликанты g3 и g5 в совокупности покрывают своими единицами все единицы функции f. Получение сокращенных ДНФ является первым этапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращенную ДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая эквивалентности исходной функции. Такие простые импликанты назовем лишними. Исключение лишних простых импликант из сокращенных ДНФ — второй этап минимизации.