Раздел: Документация

0 ... 2 3 4 5 6 7 8 ... 119

(вход D не используется) и Т = Q+ ф Q, а при L = 1 - функции D = Q+ и Г = Й! (вход Г не используется), что полностью соответствует мультиплексной относительно сигнала L функции переходов D-T-L-триггера. Таким образом, D-T-L-триггер обладает избыточностью в числе информационных входов, а значит и большей универсальностью по отношению к триггерам других типов.

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

1.7. Первичные термы, минтермы и макстермы

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

Первичные термы. Переменные хр и их инверсии хр называются первичными термами. Для первичных термов используется символическое обозначение

хе/ = ёрхр V ерхр = ер ф хр,(1.62)

где ер = 0 или 1. Здесьв одном символе хрр объединены оба первичных терма хр и хр. Действительно, при подстановке в (1.62) значений ер = О и 1 будем иметь:

хеР j Хр, если ер = 0.

р хр, если ер = 1.

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

хрр и хрр равны только в том случае, если ер = ер (если ер ф е,

то ер = ер). Для первичных термов справедливы следующие соотношения:

хр = х р = xpixp = хр = хр,

херр = xf = хр";(1.63)

хе/ = 0, хер" V х/ = 1;(1.64)

е„ Г 0, если хр = ёр, Хр ~ \ 1, если хр = ev.(L65)

Истинность этих соотношений элементарно проверяется на основании определения первичных термов (1.62).

1.7. Термы

35

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

е6 е4 е1 Г x6x4xi при е6 = 0, е4 = 1,ех = 1, х6 х4хг - jgazj ПрИ е6 = 0, е4 = 1,ех - 0.

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

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

Р=1

где v = (хп,xi), ev - 0 или 1, г = е„... ех (минтерм - невырожденная функция). Из данного определения следует, что имеется 2" различных минтермов п переменных, так как имеется 2" различных n-разрядных двоичных чисел г = 0,1,..., 2"-1. Минтермы обладают следующими свойствами:

, . Г 1, если v =67ч

bXbcjwvvVx-

Ki{v) Kj{v) = 0, если i ф j;(1-68)

2yKt(v) = l.(1-69)

i=0

Свойство минтермов (1.67), заключающееся в том, что любой минтерм hi(v) равен 1 только в одной точке i/t области определения, состоящей из 2" точек, легко доказать, используя свойство первичных термов (1.65): при v = V{ = (еп,..., ер,..., ех) значения переменных хр = ер, а значит, только в этом случае

Р=1 Р=1

(при значении хотя бы одной переменной a:p ф ер, т.е. при Хр = ёр, значение первичного терма Хрр - ерр = 0 на основании соотношения (1.65) и минтерм Ri(v) = 0). Свойства минтермов (1.68) и (1.69) доказываются на основании свойства (1.67).

з*

---

Запишем все минтермы K{(v) = хе22х\г двух переменных х2

и Х\\

АоН = х%х\ = х2хь Ki(v) = хх\ = х"2хь K2(v) = х\х\ = x2xx,K3(v) = х\х\ = х2хъ

где v = (х2,хх), i = е2ех.

Таким же способом можно записать любой минтерм А,(ь>) большего числа переменных. Пусть, например, п = 4 и г = 13 = (1101)2, тогда KX3(v) = жжжж = х4х3х2хх.

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

Mi{v) = Щи) = J] хер" = V хе/.(1.70)

p=i Р=1

Согласно свойству первичных термов (1.63) можно записать:

п

Mi(v) = У Xе/ = xln V ... V xf, Р=1

где v - (х„,..., хх), г = еп ... ех (макстермы - невырожденные функции).

Макстермы обладают следующими свойствами:

МгЫ=( ? если « = «..

,v 1 [1, если v = vj ф i/t;

Mi(v) V Mj(v) = 1, если г ф j; 2П Mt(u) = 0.

t=0

Свойства макстермов могут быть получены из свойств мин-термов (1.67) - (1.69) на основании определения макстермов (1.70). Например, из свойства минтермов (1.68) следует, что

Щу) К3{у) = 0,i ф j =» Щу) Kj{v) = Ь

=> Ki{v) V Kj(v) = 1 => Mi{v) V Mj(v) = \,1ф j.

Из первого свойства макстермов следует, что они представляют собой функции, равные нулю только в одной точке j/,

области определения, состоящей из 2" точек. Запишем все макстермы M~i(v) = хе2 V Xj1 двух переменных х2 и х\\

M0(v) = х\ V = х2 V хь Mx(v) = х V х] = х2 V хь

M2(v) = х\ V х\ = х2 V xi, M3(v) = х\ V х\ = х2 V хь

где v - (x2,xi), г = е2ех. Аналогичным образом можно записать любой макстерм M;(f) большего числа переменных. Пусть, например, п = 4 и г = 13 = (1101)2- Тогда макстерм

Mi3(f) = х\ V х\ V х°2 V х\ = х4 V х3 V х2 V хх.

В табл. 1.4 (таблица истинности) приведены все минтермы и макстермы двух переменных х2 и хх.

Таблица 1.4. Минтермы и макстермы двух переменных

I	Х2ХХ	K0KiK2K3	Mo Mi М2Мз
0 1 2 3	0 0 01 10 1 1	10 0 0 0 10 0 0 0 10 0 0 0 1	0 111 10 11 110 1 1110

Минтермы и макстермы играют важнейшую роль в теории переключательных функций и ее практических приложениях. Устройства, реализующие все 2" минтерма (макстерма), называются полными дешифраторами с прямыми (инверсными) выходами. Эти устройства используются для коммутации (включения-выключения) других устройств, так как в каждый момент времени только один их выходной сигнал равен 1 (0). Дешифратор называется неполным, если он реализует не все 2" минтерма (макстерма). Если дешифратор реализует только один минтерм (макстерм), то его принято называть детектором состояния. В цифровых устройствах детекторы состояния используются для обнаружения на выходах схем одной определенной комбинации значений сигналов.

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

Теорему разложения (1.29) для функций п переменных можно использовать п раз, т.е. функцию можно разложить по всем п переменным хр, где р = 1,2,..., п. В качестве примера

---

рассмотрим разложение функции f{v) = f(x2, х\) двух переменных х2 и х\. По теореме разложения (1.29) получим:

f(x2,xi) = х2 /(0,жх) V х2 • /(1,

Далее каждую из функций f(0,xi) и f(l,xi) можно разложить по переменной х\:

f(x2, Xl) = x2[Xlf(0,0) V zx/(0, 1)] v x2[Xlf(l,0) v zx/(l, 1)] =

= x-2x"i/(0,0) V z2zi/(0,1) V x2Xlf(l,0) V x2Xlf(l, 1) =

= "/(0,0) V x°x\f(0,1) V а:?/(1,0) V x\x\f(l, 1) =

= v2il-/(e2,ex)= v/w-ед,

t=0i=0

где v - (x2,xi), Vi = (e2,ex), i = e2ex, Iii(v) = a:2 • x\l - минтермы двух переменных x2 и x\. Так как f(vi) = aj = 0 или 1 (значение функции в точке vx), то

з

/() = V atKt(v).

i=0

Такая форма представления функции двух переменных называется совершенной дизъюнктивной нормальной формой (СДНФ). Термин "совершенная форма" означает, что все члены имеют одинаковую размерность, а термин "нормальная форма" - что в выражении, задающем функцию, последовательно выполняются не более двух базовых операций алгебры логики (операция отрицания в расчет не принимается). Полученная СДНФ функции двух переменных х2 и Х\ эквивалентна выражению (1.35) для мультиплексной функции.

Разложение функции п переменных представляет собой дизъюнкцию 2" членов вида хе хе/ х\1 /(е„,..., ер,..., ех) = = f{vi) K{(v) = а, hi{v):

2"-l

f(v)= V ai-Ki(v).(1.71)

«=o

Выражение (1.71) представляет собой СДНФ функции п переменных, т. е. СДНФ является полным разложением (по всем переменным) функции по теореме Шеннона (1.29). Так как значения функции a,i = 0 или 1, то • Kj(i/) = 0, если а, = 0, и а, • Ki(v) = Ki(v), если а; = 1. Поэтому СДНФ функции можно представить в виде

f{v) = \J Kh(v),(1.72)

и

где ii - номера тех точек, в которых функция f(v) равна 1, т. е. /(i/,x) = a,-j = 1. Таким образом, СДНФ функции п переменных представляет собою дизъюнкцию некоторого числа к < 2" минтермов.

В качестве примера рассмотрим функцию f(v) трех переменных хз, х2их\, заданную таблицей истинности (табл. 1.5), из которой следует, что ао = аз = оц = а& = 0, ах = а2 = а$ = aj = 1. Поэтому на основании (1.72)

f(v) = Ri{v) V K2(v) V K5(v) V K7(v) = = xzx2xi V х"за:2х"х V хзх2хг V x$x2x\.

Это и есть СДНФ функции f(v), заданной табл. 1.5.

Таблица 1.5. Функция трех переменных

i	x3x2xi	/	i		/
0	0 0 0	0	4	1 0 0	0
1	0 0 1	1	5	1 0 1	1
2	0 1 0	1	6	1 1 0	0
3	0 1 1	0	7	1 1 1	1

СДНФ полностью неопределенной функции имеет вид:

2"-1

Цу) = V ciKi(v),

«=0

где с, - неопределенные значения функции (с = 0 или 1).

Совершенную конъюнктивную нормальную форму(СКНФ) функции п переменных f(v) можно получить на основании двойственной теоремы разложения (1.33). Однако предпочтительнее более простой способ, основанный на записи СДНФ инверсной функции f(v). Инверсия функции в каждой точке V{ должна иметь инверсные значения aj по отношению к значениям а,- самой функции, т.е. f{vt) = Щ, если f{vt) = aj. На основании (1.72) запишем СДНФ инверсной функции:

2"-1

f(v) = V №И-

i=Q

Из данного соотношения на основании закона двойственно-

0 ... 2 3 4 5 6 7 8 ... 119