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

	указаны булевы переменные (x1									и			x2 ) и функции (y1, y2 , …,																	y16 ) как
	обозначение соответствующих строк таблицы. В строках, помеченных
	символами				y1,y2 , …,			y16 , стоят нули и единицы. Единицы указывают,
	какие вершины единичного квадрата принадлежат области истинности
	(ОИ) соответствующей функции yi .
С																									Таблица 1.1.
			Перечень всех булевых функций с числом аргументов
	№		0	1		2	3		Название функции														Обозначение
	пары								Название функции														Обозначение
	x		0	0		1	1
		1
	x	2	0	1		0	1
		2
	y		0	0		0	0		Константа «ложь»																		0
		1
	y		0	0		0	1		Конъюнкция (логическое И)														x & x
	y10				бА																	x1			x2
		2																						1									2
	y	3	0	0		1	0		Запрет (x запрещает x									2	)				x		x									2
		3						1										2					1											2
			и
	y4								Пустая операция над x1																		x1
	y	5	0	1		0	0		Запрет (x	2	запрещает x )												x	2		x
		5								2								1						2										1
	y6		0	1		0	1		Пустая операция над x2																	x2
	y	7	0	1		1	0		Сложение по модулю 2														x x										2
		7																						1									2
	y		0	1		1	1		Дизъюнкция (логическое ИЛИ)														x x									2
		8																							1							2
	y9		1	0		0	0		Д																	x
	y9		1	0		0	0		Стрелка Пирса					(ИЛИ-НЕ)									x			x						2
																									1							2
			1	0		0	1		Эквиваленция
	y		1	0		1	0		Инверсия x			2	(НЕ x			2	)									x		2
	11											2				2												2
	y		1	0		1	1		Импликация (x					2	влечетx )								x	2		x
	12													2					1					2										1
																И
	y		1	1		0	0		Инверсия x (НЕ x )																		x
	13											1				1												1
	y		1	1		0	1		Импликация (x влечетx											2	)		x		x									2
	14														1					2			1											2
	y		1	1		1	0		Штрих Шеффера ( -НЕ)														x						x
	15																						x						x		2
																									1						2

	y		1	1		1	1		Константа «истина»																		1
	16

Анализ связей между логическими операциями соединения

Поскольку строка y1 содержит одни нули, то область истинности данной функции (константы «ложь») – пустое множество. В строке y2

Чарлз Сандерс Пирс (1839 – 1914) – амер. математик и логик. Родоначальник американского прагматизма.

6

только одна единица, соответствующая вершине 1,1 с номером 3 еди-

ничного квадрата 0,1 2 , и, следовательно, областью истинности для конъюнкции будет подмножество 1,1 .

На рис. 1.2 и 1.3 показаны границы областей истинности для конъюнкции, сложения по модулю 2, дизъюнкции, стрелки Пирса, им-

С
пликации x1 x2 , эквиваленции и запрета x1 x2 (сравните выделен-
ные области с соответствующими строками y2 , y7 , y8, y9 , y14 , y10 , y3
нашей	табл цы).	Здесь		единичный			квадрат
0,1 2	0,0 , 0,1, 1,0 , 1,1 в качестве примера разбит семью спо-
собами
	на два подмножества.
Рис. 1.2. ОИ функций: y2,y7		,y8,y9	Рис. 1.3. ОИ функций: y3,y10,y14
СобственнобАбинарных функций в табл. 1.1 только десять, т.к. y1 и
y16 логические константы (0 и 1), а y4 ,				y6 , y11 и y13 унарные функции,
т.е. функции одной переменной, из которых практический интерес
представляет лишь одна унарная булева функция y					x	, называемая ин-
версией (отрицанием) переменнойД.
Итак, в качестве простейших булевых функций мы получили две
логические константы, одну унарную и десять бинарных функций. Ни-
же покажем, что изначальных булевых функций, из которых строятся
все остальные, гораздо меньше.
Полученные выше логические операцииИсоединения можно выра-
зить через три основные булевы функции: инверсию, конъюнкцию и
дизъюнкцию, т.е. через те		логические		операции, которыми			обычно

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

yi Fi( ,&, ) Fi(НЕ,И,ИЛИ). (1.1)

7

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

С												Таблица 1.2
		Таблица истинности основных булевых функций

			x2		x1			x	2		x1 & x2	x1 x2
	x1		x2		x1			x	2		x1 & x2	x1 x2
	1		1	0			0				1	1
	1		0	0			1				0	1
	0		1	1			0				0	1
компози			ц	ию			1				0	0
	0		0	1			1				0	0
Подставляя в конъюнкции вместо переменной												x2 ее инверсию
(осуществляя						конъюнкции и инверсии),						получим новую
булеву функц ю x1 & x2 . Согласно табл. 1.2 областью истинности дан-
ной функц	удет множество									1,0 . Только на вершине 1,0 эта

функц я меет значение единицы, а на всех остальных вершинах единичного квадрата она о ращается в нуль. Но ту же область истинности

имеет и запрет x1 x2 , т.е. данные функции одно и то же. Поэтому
y3=x1 x2 =x1 & x2 .	(1.2)

Иначе говоря, мы выразили функцию y3 через конъюнкцию и ин-


версию формулой (1.2). налогично можно выразить и другие булевы
Д
функции, область истинности которых содержит только одну вершину
единичногобквадрата. ПолучимА
y5=x2 x1=		x1 & x2 ,		(1.3)
y9 =x1 x2 =	x1 & x2 .			(1.4)
Основные результаты анализа			И

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

Теперь вычислим дизъюнкцию функций y3 и y5 по правилам логического сложения (см. 1-й, 2-й и последний столбцы табл. 1.2). По этим правилам будут складываться соответствующие элементы строк y3

и y5 табл. 1.1. В результате такого сложения получится строка y7 той же таблицы.

8

Замечание 2. Строка y7 определяет множество вершин, равное объединению множеств, определяемых складываемыми строками y3 и y5. Следовательно, операцию дизъюнкции булевых функций можно заменить операцией объединения их областей истинности.

Таким образом,	установлено, что y7 y3 y5, а с учетом выраже-
ний (1.2) и (1.3)	x1 x2 (x1 &	x		x1 & x2 ).
y7			2 ) (		(1.5)

Замечан е 3. Функция y7 (сложение по модулю 2) имеет область

истинности 1,0 , 0,1 (рис. 1.2), сопоставление которой с формулой

правило

(1.5) дает следующее правило аналитического выражения булевой

Сфункц , область

стинности которой содержит более одной вершины.

начала находятся формулы для каждой из вершин области истинности

по прав лу, указанному

замечании 1, а затем эти формулы соединяют-

бА

ся знаком д зъюнкц .

Используя это

, найдем аналитические выражения, по-

строенные на трех логических операциях (инверсии, конъюнкции и

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

y8 x1 x2

(x1 &

x

2 ) (

x1 & x2 ) (x1 & x2 ),

(1.6)

y10 x1 x2

(

x1 &

x

2 ) (x1 & x2 ),

(1.7)

y12 x2 x1

(

x1 &

x

2 ) (x1 &

x

2 ) (x1 & x2 ),

(1.8)

y14 x1 x2

(

x1 &

x

2 ) (x1 & x2 ) (x1 & x2 ),

(1.9)

Д

y15 x1

x2

(

x1 &

x

2 ) (

x1 & x2 ) (x1 &

x

2 ).

(1.10)

Равенство (1.6)

вызывает некоторое удивление, где дизъюнкция

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

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

Еще одним важным свойством этих функций является принцип двойственности: i 1,16 j 1,16 (yi yj )&(yj yi) . Иначе гово-

9

ря, для каждой логической операции соединения существует ей противоположная, т.е. такая, у которой область истинности совпадает с областью ложности первой логической операции и, наоборот, область истинности первой логической операции совпадает с областью ложности ей противоположной операции. Это понятие противоположности распространяется на все логические функции.

Тогда противоположные функции в табл. 1.1 будут иметь строки со взаимно противоположными элементами (одна строка переходит в другую при замене в ней всех единиц на нули, а нулей на единицы. На-

пример,

y

8 y9, т.е.

нверсией дизъюнкции является стрелка Пирса, что

и

дает еще одну формулу для определения данной функции y9 x1 x2 .

САналог чно y

y

тогда y

x

, т.е. штрих Шеффера

2

x & x

2

15

1

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

лой, чем в выражен

(1.10).

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

1.По

. 1.1 определите области истинности функций y5 и y15.

2.Область

А

ст нности какой функции равна объединению областей

истинности конъюнкции и сложения по модулю два?

3.Потабл. 1.1 и 1.2 найдите области истинности для функций

x1 x1

и x1 x1. Установите, каким булевым функциям они отве-

чают.

4.Определите все противоположные пары для функций табл. 1.1.

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

лы: (x1 & x2 ) (x1 & x2 ), (x1 & x2 ) (x1 & x2 ), (x1 & x2) (x1 & x2)?

Приведите для них таблицы истинности.Д

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

СОВЕШЕННЫЕ ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ. ШЕФФЕРОВЫ ФУНКЦИИ

Цель занятия: усвоение методов моделирования работы комбинационных устройств совершенными дизъюнктивными нормальными формами.

Краткие теоретические сведения

Распространим полученные результаты предыдущего параграфа на n-арные булевы функции. Функция

y f x1, x2,..., xn

10

Материал: 2160

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