билеты_41_81

Билет 65.

Дополнительные функционально полные системы логических функций.

o

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

“ИЛИ-НЕ”)

Записывается А =

.

a1 Ú a2 Ú... Ú aN

Элемент, который выполняет эту логическую функцию, обозначается

а1

1

а2

А = a1

a2

... aN

аN

Докажем, что эта функция является функционально полной системой логических функций.

Доказательство проведем на примере стрелки Пирса с двумя входными аргументами, т.е. А = a1 a2 .

Элемент, который выполняет эту логическую функцию, обозначается

	a1
				1
					А = a1		a2
	b2

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

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

А = a b = a b = a b a b .

Структурная схема, выполняющая эту операцию, имеет вид

a			1
				А = a b

1	А = a b или

1

b

А =

a b

А =

а

a b

1

1

А = a b

b

б). Логическое умножение

А = a ×b = a ×b = а Ú b = a Ú a Ú b Ú b .

Структурная схема, выполняющая эту операцию, имеет вид

a

b

1
		А = a a
						1				А = a × b
1
		А =
			a a

в). Логическое отрицание

А = a = a Ú a .

Структурная схема, выполняющая эту операцию, имеет вид

1

А =

a

a

o

Штрих Шеффера (отрицание конъюнкции, или логическая связь

“И-НЕ”)

Записывается А =

a1 × a2 ×...× aN

.

Элемент, который выполняет эту логическую функцию, обозначается

а1

&

а2

А

= a1 × a2 ×...× aN

а

N

Докажем, что эта функция является функционально полной системой логических функций.

Доказательство проведем на примере штрих Шеффера с двумя входными аргументами, т.е. А = a1 × a2 .

Элемент, который выполняет эту логическую функцию, обозначается

a1
		&	А =
b2				a1	× a2

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

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

А = a Úb = a Úb = a ×b = a × a ×b ×b .

Структурная схема, выполняющая эту операцию, имеет вид

А =

a

&

&

&

b

А = a × a

Аab

б). Логическое умножение

А = a ×b = a ×b = a ×b ×a ×b .

Структурная схема, выполняющая эту операцию, имеет вид

a

b

&

А =

a × b

а

&

&

&

или

b

&

А =

a× b

А = a× b

в). Логическое отрицание

А = a = a × a .

Структурная схема, выполняющая эту операцию, имеет вид

a					&	Аa

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

разделе 7.2.1, а, следовательно, и любую сколь угодно сложную логическую функцию.

Билет 66. Способы представления логических функций

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

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

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

A= a ×b Ú c ×b Ú d .

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

x1x2y00y001y110y211y3Табли ца истинности на 2 (два)

входных аргумента x1 и x2.

	x1x2х3x4y0000y00001y10010y20011y3
	0100y40101y50110y60111y71000y8100
	1y91010y101011y111100y121101y131110
	y141111y15Таблица истинност на 4
x1x2х3y000y0001y1010y2011y31	(четыре) входных аргумента x1, x2, x3
00y4101y5110y6111y7Таблица	и x .
	4
истинност на 3 (три) входных
аргумента x1, x2 и x3.

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

набору входных аргументов.

x1=1

			x1=1
y0y2y1y3	x2=1
Карта Карно на два входных		x4=1	y0y4y12y8y1y5y13y9y3
аргумента			y7y15y11y2y6y14y10
x1=1				x3=1
y0y2y6y4y1y3y7y5		x3=1	x2=1
			Карта Карно на четыре входных

x2=1	аргумента
Карта Карно на три входных
аргумента

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

Правило составления логической формулы по карте Карно.

Логическая формула по карте Карно будет иметь вид:

N
Y = åAn ,	(7.2.1)
n=1	An - логическая функция “И”,
где N – число объединений единиц в карте Карно,

составленная для n-го объединения.

Объединения составляются по правилу соседства. Соседними считаются единицы, рядом стоящие по столбцу или по строке, стоящие на противоположных концах столбца или строки. Возможно объединение по 2(две), 4 (четыре) и 8 (восемь) единиц.

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

если они входят в n-ое объединение только единицами, и в инверсном виде, если они

входят в n-ое объединение только нулями, если аргумент входит в это объединение и нулем и единицей, то такой аргумент отбрасывается.

o Временные диаграммы представляют собой расположенные

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

Билет 67.

Связь между таблицами истинности и структурными формулами.

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

Минтермом (m) называется конъюнкция всех входных переменных, взятых в прямом ( xn ,если xn входит в данный набор значением 1) или инвертированном ( xn , если xn входит в данный набор значением 0) виде, обеспечивающая требуемое по

условию задачи обращение выходной логической функции в единицу.

Макстермом (M) называется дизъюнкция всех входных переменных, взятых в прямом ( xn ,если xn входит в данный набор значением 0) или инвертированном ( xn , если xn входит в данный набор значением 1) виде, обеспечивающая требуемое по

условию задачи обращение выходной логической функции в ноль.

На основе этих определений осуществляется переход от таблиц истинности к структурным формулам. При этом функция Y представляется в виде одной из двух форм

– совершенной нормальной конъюнктивной форме (СНКФ) и совершенной нормальной дизъюнктивной форме(СНДФ):

N	K
Y = å mn - СНКФ;	Y = ÕM k - СНДФ,	(7.2.5)
n=1	k

где N и K - общее количество минтермов и макстермов логической функции соответственно.

Из (7.2.5) вытекают алгоритмы перехода от таблиц истинности 5к структурной формуле.

Для СНКФ

∙Запись Y в виде суммы слагаемых, каждое из которых представляет собой логическое умножение всех аргументов; число слагаемых равно количеству минтермов.

∙Инвертирование в каждом произведении тех аргументов, которые входят в минтерм нулями.

Для СНДФ

1.Запись Y в виде произведение сомножителей, каждое из которых представляет собой логическое сложение всех аргументов; число слагаемых равно количеству макстермов.

2.Инвертирование в каждом произведении тех аргументов, которые входят в макстерм единицами.

Переход от таблиц истинности к структурным формулам с использованием

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

Билет 68. Транзисторная логика с непосредственными связями

(НСТЛ) и резисторно - транзисторная логика (РТЛ)

Базовый логический элемент транзисторной логики с непосредственными связями (рис.7.2.2).

Ek

RH

VT1

x1

VT2

1

Y

x1

ИМС2

x2

x2

“2ИЛИ-НЕ”

a)

b)

Рис.7.2.2. Базовый элемент НСТЛ (а) и его функциональная характеристика (б).

Базовый логический элемент резисто-транзисторной логики (рис.7.2.3).

Еk

R

Y

H

х1

Y

VT

VT1

R2

1

х1

R1

2

x2 x2

“2ИЛИ-НЕ”

b)

a)

Рис.7.2.3. Базовый элемент РТЛ (а) и его функциональная характеристика

(б).

Билет 69.Логика на МОП-транзисторах (МОП-логика), логика на

комплиментарных МОП-транзисторах (КМОП-логика) и интегрально-инжекционную логика (ИИЛ).

Базовый логический элемент на n-канальном МДП-транзисторе (рис.7.2.8).

Ek

VT3

Y

VT1 VT2

x1

x2

а)

Ek

x1

Ri3 Y

x1

x2

Y

1

x2

Ri1

Ri2

2ИЛИ-НЕ

б)

в)

Рис.7.2.8. Базовый логический элемент на n-канальном МДП-транзисторе (а), его эквивалентная схема (б) и функциональная характеристика (в).

Базовый элемент КМОП - логики (рис.7.2.9).

Eс

Eс

VT4

Ri4

	VT3		Ri3		x1	Y
					1
		Y		Y	x2
					2ИЛИ-НЕ
VT1	VT2		x1	x2
x1		x2	Ri1		в)
				Ri2

а)

б)

Рис.7.2.9. Базовый логический элемент комплиментарном МДП-транзисторе (а), его эквивалентная схема (б) и функциональная характеристика (в).

Базовый элемент интегрально-инжекционной логики (рис.7.2.10).

I1

>>

VT4

Г1

Rн

x1

Y

1

2I0

VT3

x2

>>

2ИЛИ-НЕ

I2

VT2

Г2

>>

VT1

a)	б)

Рис.7.2.10. Базовый элемент интегрально-инжекционной логики(а) и его функциональная характеристика (б).

На рисунке 7.2.10 Г1 и Г2 источники входных сигналов (токов), Г3 - источник питания.

Билет 70. Комбинационные цифровые устройства

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

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

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

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

6)занесение в карту значений Y, равных 1;

7)объединение единиц в группы по 2, 4, 8 в соответствии с правилом “соседства”:

8)соседними считаются ячейки, расположенные по одной горизонтали или вертикали непосредственно рядом или на противоположных границах карты;

9)представление каждого объединения в виде слагаемого, являющегося логическим произведением всех аргументов, за исключением тех, которые принимают в рамках этого объединения как значения 0, так и 1 (если аргумент входит в рассматриваемое объединение нулем, то он включается со знаком инверсии).

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

Вслучае дизъюнктивной формы работа с картой Карно осуществляется по следующему алгоритму:

10)занесение в карту значений Y, равных 0;

11)объединение нулей в группы по 2, 4, 8 в соответствии с правилом “соседства”:

12)соседними считаются ячейки, расположенные по одной горизонтали или вертикали непосредственно рядом или на противоположных границах карты;

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

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