Раздел: Документация
0 1 2 3 4 5 ... 119 1.3. Переключательные функции Любое логическое выражение, составленное из п переменных xn,...,xi с помощью конечного числа операций алгебры логики, можно рассматривать как некоторую функцию п переменных. В соответствии с аксиомами (1.1) - (1.5) функция может принимать в зависимости от значений переменных хр = О или 1 только два значения: 0 и 1. Такие функции являются весьма удобным инструментом для описания, анализа и синтеза переключательных схем, выходные сигналы которых характеризуются лишь двумя уровнями напряжения: высоким (1) и низким (0). В связи с этим такие функции называются переключательными (термин "переключательная" обычно будем опускать, так как никакие другие функции рассматриваться не будут). Для функций п переменных xn,...,xi будем использовать общее обозначение f(v) = /(хп,..., х\), где v - (х„,..., xi), т. е. совокупность переменных xn,...,xi можно рассматривать как n-мерный вектор. Каждая переменная хр (р = 1,2,..., п) может принимать только два значения: 0 и 1. Поэтому число всех возможных комбинаций значений хп,..., хх конечно. В общем виде конкретное значение переменной хр (0 или 1) будем обозначать через ер. Для обозначения произвольных десятичных чисел будем использовать символы г, j и т. п., а двоичные числа будем записывать в виде еп ... ер ... ej, где ер = 0 или 1. Равенства для десятичных и двоичных чисел будем записывать, опуская индекс, указывающий основание системы счисления: г = еп ... ер ... е\. Значения ер = 0 и 1 являются элементами алгебры логики (булевой алгебры), если они используются в качестве значений переменных хр. Для этих элементов не существует соотношений больше и меньше. В записи же двоичного числа еп ... ej значения ер = 0 и 1 считаются элементами кольца целых чисел (1 > 0 и 0 < 1). Какими элементами являются символы 0 и 1, всегда ясно из контекста или используемых в выражениях операций. На основании этого, например, можно записать, что ёр = 1 - ер (в левой части используется логическая операция отрицания, а в правой - арифметическая операция вычитания). Областью определения функции я переменных хп,...,х\ является совокупность точек n-мерного пространства, причем каждая из точек задается определенной комбинацией значений этих переменных: где ер = 0 или 1 (р = 1,2, ...,п). Точки, задающие область определения функции f(v), будем обозначать через V{ = (еп,..., ер,..., ei), где г = еп ... ер ... ех, т. е. все точки области определения функции п переменных можно пронумеровать с помощью двоичных n-разрядных чисел en...ep...ei или десятичных чисел г. На основании (1.23) имеется 2" различных n-разрядных двоичных чисел, поэтому область определения функции п переменных состоит из 2П точек, т. е. v G {l/0,J/b...,2"-l}- Для задания функции f(u) следует указать ее значения во всех точках области определения, т.е. следует задать значения f(u{) = 0 или 1, где г = 0,1,...,2" - 1. Каждой конкретной функции п переменных можно поставить в соответствие 2п-разрядное число, составленное из значений /(»>,•) - 0 или 1(г = 0,1,..., 2" - 1), которые она принимает в 2" точках области определения. Так как имеется всего 22 различных 2П-разрядных двоичных чисел, то и число различных функций п переменных равно 22". Функции п переменных могут зависеть не от всех переменных £„,...,Хх. Такие функции называются вырожденными. В частности, функция fo(v), равная нулю во всех точках f,, и функция /i(), равная единице во всех точках V{ (г = 0,1,...,2" - 1), не зависят ни от одной переменной. Эти функции называются константой нуль и константой единица соответственно. Значительный интерес представляют следующие невырожденные функции двух переменных х2 и хь названия которым даны по используемым для их образования операциям алгебры логики: /(х2,Х!) = х2 V X! - дизъюнкция (ИЛИ), /(x2,Xi) = Х2 хх - конъюнкция (И), f(x2,x\) = х2 • хх - функция И-НЕ, f(x2,xi) = х2 V X! - функция ИЛИ-НЕ, /(x2,xi) = х2 8 хх- сумма по модулю два. Область определения этих функций состоит из четырех точек: Щ = (0,0), i/i = (0,1), и2 = (1,0), из = (1,1), поскольку 2п = 22 = 4. 2Пухальский Г. и., Новосельцева Т. Я. Так как область определения любой функции п переменных конечна (2" точек), она может быть задана таблицей значений f{yi) = а, = 0 или 1, которые она принимает в точках Vi, где i = 0,1,..., 2" - 1. Такие таблицы называются таблицами истинности. Табл. 1.3, которая составлена в соответствии с аксиомами (1.2) - (1.5) для указанных выше функций двух переменных, представляет собой таблицу истинности, задающую эти функции. В предпоследнем столбце помещена функция, заданная в общем виде коэффициентами = f(V{), где г = 0,1,2,3, а в последнем столбце - инверсная функция, заданная коэффициентами а, = f(vt). Подставляя различные значения di = 0 или 1, можно задать все 16 функций двух переменных (22 = 24 = 16). В частности, можно получить вырожденные функции: Д*2, zi) = х2 (а0 = ах = 1, а2 = а3 = 0), /(x2,xi) = х, (а0 = а2 = 1, ах = а3 = 0), называемые инверсиями переменных (в табл. 1.3 показаны вырожденные функции /о(*>) - константа нуль и fi{v) - константа единица). Таблица 1.3. Функции двух переменных
Функции двух переменных исключительно важны в силу того, что любая функция п переменных может быть получена из них методом суперпозиции [7] - подстановкой этих функций вместо переменных в другие функции. Такая подстановка возможна на основании того, что области значений функций и переменных совпадают (0 и 1). Функция п переменных f(v) называется полностью определенной, если ее значения f(vi) = а, = 0 или 1 заданы во всех 2™ точках Vi области определения. Если же значение функции не задано хотя бы в одной точке i/j, то она называется неполностью определенной. Не определенное в точке I/, значение функции будем задавать произвольным коэффициентом с,- = Ф (Ф - совмещенные символы 0 и 1, что указывает на неопределенность значения с,), т.е., если в точке j/, значение функции не задано, то f(v{) = с,. Неполностью определенные функции можно доопределять произвольным способом, полагая с = 0 или 1. Если значения функции не заданы в тп точках, то функцию можно доопределить 2т способами, так как имеется 2т различных поразрядных двоичных чисел, соответствующих различным способам доопределения функции в тп точках. Таким образом, не определенной в то точках функции соответствует класс из 2т полностью определенных функций. Если значения функции не заданы ни в одной точке j>,, то она называется полностью неопределенной к обозначается через h [10]. Теории переключательных функций посвящено много работ, среди которых следует выделить [5, 7, 8] как наиболее фундаментальные. 1.4. Принцип и закон двойственности Алгебра логики обладает замечательным свойством, которое называется принципом двойственности: если имеет место тождество f(v, 0,1/V, &) = g(v, 0,1/V.&),(1.24) где v - (хп,..., хх), то справедливо также тождество /(*/, 1,0/&, V) = «7(1/, 1,0, /&, V),(1.25) т.е., если в каком-либо тождестве произвести взаимную замену символов 0 и 1 (если они имеются) и операций дизъюнкции и конъюнкции, то в результате также будет получено тождество. Два тождества, связанные между собой таким образом, называются двойственными. Соотношения (1.24) и (1.25) позволяют доказывать только одно из тождеств, второе же непосредственно следует из этих соотношений. Если выражения (1.24) и (1.25) совпадают, то они называются самодвойственными. Истинность самого принципа двойственности не доказывается, так как данный принцип является внутренним свойством алгебры логики (заключен в ее аксиомах). Законы двойственности (1.13) определяют способ отыскания инверсных функций, представляющих собой дизъюнкцию и конъюнкцию двух переменных. К. Шеннон предложил обобщение этих теорем, позволяющее отыскивать инверсию любой функции f(v), где v = (хп,..., хх). Закон двойственности, установленный К. Шенноном, имеет вид 7(I7M0 = /(f/&,v),(1.26) где v - (хп, ...,xx),v = (хп,.. .,xi), т.е. инверсию любой функции f(v) можно получить взаимной заменой переменных хр и их инверсий хр (р = 1, 2,..., п) и операций дизъюнкции и конъюнкции. Докажем теорему (1.26). Пусть задана полностью определенная функция f(v/V,&), где v = (x„,...,xi), которая в точках v{ -(е„,..., ci) имеет значение 0 (» = е„ .. .ех), а в точках uj = (еп,..., е[) - значение 1 (j = еп ...е[; jI ф j; общее число точек равно 2"), т.е. /(J/,7V,&) = 0, /(/V,&) = 1. Так как точки Vi = (e„,...,ep,...,ei) и i/j = (е„,..., ер,..., е[) представляют собой комбинации символов 0 и 1 (ер = 0 или 1, е =0 или 1), то по принципу двойственности /(F,/&,V) = 1, /(/&,У) = 0, где F, = (ё„,...,ёх), = (ё(,,... Очевидно, что /(i/./V,fe) = 1, /te/V,fe) = 0, /(/V, &) = /(F.-/&, V), /(i/j/V, &) = /(Fj/fc, V). Из последних двух соотношений следует, что /(y/V,fe) = /(F/t,V), так как равенства выполняются для всех 2" точек 1/ = и Рассмотрим два примера на применение закона двойственности. Пусть f(v) = х2ххУх2хх, тогда f(v) = (х2 Vхх) (х2 V хх). Если /(г/) = [(х2хх V aaai V ar3zi] • (х2хх V х3) v х4, то /(i/) = {[(х2 V хх)(х3 V х2) Vx3V хх](х3 V ajj) V (х2 V хх)х3}х4. Чтобы избежать ошибок при получении инверсной функции, следует учитывать все неявные скобки, положение которых задается иерархией операций конъюнкции и дизъюнкции. В дальнейшем часто будут использоваться обозначения пп У хр = хп V ...V xlt Л Хр = хп---хх.(1.27) p=iр=1 На основании закона двойственности легко показать, что пп~пп V хр = П *р> П хр = V *г-(1-28) р=1 р=1 р=1 р=1 Выражения (1.27) и (1.28) позволяют в компактной форме записывать специальные функции без ограничения числа переменных. 1.5. Теоремы разложения В теории переключательных функций особо важное значение имеет теорема разложения Шеннона: любую функцию f(v) можно разложить по переменной хр в форме /(*„, ...,хр,...,хх) = хр- f(xn,.. -, 0,.. -, *i)V 2дч Ухр- f(xn,...,l,...,xx). Эта теорема легко доказывается методом перебора: а)хр = 0 =» /(&„,...,0,...,a?i) = 0- f(xn,...,0,...,xx)v V0-f(xn, ...,l,...,xi)=> f(xn,..., 0,..., xi) = f(xn,..., 0,..., xx), т. е. при xp = 0 получилось явное тождество, а значит, теорема справедлива независимо от значений других переменных; б)Хр = 1 => /(£„,..., l,...,Zl) = I •/(£„,...,0,..., Zl)V Vl-/(ar„,...,l,...,a;i) => f(xn,...,l,...,xx) = f(xn,...,l,...,xx), т. е. при хр = 1 тоже получилось явное тождество, а значит, теорема справедлива независимо от значений других переменных. Из этого следует, что теорема истинна при любых значениях всех переменных. По принципу двойственности получается двойственная теорема разложения: /(*»,..., a;p,...,a;i) = [хр V /(х„,..., 1,..., хх)}& q 30) %v/(i„,...,o,..,4v • Теорема разложения (1.29) является удобным инструментом для преобразования логических выражений, содержащих операцию сумма по модулю два, так как в ряде практических случаев позволяет свести данную операцию над функциями к простейшим операциям (1.20) и (1.22), например: х2хх 8 (х3 V хх) 8 х3хх® (х2 V xi) = xi-[х2-0 8 (а?з V 0) Ф х3-0® 8(х2 V 0)] V хх • [х2 • 1 8 {хз V Т) 8 х3 1 8 (х2 V Т)] = = xi(0 8 1 8 0 8 1) V хх(х2 ®х3®х3ф х2) = хх 1 V хх 1 = 1. Приведем доказательство дистрибутивного закона (1.21) для операции сумма по модулю два относительно операции конъюнкции: х у ® х • z = х (Ъ у ®Ъ • z)V х (I у ®\ z) = х • (у ® z). С теоремой разложения (1.29) связаны тождества Xp-f(xn,...,Xp,...,xx) = Xp-f(xn,...,Q,...,xl), 1 31ч хр f(xn,..., Хр, ..., хг) = хр f(xn,..., 1,..., хх). / 0 1 2 3 4 5 ... 119
|
