X-PDF

Метод Квайна — Мак-Класки

Поделиться статьей

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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0).

Сверху над каждым значением функции проставлен номер набора, на котором функция это значение принимает.

Теперь по номерам наборов, восстановим те из них, на которых функция равна 1.

Это наборы (0011), (0100), (0101), (0110), (0111), (1010), (1011), (1100).

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

.

СДНФ такова

.

Конституенты и , например, можно склеить в импликанту, содержащую только три буквы, так как

.

Но гораздо удобнее склеивать не формулы, а двоичные наборы, соответствующие этим формулам. В самом деле, : одинаковые цифры остаются, а цифры 0 и 1 взаимно “уничтожают” друг друга. Ясно, что склеивать вместе можно только два набора одинаковой длины и только такие, которые различаются в одной позиции.

Рассортируем исходные 8 различных наборов длины 4 по числу единиц в них: нет единиц, одна единица,…, четыре единицы. Расположим наборы с одинаковым числом единиц в столбцы. Склейки возможны только между наборами из соседних столбцов. Соединим линиями наборы, которые можно склеить (рис.1).

Рис. 1

Выполним все 8 возможных склеек. Исчезнувшие цифры заменим черточкой. В результате склеек образуется 8 импликант — 010_ . 01_0 . _100 . 0_11 . _011 . 01_1 . 011_ . 101_.

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

Вновь рассортируем наборы по номеру места, на котором стоит черточка. Ясно, что склеивать вместе можно только те наборы, у которых совпадает положение черточки. Соединим линиями наборы, которые склеиваются (рис. 2).

Рис. 2

В итоге получилось 5 наборов — _100 . _011 . 0_11 . 01_ _ . 101_, которые далее нельзя склеить. Эти наборы соответствуют таким ипликантам единицы: .

Выпишем сокращенную ДНФ нашей функции

.

Продолжим процесс минимизации, для чего составим таблицу, которая называется таблицей Квайна (табл.1). В первой строке таблицы перечислим все восемь исходных наборов длины 4, соответствующих конституентам единицы данной функции . В первом столбце запишем 5 наборов, получившихся в результате всех возможных склеек. Эти наборы, как уже было сказано, соответствуют слагаемым сокращенной ДНФ функции . Во внутренних клетках таблицы поставим 1, если данная импликанта “содержит в себе” данную конституенту.

Представленная информация была полезной?
ДА
59.4%
НЕТ
40.6%
Проголосовало: 1133

Таблица 1

                 
_100 1         1    
_011   1            
0_11   1            
01_ _     1+ 1     1  
101_         1     1

В соответствии с построением, для каждой конституенты имеется хотя бы одна импликанта, “поглотившая” ее. При этом четыре из пяти импликант “поглотили” по две конституенты, а импликанта — четыре. Значит, в каждом столбце таблицы стоит хотя бы одна единица . в каждой строке – не менее двух единиц.

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

Начнем с определения ядра функции. Конституенту 1100 “поглотила” только импликанта _100 . конституенту 1010 — только импликанта 101_ . конституенты 0101 и 0110 “содержатся” только в импликанте 01_ _.

Ядро функции таково: . Три импликанты, составляющие ядро, “содержат в себе” 7 из 8 конституент. Не выбранной осталась конституента 0011, которая “содержится” в двух импликантах: _011 и 0_11. Чтобы получить минимальную ДНФ, нужно добавить к ядру любую из этих импликант. Следовательно, минимальных ДНФ две и можно записать

Минимальная КНФ по методу Квайна – Мак-Класки строится так же. Конституенты и импликанты нуля склеиваются в соответствии с равносильностью . Например,

или (011)&amp .(010)→(01_).

Построим минимальную КНФ нашей функции. Сначала выпишем наборы, на которых функция равна 0. Одновременно покажем, какие конституенты нуля соответствуют каждому набору (табл.2).

Таблица 2

Набор Конституента нуля Набор Конституента нуля
   
   
   
   

Осуществим склейки (рис. 3).

1101 0001

1111 1001 0010 0000

1110 1000

Рис. 3

В результате имеем 8 импликант нуля, ни одной конституенты нуля не осталось. Продолжим склеивание (рис. 4)

_001 1_01 11_1 100_

_000 00_0 111_

000_

Рис. 4

Получились 5 различных импликант нуля — _00_ . 1_01 . 11_1 . 00_0 . 111_. Дальнейшие склейки невозможны.

Составим таблицу Квайна (табл.3). В ее клетках поставим нули, если данная импликанта нуля “содержит в себе” данную конституенту нуля. В соответствии с построением, в каждом столбце таблицы строит хотя бы один 0, а в каждой строке – два (четыре) нуля.

Таблица 3

                 
_00_ 0 0   0 0      
1_01           0    
11_1           0    
00_0     0          
111_             0 0

Ядро функции – множество импликант . Только конституента “не содержится” в импликантах ядра. Ее “содержат” две импликанты , , минимальных КНФ две,

.


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
59.4%
НЕТ
40.6%
Проголосовало: 1133

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

Поделиться статьейЭтические проблемы современной науки являются чрезвычайно актуальными и значимыми. В связи с экспоненциальным ростом той силы, которая попадает в


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

Поделиться статьейВключает 30 родов, около 1000 видов. Распространение: горные и умеренные области Северного полушария . многие виды произрастают в горах


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет