Главная страница | Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей |
|
раздел 2. 2. элементарные булевы функции совершенные формы булевых функций алгебраическая минимизация Суперпозиция бф
Наборы логических переменных х1х2…хn, на которых БФ принимает единичные значения f(х1,х2,…,хn)=1, называют единичными наборами. Наборы логических переменных х1х2…хn, на которых БФ принимает нулевые значения f(х1,х2,…,хn)=0, называют нулевыми наборами. Конъюнкцией называется логическое произведение произвольного числа аргументов. Конъюнкция называется элементарной, если она содержит любое количество попарно различимых букв в прямой или инверсной форме. Например, конъюнкция является элементарной, а вот конъюнкция не является элементарной. Назовем рангом R элементарной конъюнкции количество входящих в нее букв. Две конъюнкции назовем соседними, если они зависят от одних и тех же аргументов, имеют одинаковый ранг и отличаются знаком инверсии только одного аргумента (например, ). Длиной функции L назовем сумму рангов всех входящих в функцию конъюнкций (т. е. количество букв в формуле). Дизъюнктивной нормальной формой (ДНФ) БФ назовем дизъюнкцию (логическую сумму) конечного множества попарно различимых элементарных конъюнкций: Функция ДНФ не является. Конституентой единицы или минтермом назовем элементарную конъюнкцию, содержащую все аргументы, от которых зависит БФ. Совершенной дизъюнктивной нормальной формой БФ (СДНФ) назовем ДНФ, каждый член которой является конституентой единицы: Дизъюнкцией называется логическая сумма произвольного числа аргументов. Дизъюнкция называется элементарной, если она содержит любое количество попарно различимых букв в прямой или инверсной форме. Например, дизъюнкция является элементарной, а вот дизъюнкция не является элементарной. Назовем рангом R элементарной дизъюнкции количество входящих в нее букв. Две дизъюнкции назовем соседними, если они зависят от одних и тех же аргументов, имеют одинаковый ранг и отличаются знаком инверсии только одного аргумента (например, ). Длиной функции L назовем сумму рангов всех входящих в функцию дизъюнкций, т. е. количество букв в формуле. Конъюнктивной нормальной формой (КНФ) БФ назовем конъюнкцию (логическое произведение) конечного множества попарно различимых элементарных дизъюнкций: Конституентой нуля или макстермом назовем элементарную дизъюнкцию, содержащую все аргументы, от которых зависит БФ. Совершенной конъюнктивной нормальной формой БФ (СКНФ) назовем КНФ, каждый член которой является конституентой нуля: 2.4. Переход от табличного способа задания БФ к аналитическому Пусть БФ f1 и f2 заданы табл. 2.2: Таблица 2.2 Таблица истинности функций f1,f2,f3
При переходе от табличного способа задания БФ к аналитическому в форме ДНФ можно получить только совершенные формы. Для получения СДНФ БФ записывается как логическая сумма конституент единицы. Для этого используется следующий алгоритм:
. БФ f2 из табл. 2.2 представим в КНФ. Из таблицы можно получить только СКНФ. БФ записывается как логическое произведение конституент нуля. Для получения аналитического выражения БФ:
. Следует уяснить, что СДНФ и СКНФ это просто разные формы БФ, и одна и та же БФ может быть записана в любой из них. Например, пусть БФ Z задана табл. 2.3. Таблица 2.3 Таблица истинности функции Z
Запишем эту функцию в обеих формах: В формуле СКНФ раскроем скобки и применим закон поглощения: т. е. совпадает с СДНФ. Если функция задана алгебраически, то может быть восстановлена таблица истинности. Например, задана функция Р: Вычисляются значения функции для всех наборов переменных: Вычисленные значения функции заносятся в таблицу (табл. 2.4). Таблица 2.4 Восстановленная таблица истинности функции Р
По табл. 2.4 можно записать СДНФ: Для функции R, заданной в конъюнктивной форме , вычислены значения функции, которые занесены в табл. 2.5: Таблица 2.5 Восстановленная таблица истинности функции R
2.5. Применение законов склеивания для минимизации булевых функций Две БФ называются эквивалентными, если они принимают одинаковые значения на одних и тех же наборах аргументов. Одна и та же БФ может быть записана разными формулами. Из нескольких формул предпочтительней та, которая имеет наименьшую длину. Для получения более короткой формулы применяются эквивалентные преобразования с использованием правил склеивания и поглощения. Процедура получения минимальной формулы БФ называется минимизацией. Алгоритм минимизации БФ, заданной в форме СДНФ, следующий:
Исходя из этого для БФ f1 из табл. 2.2 :
БФ f1 запишется как: , т. е. очевидно, что полученная ДНФ короче, чем исходная СДНФ. Алгоритм минимизации БФ, заданной в форме СКНФ:
Минимизация БФ f2 из табл. 2.2
;
, т. е. очевидно, что полученная КНФ короче, чем исходная СКНФ. Для f2 операции склеивания можно выполнить и по-другому:
. Оба варианта функции f2 имеют одинаковую длину L=6, поэтому они равноценны. 2.6. Применение законов поглощения для минимизации булевых функций Применение законов поглощения также позволяет минимизировать БФ. Пусть БФ задана в форме ДНФ: Применим закон склеивания к первой и второй конъюнкции: В соответствии с законом поглощения (переменная х1 поглощает все конъюнкции, содержащие х1): Для функции P: 2.7. Понятие фиктивной переменной Любая переменная Хк в БФ называется несущественной, или фиктивной, если выполняется условие: , т. е. переменная изменяет свое значение на любом наборе остальных аргументов, но это не сказывается на значении БФ. Фактически, такая БФ, зависит от n -1 аргументов. В таблице истинности столбец несущественной переменной можно удалить. Например, БФ f3 (табл. 2.2) имеет следующую СКНФ: . После выполнения склеивания по х1 она будет иметь вид: , т. е. f3 не зависит от переменной х1. Иногда, выгодно, наоборот, вносить в БФ несущественную переменную, при этом БФ может стать зависимой от любого числа аргументов. Например, функция В задана в ДНФ и зависит от переменных х1 и х2: Умножая каждую конъюнкцию на сумму той переменной и ее инверсии, которые отсутствуют в данной конъюнкции, можно получить СДНФ функции В от переменных х1,х2,х3: Такие же преобразования можно выполнить и с БФ, заданной в КНФ. Например, КНФ функции сначала преобразована в СКНФ, а затем в нее добавлена переменная х3: Добавление фиктивной переменной может привести к упрощению функции. Например, в функции G упрощение, на первый взгляд, невозможно: Однако введем в первую конъюнкцию недостающую переменную х1 и проведем склеивание: перейти в каталог файлов Образовательный портал
Как узнать результаты егэ
Стихи про летний лагерь
3агадки для детей | |