Структурные формулы. 
Информатика

О формах представления структурных формул

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

Рассмотрим способ получения структурных формул на основании таблицы истинности. При этом способе в структурных формулах сигнал Yn (п = 0,1,…, 1) на любом из выходов комбинационного устройства может быть выражен через сигналы Хм v Хт Х0 с помощью рассмотренных выше основных логических операций в двух алгебраических формах:

• • в совершенной дизъюнктивной нормальной форме (СДНФ) — структурная формула записывается в виде логической суммы, слагаемыми которой являются логические произведения всех входных сигналов, причем каждый сигнал может быть выражен как в прямой, так и в инверсной форме;
• • в совершенной конъюнктивной нормальной форме (СКНФ) — структурная формула представляет собой логическое произведение с сомножителями в виде логических сумм всех входных сигналов, каждый из которых может быть выражен как в прямой, так и в инверсной форме.

Совершенная дизъюнктивная нормальная форма

Для наглядности проиллюстрируем способ получения структурных формул в СДНФ на примере комбинационного устройства с двумя входами (М = 2) и одним выходом (JV = 1), описание которого приведено в табл. 3.4.

Для перехода от табличного описания комбинационного устройства к алгебраическому в СДНФ каждой ?-й комбинации (набору) входных переменных (сигналов) ставится в соответствие минтерм ш^, который представляет собой логическое произведение всех входных переменных, при этом переменная включается в минтерм в прямом виде, если ее значение для й-й комбинации равно единице; в инверсном виде, если ее значение равно нулю.

В табл. 3.4 приведены выражения минтермов шА и значение каждого из них (mj, mf, т, т) как логической функции для k-vi комбинации входных переменных. Из приведенных значений следует важное свойство минтермов: m* = 1, если его номер п (п = 0, 1, 2, 3) совпадает с номером k комбинации (набора), для которой он рассчитан. Это позволяет представить сигнал У комбинационного устройства в виде суммы минтермов с теми номерами п = к, для которых значения сигналов У* = 1. Для рассматриваемого примера сигнал У* = 1 для комбинаций k = 1 и k = 2, поэтому:

Таблица 3.4

Примечание. Нижний индекс k в обозначении минтерма т4 соответствует номеру k комбинации (набора) входных сигналов, к которому он «привязан», т. е. его собственному номеру. Верхний индекс^{минтермов} in* (п = 0,1,2,3) соответствует номеру k комбинации, для которой приведено его значение. В последней графе приведены значения выходного сигнала Y, используемого для иллюстрации рассматриваемого способа.

(3.3).

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

(3.4).

где У* - значение функции Y на k-м наборе; К = 2м — число возможных наборов; М — число входов комбинационного устройства.

Отметим, что в формулу (3.4) входят также произведения тех наборов, для которых У* = 0. Эти произведения равны нулю, не влияют на результат и включены для общности записи.

Практически при составлении структурной формулы в СДНФ по таблице истинности поступают так:

• • записывают логическую сумму, каждое слагаемое которой представляет собой логическое произведение всех входных переменных, а их число равно числу единичных наборов таблицы истинности, на которых У = 1;
• • над каждым слагаемым-произведением ставят номер единичного набора;
• • над теми независимыми переменными каждого слагаемого-произведения, значения которых в рассматриваемом единичном наборе равны нулю, ставят знак инверсии.

Проиллюстрируем рекомендуемый порядок для записи функции Y

Над слагаемыми проставлены номера единичных наборов, к которым они отнесены, а под независимыми переменными — их значения на рассматриваемом наборе.

Совершенная конъюнктивная нормальная форма

Для представления структурной формулы в СКНФ каждому k-му набору переменных ставится в соответствие макстерм М^, представляющий собой логическую сумму всех переменных, причем если в наборе Хт = 0, то переменная входит в сумму в прямом виде, а если Хт— - ъ инверсном. Логическая функция выражается в виде произведения (конъюнкции) макстермов.

(3.5).

Справедливость представления (3.5) вытекает из свойства макстермов: только на одном наборе входных переменных, номер k которого совпадает с номером п (и = 0,1,…, К — 1) макстерма, т. е. п = k. Для рассматриваемого примера (см. У? в табл. 3.4) структурная формула в СКНФ имеет вид