Документ: 2160, страницы 16-20 | База учебных материалов

Материал: 2160

Смотрите также:

Аналогично

можно

показать, что

x1 x2

x1

x2

x2 и

x1 x2 x1

x2

x1

x2 . Схемы этих формул приведены на рис. 1.9 и

1.10.

Таким образом, весь мир булевых функций составлен из «кирпи-

чиков» типа « » или

«

».

Каждая из них образует функционально

С

полную систему (функции подобного рода называют шефферовыми1

[4]). Этот факт используется при создании арифметико-логических уст-

ройств м кропроцессоров.

Используя стандартные электронные схемы

(элементы), выполняющие функцию « » (или «

»), можно собрать

выполнения

y

устройства для

любых арифметико-логических операций.

&

бА

x1

x2

Д

Рис. 1.9. x1

x1

x2

x1

x2

Рис. 1.10.

x1

x2

Однако эти функции плохо сочетаются со спецификой человече-

ского мышления. Нам удобнее мыслить,

используя

более крупные

«кирпичи», контуры которых указаны на рис. 1.5 – 1.10. Поэтому в ма-

И

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

В цифровой электронике также не ограничиваются только стрелкой Пирса ( микросхема ИЛИ-НЕ) или штрихом Шеффера (микросхема И-НЕ). Электронная промышленность выпускает также микросхемы, реализующие логические операции инверсии, конъюнкции, дизъюнкции, сложения по модулю 2 и эквиваленции.

1 В 1913 г. Г. Шеффер (H.M. Sheffer) показал, что любую логическую операцию можно определить через единственный оператор, названный впоследствии штрихом Шеффера

(прим. автора).

16

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

1. Определите совершенные д.н.ф. для двух функций, области истинности которых верхнее переднее и правое переднее ребра куба 0,1 3 (рис. 1.4) соответственно. Затем получите д.н.ф. для функции с областью истинности, равной пересечению указанных выше ребер. Сравните полученные д.н.ф.

2. Чему равна область истинности конъюнкции двух функций – объе-

д нен ю

ли пересечению их областей истинности?

3. Чему равна область истинности дизъюнкции двух функций – объеди-

нен ю

пересечению их областей истинности?

ли

4. Что такое функц онально полная система булевых функций?

С5. уществуют такие улевы функции, которые нельзя выразить че-

рез д зъюнкц ю, конъюнкцию и инверсию?

6.

будет

x1

x2

x2 и x1 x2

Докаж те равенства x1 x2 x1

7.

x1

x2

x1

x2 .

Какую лог ческую операцию

выполнять формула

x1 x1 x1 x1

?

А

Практическое занятие №3

ОПТИМИЗ ЦИЯ КЛУ. БУЛЕВА АЛГЕБРА

Цель занятия: усвоение методов упрощения дизъюнктивных

нормальных форм с помощью формальных алгебраических преобразо-

ваний.

Краткие сведения о булевой алгебре

И

Данная алгебра, носителем которой является все множество буле-

вых функций, а сигнатурой Д(сигнатура – множество алгебраических

операций, носитель – множество объектов, на которых эти операции за-

даны) три логические операции – инверсия, конъюнкция и дизъюнкция,

– восходят

к трудам О. Де Моргана и Дж. Буля1. Основные же тожде-

ства этой алгебры непосредственно следуют из табл. 1.1.

х можно ис-

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

1 Джордж Буль (Boole, 1815 – 1864) – профессор математики в университете г. Корка (Ирландия) – один из основоположников математической логики. Следует отметить, что современная булева алгебра существенно отличается от того, что изложено в его трудах «Математический анализ логики» (1847) и «Исследование законов мысли» (1854). Тем не менее его вклад в современный язык математической логики не может вызывать какихлибо сомнений.

17

Пусть x,y и z произвольные булевы функции. Тогда тождества булевой алгебры будут иметь следующий вид.

войства коммутативности операций и &:

1а. x y y x,

1б. x& y y & x.

С

войства ассоциативности операций и &:

2а. x (y z) (x y) z,

2б. x&(y & z) (x& y)& z.

войства д стрибутивности операций от &

и

& от :

3а. x (y & z) (x y)&(x z),

и

3б. x&(y z) (x& y) (x& z).

4а. x

x

1 – определение единицы и 4б. x&

x

0–

нуля.

войства нуля

единицы:

5а. x 1 1,

5 . x&1 x,

6а. x 0 x,

6б. x&0 0,

7а.

1,

7 .

0.

0

1

Свойства демпотентности операций и &:

8а. x x x,

8б. x& x x.

Законы поглощения:

9а. x (x & y) x,

9б. x&(x y) x.

Законы Де Моргана:

10а.

x

& y,

10б. x& y

x

y

.

x y

Д

Алгебраические преобразования булевых функций

РассмотримбАнесколько примеров на алгебраические преобразова-

ния булевых формул.

Пример 1. Упростить выражение (x1 &

x

2 ) (

x1 & x2 ) (x1 & x2 ).

И

Решение. Используя тождества 1б, 2а и 3б, получим

((x1 & x2 ) (x1 & x2 )) (x1 & x2 ) (x1 & x2 x2 ) (x1 & x2 ).

Откуда на основании 1а, 4а, 5б, 3а, 4а, 1б и 5б имеем

(x1 & x2 x2 )& (x1 & x2) (x1 &1) (x1 & x2) x1 (x1 & x2)

x1 x1 & (x1 x2) 1&(x1 x2) (x1 x2)&1 x1 x2 .

Таким образом, (x1 & x2 ) (x1 & x2 ) (x1 & x2 ) x1 x2 . Теперь сравним полученный результат с равенством (1.6). Следовательно, мы нашли те преобразования, о существовании которых говорилось выше.

Пример 2. Упростить совершенную д.н.ф. для импликации. Решение. Согласно (1.9) импликация может быть определена по

формуле x1 x2 (x1 x2 ) (x1 x2 ) (x1 x2 ).

18

Упростим правую часть равенства. Применяя тождества 3б, 1а, 4а, 1б, 5б, 3а, 1а, 4а, 1б и 5б, получим

(x1 x2 ) (x1 x2 ) (x1 x2) (x1 (x2 x2 )) (x1 x2)( x1 (x2 x2 )) (x1 x2) (x1 1) (x1 x2)

x1 (x1 x2) (x1 x1) (x1 x2 ) (x1 x1) (x1 x2 )

Напримерются сокращенными д.н.ф. В примерах 1 и 2 был осуществлен переход от совершенных д.н.ф. к сокращенным. Сокращенные д.н.ф. можно за-

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

мерности 1, т.е. ре ро с вершинами 10 и 11. Аналогично второй столбец

Х1={01, 11} и столбцы второй матрицы 0Х={00, 01}, Х1={01, 11}.

полученных в пр мерах 1 и 2,

удут такими:

x x

:

x1

1

Х

,

x x

:

x1

0

Х

.

1

2

x

2

Х

1

2

x

2

Х

1

б

Здесь первый стол ец первой матрицы определяет грань 1Х раз-

А

Напомним, что число символов Х в троичном векторе определяет

размерность грани. Например, грань 1ХХ куба 0,1 3 имеет размерность

2 и представляет собой множество {100, 101, 110, 111}, что соответствует четырем столбцам булевой матрицы. Поэтому троичные матрицы

Переход от совершенных д.н.ф. к сокращенным называют минимизацией д.н.ф. Существуют различные алгоритмы минимизации д.н.ф. Они нашли применение в проектировании средств цифровой техники.

	по сравнению с булевыми более компактно описывают одну и ту же бу-
	леву функцию.	Д
		И

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

Пример 3. Найти совершенную д.н.ф. для инверсии функции.

f x1,x2,x3 x1x2x3 x1x2x3 x1x2x3 x1x2,x3 x1x2x3 . (1.15)

Решение. Функция f x1,x2,x3 имеет область истинности, равную области ложности заданной функции f x1,x2,x3 . Область истинности

19

этой функции согласно (1.15) представлена следующими пятью вершинами {001, 010, 100, 101, 110}. Тогда ее область ложности будет содер-

жать все остальные вершины куба 0,1 3 (рис. 1.4), т.е. множество {000, 011, 111} – ее область ложности и область истинности функции

f x1,x2,x3 . Значит булева матрица функции f x1,x2,x3 имеет вид

x1 0	0	1		x1,x2,x3
x2 0	1	1, откуда			x1	x	2	x	3	x1x2x3 x1x2x3 .
			f
x3 0	1	1

и

Пр мер 4. Используя законы Де Моргана (10а, 10б), выразить

Сфункц ю з предыдущего примера в виде конъюнкции дизъюнкций.

Решен е.

Поскольку двойная инверсия пустое преобразование, то

f x1,x2,x3

f

x1,x2 ,x3

x1

x

2

x

3

x1x2 x3 x1x2 x3

x1

x

2

x

3

бА

x1x2x3 x1x2x3 (

x1

x

2

x

3)

x1

x

2x3

x1x2x3 (x1

x

2

x

3)

(

x1

x2x3

)(

x1

x2x3

) (x1 x2 x3 )(x1

x

2

x

3 )(

x1

x

2

x

3). (1.16)

Построение совершенных конъюнктивных нормальных форм

Полученная формула (1.16) для функции (1.15) называется совершенной к.н.ф. Ее можно строить по области ложности функции, следуя такому правилу.

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


динатам вершин, равным единице.										И
Для нашего примера областью ложности было множество {000,
011, 111}. Поэтому				Д
	{(0	0		0),(0		1			1),			(1		1			1)}			.
	(x x		2	x )(x			x	2		x	)(		x		x	2		x	)	.
	1		2	3	1			2	3			1				2	3

Совершенную к.н.ф. не имеет только одна булева функция – константа «истина», т.к. ее область ложности пустое множество.

Конъюнкции из неполных дизъюнкций образуют сокращенную к.н.ф.

Например, формула (x1 x2 x3)(x2 x3) будет уже сокращенной к.н.ф., т.к. одна из ее дизъюнкций неполная (во второй дизъюнкции отсутствует переменная x1).

20

Таким образом, искомая формула будет

Левая часть равенства (1.6) и правая часть равенства (1.14) пред-

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