Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Алгоритм построения сокращенной ДНФ с помощью КНФ

Читайте также:
  1. II. Системы, развитие которых можно представить с помощью Универсальной Схемы Эволюции
  2. III. Произвести анализ риска путем построения дерева событий.
  3. III. Решение логических задач с помощью рассуждений
  4. Lt;variant>возлагается. Эта обязанность состоит в том, что обвиняемому дозволяется обратиться за юридической помощью
  5. lt;variant>Эта обязанность состоит в том, что обвиняемому дозволяется обратиться за юридической помощью
  6. Автоматизированный перевод документов с помощью программы Promt
  7. Аксиоматический способ построения теории
  8. Алгоритм RSA
  9. Алгоритм виконання часткового технологічного процесу
  10. Алгоритм выборки сообщений из очереди потока

(метод Нельсона)

Пусть f(x1, … , xn) есть некоторая функция алгебры логики. Построим для f некоторую КНФ. Осуществим далее следующие преобразования.

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

2. В полученном выражении удалим нулевые дизъюнктивные слагаемые.

3. В полученном выражении проведем все поглощения, а затем удалим дублирующие члены.

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

Для каждой элементарной дизъюнкции D в КНФ и каждой элементарной конъюнкции K в сокращенной ДНФ (сокр. ДНФ) существует некоторый множитель вида x из K, содержащийся в D, т.е.

" DÎ ДНФ " K Î сокр. ДНФ $ xa Î K (xaÎ D).

Допустим противное: в КНФ существует элементарная конъюнкция D, в сокращенной ДНФ существует элементарная конъюнкция K, для которой всякий множитель вида xa из K не входит в D. Не уменьшая общности возьмем для простоты

Положим x1 = a1, …, xk=ak, xk+1 = ck+1 ¹ ak+1, …, xr = cr ¹ ar. Тогда K(a1, …, ak) = 1, и потому f (a1, …, ak, ck+1, …, cr ) = 1. С другой стороны, D(ck+1,…, cr) = 0, и потому f (a1, …, ak, ck+1, …, cr ) = 0. Противоречие.

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

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



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

f = (1111010010101111) из примера 1 :

Сокращенная ДНФ для функции

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

Пример 4. Построить сокращенную ДНФ по заданной КНФ

После раскрытия скобок имеем:

После второго этапа получаем сокращенную ДНФ:

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

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

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

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




Дата добавления: 2014-11-13; просмотров: 52; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Алгоритм Квайна построения сокращенной ДНФ. | Построение всех тупиковых ДНФ.
lektsii.com - Лекции.Ком - 2014-2020 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты