Студопедия

КАТЕГОРИИ:


Архитектура-(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. G ГРАЖДАНСКО-ПРАВОВОЙ МЕТОД ПРАВОВОГО РЕГУЛИРОВАНИЯ Метод правового регулирования, характеризуется
  2. G ГРАЖДАНСКО-ПРАВОВОЙ МЕТОД ПРАВОВОГО РЕГУЛИРОВАНИЯ Метод правового регулирования, характеризуется
  3. I. Метод
  4. I. Моделирование как метод познания.
  5. II Методы расчета и переоценки ВВП
  6. II процессуальные и организационно-методические основания
  7. II. Метод синтаксического анализа по непосредственно составляющим.
  8. II. Три точки зрения дизайнера на вещь и методы их реализации
  9. III. Социально-психологические методы.
  10. III. Трансформационный метод.
  11. Meтoдикa oбyчeния rpaмoтe кaк cocтaвнaя чacть мeтoдики пpeпoдaвaния pyccкoro языкa. Главные объекты методики обучения грамоте
  12. REM Метод простой итерации

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

С целью упрощения этой процедуры Мак – Класки предложил алгоритм, существо которого сводится к следующему:

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

Пример:

Произведению x1x2x4 для функции, зависящей от пяти переменных нужно поставить в соответствие следующий цифровой набор: x1x2x4: 11-0-

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

f(x1x2x3x4) = x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4

запишем выражение функции в виде дизъюнкции цифровых эквивалентов:

f(x1x2x3x4) = 1101 1010 0101 1000

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

Для нашего примера это выглядит так:

Цифровые эквиваленты конституенты единицы Отметки о склейке Результат склейки Отметки о склейке
* 10-0 -
*
* -101 -
*

Итак, простые импликанты:

10-0 и -101, т.е. f(x1x2x3x4) = x1x2x4 x2x3x4

<== предыдущая лекция | следующая лекция ==>
| Метод Квайна – Мак – Класки

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


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



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


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



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.166.245.10
Генерация страницы за: 0.006 сек.