2Дискретка / Метода / 3. Математическая логика

x,y,z,p	f		xyp			xy z					x z p							y z p						xz p			y z p			x y
0 0 0 0	1									1							1
0 1 0 0	1				1					1
0 1 0 1	1	1			1																						1
0 1 1 1	1	1
1 0 0 0	1																1													1
1 0 0 1	1																							1						1
1 0 1 0	1																													1
1 0 1 1	1																													1
1 1 0 1	1																							1			1

В таблице отмечены те единицы функции, которые говорят, что импликан- та точно не лишняя. Лишними можно считать, например, импликанты xy z , y z p

иy z p , тогда fтуп. ( x, y, z, p) = xyp x z p p zx yx .3

2.3.Аналитические методы нахождения МДНФ.

Метод Квайна

Дает возможность нахождения Сокр. ДНФ из СДНФ функции.

Формулы метода:

Ax Ax = Ax Ax A – неполное склеивание, AB A = A – поглощение,

где x – переменная, A и B – конъюнкции любой длины.

Алгоритм метода.

Шаг 1. Положить «формулу» равной СДНФ функции. Шаг 2. Положить n равным числу переменных функции.

Шаг 3. Провести все возможные операции неполного склеивания для входя- щих в «формулу» элементарных произведений, содержащих ровно n переменных. Все получаемые элементарные произведения, ранее от- сутствовавшие в «формуле», дописывать в нее через дизъюнкцию. Ес- ли формула не изменилась, то перейти на шаг 6.

Шаг 4. Удалить из «формулы» все элементарные произведения, для которых операция неполного склеивания была проведена хотя бы один раз (то есть выполнить поглощение).

Шаг 5. Если n≠1, то уменьшить n на 1 и перейти на шаг 3.

Шаг 6. Алгоритм закончен, «формула» является дизъюнкцией всех простых импликант исходной функции.

Метод Блейка

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

Формулы метода:

Ax B x = Ax B x AB – обобщенное склеивание,

AB A = A – поглощение,

где x – переменная, A и B – конъюнкции любой длины.

Алгоритм метода.

Шаг 1. Положить «формулу» равной заданной ДНФ функции.

Шаг 2. Провести все возможные операции обобщенного склеивания для вхо- дящих в «формулу» элементарных произведений.

Шаг 3. Все полученные на шаге 2 элементарные произведения, ранее отсут- ствовавшие в «формуле», дописать в нее через дизъюнкцию. Если формула не изменилась, то перейти на шаг 5.

Шаг 4. Провести в «формуле» все возможные операции поглощения и перей- ти на шаг 1.

Шаг 5. Алгоритм закончен, «формула» является дизъюнкцией всех простых импликант исходной функции.

Сравнение методов Квайна и Блейка.

Параметры	Метод Квайна					Метод Блейка
Область применения		СДНФ				Любая ДНФ
Формула склеивания
	Ax Ax		= Ax Ax A			Ax B x = Ax B x AB
Формула поглощения	AB A = A					AB A = A
Количество шагов	Не превышает число					Заранее не известно
	переменных функции
Результат алгоритма	Сокращенная ДНФ					Сокращенная ДНФ

Построение МДНФ из Сокр.ДНФ с помощью таблицы Квайна

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

Алгоритм получения fМДНФ с помощью таблицы Квайна.

Шаг 1. Для всех столбцов, содержащих ровно одну , выписать в fМДНФ (через дизъюнкцию) соответствующие простые импликанты.

Шаг 2. Удалить из таблицы все столбцы, в которых на пересечении со стро- ками, выбранными на шаге 1, стоит .

Шаг 3. Удалить из таблицы все строки, соответствующие выбранным на шаге

1 простым импликантам, а также все строки, в которых нет ни одной

.

Шаг 4. Повторять шаги 1–3 до тех пор, пока таблица изменяется.

Шаг 5. Из оставшихся строк перебором всех возможных вариантов выбрать минимальное по суммарному числу вхождений переменных множест- во простых импликант так, чтобы все оставшиеся столбцы имели на пересечении хотя бы с одной из выбранных строк .

Пример 25. Для функции f ( x, y, z, p) = y p x / z ← y x y p z по-

лучить сокращенную и минимальную ДНФ)

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

1 2 3 4 5 6 7 8 9

fСДНФ = x y z p x y z p x y z p x y z p x y z p x y z p x y z p x y z p x y z p

I этап – операции полного склеивания для конъюнкций длины 4

1-2 x z p (1’)

3-9

y z p (5’)

5-9 xz p (9’)

1-5

y

z

p

(2’)

5-6

x

y

z

(6’)

7-8 x

yz (10’)

2-3

xy z (3’)

5-7 x

y

p

(7’)

3-4

xyp (4’)

5-8

x

y

p (8’)

II этап – операции полного склеивания для конъюнкций длины 3 (взятых с

предыдущего этапа)

7’-8’ x

(1”).

6’-10 x

y

(1”)

y

После проведения всех необходимых операций поглощения получим: fСокр. = x z p y z p xy z xyp y z p xz p x y .

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

(см. Пример 24, стр.38): f ( x, y, z, p) = yx y p z pxyz pzx pzy xy p z . Так же как и в предыдущем случае, пронумеруем дизъюнкты.

f ( x, y, z, p)					1			2						3	4							5		6
					=
						yx y p z pxyz pzx pzy xy p z
I этап. Операции обобщенного склеивания:
1-3 0															2-5 0									3-6 0
1-6 0																					(8)			4-6 0
															2-6	x		z		p
2-3 0
				(7)											3-4 0													5-6	xy z (10)
2-4 x	y		z
															3-5 xyp (9)
Операции поглощения:
1 поглощает 7,															8 поглощает 6,													9 поглощает 3.

1

2

9

4

5

8

10

f( x, y, z, p) = yx y p z xyp pzx p zy x z p xy z

IIэтап. Операции обобщенного склеивания (склеивания, в результате которых получены 0 не указаны):

1-5 pzx (4)

2-10 x z p (8)

5-8 xy z (10)

1-8

y

p

z

(2)

9-4 p

zy (5)

5-10 p

zy (5)

(7)

2-4 x

y

z

4-10 p

zy (5)

Новых конъюнкций не появилось, поэтому можно записать

fСокр. =

x

z

p

y

z

p

xy z xyp y z p xz p x y .

Матрица Квайна для функции f имеет вид

x y z p

x y z p

x y z p

x y z p

x y z p

x y z p

x y z p

x y z p

x y z p

*

*

x z p

*

*

y z p

*

*

xy z

*

*

xyp

*

*

y z p

*

*

xz p

*

*

*

*

x y

Простыми не лишними импликантами точно являются x

,

y

xyp

После первого этапа матрица примет вид

x y z p

x y z p

x y z p

*

*

x z p

*

y z p

*

xy z

*

y z p

*

xz p

Функция f имеет четыре тупиковые формы: f1 ( x, y, z, p) = x y xyp x z p y z p ,

f2 ( x, y, z, p) = x y xyp x z p xz p ,

f3 ( x, y, z, p) = x y xyp y z p xy z y z p , f4 ( x, y, z, p) = x y xyp y z p xy z xz p ,

среди которых минимальными являются f1 и f2 .3

Отметим, что в методе Квайна была использована на каждом этапе новая нумерация, так как на i-ый этап выходят только элементарные произведения i-1-ого этапа. А в методе Блейка в i-ом этапе участвуют все конъюнкции, полу- ченные вплоть до i–1-ого этапа, поэтому там использована сквозная нумерация.

2.4. Графическая минимизация логических функций.

Будем считать, что область определения функции f (x1, x2 ,..., xn ) – верши-

ны n-мерного куба. Причем вершины, в которых функция равна 1, помечены *. Рассмотрим идею графической минимизации на примере функции 3-х пе- ременных. Для того, чтобы определить четыре вершины куба, принадлежащие

плоскости x=1, имеется три способа:

1) x =1, y =0, z =0 или x =1, y =0, z =1 или x =1, y =1, z =0 или x =1, y =1, z =1; 2а) x =1, y =1 или x =1, y =0 ( x =1, y =1 – это прямая перпендикулярная ко-

ординатной плоскости Oxy, из этой прямой лишь 2 точки x =1, y =0, z =0 и x =1, y =0, z =1 входят в область определения логической функции f (x, y, z ) ,

причем именно те, которые нужны); 2б) x =1, z =1 или x =1, z =0 ;

3) x =1 ( x =1 – уравнение плоскости перпендикулярной оси Ox).

Видно, что запись 3), определяющая одновременно все 4 точки (вершины), самая короткая. В общем случае, если необходимо задать m-грань (m-куб) n- мерного булевого куба, то необходимо ровно (n–m) равенств вида xi = 0 или

xi =1, где i =1,n . Если же записывать по отдельности все вершины этой m- грани, то понадобится nm таких равенств. Именно это наблюдение лежит в ос- нове графической минимизации.

Метод карт Карнапа

Картой Карнапа (Карнап (Carnap) Рудольф (1891-1970) – нем.-амер. фило-

соф и логик) для четырех переменных называется таблица 4 × 4 , каждая клетка которой соответствует вершине четырехмерного куба, причем соответствие за- дается таким образом, что если склеить карту по вертикали и горизонтали в тор, то соседние клетки карты будут соответствовать соседним вершинам куба. Со- ответствие вершинам куба обычно задают явно, указывая координаты строк и столбцов таблицы. В клетках таблицы, соответствующих вершинам куба, в ко- торых минимизируемая функция равна 1, проставляют . Трехмерный куб можно рассматривать как грань четырехмерного, поэтому в качестве карты Карнапа для функции 3-х переменных берут часть карты для функции 4-х пе- ременных.

Будем называть гранью множество звездочек карты, соответствующее ка- кой-либо грани куба (отметим, что грань на карте Карнапа – всегда множество соседних звездочек). Мощность грани (количество *) может быть равна 1, 2, 22,

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

..., m, где m – мощность данной грани. Обратим особое внимание на то, что по- лезная мощность определена только для максимальной грани. Причем незави- симо от шага алгоритма мощность максимальной грани для каждой звездочки

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

Пример 26.		Пример 27.
f (x, y, z) = (1010 1011)	f (x, y, z, p) = (0010 1010 0101 0111)
z z		z	z
y			y
x	x
y			y
x	x
y			y
	p	p	p

Алгоритм минимизации по карте Карнапа

Шаг 1. Находим непокрытую, немаркированную звездочку. Если все звездоч- ки покрыты, то stop. Если все непокрытые звездочки маркированы, то переходим на шаг 5.

Шаг 2. Среди всех возможных вариантов граней для данной звездочки выби- раем грани, максимальные по мощности. Если такая грань единствен- ная, то обводим ее и переходим на шаг 5.

Шаг 3. Среди граней максимальной мощности выбираем грань с максималь- ной полезной мощностью. Если такая грань единственная, то обводим ее и переходим на шаг 5.

Шаг 4. Маркировать звёздочку и перейти на шаг 1.

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

Шаг 6. Снять все маркировки. Перейти на шаг 1.

Пример 28. Приведем для некоторых функций примеры карт и минимальных покрытий:

z		z
		y
x
		y
x
		y
p	p	p
	y p
z		z
		y
x
		y
x
		y
p	p	p
x y z p x y p x y z
z		z
		y
x
		y
x
		y
p	p	p
	y p

z		z
		y
x
		y
x
		y
p	p	p
	p
z		z
		y
x
		y
x
		y
p	p	p
x z x p y z x y p
z		z
		y
x
		y
x
		y
p	p	p
z p y p x z p

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

	z	z
		y
x
		y
x
		y
p	p	p

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

	2.5. Полнота систем булевых функций
Как уже	говорилось выше, система переключательных функций
F = ( f1, f2 ,..., fn )	называется полной, если всякая переключательная функция

является некоторой суперпозицией этих функций f1, f2, ... , fn.

Примерами функционально полных систем могут служить следующие

системы логических операций:

{ , ,←} , { , ,1} , { ,←} , { ,←} , {/} , {↓} , { ,←} , { , , } , { , , } и др.

Для определения функциональной полноты системы используются так на- зываемые классы Поста.

Классы Поста

I.Класс функций, сохраняющих нуль (P0). Переключательная функция называ-

ется сохраняющей нуль, если f(0,0,...,0)=0.

II. Класс функций, сохраняющих единицу (P1). Переключательная функция на-

зывается сохраняющей единицу, если f(1,1,...,1)=1.

III. Класс самодвойственных функций (S). Функция f * ( x1,…, xn ) называется

двойственной к функции f ( x1,…, xn ) , если f * ( x1,…, xn ) = ← f ( ← x1,…, ← xn ).

Переключательная функция f ( x1,…, xn ) называется самодвойственной, если

f * ( x1,…, xn ) = f ( x1,…, xn ).

IV. Класс монотонных функций (M). Переключательная функция называется монотонной, если f(α1α2 ... αn)≤f(β1β2 ... βn) на всех сравнимых наборах, т.е.

таких, что (α1α2 ... αn)≤(β1β2 ... βn). Причем (α1α2 ... αn)≤(β1β2 ... βn), если при любом i: αi≤βi.

IV. Класс линейных функций (L). Переключательная функция называется ли- нейной, если она представима линейным полиномом Жегалкина.

Теорема 3. Всякая булева функция представима полиномом Жегалкина, т.е. в

виде f(x1, x2,..., xn)=a0 a1x1 … anxn an+1x1x2 … a2n-1x1xna2nx2x3 … akx1x2…xn, где ai {0,1}.

4Для доказательства достаточно привести тождества (эквивалентные от- ношения), позволяющие преобразовать произвольную ДНФ в полином Жегал- кина:

Тождества,
1) x y=x y xy,			3) x		=1,	5) x x=0,
				x
2)		=x1,	4) x0=x,			6) x(y z)=xy xz.
	x
3

В качестве примера приведем полиномы Жегалкина для конституент 1 функции 3-х переменных:

x y z	Формула	Полином Жегалкина
	конституенты

											(	)(	y			)(					)	≡ xyz xy xz yz x y z 1
	x y z
0 0 0												x 1		1				z 1
													(		x			)(		y			)	≡ xyz xz yz z
	x yz
0 0 1																	1					1 z
													(		x			)		(			)	≡ xyz xy yz y
		xy z
0 1 0																	1 y					z 1
																			(				)
		xyz
0 1 1																					x 1 yz ≡ xyz yz
													x			(			)(				)	≡ xyz xy xz x
	x y z
1 0 0																	y 1					z 1
																			x		(	y 1 z ≡ xyz xz
1 0 1		x yz
																							)
																			xy				z 1 ≡ xyz xy
1 1 0		xy z
																						(		)
1 1 1		xyz																						xyz

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

Лемма 9. В СДНФ при построении полинома Жегалкина можно все ‘ ’ заме- нить на ‘ ’.

Полином Жегалкина называется линейным, если он не содержит произве- дения переменных, т.е. ai=0 i>n.

Теорема 4. Если функция принимает значение 1 на нечетном количестве набо- ров, то она не линейна.

4Доказательство вытекает из таблицы предыдущего примера и леммы 9. Каждая конституента функции f ( x1, x2 ,..., xn ) «даст» ровно одно слагаемое вида x1x2...xn . А сумма по модулю 2 нечетного количества одинаковых слагаемых равна одному слагаемому (так как x x=0), поэтому соответствующий функции f полином Жегалкина будет содержать конъюнкцию x1x2 ...xn , т.е. будет нели-

нейным.3

Пример 29. Для функции f(x,y,z,p)=(1000 1101 1111 0100) определить принадлежность классам Поста.

4 f P , т.к. f (0000) = 1;	f P , т.к. f (1111) = 0 ;
0	1

f S , т.к.	f (0001) = f (1110);	f M , т.к. f (0000) > f (0001) ;
f L , т.к.	функция имеет нечетное количество единиц.3

Лемма 10. Каждый класс Поста замкнут относительно операций подстановки и суперпозиции, то есть с помощью этих операций можно получить только функ- ции того же класса Поста.

Теорема Поста (сильная). Система переключательных функций тогда и только тогда является функционально полной, когда для каждого класса P0, P1, S, M, L в ней найдется функция, не принадлежащая этому классу.

Теорема Поста (слабая). Система переключательных функций, содержащая const 0 и const 1, является функционально полной тогда и только тогда, когда она содержит хотя бы одну нелинейную и хотя бы одну немонотонную функ- цию.

Система функций F называется независимой, если никакая функция f F не представима суперпозициями функций из F\{f}. Независимая система функций называется базисом класса K, если всякая функция из K есть суперпозиция функций из F, или, другими словами, система переключательных функций на- зывается базисом, если она функционально полная, а удаление любой функции из этой системы делает ее неполной.

Теорема 5. Каждый базис функционально полной системы содержит не более 4 булевых функций.

4Для доказательства рассмотрим четыре случая:

1) Система не содержит функций const 0 и const 1. Но по сильной теореме Поста в ней должна быть функция f, не сохраняющая 0. Так как это не может быть const 1, то эта функция являеsтся также немонотонной. Поэтому, чтобы получить базис, достаточно кроме функции f включить в базис системы одну несамодвойственную, одну нелинейную и одну не сохраняющую 1 функции. А, следовательно, базис функционально полной системы будет содержать не более 4 функций.

2), 3) Система содержит одну из функций const 0 или const 1. Достаточно отметить, что функции const 0 и const 1 обе являются несамодвойственными. Далее доказательство аналогично случаю 1.

4) Система содержит обе функции const 0 и const 1. Доказательством в этом случае служит слабая теорема Поста.3

Пример 30. Выписать все базисы, содержащие функции из совокупности { f1, f2 , f3 , f4 , f5 , f6} , если принадлежность классам Поста для этих функций ука-

зана в таблице («+»означает, что функция принадлежит соответствующему классу, а «–» – не принадлежит):

P0

P1

S

M

L

f1

+

–

–

–

–