ДМ_Конспект

3	0	1	1							x y z
					xyz
4	1	0	0
				x y z						x y z
5	1	0	1
				x yz						x y z
6	1	1	0
					xy z					x y z
7	1	1	1		xyz
										x y z

Различных конституент единицы и нуля для функции n			переменных
f (x , x	, ..., x	) имеется столько же, сколько и интерпретаций этой функции, т.е. 2n .
1 2	n
Определение.
Совершенной конъюнктивной нормальной формой (СКНФ) функции
f (x1, x2 ,...,xn ) , содержащей n различных переменных,			называется

конъюнктивная нормальная форма, обладающая следующими свойствами: а) в ней нет двух одинаковых множителей; б) ни один множитель не содержит двух одинаковых слагаемых;

в) ни один множитель не содержит какой-нибудь переменной вместе с еѐ отрицанием;

г) каждый множитель содержит в качестве слагаемого либо переменную xi , либо еѐ отрицание xi для любого i 1, 2, ..., n .

Условия а), б), в), г) являются необходимыми и достаточными для того, чтобы ДНФ была СДНФ.

Определение.

Совершенной конъюнктивной нормальной формой (СКНФ) булевой функции называется формула, представленная в виде конъюнкции конституент нуля данной функции.

В каждом члене СКНФ представлены все переменные (либо в прямом,

либо в инверсном виде).
Всякая булева функция	f (x1 , x2 , ..., xn ) , которая не является
тождественной единицей, имеет:

несколько КНФ;

одну и только одну СКНФ (количество еѐ членов равно количеству единичных значений функции).

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

разложить булеву функцию по переменным;

перейти от табличного представления функции к алгебраическому;

преобразовать произвольную формулу алгебры логики в нормальную форму, проводя тождественные (эквивалентные) преобразования (используя законы (тождества) алгебры логики).

81

7.3 Теоремы о разложениях булевой функции по переменным

Рассмотрим теоремы о разложениях булевой функции по переменным.

Для упрощения математических выкладок введем двоичный параметр и

обозначение x			следующим образом: x, B {0, 1};
			если 0		1,	если x
	x,
x
			если 1	и	x	если x	.
x,					0,

Бинарная функция f (x, ) x представляется формулой x x x .

Теорема о дизъюнктивном разложении булевой функции f (x1 , x2 , ..., xn ) по k переменным.

Любую булеву функцию f (x1 , x2 , ..., xn ) можно представить в следующей форме

f (x1, ..., xk , xk 1, ..., xn )			x1 1 x2 2 ... xk k f (1, 2 , ..., k , xk 1, ..., xn ).
		( 1 , 2 ,..., k )
Запись	означает многократную дизъюнкцию, которая берется по
( 1 , 2 ,..., k )
всем возможным наборам значений (1, 2 , ..., k ) при любом k (1 k n) .
Следствие 1.		Дизъюнктивное разложение булевой функции

f (x1 , x2 , ..., xn ) по одной переменной.

Любую булеву функцию f (x1 , x2 , ..., xn ) можно представить в следующей

форме f (x1, x2 ,..., xn ) xi i

f (x1, x2 , ..., xi 1, i , xi 1, ..., xn ) .

1

Запись

означает, что дизъюнкция берется по всем значениям i ,

то

1

есть по 0 и по

1. Запись

f (x1, x2 , ..., xi 1, i , xi 1, ..., xn ) обозначает

значение

функции на наборе x1, x2 ,..., xn , где вместо значения переменной xi

подставлено i .

Следствие

2.

Дизъюнктивное

разложение булевой

функции

f (x1 , x2 , ..., xn ) по всем n переменным.

Любую

булеву

функцию

f (x1, x2 , ..., xn ) 0

можно

представить

в

следующей форме: f (x1, x2 ,..., xn )

x1 1 x2 2

... xn n .

( 1

, 2 ,..., k )

f ( 1 , 2 ,..., n ) 1

Запись

означает, что дизъюнкция

берется по

всем

наборам

( 1 , 2

,..., k )

f ( 1 , 2 ,..., n ) 1

значений (1, 2 , ...,n ), на которых

f (1, 2 ,..., n ) 1.

Пример.

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

f (x, y, z) xy z

по всем

переменным.

Определим

значение

функции

на

каждой

интерпретации:

f (0, 0, 0) 0 0 0 0 1 1,

f (0, 0, 1) 0 0 1 0 0 0 ,

82

f (0, 1, 0) 0 1 0 0 1 1,					f (0, 1, 1) 0 11 0 0 0 ,
f (1, 0, 0) 1 0 0 0 1 1,					f (1, 0, 1) 1 0 1 0 0 0 ,
f (1, 1, 0) 11 0 11 1,					f (1, 1, 1) 1 1 1 1 0 1.

Запишем формулу, используя следствие 2 теоремы о разложении функций:

f (x, y, z) x0 y0 z0 x0 y1z0 x1 y0 z0

x1 y1z0

x1 y1z1 x yz xyz x yz xyz xyz .

СДНФ функции является результатом дизъюнктивного разложения

функции по всем переменным.

СДНФ

функции содержит только ,, ,

следовательно, применив к СДКФ принцип двойственности, можно получить двойственное представление, которое называется конъюнктивным разложением.

Теорема

о

конъюнктивном

разложении

булевой

функции

f (x1 , x2 , ..., xn ) по k переменным.

Любую булеву функцию f (x1 , x2 , ..., xn )

можно представить в следующей

форме

f (x1, ..., xk , xk 1, ..., xn )

x1 1 x2 2

... xk k

f (1, 2 , ..., k , xk 1, ..., xn ) .

( 1 , 2 ,..., k )

Запись

означает многократную конъюнкцию, которая берется по

( 1 , 2 ,..., k )

всем возможным наборам значений (1, 2 , ..., k ) при любом k

(1 k n) .

Следствие

3.

Конъюнктивное

разложение

булевой

функции

f (x1 , x2 , ..., xn ) по одной переменной.

Любую булеву функцию f (x1 , x2 , ..., xn )

можно представить в следующей

форме f (x1, x2 ,..., xn ) xi i

f (x1, x2 , ..., xi 1, i , xi 1, ..., xn ) .

1

Запись

означает, что конъюнкция берется по всем значениям i ,

то

1

есть по 0 и по 1. Запись

f (x1, x2 , ..., xi 1, i , xi 1, ..., xn )

обозначает

значение

функции на наборе x1, x2 ,..., xn , где вместо значения переменной xi

подставлено i .

Следствие

4.

Конъюнктивное

разложение

булевой

функции

f (x1 , x2 , ..., xn ) по всем n переменным.

Любую

булеву

функцию

f (x1, x2 , ..., xn ) 1

можно

представить

в

следующей форме: f (x1 , x2 ,..., xn )

x1 1

x2 2

... xn n .

( 1

, 2

,..., k )

f ( 1 , 2 ,..., n ) 0

Запись

означает, что

конъюнкция

берется по

всем

наборам

( 1 , 2

,..., k )

f ( 1 , 2 ,..., n ) 0

значений (1, 2 , ...,n ), на которых

f (1,2 ,...,n ) 0 .

Пример.

Запишем конъюнктивное разложение функции

f (x, y, z) xy z

по всем

переменным. Определим значение функции на каждой интерпретации:

83

f (0, 0, 0) 0 0 0 0 1 1,

f (0, 0, 1) 0 0 1 0 0 0 ,

f (0, 1, 0) 0 1 0 0 1 1,

f (0, 1, 1) 0 11 0 0 0 ,

f (1, 0, 0) 1 0 0 0 1 1,

f (1, 0, 1) 1 0 1 0 0 0 ,

f (1, 1, 0) 11 0 11 1, f

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

Запишем формулу, используя следствие 4 теоремы о разложении функций

f (x, y, z) (x1 y1 z0 )(x1 y0 z0 )(x0 y1 z0 ) (x y z)(x y z)(x y z)

СКНФ функции является результатом конъюнктивного разложения функции по всем переменным.

7.4 Переход от табличного представления функции к алгебраическому представлению функции

Любая таблично заданная функция алгебры логики может быть

				n
представлена в		виде	f (x1, x2 , ..., xn ) F11 F21	... Fn1 Fi1 или	в виде
				i 1
			n
f (x1, x2 , ..., xn ) F10		F20	... Fn0 Fi1 ,
			i 1
где F1 элементарная конъюнкция ранга n (конституента единицы);
	i
i	номера наборов, на которых функция F1			равна 1, а функция F 0	равна 0;
			i	i
	n
символ обобщенной дизъюнкции;
i	1
F 0 элементарная дизъюнкция ранга n (конституента нуля);
	i
	n
символ обобщенной конъюнкции.
i	1

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

а) выделить в таблице истинности все интерпретации, на которых значение функции равно единице;

б) записать конституенты единицы, соответствующие отмеченным интерпретациям;

в) получить СДНФ функции посредством соединения операцией дизъюнкции записанных конституент единицы.

Пример.

Получим СДНФ для функции f (x1, x2 ) x1 x2 .

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

а) построим таблицу истинности функции и отметим интерпретации, на которых функция равна единице (табл. 7.2).

84

Таблица 7.2 Функция f (x1, x2 ) x1 x2 , заданная в табличном виде

x1	x2	f (x1, x2 ) x1 x2
0	0	1
0	1	1
1	0	0
1	1	1

б) запишем конституенты единицы, соответствующие отмеченным

интерпретациям: x1 x2 , x1 x2 , x1 x2 .

в) получим СДНФ функции

f (x1, x2 ) x1 x2 посредством соединения

операцией

дизъюнкции

записанных

конституент

единицы

СДНФ f (x1, x2 ) x1 x2 x1x2

x1x2

Для перехода от таблицы истинности булевой функции к СКНФ можно

воспользоваться следующим алгоритмом:

а) выделить в таблице истинности все интерпретации, на которых

значение функции равно нулю;

б)

записать конституенты

нуля,

соответствующие

отмеченным

интерпретациям; в) получить СКНФ функции посредством соединения операцией

конъюнкции записанных конституент нуля.

Пример.
Получить СКНФ для функции f (x1, x2 ) x1	x2 .
Используем алгоритм перехода от	таблицы истинности к

алгебраическому представлению функции.

а) построим таблицу истинности функции и отметим интерпретации, на которых функция равна нулю (табл. 7.3).

Таблица 7.3 Функция				f (x1, x2 ) x1 x2 , заданная в табличном виде
	x1	x2	f (x1, x2 ) x1 x2
	0	0		1
	0	1		1
	1	0		0
	1	1		1

б) запишем конституенту нуля, соответствующую отмеченной интерпретации: x1 x2 .

в) получим СКНФ функции: СДНФ f (x1, x2 ) x1 x2 .

Обратный переход от алгебраического к табличному представлению функции выполняется путем последовательной подстановки в данное алгебраическое выражение всех возможных наборов переменных, определения соответствующих значений fi для каждого i -го набора и заполнения таблиц

истинности.

85

7.5 Правила преобразования произвольной формулы алгебры логики в

нормальную форму с использованием законов булевой алгебры

Для любой формулы алгебры логики путем равносильных (тождественных) преобразований можно получить еѐ нормальную форму, причем не единственную.

Рассмотрим правила преобразования произвольной формулы алгебры логики к ДНФ (КНФ) и СДНФ (СКНФ), представленные в виде следующего алгоритма:

1.Исключить константы, используя законы действия с константами.

2.Опустить знаки отрицания непосредственно на переменные, используя законы де Моргана.

3.Используя дистрибутивный закон, раскрыть скобки (для получения

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

4. Построить конституенты единицы (нуля) введением в каждую элементарную конъюнкцию (дизъюнкцию) недостающих переменных, используя закон исключенного третьего (для получения СКНФ закон противоречия).

5. С помощью дистрибутивного закона раскрыть скобки и привести подобные (для получения СКНФ используя дистрибутивный закон привести функцию к виду конъюнкции конституент нуля и упростить формулу), используя закон идемпотентности. Полученная формула соответствует СДНФ (СКНФ) функции.

Пример.

Построим СДНФ функции f (x, y, z) xy (x( y z) yz) .

Воспользуемся правилами преобразования произвольной формулы алгебры логики к СДНФ. Опускаем отрицания на переменные, используя закон де Моргана:

xy (x( y z) yz) xy (x( y z))( yz) xy (x ( y z))(y z) xy (x ( yz))(y z).

Построим ДНФ, используя дистрибутивный закон, законы идемпотентности и противоречия:

xy (x ( yz))(y z) xy (x y yz y xz yz z) xy x y 0 xz yz

xy x y xz yz .

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

86

исключенного

третьего:

xy x y xz yz xy(z z) x y(z z) x( y y)z (x x) yz .

Используя дистрибутивный закон, раскроем скобки и приведем подобные для получения СДНФ:

xyz xyz x yz x yz xyz x yz xyz xyz xyz xyz x yz x yz xyz .

Получена СДНФ заданной функции:

f (x, y, z) xyz xy z x yz x yz xyz .

7.6 Контрольные вопросы и задания

1.На примере булевых функций опишите понятие «нормальной формы» функции.

2.Что представляет собой элементарная конъюнкция, элементарная дизъюнкция?

3.Какая формула называется дизъюнктивной нормальной формой, конъюнктивной нормальной формой?

4.Дайте определение понятиям минтерм, макстерм, конституанта единицы, конституанта нуля.

5.Что такое совершенная нормальная форма и какими свойствами она обладает?

6.Сколько имеется различных конституент единицы и нуля для функции n переменных f (x1 , x2 , ..., xn ) ?

7.Сколько ДНФ и сколько СДНФ может иметь булева функция?

8.Запишите формулы дизъюнктивного разложения булевых функций от n переменных по k (k n) переменным, по всем n переменным, по одной

переменной.

9. Запишите формулы конъюнктивного разложения булевых функций от n переменных по k (k n) переменным, по всем n переменным, по одной

переменной.

10.Опишите алгоритмы перехода от таблицы истинности булевой функции к СДНФ и СКНФ.

11.Сформулируйте правила преобразования произвольной формулы алгебры логики в нормальную форму с использованием законов булевой алгебры.

ЛЕКЦИЯ 8. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

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

минимизации.

Функция алгебры логики может быть представлена различными формулами (в частности, различными ДНФ и КНФ), а, следовательно,

87

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

Пример.

Функция

f (x, y, z) , заданная вектором f (10001111) ,

может быть

представлена в виде СДНФ F1 x y z x y z x y z x y z x y z

и реализована

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

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

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

Пример.

Функция f (x, y, z) (x | y) (z x) в булевом базисе преобразуется к

виду:

f (x, y, z) (x | y) (z x) xy (z x) (xy z x)(xy z x).

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

f (x, y, z) (x | y) (z x) ((z x) (x y)) (x y) (z x) .

Для оценки формы булевой функции, которая наиболее предпочтительна для практической реализации, обычно вводится индекс (коэффициент) простоты L(F ) , где F формула, реализующая функцию, характеризующий

«сложность» ДНФ (КНФ). Наиболее часто встречаются следующие виды коэффициентов простоты:

а) LБ (F ) число символов (букв) переменных, встречающихся в записи ДНФ (КНФ);

б) LК (F) число элементарных конъюнкций (дизъюнкций), входящих в F ; в) LИ (F ) число символов инверсий, встречающихся в записи ДНФ

(КНФ).

Пример.

Сравним две формулы F1 x y z x y z x y z x y z x y z и F2 y z x , реализующие одну функцию. Для них: LБ (F1 ) 15 и LБ (F2 ) 3, следовательно

F2 проще, чем F1 ; LК (F1 ) 5 и LК (F2 ) 2 , следовательно, F2 проще, чем F1 ; LИ (F1 ) 7 и LИ (F2 ) 2, следовательно, F2 проще, чем F1 .

88

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

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

Определение.

Импликантой некоторой функции f называется функция g , такая, что на всех интерпретациях, на которых g равна единице, f тоже равна единице.

Минтермы любого ранга, входящие в состав ДНФ функции, являются еѐ импликантами.

Определение.

Множество S , состоящее из импликант функции f , называется

покрытием (или полной системой импликант) функции f , если каждое единичное значение функции f покрывается единицей хотя бы одной

импликанты из множества S .

Пример.

Набор импликант, составляющих ДНФ функции, является еѐ покрытием. Набор всех конституент единицы функции, входящих в еѐ СДНФ, является покрытием данной функции.

Всякая элементарная конъюнкция A , входящая в состав элементарной конъюнкции B и содержащая меньше переменных, чем конъюнкция B , называется собственной частью конъюнкции B , и говорят, что конъюнкция

A покрывает конъюнкцию B .

Определение.

Простой импликантой функции f называется такая конъюнкция-

импликанта, что никакая еѐ собственная часть не является импликантой данной функции.

Множество всех простых импликант функции составляет покрытие данной функции.

Определение.

Дизъюнкция всех простых импликант функции называется еѐ

сокращенной ДНФ.

Определение.

Дизъюнктивным ядром булевой функции f называется такое множество еѐ простых импликант, которое образует покрытие f , но после

удаления импликанты теряет это свойство, то есть перестает быть полной системой импликант.

Определение.

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

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

89

единственную сокращенную ДНФ и может иметь несколько тупиковых ДНФ. В каждую из тупиковых ДНФ входят все импликанты дизъюнктивного ядра данной функции. |Тупиковые ДНФ могут иметь различную сложность и отличаться от минимальных. Среди тупиковых ДНФ всегда содержатся и минимальные ДНФ.

Определение.

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

Пример.

Пусть имеется функция f , заданная в виде СДНФ: f (x, y, z) xyz xyz x yz x yz .

Выполним операции полного склеивания следующим образом:

f (x, y, z) xyz xyz x yz x yz (xyz xyz) (xyz x yz) (x yz x yz) yz xz x y

Операцию склеивания можно выполнить другим способом: f (x, y, z) (xyz xyz) (x yz x yz) yz x y .

В обоих случаях получены тупиковые ДНФ функции f (x, y, z) . Вторая

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

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

имплицент, сокращенная КНФ, тупиковая КНФ, минимальная КНФ.

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

в аналитической форме;

в геометрической форме (задача о покрытии). Употребляются два языка: аналитический и геометрический.

Для решения данной задачи в современной теории и практике алгебры

логики существуют следующие основные подходы:

перебор (просмотр) всех возможных ДНФ и КНФ произвольной функции с целью поиска минимальной формы (первый подход);

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

Процесс перебора всех возможных ДНФ и КНФ функции является, хотя и

наиболее понятным, но достаточно трудоемким процессом. Им нельзя воспользоваться практически уже с n 3, а для n 1 и n 2 проблема является тривиальной.

90