рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Минимизация функций в базисах И-НЕ и ИЛИ-НЕ

Реферат Курсовая Конспект

Выберите учебное заведение

Минимизация функций в базисах И-НЕ и ИЛИ-НЕ

Минимизация функций в базисах И-НЕ и ИЛИ-НЕ - раздел Образование, Понятие равносильности формул Функции " Стрелка Пирса" (Или-Не) И "штрих Шеффера" (И-Не...

Функции " стрелка Пирса" (ИЛИ-НЕ) и "штрих Шеффера" (И-НЕ) обладают функциональной полнотой; для двух переменных:

Для n переменных:

Эти соотношения позволяют свести задачу минимизации булевой функции в рассматриваемых базисах к задаче минимизации ДНФ и КНФ.

Для того, чтобы перейти от КНФ функции к выражению, представляющему функцию с помощью операции "стрелка Пирса" достаточно заменить в КНФ все операции конъюнкции и дизъюнкции операцией , сохранив скобки и отрицания на своих местах.

КНФ функции можно представить в общем виде:

где – элементарные дизъюнкции : ;

Используя операцию для n переменных, получим:

Таким образом, минимизацию функции можно осуществлять в базисе , а затем перейти к операции . Операция с помощью реализуется таким образом:

При переходе от многоместных операций к двухместным, необходимо учитывать, что функции и / не подчиняются закону ассоциативности (;). Если элементы только двухвходовые, то можно использовать следующие переходные соотношения:

Пример: рассмотрим функцию, заданную диаграммой Вейча:

МКНФ:

Переходя к двухместным операциям, получаем:

Аналогично осуществляется переход от произвольной ДНФ к выражению, содержащему только операцию "штрих Шеффера". Справедливы также переходные соотношения:

Пример:

МДНФ:

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Понятие равносильности формул

Если функция f задана формулой построенной с помощью amp и переменных то по теореме о суперпозиции двойственных функций и ввиду того... Дизъюнктивная нормальная форма и совершенная дизъюнктивная...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Минимизация функций в базисах И-НЕ и ИЛИ-НЕ

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Понятие равносильности формул
Определение 4.1. Формулы и

Булева алгебра
Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями

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

Представление произвольной логической функции в виде формулы алгебры логики
Пусть с помощью таблицы истинности задана произвольная функция алгебры логики n переменных F(x1, x2, …, xn). Расс

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

Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма
Элементарной дизъюнкцией п переменных называется дизъюнкция переменных или их отрицаний. Конъюнктивной нормальной формой (КНФ) формулы А называется р

Сокращенная ДНФ
Определение: Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами: § Любые два слагаемых различаются как минимум в двух позициях § Ни о

Минимальная ДНФ
Определение: Минимальная ДНФ — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных. Каждая миним

Метод Квайна
Метод применим к СДНФ и основывается на применении двух основных соотношений: 1. склеивание

Метод Квайна-Мак-Класки
Метод формализован на этапе нахождения простых импликант. Формализация проводится таким образом: 1) Все конституэнты "1" из СДНФ булевой функции

Метод диаграмм Вейча
Метод получает МДНФ булевой функции небольшого числа переменных. Булевы функции задаются в виде специальных диаграмм. Для функции 2-х переменных и 3-х переменных:

Минимизация частично определенных булевых функций
В реальных задачах часто бывает так, что значение булевой функции на некоторых наборах не определено и может доопределяться произвольно. Тогда доопределение функции целесообразно проводить так, что

Полные системы булевых функций
Полные системы функций Править Множество

Линейные функции
Определение. Функция называется линейной, если её полином Жегалкина не содержит конъюнкций. Общий вид линейной функции