ных Xn,...,Xi используется общее обозначение f (v) =/(л:„,ж,), где v=(Xn,.-,Xi), т. е. совокупность Лременных Хп,...,х, можно р:":-

сматривать как п-мерный вектор. Каждая переменная Хр{р=1, 2.....п)

может принимать только два значения: О и 1, поэтому число всех возможных комбинаций значений Хп, конечно. В общем виде конкретное значение переменной Хр (О или 1) обозначается вр.

Областью определения функции п переменных Хп,xi является совокупность точек п-мерного пространства, причем каждая из точек задается определенной комбинацией знат1ений этих переменных Хп-вп.....д:р=ер,л:1=е!, где ер = 0 или 1 {р= 1, 2,п). Точки, задающие область определения функции f(v), - это v< = (е„,gp,.... ...Bl), где i=en...ep...e], т.е. все точки области определения функции п переменных можно пронумеровать с помощью двоичных «-разрядных чисел* en...ep...ei или с помощью десятичных чисел i. Так как имеется всего 2" различных «-разрядных двоичных чисел, то область определения функции « переменных состоит из 2" точек, т. е. ve{vo, V,, ..,vn A

Для задания функции f(v) следует указать ее значения во всех точках области определения, т. е. задать значения f(vi)=0 или I, где 1=0, 1.....2"-1. Каждой конкретной функции « переменных можно поставить в соответствие 2"-разрядное число, составленное из значений f{vi)=0 или 1 (t=0, 1, ..„2"-1), которые она принимает в 2" точках области определения. Так как имеется всего (2)" различных 2"-разрядных двоичных чисел, то и число различных функций « переменных равно 2 .

Функции п переменных могут зависеть не от всех переменных

Хп.....Xi. Такие функции называются вырожденными. В частности,

функция f(v), равная нулю во всех точках Vj, и функция f(v), равная единице во всех точках v; (г=0, 1,..., 2"-1), ие зависят ни от одной переменной. Эти функции называются константой нуль и константой единица соответственно.

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

f {Хг, Хх) = xS/ Xi - дизъюнкция (ИЛИ);

f (Xj. Xj) = x-Xi - конъюнкция (И);

/ (Хг< x-ii = X2-Xi- функция И-НЕ;

/ (2, Xi) =х\/ Xi- функция ИЛИ-не;

f (2 • i) = х® Xi - сумма по модулю два.

Область определения этих функций состоит из четырех точек: Vo=(0,0), v,= (0,l), V2=(l,0), V3=(l,l), так как. 2" = 22=4.

* Значения ер = Ои 1 являются элементами алгебры логики (булевой алгебры), если они используются в качестве значении переменных Хр. Для этих элемеотов не существует соотношений больше и меньше. В записи же двоичного числа еп...е\ значения ер=й и 1 считаются элементами кольца целых чисел (1>0 и 0<1), Какими элементами являются символы О и 1, всегда ясно из шжтекста или используемых в выражениях операций. На основании этого, например, можно записать, что ер=1-е.

Так как область определения любой функции п переменных конечна (2" точек), то она может быть задана таблицей значений /(Vi)=ai=0 или 1, которые она принимает в точках v,, где i=0,

1.....2"-1. Такие таблицы называются таблицами истинности.

Табл. 1.2, которая составлена в соответствии с аксиомами (1.1)- (1.5) для указанных функций двух переменных, представляет собой таблицу истинности, задающую эти функции.

В крайнем правом столбце помещена функция, заданная в общем виде коэффициентами ai = /(Vi), где i=0, 1, 2, 3. Подставляя различные значения а; = 0 или 1, можно задать все 16 функций двух переменных (22)=2"= 16. В частности, можно получить вырожденные функции: константа нуль (аг=0, г=0...3) и константа единица

(а, = 1, (=0.), а также функции f(x2, xi) =JC2(ao=ai= 1, а2=аз=0) •и/(а:2, Xi)=Xi(aa=a2 = \, а = аз=0), называемые инверсиями переменных.

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

Функция п переменных /(v) называется полностью определенной, если ее значетя /(V()=ai = 0 или 1 заданы во всех 2" точках Vi области определения. Если же значение функции не задано яо-гя бы в одной точке Vi, то она называется не полностью определенной. Не определенное в точке Vi значение функции будем задавать произвольным коэффициентом Ci = Ф (Ф - совмещенные символы О и 1, что указывает на неопределенность значения Ci),i.c. если в точке Vj значение функции не задано, то (vi)=Ci. Не полностью определенные функции можно доопределять произвольным способом, пачагая Ci=0 или 1. Если значения функции не заданы в m точках, то функцию можно доопределить 2™ способами, так как имеется 2™ различных га-разрядных двоичных чисел, соответствующих различным способам доопределения функции в m точках. Таким образом, не определенной в m точках функции соответствует совокупность 2" полностью определенных функций. Если значения функции Qi ие заданы ни в одной точке Vi, то она называется полностью неопределенной и обозначается через h (v) [2].

Принцип и закон двойственности. Алгебра логики обладает замечательным свойством, которое называется принципом двойственности, если имеет место тождество /(v. О, l/V, &)=g(v> О, 1/Vi &), где v=(Xn,...,Xi), то справедливо также тождество /(v, 1, 0/&,

\/)=g(v, 1, 0/&, V), т.е. если в каком-либо тождестве произвести взаимную замену символов О и 1 (если они имеются) и операций дизъюнкции и конъюнкции, то будет получено также тождество. Два тождества, связанные между собой таким образом, являются двойственными. Истинность самого принципа двойственности не доказывается, так как даииый принцип является внутренним свойством алгебры логики (заключен в ее аксиомах).

Законы двойственности (теоремы де Моргана) (1.13) устанавливают способ отыскания инверсных функций, представляющих собой дизъюнкцию и конъюнкцию двух переменных. Клод Шеннон предложил обобщение этих теорем, позволяющее отыскивать инверсию любой функции f(v), где v=(Xn.....Xi). Закон двойственности,

установленный К. Шенноном, имеет вид

/(v/V.&) = /(v/&, V), (1-23)

где v= (л„,jci), v=(Xn.....Xi), т. е. инверсию любой функции f(v)

можно получить взаимной заменой переменных Хр и их инверсий Хр(р=1...п) и операций дизъюнкции и конъюнкции.

Рассмотрим несколько примеров на применение закона двойственности. Пусть f(v)=X2Xl\/XiXl, тогда f(v) = (Xi\/Xj)(Xl\/Xi).

Пусть f(v)=j(x2XiyxX2)X3Xt\/X3Xt]{x2Xi\/xz)\/Xi, тогда f(v) =

•={1{X2\/Xi) (X3VX2)\/X3\/Xl] {X3\/Xl)\/(Xi\/Xl) •Хз)Х.

в дальнейшем часто будут использоваться обозначения: ухр

«*XnV...V-<i; П ХрХп-• -Хи

На основании закона двойственности легко показать, что

ух,пхрпх=\/ р=1 р=1 р=1 р=1

Теоремы разложения и связанные с ними тождества. В теории переключательных функций особо важное значение имеет теорема разложения: любую функцию f(v) можно разложить по переменной Хр в форме

f(xn,...,xp.....Xi) = Xp-f (хп-, ...Qi...-,Xi)S/

•V Xp-f(Xn,...,l,...-.Xi). (1.24)

Эта теорема легко доказывается методом перебора:

а) Xp=0f(xn,...,0.....xi)=0-f(x„.....О.....Xi)\yO-f(Xn.....1.....*i)=.

=f(a:n,..., О.....xi), т. е. при Хр=0 теорема справедлива независимо от

звачений других переменных; "

б) Xp=lf(x„..... 1.....Xi) = l.f(Xn.....0,...,Xi)yi.f(X„..... l,...,JC,)=i

=f(JCn.....1.....xi), T. e. при jCp=l теорема справедлива независимо

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

По принципу двойственности получается двойственная теорема разложения

ЦХп.....Хр.....Xj) = [Хр f(Xn,...i li...,Xi)\lXpSyf{x„,...

....0,...,xi)]. (1.25)