Днф минимальная: Недопустимое название — Циклопедия

Сокращенная и тупиковая ДНФ — Студопедия

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

Дизъюнктивная нормальная форма называется минимальной, если она включает минимальное число символов по сравнению со всеми другими эквивалентами ей дизъюнктивными нормальными формами.

Заметим, что если некоторый символ в формуле, скажем , встречается, например, два раза, то при подсчете числа символов в формуле он учитывается два раза.

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

Существует тривиальный алгоритм построения минимальной ДНФ для произвольной булевой функции .

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

Число различных ДНФ, составленных из переменных , равно .

Прежде чем доказать данное утверждение, приведем следующее определение.

Конъюнкция называется элементарной, если при .

Число r называется рангом элементарной конъюнкции. В случае r = 0 конъюнкция называется пустой и полагается равной 1.

Так как каждая из n переменных  либо не входит в элементарную, либо входит в нее с отрицанием, или без отрицания, то число элементарных конъюнкций, составленных из  равно . Ясно, что число различных ДНФ, составленных из переменной

, равно числу подмножеств множества, из элементов, т. е. .

Рассмотрим геометрическую интерпретацию задачи минимизации булевых функций.

Обозначим через множество всех точек , где . Ясно, что – множество всех вершин единичного n-мерного куба.

Сопоставим каждой булевой функции подмножество из , определенное следующим образом:

 

Например, функции, заданной следующей таблицей истинности:

x	y	z

соответствует подмножество

вершин трехмерного единичного куба

Данное соответствие является взаимно однозначным и обладает следующими свойствами:

1) булевой функции соответствует подмножество ;

2) булевой функции соответствует подмножество ;

3) булевой функции соответствует подмножество .

Докажем свойство 2. Пусть

Отсюда .

Тогда .

А это значит, что .

Отсюда .

Пусть ДНФ, где – элементарные конъюнкции. Подмножество называется интервалом r-го ранга, если оно соответствует элементарной конъюнкции К r-го ранга. Как показано выше, . Итак, с каждой ДНФ функции f связано покрытие такими интервалами , что .

Пусть – ранг интервала . Тогда совпадает с числом букв в ДНФ функции .

Теперь ясно, что задача построения минимальной ДНФ сводится к отысканию такого покрытия подмножества интервалами , чтобы число было наименьшим.

Интервал , содержащий , называется максимальным для булевой функции, если не существует интервала , такого, что .

Заметим, что соотношение выполняется тогда и только тогда, когда элементарная конъюнкция получается из элементарной конъюнкции К путем вычеркивания непустого числа сомножителей.

Очевидно, что каждый интервал из содержится в некотором максимальном интервале. Если – список всех максимальных интервалов подмножества , то нетрудно видеть, что .

ДНФ булевой функции f, соответствующая покрытию

подмножества всеми максимальными интервалами, называется сокра

щенной ДНФ функции f.

Ясно, что сокращенная ДНФ для любой булевой функции f определяется однозначно.

Пример 1. Пусть . Обозначим , , . Найдем соответствующие этим конъюнкциям интервалы , , .

Изобразим эти интервалы

Очевидно, что и – все максимальные интервалы. Интервал не является максимальным, ибо . Следовательно, покрытию подмножества соответствует сокращенная ДНФ функции , равная .

Данный геометрический подход дает и метод построения сокращенной

ДНФ.

Теперь рассмотрим аналитический метод построения сокращенной ДНФ – метод Блейка. Этот метод основан на следующей теореме.

Теорема 1. Если в произвольной ДНФ булевой функции f произвести все возможные обобщения склеивания и устранить затем все элементарные поглощения, то в результате получится сокращенная ДНФ функции f.

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

Пример 2. Найти сокращенную ДНФ для функции .

Применяя правило обобщенного склеивания, получаем: , а затем правило поглощения и находим сокращенную ДНФ: .

Рассмотрим еще один метод построения сокращенной ДНФ – метод Нельсона. Этот метод основан на следующей теореме.

Теорема 2. Если в произвольной КНФ булевой функции раскрыть все скобки в соответствии с дистрибутивным законом и устранить все элементарные поглощения, то в результате получится сокращенная ДНФ этой функции.

Пример 3. Найти сокращенную ДНФ для функции

.

После раскрытия скобок с помощью дистрибутивного закона, получаем:

.

Так как , , то имеем:

.

Далее, применяя правило поглощения, получаем сокращенную ДНФ:

.

Рассмотрим табличный метод построения сокращенной ДНФ. Этот метод основан на составлении прямоугольной таблицы (минимизирующей карты).

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

z x y

x4x3x1 x2
0 0
0 1
1 1
1 0

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

Пример 4. Найти сокращенную ДНФ для функции, заданной следующей таблицей.

x4x3x1 x2
0 0
0 1
1 1
1 0

В данной таблице объединены клетки в максимальные интервалы

.

Этим интервалам соответствуют элементарные конъюнкции

, , , , .

Следовательно, сокращенная ДНФ для данной функции имеет вид:

.

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

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

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

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

Теорема 4. Сокращенная ДНФ монотонной булевой функции не содержит отрицаний переменных и является минимальной ДНФ этой функции.

Пусть К – элементарная конъюнкция, входящая в сокращенную ДНФ. Предположим, что К содержит отрицание переменных. Обозначим через произведение всех переменных, входящих в К без отрицания. Пусть – набор переменных, в которых всем переменным, входящим в , приписано значение 1, а всем остальным – значение 0. Ясно, что при этом наборе значение функции равно 1. Элементарная конъюнкция обращается в 1 при всех наборах . Очевидно, что при этих наборах значение функции также равно 1. Следовательно, .

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

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

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

элементарная конъюнкция поглощается дизъюнкцией остальных элементарных конъюнкций, т.е. .

Ввиду этого введем следующее определение.

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

Теорема 5. Всякая минимальная ДНФ является тупиковой.

Доказательство этого утверждения следует из того, что покрытие, соответствующее минимальной ДНФ, является неприводимым.

Заметим, что булева функция может обладать несколькими различными минимальными ДНФ. Существуют также тупиковые ДНФ, не являющиеся минимальными ДНФ. Соответствующие примеры будут разобраны ниже.

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

1. Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2. Строятся все тупиковые ДНФ.

3. Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

Рассмотрим алгоритм построения всех тупиковых ДНФ.

Суть данного алгоритма состоит в следующем:

1) для булевой функции строим сокращенную ДНФ;

2) для каждой вершины из выделяем в сокращенной ДНФ функции f все такие элементарные конъюнкции , что ;

3) составляем выражение вида

(6. 1)

4) применяем к выражению вида (6.1) законы дистрибутивности и поглощения. В результате получаем .

Теперь каждая ДНФ является тупиковой ДНФ функции .

Рассмотрим работу данного алгоритма на следующем примере.

Пример 5. Рассмотрим булеву функцию, заданную следующей таблицей:

x	y	z

Найдем сокращенную ДНФ данной функции по методу Нельсона. Для этого составим КНФ данной функции .

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

.

Обозначим , , , , , .

Составляем выражение (6.1)

.

Преобразуем данное выражение к виду

= = .

Таким образом, имеет шесть тупиковых ДНФ:

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

Две из них и являются минимальными.

НОУ ИНТУИТ | Лекция | Минимизация логических функций

< Лекция 10 || Лекция 3: 12345678910111213

Аннотация: Цель лекции: познакомить студента с основными методами минимизации логических функций: методом Квайна – Мак-Класки, методом минимизирующих карт. Ключевые слова: импликанта, простая импликанта, сокращенная нормальная форма, тупиковая нормальная форма.

Минимизация логических функций

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

Понятие «упрощение» требует определенных договоренностей, что под этим будет пониматься. Упрощение можно рассматривать с точки зрения числа переменных в получаемоq эквивалентной функции, уменьшения количества отрицаний в результирующем выражении, более простой схемотехнической реализации при переводе получающейся ФАЛ на уровень интегральных микросхем и так далее.

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

Методы минимизации можно разделить на несколько типов:

1. Метод непосредственных преобразований логических функций.
2. Метод неопределенных коэффициентов.

3. Аналитические методы (метод Квайна1^{1Квайн, Уиллард Ван Орман — американский философ, логик и математик}, метод Квайна – Мак-Класки).

4. Метод минимизирующих карт (карты Карно, диаграммы Вейча).

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

В то же время, иллюстрировать соответствующие положения будем как на примерах дизъюнктивны, так и конъюнктивных форм.

Если некоторая логическая функция равна нулю на тех же наборах, на которых равняется нулю другая функция f, то говорят, что функция входит в функцию f. Другими словами, функция входит в функцию f тогда, когда она накрывает нулями все нули функции f, а единицы функции f могут быть накрыты как нулями, так и единицами функции .

Очевидно, что ФАЛ «Константа ноль» входит во все функции, а в ФАЛ «Константу единица» входят все функции.

Функцию , входящую в данную функцию f, называют ее импликантой.

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

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

Примеры этих определений показаны в Табл. 3.1.

Таблица 3.1.

x	y	z	f(x,y,z)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	1	0	0	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	0	0	1	0
1	0	1	0	0	0	1	1
1	1	0	1	0	1	1	0
1	1	1	1	1	1	1	1
				Импликанта ф-ии f(x,y,z)	Простая импликанта	Неимпликанта	Неимпликанта

Дальше >>

< Лекция 10 || Лекция 3: 12345678910111213

cc.

complexity theory — Длина минимального логического выражения DNF

спросил 10 лет, 3 месяца назад

Изменено 10 лет, 3 месяца назад

Просмотрено 1к раз

$\begingroup$

Рассмотрим дизъюнктивное логическое выражение нормальной формы от $n$ переменных. Какова верхняя граница количества терминов в минимальном эквивалентном выражении ДНФ? То есть, если задано произвольное выражение ДНФ для переменных $n$, после исключения избыточных членов, какой длины оно гарантированно будет меньше (сколько $\vee$)? 9{n-1}$.

$\endgroup$

0

Зарегистрируйтесь или войдите в систему

Зарегистрируйтесь с помощью Google

Зарегистрироваться через Facebook

Зарегистрируйтесь, используя электронную почту и пароль

Опубликовать как гость

Электронная почта

Требуется, но никогда не отображается

Опубликовать как гость

Электронная почта

Требуется, но не отображается

Нажимая «Опубликовать свой ответ», вы соглашаетесь с нашими условиями обслуживания, политикой конфиденциальности и политикой использования файлов cookie

. 9Системные требования 0000 DNF Duel | Могу ли я запустить DNF Duel

Проверить цены

Могу ли я запустить DNF Duel

Проверьте системные требования DNF Duel. Могу ли я запустить его? Проверьте свои характеристики и оцените свой игровой ПК. Лаборатория системных требований ежемесячно проводит миллионы тестов ПК для более чем 8500 игр.

Вы можете запустить его?

Вот

DNF Duel Системные требования (минимум)

• ЦП : AMD FX-4350, 4,2 ГГц / Intel Core i5-3450, 3,10 ГГц
• ОЗУ : 4 ГБ
• ОС : Windows 8/10 (требуется 64-разрядная ОС)
• ВИДЕОКАРТА : Radeon HD 6870, 1 ГБ / GeForce GTX 650 Ti, 1 ГБ
• ПИКСЕЛЬНЫЙ ШЕЙДЕР : 5,0
• ВЕРШИННЫЙ ШЕЙДЕР : 5. 0
• ЗВУКОВАЯ КАРТА : DirectX-совместимая звуковая карта или встроенный чипсет
• СВОБОДНОЕ ДИСКОВОЕ МЕСТО : 20 ГБ
• ВЫДЕЛЕННАЯ ВИДЕОПАМЯТКА : 1024 МБ

Нажмите здесь, чтобы увидеть рекомендуемый компьютер

DNF Duel Рекомендуемые требования

• ЦП : Intel Core i7-3770, 3,40 ГГц
• ОЗУ : 8 ГБ
• ОС : Windows 8/10 (требуется 64-разрядная ОС)
• ВИДЕОКАРТА : GeForce GTX 660
• ПИКСЕЛЬНЫЙ ШЕЙДЕР : 5.0
• ВЕРШИННЫЙ ШЕЙДЕР : 5. 0
• ЗВУКОВАЯ КАРТА : DirectX-совместимая звуковая карта или встроенный чипсет
• СВОБОДНОЕ ДИСКОВОЕ МЕСТО : 20 ГБ
• ВЫДЕЛЕННАЯ ВИДЕОПАМЯТКА : 2048 МБ

Последние графические карты

Щелкните здесь для получения последних версий драйверов видеокарты

Онлайн игры Тестовая задержка

Ниже приведены некоторые игровые компьютеры с изображениями, которые показывают, сколько игр будет работать на каждом из них. Каждый компьютер был протестирован на соответствие минимальным и рекомендуемым требованиям более чем 8500 новейших компьютерных игр. Щелкните здесь, чтобы просмотреть дополнительные параметры.