Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод Квайна





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

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

1) соотношение неполного склеивания

, где и - две конъюнкции, а F - любое элементарное произведение;

2) соотношение поглощения

.

Справедливость обоих соотношений легко проверяется. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью. Для доказательства достаточно показать, что произвольная простая импликанта р = xi1xi2 ... xin может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания)

по всем недостающим переменным xik, ..., xim исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f, поскольку р - ее импликанта.

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

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

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

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



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

fСДНФ= V (1,2,5,6,7)=x1x2x3+ x1x2x3+ x1x2x3+ x1x2x3+ x1x2x3.

1 2 3 4 5

Выполним операцию склеивания:

1 – 3 (x1) x2x3 1

2 – 4 (x1) x2x3 2

3 – 5 (x2) x1x3 3

4 – 5 (x3) x1x2 4

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

fсокр СДНФ=x2x3+ x2x3+ x1x3+ x1x2 .

Для выявления обязательных простых импликант и формирования на их основе минимального покрытия строится импликантная таблица (табл. 13). В строках импликантной таблицы записываются простые импликанты, а в столбцах − конституенты единицы. Звездочка ставится, если простая импли-канта покрывает конституенту.

Таблица 13

  x1x2x3 X1x2x3 x1x2x3 x1x2x3 x1x2x3  
x2x3 *   *      
x2x3   *   *    
  x1x3     *   *  
  x1x2       * *  

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





Дата добавления: 2014-12-26; Просмотров: 260; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:

  1. A. Матеріали методичного забезпечення для основного етапу заняття
  2. BTL–ATL методи міжнародної маркетингової комунікації: сутність, особливості та сфери застосування.
  3. Compare Means - простые параметрические методы сравнения средних.
  4. I. МЕТОДИКА ИССЛЕДОВАНИЙ В СОЦИАЛЬНОЙ РАБОТЕ
  5. I. Методические рекомендации (материалы) для преподавателя
  6. I. Методы организации и осуществления учебно-познавательной деятельности
  7. I.2. Философский уровень методологического анализа педагогических конфликтов
  8. I.3. Общенаучный уровень методологического анализа педагогических конфликтов
  9. I.4. Конкретно-научный уровень методологического анализа педагогических конфликтов
  10. I.5. Методико-технологический уровень анализа педагогических конфликтов
  11. II) Вероятностные методы расчета надежности систем.
  12. II. Методические основы определения рыночной стоимости интеллектуальной собственности.

studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.021 сек.