Пример

f(x ₁, x ₂, x ₃ ) =.

f(x ₁, x ₂, x ₃ ) =.

x 2	Четыре единицы, находящиеся в первой и последней колонках, можно накрыть пере­мен-
x 1						­ной , а две остальные объеди­нить с едини­ца­ми, расположенными в левой нижней и правой

x ₃ верхней клетках диаграммы (склеивание по x ₃).

Данная функция имеет единственную минимальную форму, так как при любом другом способе объединения единиц количество букв в ДНФ уве­ли­чивается.

Пример. Найти минимальные ДНФ и КНФ функции

f(x ₁, x ₂, x ₃ ) = .

x 2 x 2
x 1					x 1

x ₃ x ₃

f(x ₁, x ₂, x ₃ ) = x ₁ x ₂Ú x ₁ x ₃Ú f(x ₁, x ₂, x ₃ ) = x ₁ x ₂Ú x ₃Ú

Для получения минимальной КНФ следует объединить нули пере­клю­ча­тель­ной функции: две конституенты нуля соответствуют клеткам, объе­ди­ненным пунктиром, склеиваются по x ₃ и представляются импликантой x ₁Ú, а оставшийся нуль – конституентой Ú x ₂Ú x ₃. Поэтому минимальная КНФ будет иметь вид:

f (x ₁, x ₂, x ₃) = (x ₁Ú)(Ú x ₂Ú x ₃).

Минимальная КНФ имеет меньше букв, чем минимальная ДНФ.

Пример. Найти минимальную ДНФ.

f(x ₁, x ₂, x ₃ ) =.

x 2	Единственная минимальная ДНФ имеет вид
x 1

x ₃

Пример. Найти минимальную ДНФ.

f(x ₁, x ₂, x ₃ ) = .

x 2	f(x 1, x 2, x 3 ) = x 2 x 3Ú x 1 x 3Ú x 1 x 2; f(x 1, x 2, x 3 ) = x 1 x 3Ú x 1 x 2Ú x 2 x 3;
x 1

x ₃ При других способах объединения консти­-

туент число логических слагаемых в ДНФ

будет больше трех.

Пример. Найти минимальную ДНФ функции

f(x ₁, x ₂, x ₃ ) = .

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

x ₃

Диаграмма Вейча для функции четырех аргументов представляет собой квадрат, разделенный на 16 клеток.

	Одной букве соответ­ству­ет восемь единиц, рас­по­ло­женных в соседних клет­ках; произведению, включаю­ще­му две переменные соот­ветствуют че­тыре со­сед­ние единицы; про­изведению трех пере­мен­ных – две и произ­ведению че­тырех переменных – одна еди­ница.

x 1	x 2	x 3
x 4

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

Пример.

– - это минимальная ДНФ.   x 1	x 2	x 3
x 4

Диаграмма Вейча для функции пяти аргументов имеет следующий вид:

x 1	x 2 x 5 x 5	x 3
x 4 x 4

Одной букве в этом случае соответствуют шестнадцать еди­ниц, рас­по­­ложенных в смежных клет­­­ках; произведе­ние двух букв – восемь еди­ниц, трех букв – че­тыре, четырех – две и пяти – одна единица.

Следует помнить, что для букв , x ₄, и x ₅ "соседние" клетки ока­зы­ваются разнесенными.

Аналогично строится диаграмма Вейча и для переключательных функ­ций большего числа аргументов. Однако с увеличением числа аргументов ра­бо­та с диаграммами затрудняется, т.к. теряется геометрический смысл "со­сед­них" клеток.

2.6. Второй метод получения минимальных КНФ

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

1. Записывают дизъюнкцию всех конституент единицы, которые не входят в СДНФ заданной функции.

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

2. Находят минимальные ДНФ по рассмотренным алгоритмам.

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

Для обоснования приведенного алгоритма получения минимальной КНФ доста­точно доказать два положения.

1. Дизъюнкция всех конституент единицы, не входящих в совершенную дизъюнктивную нормальную форму данной функции f (x ₁, x ₂, …, x_n) является отрицанием данной функции .

2. Преобразования по формулам де Моргана минимальной дизъ­юнк­тивной нормальной формы функции приводит к получению минимальной конъюнктивной нормальной формы функции f (x ₁, x ₂, …, x_n).

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

В общем виде:

, (*)

где n – число аргументов.

Рассмотрим некоторую ПФ, заданную в СДНФ:

, (**)

где m – число наборов, на которых ПФ равна единице.

Обозначим конституенты единицы, не входящие в последнее выра­же­ние, через , где p = 2 ⁿ – m – число наборов, на которых функция равна нулю. Тогда на основании соотношения (*)

Учитывая (**), получим

Сравнивая последнее соотношение с тождеством х ₁Ú = 1, которое можно записать в форме

,

получим

,

что и требовалось доказать.

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

Если предположить, что эта форма не является минимальной, то существует другая конъюнктивная форма, содержащая меньшее число букв. Тогда, взяв от нее отрицание и применив формулы де Моргана, получим дизъ­юнктивную форму с меньшим числом букв, чем в минимальной. Это противоречит определению минимальной формы и, следовательно, пред­по­ло­жение о том, что полученная конъюнктивная форма не является мини­мальной, не верно.

Пример 1. Найти минимальную конъюнктивную форму ПФ, заданной таблицей.

	1. Запишем дизъюнкцию кон­ституент единицы, которые соответ­ствуют набо­рам, на ко­торых функция равна нулю.

Номер набора
x 1
x 2
x 3
f (x 1, x 2, x 3)

.

2. Выполним операции склеивания и поглощения, после чего получим сокра­щен­ную ДНФ функции :

.

3. Испытывая импликанты, обнаружим, что вторую импликанту можно исключить (при x ₂ = 1, x ₃ = 0, выражение º 1), т.е. минимальная ДНФ функции имеет вид

.

Использовав формулу де Моргана, получим минимальную КНФ заданной функции

.

Пример 2. Найти минимальную конъюнктивную нормальную форму функции

.

1. Находим СДНФ:

.

2. Записав дизъюнкцию конституент единицы, не вошедших в преды­ду­щее выражение, получим СДНФ функции :

.

3. Сокращенная ДНФ имеет вид:

.

4. Находим минимальные формы функции .

Импли- канта	Конституента
				x 1 x 2 x 3
	*	*
		*	*
x 2 x 3			*		*
x 1 x 3				*	*

1) .

2) .

Воспользовавшись формулой де Моргана получим две мини­маль­ные КНФ:

1. f (x ₁, x ₂, x ₃) = (x ₁Ú x ₃)(x ₂Ú x ₃)(x ₁Ú x ₃).

2. f (x ₁, x ₂, x ₃) = (x ₁Ú x ₃)(x ₁Ú x ₂)(x ₁Ú x ₃).

2.7. Минимизация неполностью определенных переключательных функций

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

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

x 1
x 2
x 3
f (x 1, x 2, x 3)

определена только на шести наборах. Клетки, соответствующие наборам 1,0,0; 1,1,1 остаются пустыми.

Форма представления функции f (x ₁, x ₂, x ₃) существенно зависит от вы­бо­ра ее значений на запрещенных наборах, Например, для заданной функции, выбирая ее запрещенные значения равными нулю, можно получить мини­мальную ДНФ в виде

Если значения функции на запрещенных наборах принять равными единице, то форма представления упрощается

.

Рассмотрим общую методику получения минимальных ДНФ непол­ностью определенных переключательных функций

Дата добавления: 2014-01-06