518 Б70 УДК 518(075.8) Рецензенты: Академик АН БССР, доктор физико-математических наук, про- фессор Д. А. Супруненко. Зав.. кафедрой электронных математических машин Белорусского государственного университета им. В. И. Ленина, кандидат физико- математических наук, доцент Н. Н. Поеное. Рекомендовано Министерством высшего и среднего специального образования БССР в качестве учебно-вспомогательного пособия для студентов математических и инженерно-технических специальностей высших учебных заведений. 20204—040 М304(05)—75 33—75 © Издательство «Вышэйшая школа», 1975 г. ПРЕДИСЛОВИЕ Учебные курсы по вычислительным и автоматическим устройствам предусматривают обязательное изучение основ бу- левой алгебры. Однако в рамках булевой алгебры может быть описано не все множество переключательных схем, а только не- значительная его часть, к которой обычно не принадлежат оптимальные схемы. В этой связи и возникла необходимость рас- смотрения не только булевых, но и арифметических функций, т. е. таких, которые принимают вместе со своими переменными только целые неотрицательные значения. Целые числа в рассматриваемой теории арифметических функций играют роль символов, номеров, которыми обозначают- ся различные ситуации, поэтому интерес представляют те свой- ства арифметических функций, которые инвариантны относи- тельно перенумеровки значений как самой функции, так и ее пе- ременных. Алгебраическое описание арифметических функций неэффективно, так как алгебраические операции не инвариантны относительно перенумеровки. Нам представляется, что наиболее естественным и эффектив- ным способом является задание арифметической функции граф- схемой. Граф-схемное представление арифметических функций позволяет с единых позиций рассматривать широкий круг вопро- сов дискретного управления. Эта книга представляет собой существенную обработку про- читанных автором на математическом факультете Минского педагогического института им. А. М. Горького спецкурсов: «Ко- нечные автоматы и машины Тьюринга», «Синтез переключатель- ных схем», «Конечная модель обучения», «Граф-схемы арифме- тических функций». Наиболее интенсивно исследования по граф-схемам проводи- лись в Минске. Этим объясняется то, что значительную часть книги составляют итоги исследований автора и его учеников. Книга рассчитана на широкий круг читателей, работающих в области кибернетики, вычислительной техники и автоматики. Для чтения книги не требуется специальных математических Предисловие знаний. При первом чтении можно следовать приведенной схеме зависимости глав книги. Автор считает своим долгом выразить благодарность акаде- мику АН БССР, доктору физико-математических наук, профес- сору Д. А. Супруненко и заведующему кафедрой электронных математических машин Белорусского государственного универ- ситета им. В. И. Ленина, кандидату .физико-математических наук, доценту Н. Н. Поснову за проведенную работу по рецензи- рованию рукописи и ряд ценных замечаний и рекомендаций, ко- торые были учтены при окончательной доработке книги. Все критические замечания и пожелания, направленные на ^^ейшее У^4111^^ книги, просим присылать по адресу 22UbOO. Минск, ул. Кирова, 24, издательство «Вышэйшая школа». Автор Глава 1 АРИФМЕТИЧЕСКИЕ ФУНКЦИИ § 1.1. ОПРЕДЕЛЕНИЕ И ПРИМЕРЫ АРИФМЕТИЧЕСКИХ ФУНКЦИЙ •к Функция называется арифметической, если как переменные, так и сама функция принимают только нулевое и целые положи- тельные значения. Приведем несколько примеров. Пример 1.1. Электрическая цепь с тремя выключателями а, Ь, с и двумя лампочками функционирует следующим образом: 1) первая лампочка горит, когда включены любые два выключателя или все три; 2) вторая лампочка горит при включении только одного выключателя а или с. Работу электрической цепи можно описать арифметической функцией y==f(a, Ь, с). Условимся, что аргумент я==1, когда выключатель а включен, и в==0 в противном случае. Аналогичные условия примем для аргументов Ь, с: у=\ будет означать, что первая лампочка горит, у=2—что вторая лампочка горит, ==0, D^=0, u;i=0, &1^0. Тогда решением будет у=— их— произвольное число. ?>=0, ?>.c==0, 0^=0, г>1 = 0 (конечно, с^-^0).. В этом случае реше- ния нет. Укажем арифметическую функцию Р == f (р^ р^, ру, ру), которая опре- деляет логику решения системы уравнений. Переменные и функция опреде- ляются так: Pi= 1, если D ф 0; I1' если ^ ^-0; 0, если D =- о; Р2= io, если Dx =0; 1, если Д1 + о; если Ь^О; о, если Д1 о; Pl= f1'to, если b,-- =0, а функция принимает значения Р == 0, когда система уравнений не имеет решения; Р = 1 — решения находят по формулам х =——, у = ——; 2 — решение находят по формуле х = —\-——"-, где у — произволь- fl'1 P ное число; P = 3 — решением будет у = — и х — произвольное число. Функция P=f(p^, р^ рз, р^ задана таблицей (табл. 1.2). Прочерк в столбце означает, что возможно любое значение: 0 или 1. При решении человеком системы линейных уравнений арифметическая функция, характеризующая логику решения, не определяется явно. Однако при решении на ЭВМ она обязательно задается в виде программы. Пример 1.3. На автобазе имеются грузовые машины общего назначения и рефрижераторы. Требуется найти арифметическую функцию, дающую рас- пределение средств транспорта в соответствии с поступившими заявками §1.1. Определение и примеры Таблица 1.2 Р Pi Рг Рз Pt Р 1 — — — 1 0 1 — — о 0 0 1 — 2 0 о о 1 3 0 о о о 0 и с учетом категории груза. Функция должна указать тип транспортных средств для каждой заявки. Распределение средств транспорта по заявкам должно производиться с учетом следующих обстоятельств. 1. Скоропортящиеся грузы должны перевозиться на рефрижераторах, остальные — на грузовиках, причем срочные — в первую очередь. 2. Если на базе рефрижераторов нет, то заявка на перевозку скоропортя- щихся грузов не может быть удовлетворена. 3. Если грузы срочные и непортящиеся, но на базе имеются только рефри- жераторы, то для их перевозки могут быть использованы рефрижераторы. 4. Если все машины парка в разъезде, то заявки не могут быть удов- летворены. Возьмем переменные pi, p2, pa, pi и функцию y=f(pi, p2, рз, pi) с такими условиями: /?i = 1, если на базе есть свободные грузовики, в противном случае Pi=0; ра = 1, если на базе есть свободные рефрижераторы, иначе рд == 0; ря= 1, если груз требует срочной перевозки, иначе рз=0; Pt = 1, если груз скоропортящийся, иначе р^ = 0; 4=0, если заявка не может быть удовлетворена; у == 1, если следует использовать грузовик; у =2, если следует использовать рефрижератор. Переменные pi, p2 определяют наличие транспорта, а переменные рз, pi —• категорию груза. Составим теперь по условию задачи табл. 1.3 для функции y=f(pi, p2, рз, pi). Она будет содержать 16 строк. Строки для переменных заполняются Таблица 1.3 № строки Pi Ръ Рз Ри. У № строки Pi Ръ Рз Pi У 1 0 0 0 0 0 9 1 0 0 0 1 2 0 0 0 1 0 10 1 0 0 1 0 3 0 0 1 0 0 11 1 0 1 0 1 4 0 0 1 1 0 12 1 0 1 1 0 5 0 1 0 0 0 13 1 1 0 0 1 6 0 1 0 1 2 14 1 1 0 1 2 7 0 1 1 0 2 15 1 1 1 0 1 8 0 1 1 ' 2 16 1 ! 1 1 2 Гл. 1. Арифметические функции заранее, а затем для каждой строки находят значение функции. В первых восьми строках pi=0, т. е. свободных грузовиков в парке нет. Следовательно, речь может идти только о наряде на рефрижераторы. В столбце рч. в 1—4-й стро- ках рг==0, т. е. рефрижераторов тоже нет. В соответствии с этим в 1—4-й стро- ках проставлено у=0. В 5—8-й строках рг=1, следовательно, в парке есть свободные рефрижераторы. В 5—6-й .строках рз=0—грузы несрочные. В 5-й строке по признаку /ц==0 груз допускает продолжительное хранение. Поэтому целесообразно подождать возвращения грузовиков и заявку не удов- летворять. Проставляем г/=0. В 6-й строке р4=1—наряд на рефрижератор. Но, согласно условию задачи, при отсутствии грузовиков срочный груз пере- возится на рефрижераторах. В соответствии с этим в столбце у проставляем число 2 и в 7-й, и 8-й строках. Проанализируем логические комбинации в 9—16-й строках. В них pi=l, в 9—12-и строках рг=0. Следовательно, могут быть предоставлены только гру- зовые машины. Вследствие этого заявки на перевозки скоропортящихся грузов не могут быть удовлетворены. Тогда в строках 10-й и 12-й проставляем число 0, а в 9-й и 11-й—число 1. Строки 13—16-я означают наличие обоих типов машин. Поэтому там, где р4==1, проставляем число 2, а где />4=0,— число 1. Пример 1.4. Функция определяется следующим образом: если х < о; если 5<;с < 11; если х > 11. (а) (б) (в) Укажем арифметическую функцию, определяющую логику вычисления/^). Возьмем переменные pi, р^, ру, рд и функцию Р = F (р^, ру, ру, р^) с такими условиями: Р= { 1, если х < 5; СО, если ж<2; о, = { р, = < 2, если 5 < х < 11; •1 11, если ж > 2; 2 - ' [3, если х>11: Рз= 'О, если х = 3: (0, если х = 7; . 1, если х ф 3; 11, если х =f= 7. 1. означает, что вычислять f (х) следует по формуле (а); 2. означает, что вычислять f (х) следует по формуле (б); 3. означает, что вычислять f (х) следует по формуле (в); О—функция f (х) при данном х не существует. Из условия для f (х) получим для P=F(p^, р^, ру, р^) табл. 1.4. Про- черк в столбце означает любое значение^переменной. Следует подчеркнуть одну характерную особенность рассмотренных при- меров: как переменные, так и функции не определяли значения каких-то вели- чин. Можно было вместо значений 0,1 брать любую другую пару чисел. И вообще, не обязательно было брать числа для переменных и функций. С таким же успехом можно было использовать не О, 1, 2, 3, а какие-нибудь четыре буквы или другие различаемые символы. Выбор целых чисел при рас- смотрении подобных функций обусловлен только желанием иметь дело со стандартным множеством. § 1.2. Независимые переменные Таблица 1.4 Pi Рз Р2 Pi Р 0 — —— — 0 1 0 —— — 0 1 1 1 0 0 1 1 1 1 1 1 1 2 1 2 1 1 3 1 3 Хп-\ § 1.2. НЕЗАВИСИМЫЕ ПЕРЕМЕННЫЕ Общие сведения. Независимые переменные XQ, х^, ... , I f\ 1 Г» О 1 принимают только значения из множества О, 1, 2, 3, 1. На- пример, х == ( 2, 1, 5, 0}. Запись a^Cx^.b, где а, Ь—целые числа, означает, что х принимает только целые значения из отрезка [а, Ь]. Длина отрезка равна Ь—а, а целых точек будет b—a+ 1. Пусть 0 •< Хц < go — 1, 0 < х^ -< gi — 1. На координатной плоскости точки (л-о, A"i) образуют целочисленную решетку. В общем случае для 0<.^.-^g,—1 точки х = (Хц, х^, ..., Xn-i) определяют целочисленную решетку в га-м пространстве. При двоичных переменных 0 <1 х, ^ 1 решетка содержит только одну ячейку, т. е. точки (Хц, х^, ... , Хп-\) являются вершинами еди- ничного куба в тг-м пространстве. Фиксированное значение переменных обозначаем буквами а, р, у, ... Будем считать, что набор а == (йд, а^, . .. , ctn-i) предшествует набору р = (ро, pi, ... , pn-i), если существует такой номер k, что а; = р, при i > k, но а<: < рд. Например, набор (2, 0, 3, 0) предшествует набору (1, 4, 3, 0). Набор а непосредственно предшествует набору р, если нет набора у, который следует за а и предшествует р. Такие наборы назовем соседними. Из определения следует, что существует такой номер k, что а, = р, при f > k, рй = ад + 1 и р, = 0, а, = g, — 1 для i < k. Для go =4, gi = 2, g'2 = 3, gy = 3 укажем несколько пар соседних наборов: а = (2, 1, 0, 1), р = (3, 1, 0, 1); а = (3, 0, 1,2), р=(0, 1, 1, 2); а=(3, 1, 1, 1), р=(0, О, 2, 1). Пусть х^ принимают g, значений. Число различных наборов (хо, JCi, . . . , Xn-i) будет Rn=::gogl•••gn-l• (1.1) В самом деле, любой набор (хц, х^, ... , Хп-ч, -v/i-i) можно получить из набора {Ху, х^, . . . , Хп-ч) приписыванием Хц-\, т. е. 10 Гл. 1. Арифметические функции каждый набор (х„ л-х, ... , Хп-^) порождает g„_, наборов (^, л-i, ... , ^„_2 ,_v„_i). Поэтому 7?„ = /?„_! g„_i. так как /?i = go, то получаем ^„ = gogi... g„_i. Если все g, = g, то /?д = g". Преобразование независимых переменных. Пусть 0<;c, то при делении U на go в остатке получим Хц. fJ __ д- Возьмем теперь U' = ————°— = х^ + gi^ + • • • + go -}- gig2...gn_2A'n—i. Чтобы найти Jfi, нужно повторить операцию деле- ния числа U' == ———0- на gi. Аналогично вычисляются осталь- §о ные Xi. Итак, Ху, х^, х^, ... , Xn—i определяются как остатки при делении последовательных частных на go, gi, ... , gn-i. Определим, например, набор для U = 148 при go =5, gi == 3, ga =2, gs = 6. Проверяем вначале выполнение неравенства 149< 5-3-2-6. Затем проводим последовательно деление: 148=5-29+3; 29 ==3-9+2; 9=2-4+ 1; 4=0-6+4. Полученные остатки определяют набор (3, 2, 1, 4). Так как преобразование (А) устанавливает взаимно-однозначное соответствие между целыми числами из отрезка 0 -^ U <1 бели 0 <:-<'(-< <; gi — 1, при необходимости будем интерпретировать как запись числа в системе счисления (gn-i, gn-z, •.. , gi, go). § 1.3. ТАБЛИЧНЫЙ СПОСОБ ЗАДАНИЯ АРИФМЕТИЧЕСКИХ ФУНКЦИЙ Табличное задание функции. Табличный способ задания функ- ций удобен тем, что по значениям переменных можно находить значения функции, не выполняя вычислительных операций. Таблица для функции, зависящей от п переменных, содер- жит п столбцов для значений переменных и один столбец для значений функции. Число строк таблицы совпадает с числом на- боров переменных, для которых функция определена. Если в таб- лице функции f(xo, Xi,. .. , Xn-i) переставить столбцы переменных или строки, то получим другую таблицу для f{xo, х\, ... , Xn-i)- При подстановке в арифметическую функцию констант вместо некоторых переменных получают функцию от оставшихся пере- менных. Подстановка Хг==аг соответствует выделению в таблице строк с Xi=ai. Отсюда следует простая процедура получения функции при любой подстановке констант. Пример 1.5. Табл. 1.6 задает y=f(Xy, х^, х^). Таблицы 1.6а, 1.66, 1.6в определяют функции (pi, фз, (pg, полученные подстановкой соответ- ственно Хц = 0; Xi --= 2; х„ = 0, л-з = 1. Таблица 1.6 X» ч Ч У •«•0 0 о о 2 1 0 о 1 3 1 о 1 о 3 1 о 1 1 3 1 о 2 1 2 1 Xi Хг У 0 0 3 2 0 2 1 0 2 1 1 3 2 1 2 Таблица 1.6а Xl Х2 -У2, Xi->-uo, Xy-^Uz. Таблица 1.86 Уг М i <г У 0 / < \ 7 -0—— —г-- - —-Э— 1 о , 4- -f—— —t ?-- —ff- В случае, когда переменные UQ, u.i, . . . , Un-i совпадают с Хо, Xi, ... , Xn-i, вместо «переименование переменных» будем гово- рить «перестановка переменных» (без отождествления или с отождествлением). S 1.3. Табличный способ задания 15 Весьма часто приходится вместо одной функции y=f(xe, Xi, ... , Xn-i) рассматривать k функций yi=fz(xo, Xi, ... , Xn-i) (l^t'^fe), где Уг является f-м разрядом числа у. Если функция y==f(xo, Xi, ... , Xn-i} задана таблицей, то таблица для всех г/i находится весьма просто. Для этого достаточно в столбце у запи- сать значения функции в требуемой системе счисления. Например, табл. 1.9а определяет две функции: yo=fo(xo, Xi, Xz), yi==fi(xo, Xi, Jz), которые являются двоичными разрядами функции y=f(xo, Xi, Xz), заданной табл. 1.9. Таблица 1.9 Таблица 1.9а л-о Xi Х2 У 1 0 4 3 0 2 0 0 3 1 2 2 5 2 3 1 0 1 1 0 X» Xl •^2 • • • , Po) . В первой таблице a предшествует (3, во второй—наоборот. Возьмем произвольный набор у. Если у^а и v^P. сложность ^ выборки у в первой и второй таблицах одинакова, т. е. C(Ti, у) == . =С(Т'г,, у}. Пусть у=а. Очевидно, что C(Ti, а) <^С(Тг, а). Вычис- лим С(Тг, a)—C(Ti, а). Пусть первые k разрядов а и р равны, , т. е. ai=pi, ct2=p2, . . . , OA=Pft и ah+i^^h+i. Во второй таблице, чтобы дойти до строки а, нужно сделать -' еще k-\-\ проверку, следовательно, С(Тч, a}==C(Ti, a)+(^+l)-^ Если у=Р, то по аналогии С(Тг, Р) ==C(Ti, p)-(^-)-l). Отсю- , да следует: C(Ti, a)+C(Ti, р) ==С(Тг, а)+С(7'з, р). Так как.' С(Г1,у) =0(7-2, у) приу^а,У^Р,тоС(Л)=С(Г2). Так как любое расположение строк можно получить, меняя местами только рядом расположенные строки, то теорема доказана. Следствие. Сложность C(T') обработки таблицы не зави- сит от принятого порядка проверки строк. В самом деле, любой порядок проверки можно свести к дан- ному, изменив только соответствующее расположение строк. Обозначим через Ni(T,a) число проверок в f-м столбце таб- лицы Т при выборке строки а, а суммарную проверку t'-ro столб- ца — через Ni (Т) = 2 N: (Т, а). а. Лемма 1.2. Суммарная проверка данного столбца не зависит от порядка расположения строк в таблице. Доказательство. Эта лемма доказывается так же, как и теорема 1.1. Если у^а и у^Р> то ^i(Ti, у) =Ыг(Т^ у). Пусть у==а и первые k разрядов а и ? равны. Если i~>k, то Л^(Гд, а) == =Ni{Ti, р); если asS:k, то Ni(Ts, a) ==Ni(Ti, a)+l. Аналогично, при i'>k имеем Ni(Tz, Р) =Ni(Ti, р) и при is^k Ni(Tz,^)= =^.(Г1,р)-1. Следовательно, //.(Га, а)+Л^(Г2, р) ==Nz(Ti, a)+Ni(Ti, p). Учитывая, что Ni(Tz, у) =Nf(Ti, у) при у^а, у^Р. получаем Ni(T2)==Ni(T^). Суммарная проверка No (Г) столбца Хц будет 1 + 2 + 3 + П /Г» 1 1\ + ... + R = —•———'-, где R — число строк в таблице. Для упрощения вычисления Л^ (Т) выберем такое расположе- ние строк, при котором в столбце Ху вначале следуют г нулей, затем — s единиц (/• + s = ./?). Для набора а, в котором а.о = 0, проверяется только верхняя часть столбца л-i, т. е. г строк, а при а.у = 1—нижняя часть столбца, т. е. s строк. Очевидно, N, (Т) = 2Л^ (Г, а) = ^±-1^ + (s^1^. § i.3. Табличный способ задания 19 В итоге N, (Т) = (r-s)2 JR_ 2 При перестановке столбцов таблицы Т сложность С (Г) может измениться, о чем свидетельствует теорема 1.2. Пусть таблица Т' получена из таблицы Т перестановкой по- следних двух столбцов; С(Т) и С(Т'}—их суммарные слож- ности. Число нулей и единиц в столбце л"о равно соответственно Га, So, а в столбце Xi их ri, Si (ro+so==/'l+sl=^'^ где R—число строк в таблице). Теорема 1.2. Имеет место условие (^(г)-^^-!-^/.,^)2-^^)2}. Доказательство. Обозначим через Na(T,a) номер строки a= (an-i, an-2, • • • , cii, ao) в таблице Т, считая верхнюю строку первой. Вообще говоря, No(T, а) ^=а. При поиске строки a компонент ao проверяется No(T,a} раз. В строках р, в которых Ро^ао, дальнейшая проверка не производится. Обозначим через Ni(T,a) число строк, расположенных выше а, включая и стро- ку и, в которых ро=ио. Очевидно, что компонент ai проверяется Ni(T,a) раз. Пусть число проверок компонентов 02,..., cin-i строки а будет Р(Т,а). Итак, сложность С(Т,а) выборки стро- ки а в таблице Т равна С{Т, а) =М)(Г, a}+Ni(T, a)+P(T, a). Возьмем таблицу Т', полученную из Т перестановкой столб- цов ^о, Xi. Очевидно, что No(T, а) ==Мо{Г, а) и Р{Т, а) =Р(Г, а). Поэтому С {Т, а) -С {Г, а) =Л^(Т, a}-Ni(T', a). Так как суммарная сложность С (Т) обработки таблицы С (Т) = 2С (Г, а), то а С (Г) — С (Г) = 2Wi (Г, а) — 2Wi (Т', а). (X tt Следовательно, С (Т) — С (Г') = -^ ((го — So)2 — (?-i — Si)2}. Разность | /-о— so\ характеризует информативность отдельного столбца Хо: чем меньше [/"о—So], тем больше содержится в столб- це информации. Теорема 1.3. Суммарная сложность обработки полной табли- цы не зависит от порядка следования столбцов. Доказательство. В самом деле, полная таблица от п переменных содержит 2" строк. Если в ней поменять местами столбцы, снова получим таблицу, состоящую из 2" строк, но рас- положение строк в полученной и данной таблицах будет различ- 2* 20 Гл. I. Арифметические функции ным. Таким образом, перестановка столбцов таблицы сводится к перестановке ее строк, а для последнего утверждение доказано (теорема 1.1). Через С (га, а) обозначим сложность выборки строки а в пол- ной таблице от п переменных, заданной в стандартной форме. Числовой эквивалент а строки (cin-i, ... , 0.1, ао) совпадает с но- мером строки,начиная с нулевой. Теорема 1.4. Для С (п, а) имеет место формула п-1 С(п, а) а ~? +га. Доказательство. Младший разряд Хц проверяется во всех строках, от нулевой до строки а включительно, т. е. а + 1 раз. После проверки Хц строки, у которых Хо^а^, исключаются. Если зачеркнуть эти строки и столбец Хц, получим таблицу от/г — 1 переменных, в которой нужно найти строку а*, где а*—число, полученное из числа а зачеркиванием младшего разряда а„. Поэтому для С (п, а) имеет место равенство С (п, а) = (а + 1)+ -)- С (п—1, а*). Очевидно, а* = —— , где квадратная скобка L " J означает взятие целой части. Следовательно, для С (п, а) спра- ведлива рекуррентная формула C(ra,a)=(a+l)+c(ra-l, (а)). \ L " J/ Применяя га—1 раз рекуррентную формулу, получим С(п, а)=(а+ 1)+ (f^-]+ l) + ft——] + l) + \. I z J / \L"J / + ... + (h-H или n—l С(п, ")=^ > -о а '2Г +га. Например, С (4, 9)= + + + + 4 = 20 д. о. ^ST^S^ST» —————— <- полно» § 1.3. Табличный способ задания 21 Теорема 1.5. Для С (га) имеет место формула C(ra)=22"+(ra—2)2"-l. Доказательство. В самом деле, 2»-1 2—1 n—l ^1 а_ Ч1 C(ra)=^C(ra,a)=S(S[^ а^О и=0 1'=0 2"-1 п-1 , _ п-1 2"-! ^[^———^ " -• " l- i .'——Л п—Л a 27 +.}= - Н-га-2". а-О 7^0" '- - J i=0 a.=0 *- '" -J Воспользуемся для вычисления первой суммы формулой а 1 _ bk (fe—1) kb-l ^ a^O В нашем случае 6=2', k = 2"-1, следовательно, (»)=S 1=0 С(га)= 2n-{ (2n-i—l) = 2"-1 (2"+' — 2 — га) + га • 2". Итак, сложность обработки полной таблицы от га двоичных переменных С (га) = 22" 4- (га — 2) 2"-' д. о. и не зависит от порядка следования строк и столбцов. Все изложенное выше для двоичных переменных непосред- ственно обобщается для общего случая. Приведем только фор- мулы сложности. Пусть переменные Xi принимают целые значения из отрезка Os^,s=?g-l. Будем считать, что сложность сравнения двух значений пере- менного Xi равна log2 g двоичных операций. Обозначим через C(g,n,a) сложность выборки строки а из заданной в стандартной форме полной таблицы от п переменных значности g. Сложность выборки определяется формулой C(g,ra,a)=(V[__]+„)iog^. (1.2) t-O L J Суммарная сложность С (g, га) = 2 С (g, га, а) определяется a формулой Cte,„)=(i^?^+^}iog,g. 0.3) 22 Гл. 1. Арифметические функции Оценка сложности выбора наибольшего значения. Когда не существует эффективного алгоритма решения задачи или такой алгоритм неизвестен, в задачах о конечных множествах поиск решения проводят полным перебором вариантов. Типичной такой задачей является задача о выборе максималь- ного значения для заданной конечной последовательности чисел. Иначе говоря, для арифметической функции y=f(x), определен- ной на конечном отрезке, требуется найти максимальное значе- ние. Если относительно f(x) неизвестно никаких свойств, которые можно использовать для разработки эффективного алгоритма поиска максимума, то решение задачи возможно только с по- мощью алгоритма полного перебора. Итак, полагаем, что задано конечное множество чисел и тре- буется оценить сложность алгоритма поиска максимального зна- чения. Так как решение задачи сводится к полному перебору, то здесь будет по существу дана оценка сложности алгоритма пол- ного перебора. Сравнивая с этой оценкой сложность данного алгоритма, можно будет судить, насколько данный алгоритм эффективен. Чтобы не усложнять изложение, будем задавать все числа в двоичной системе счисления. Считаем, что множество чисел задано таблицей и они последовательно расположены по строкам. Пусть числа имеют п двоичных разрядов (л-n-i, Хп-ъ, ... ,Хо), и сравниваются они естественным образом, т. е. начиная со стар- шего разряда. Поясним алгоритм полного перебора на примере табл. 1.12. Таблица 1.12 л-з Х2 л-i ч О 1 1 о 0 1 о ] 1 0 1 о 1 о о 1 1 1 о о Сравниваем первую строку ОНО со второй строкой 0101. Для этого достаточно сравнить три первых разряда (3 д. о.). Остав- ляем большее число ОНО и сравниваем его со значением 1010 очередной строки (1 д. о.). Сравниваем оставшееся число 1010 с очередным значением 1001 (3 д. о.). И, наконец, большее из них число 1010 сравниваем с последним числом 1100 (2 д. о.); в ре- зультате полного перебора значений нашли А:шах=1100. Полный перебор потребовал в данном случае 9 д. о, § 1.3. Табличный способ задания 23 Отметим следующее: если а<.Ь<с, сравнение а и Ь требует не меньше двоичных операций, чем сравнение а и с. Обозначим через S (Г) сложность выбора максимума в таблице. Если разбить таблицу Т на три подтаслицы: верхнюю 7\, среднюю Tg и нижнюю Гд, то выбор максимального значения в таблице Г сводится к выбору максимального значения [А^ в таблице 7\, затем к выбору максимального числа [А^ в таблице Т*ч, где Т\ получена из Tg добавлением верхней строки p,i, и, на- конец, к выбору максимума в таблице Гз, полученной из Ту добав- лением верхней строки р,г. Таким образом, S (Г) == S (Ti) + +5(Г:)+5(Тз). Лемма 1.3. Если таблица Т' получена из таблицы Т пере- становкой k-н строки а с (^+1)-й строкой Ь и й<&, то S(T') Ь, то S (7^>') == S (Т'г), ибо в таблицах Т*ч и Т\ про- водится сравнение одинаковых чисел: p.i с а и \а с Ь. В случае а < ^ < Ь имеем S (Та) < S (Га). В самом деле, в таблице Т*ч сравниваются ^i^c а и (1д с &; в таблице Т ч сравниваются ^ с Ь и Ь с а. "Но сложность сравнения \а^ с а не меньше, чем сложность сравнения Ь с а, ибо а < p.i < Ь. Следовательно, S (7^') < S (T^), что и доказывает лемму. Если l^i <; а, то, аналогично, S^ (7^ ) <; S (Tz). Пусть G — класс таблиц, отличающихся друг от друга пере- становкой строк. Возьмем таблицу Л ^ G, в первой строке которой записано максимальное число Xmax, и В $ G, в которой строки расположены сверху вниз по возрастающим значениям х. Теорема 1.6. Для любой таблицы T(:G имеет место нера- венство 5 (Л) < S (Т) < 5 (В). Доказательство. В таблице Т строку л;шах переместим на первое место, последовательно переставляя ее с очередной верхней строкой. В результате получим таблицу А. Согласно лемме 1.3, будем иметь 5(Л)^5(Т). Очевидно, что все табли- цы Л имеют одинаковую сложность, ибо в этих таблицах -<юах сравнивается со всеми строками. Возьмем теперь в таблице Т строку л:тах и, переставляя ее с нижними строчками, переместим на последнее место. Затем из всех строк, кроме последней, выберем снова л'щах и переместим 24 Гл. 1. Арифметические функции на предпоследнее место и т. д. Таким образом получим табли- цу В. Согласно лемме 1.3, будем иметь S(B) ^S(T). В табл. 1.13 и 1.14, полученных по табл. 1.12, алгоритм пол- ного перебора потребует соответственно 6 д. о. и 9 д. о. Следова- тельно, для произвольной таблицы Т, составленной из чисел 1010, ОНО, 1100, 1001, будем иметь 6<5(Г)^9. Таблица 1.13 Хз л-э л-i ч 1 1 0 о 0 1 1 о 0 1 о 1 1 0 1 о 1 0 о 1 Таблица 1.14 л-з Л-2 Ч • 0 1 0 о 1 1 1 О о 1 0 1 1 1 о Оценим сложность выбора среди последовательности из 2" различных чисел, удовлетворяющих неравенству 0^x^2n—1, наибольшего значения. Расположим эти числа в таблице В в порядке возрастания. В этой таблице каждая i-я строка сравнивается со следующей (И-1)-й строкой. Отметим те разряды следующей строки, кото- рые сравниваются. Во второй строке, например, будут подчерк- нуты все разряды (см. табл. 1.15). Сложность выбора л-шах в таб- лице В равна числу отмеченных разрядов. В столбце Xn-i отме- чены все, кроме первой, строки, т. е. (2"—1) разрядов. Если зачеркнуть первый столбец, то получим таблицу, состоящую из двух одинаковых половинок. Поэтому получаем рекуррентное уравнение Sk==(2k—l)+2Sh-i, где 5д означает сложность вы- бора л"тах среди 2й таких чисел 0^x•gs2h—1. Решив уравнение, получим 5„=2"(/г-1)+1. Таблица 1.15 Х2 Л-1 л:о ^2 Л-1 Ху 0 0 0 1 0 0 о 0 1 1 0 о 1 0 1 1 0 о 1 1 т 1 1 1 I 1 § 1.4. Булевы функции 25 Рассуждая аналогично, можно получить нижнюю оценку S„. Пусть в таблице Л первая строка состоит из одних единиц, а строки, начиная со второй, расположены в порядке возраста- ния х. Таблицу Л разобьем на две подтаблицы — 7\ и Tg, при- чем в Тд первый столбец состоит из единиц, а в 7\ все, кроме верхней, строки состоят из одних нулей. Сложность выбора макси- мального значения S„ (Л) = S„ (Ti) 4- S„ (Га), где Т^ получена из Ту, добавлением верхней строки из одних 1. Очевидно, S (Ti) = 2"-1. Если зачеркнуть первый столбец в Та, то получим таблицу вида Л, но уже для (п—1)-го переменного. Первый столбец в Т^ доставляет (2"~1 — 1) двоичных операций. Отсюда получаем S„ = (2"—l)+Sn_i(A). Решив рекуррентное уравнение, получим S„ = 2"+1 + (га + 2). Таким образом, доказана Теорема 1.7. Сложность 5„ алгоритма выбора максимального числа из 2" различных чисел 0 ^ х -^ 2" — 1 удовлетворяет нера- венству 2"+i — (п + 2) < S„ < 2" {п — 1) + 1. § 1.4. БУЛЕВЫ ФУНКЦИИ Основные понятия. Функция f (х^, х^, ... , Хп) называется булевой, если как переменные, так и сама функция принимают только два значения: нуля и единицы. Существуют только четыре булевы функции от одного пере- менного: fi (х) = 0; /а (х) == 1; fs (х) == х; ft (х) = 1 — х. Функцию /4 (х) называют отрицанием и обычно обозначают через х. Очевидно, что х == х. Иначе говоря, двойное отрицание приводит к исходному значению. Из 16 булевых функций от двух переменных (см. табл. 1.16) рассмотрим только следующие две функции: /з (^ь -^ == ^ч и fn^i, ^2) = х! V ^2' которые определяются табл. 1.17 и 1.18. Функция Xi-Xs, определяет операцию умножения. Но так как значения переменных и самой функции равны 0 или 1, то опера- цию и функцию называют булевым умножением или конъюнк- цией. Функция д:1 V Д'2 определяет операцию, которую называют булевым сложением или дизъюнкцией. Заметим, что если х\., х-г, одновременно не равны единице, то дизъюнкция совпадает с обычным сложением. Операции отрицания, булево сложение и булево умножение являются основными операциями в алгебре логики. Любую функ- цию, как будет показано ниже, можно представить с помощью этих операций. В табл. 1.16 указаны все 16 функций от двух пе- 26 Гл. 1. Арифметические функции Таблица 1.16 0123 Название функции Обозначение Нормальная дизъюнктивная форма л-iЛ-2 0 0 1о о 1 1 1 Уо 0 о о 0 '/о=0 Уо=0 Vi 1 о о 0 Стрелка Пирса У1 = Л-i [ Х^ Vl = Х^ Л-2 У2 о 1 о 0 Запрет У2 = -Cl <- Х^ Уг = Л-1Л-2 Уз 1 1 о 0 Отрицание Уз=~Хз Уз=х^ Vi о о 1 0 Запрет Vt = Л-з <- Х^ У^ == Х^Ху '/S 1 о 1 0 Отрицание У5=~Х1 ' ys=~Xi Уч о 1 0 Исключенное ИЛИ Ув = Ч V ^а Уа = х^ v XiXa 47 1 1 1 0 Штрих Шеффера У^ = Xi/X^ Уг =^i V ~Xy, Уа о о о 1 Конъюнкция Vs = х^ Ув = ^2 Уа 1 о о 1 Равнозначность г/о = xi m Xt У, = х^х^ v ^л-з Уи о 1 о 1 '/10 = Xi Уи = Xi Уи 1 1 о 1 Импликация Yll = Ху, -> Xi Уи = -fi V 7s ЧлъJ \.?, о о 1 1 '/12 = X^ Уи = -<2, Уи 1 о 1 1 Импликация Via = ^i -+ •t-2 Уи = л-i V Ху Уи о 1 1 1 Дизъюнкция Уи = Xi v x^ Уи = Xi V х^ Vis 1 1 1 1 Уи = 1 '/15= 1 Xl Х2 h(xl, х^) 0 0 0 0 1 0 1 0 0 1 ' 1 Таблица 1.17 Таблица 1.18 х! Xt fu (x!, Х^) 0 0 о 0 1 1 1 о 1 1 1 1 ременных. В последнем столбце выписаны формулы для этих функций, составленные с помощью операций конъюнкции, дизъ- юнкции и отрицания. (Кроме этой тройки функций, существуют и другие полные наборы функций, т. е. такие, что любую булеву функцию можно представить в виде суперпозиции функций набора.) Основные операции булевой алгебры. Перепишем табл. 1.17 и 1.18 и назовем их соответственно таблицами булева умножения и булева сложения. § 1.4. Булевы функции 27 Булево умножение 0-0==0 0-0=0 1-0=0 1.1 = 1 Булево сложение OVO=0 0V 1 = 1 1 V0= 1 1 V 1 = 1 Из таблиц булева умножения, булева сложения и .отрицания непосредственно следуют четыре соотношения: IV х = 1; О V х = х; л- V х = 1; х\/ х == х; \-х==х; 0-л:=0; х-х=0', х-х=х. Чтобы убедиться в их справедливости, нужно подставить в эти соотношения значения х=0 и х= 1 и проверить результат по таб- лицам отрицания, булева сложения и булева умножения. В булевой алгебре справедливы переместительные, сочета- тельные и распределительный законы. а) Переместительные законы: х-у=у-х; х V У =• У V х. б) Сочетательные законы: (ху) г =. х (г/z); (х V У) V г = х V (У V г). в) Распределительный закон: х (у V z) == ху V xz. В справедливости этих законов легко убедиться непосред- ственной проверкой, подставляя х=0, х=1. Из сочетательных законов и соотношений х V х = х; х • х = х следует, что Х' Х ... Х =г X', А: V Х\/ Х\/ ... V ^ = X. Из соотношений \-х = х; 1 V х = 1. и распределительного закона следует, например, соотношение х V УХ = х. В булевой алгебре имеют место соотношения: ху == хV^; х\/ у== х-у, которые называются законами инверсии. Чтобы убедиться в справедливости этих законов, достаточно их проверить при х = 0 и х == 1. Подставим х = 1 в обе части первого равенства: 28 Гл. 1. Арифметические функции 1 -у=у; 1 ^ y=Q-\/ y=y. При х = 0 имеем 0^=0== 1; OV<7= 1 Vy= 1. Аналогично проверяется второе равенство. Совершенная нормальная дизъюнктивная форма. Одночленом от аргументов х^, х^, ... , Хд назовем любое произведение сомно- жителей, взятых из ряда х^, Ху,, .... х^, х^, х^ ... , Ху Напри- мер, Х-^Х^Х^Х^ X^XfyXg. Число сомножителей назовем длиной одночлена. Очевидно, что если в одночлене имеется как х^, так и его отрицание л:,., то такой одночлен равен нулю. Длина не равных нулю одночленов от п переменных х^, д-2, ... , х^ не превосходит п. В самом деле, из двух переменных х^ х^ в одночлен входит только одно, и если оно повторяется несколько раз, то по соотношению х-х ... х = х его можно оставить только один раз. Не равные нулю одночлены длиной п от переменных л:!, д-2, . •. , -Уд называются конституентами единицы. Для трех переменных х^, х^, Ху можно записать восемь кон- ституент. x^x^x^f х^х^х^, х-^х^х^, х-^х^х^ х-^х^х^ х-^х^х^ х-^х^Хц, х^х^Хд. Для п переменных будет 2" конституент. Очевидно, что произ- ведение двух различных конституент равно нулю, ибо в произ- ведение войдет какая-нибудь переменная вместе со своим отрица- нием. Сумма всех 2" конституент равна единице. Последнее утверждение следует из равенства 1 == (д-i V ~Xi) (л-2 V ^2) • • • (Хп V х„). Если раскрыть скобки, то получится сумма всех 2" кон- ституент. Для удобства изложения условимся о следующей символике, 1 которой иногда будем пользоваться: буквы х, х соответственно будем обозначать через х1 и х°. Символ х", где а—двоичное переменное, примем за общее обозначение х и х. Теперь имеем возможность ввести общее обозначение конституент: х^ху ... х^". Пусть дана булева функция у == f (х^, х^, •.. , х^)- Легко проверяются равенства: X/ (х!' • • • > Х^, • • • > xn)= х^ (^l» • • • • 1> • • • ' xn)^ Xif (х!, ... , Х„ ... , Хп}= ~Xif (Xi, ... , 0, . . . , А-„). Запишем их в виде x^f (^> • • • > ^'с • • • , xn)= х1Ч (х!, • • • , и,. ••• , -^). § 1.4. Булевы функции 29 Так как х^ V х^ == 1, то имеем / (^i, х.г, ... , х^= (х, у x,)f (xi, х^ . .. , х^= = Xif (^1. ^2, • • • , Хп} V X,f (Xi, Л:2, . . . , Л-n) = = X^ (Xi, X^ .... 1, .... X^ V Xif (^l. X^, ... , 0, . .. , Xn). Итак, / (^i, ^2, .. . , x„) === V x^f (Xi, л-2, ... , a,, ... , л-д). По- ^o следнее выражение называют разложением булевой функции относительно х^. Последовательно разлагая / (л-i, х^, ..., х^) по х^ х^, ... , х^, получим f (xi, х^, ... , х^) = V х^^ • • • x^f (ai, аэ, .... а„). (1.4) "1, «г, ..., "n Разложение (1.4) носит название совершенной дизъюнктив- ной нормальной формы. Оно доказывает, что каждая булева функция может быть задана формулой, образованной с помощью операций булева сложения, булева умножения и отрицания. Из разложения (1.4) видно, каким образом по таблице значе- ний функции можно составить совершенную дизъюнктивную форму. Это построение состоит в следующем: в таблице задания функции подчеркиваются те строки, в которых f(xi, Xz, ... , Xn)=i, затем значения переменных в отмеченной строке записы- ваются в качестве показателей степеней тех же переменных в конституенте, после чего суммируются полученные по отмечен- ным строкам конституенты. Напишем совершенную нормальную дизъюнктивную форму для функции, определяемой табл. 1.19. Таблица 1.19 А-1 Л-2 Ху f(Xi, Х^, Ху) 0 0 0 О 0 о 1 1 0 1 о 0 0 1 1 0 1 О о 1 1 0 1 0 1 1 о 1 1 ! ! 0 БИБЛИОГРАФИЯ И ПРИМЕЧАНИЯ Гл. 1, 2 О табличном и граф-схемном задании арифметических функций было опубликовано в [2]. О представлении булевых функций многочленами можно прочесть в [З]. Дискретное программирование изложено в работах Р. Беллмана и Р. Калаба (см., например [1]). 1. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М., «Наука», 1969. 2. Блох А. Ш. Арифметические функции и вопросы обучения машин.— В сб.: «Вопросы кибернетики и математики». Минск, изд-во БГУ, 1970. 3. Моисил Г. Алгебраическая теория дискретных автоматических устройств. М., ИЛ, 1963. Гл. 3 Канонический метод синтеза грф-схем арифметических функций был рас- смотрен в статье [2]. Впервые канонический метод синтеза переключательных схем был описан в статье [I]. Импульсные граф-схемы—в [З]. 1. Блох А. Ш. Канонический метод синтеза контактных схем.—«Автома- тика и телемеханика», т. 22, 1961, № 6. 2. Блох А. Ш. Арифметические функции и вопросы обучения машин,— В сб.: «Вопросы кибернетики и математики». Минск, изд-во БГУ, 1970. 3. Блох, А. Ш. Об одном классе граф-схем.— В сб.: «Вопросы кибернетики и математики». Минск, изд-во БГУ, 1970. Гл. 4 Общие принципы вычисления оценок сложности переключательных схем, которые легли в основу различных методик по вычислению оценок, разработал К. Э. Шеннон [8]. Интересные результаты в этой области получены О. Б. Лупа- новым, который, в частности, уменьшил в два раза оценку контактного дерева, что позволило ему получить точную асимптотическую оценку сложности кон- тактных схем [5]. Использовав идею канонического метода [б], Лупанов нашел точные асимптотические оценки отдельных классов схем. Некоторые из этих классов (см. теоремы 4.15, 4.18) были рассмотрены в [2]. Оценки сложности реализации инвариантных классов булевых функций приведены в работе [9]. Теоремы 4.10—4.12 являются обобщениями аналогичных результатов для буле- вых функций [9]. Оценки сложности граф-схем арифметических функций публи- куются, за некоторым исключением, впервые. О программной реализации граф- схем см. в [З]. Оценка сложности граф-схем периодических арифметических функций опубликована в [4]. Оценки сложности граф-схем для функции не более 10 переменных опубликованы в [7] (см. теорему 4). Библиография и примечания 295 -1. Блох А. Ш. Канонический метод синтеза контактных схем.—«Автома- тика и телемеханика», т. 22, 1961, № 6. 2. Блох А. Ш. О сложности переключательных схем.— «Вычислительная техника в машиностроении», 1965, № 4. 3. Блох А.' Ш. Об управляющих машинах.—«ДАН БССР», 1965, № 5. 4. Блох А. Ш., Павловский А. И. Оценка сложности реализации периоди- ческих функций.—«Вычислительная техника в машиностроении», 1967, № 4. 5. Лупанов О. Б. О синтезе некоторых классов управляющих систем.— «Проблемы кибернетики», 1963, № 10. 6. Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования.—«Проблемы кибернетики», 1965, № 14. 7. Павловский А. И. Оценки сложности граф-схем алгоритмов.— В сб.: «Вопросы кибернетики и математики». Минск, изд-во БГУ, 1970. 8. Шеннон К. Э. Работы по теории информации и кибернетики. М., ИЛ, 1963. 9. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем.— «Проблемы кибернетики», 1959, № 2. Гл. 5 Упорядоченные переключательные схемы рассматривались в указанных ниже работах. Класс упорядоченных граф-схем излагается впервые, так же как метод исследования с помощью итеративных и регулярных последователь- ностей. Синтез в классе сумматоров с использованием правила склеивания вершин в канонической таблице рассмотрен в работе [8]. Каскады Майтра впервые были рассмотрены в [14]. 1. Блох А. Ш. Синтез контактных (р, (7)-полюсников.—«ДАН СССР»,' 1956, № 5. 2. Блох А. Ш. О каноническом методе синтеза контактных схем.—«Авто- матика и телемеханика», т. 23, 1962, № 4. 3. Блох А. Ш. О синтезе с минимальным числом контактов.— «ДАН БССР», т. 4, 1960, № 11. 4. Блох А. Ш., Ладес В. И. Синтез однотактных схем, поведение которых описывается линейными неравенствами.— «Изв. АН БССР», сер. физ.-мат. наук, 1966, № 3. 5. Блох А. Ш., Ладес В. И. Метод синтеза принципиальных схем логиче- ских устройств.—В кн.: «Тр. III Всесоюз. совещ. по технической кибернетике». М., «Наука», 1967, 6. Блох А. Ш., Ладес В. И. Однотактная схема, определяющая положение данного числа относительно двух других.— «Вычислительная техника в маши- ностроении», 1967, № 10. 7. Блох А. Ш., Павловский А. И. Канонический метод синтеза и каскады -Майтра.—«ДАН БССР», т. 17, 1973, № 10. 8. Ладес В. И. Комбинационные схемы, вычисляющие значения линейных функций.—«Изв. АН БССР», сер. физ.-мат. наук, 1970, № 1. 9. Ладес В. И. Схемная реализация выборки из множества чисел числа, ближайшего к заданному.—«Изв. АН БССР», сер. физ.-техн. наук, 1971, № 3. 10. Казущик В. А., Ладес В. И. Автоматическое построение схем, сравни- вающих значения линейной функции с заданным числом.— «Изв. АН БССР», сер. физ.-мат. наук, 1968, № 4. 11. Казущик В. А., Ладес В. И. Комбинационные схемы сравнения значе- ний линейных функций с нулем.—«Изв. АН БССР», сер. физ.-мат. наук, 1971, №4. 12. Казущик В. А.. Ладес В. И., Пономаренко В. К. Комбинационные схемы, сравнивающие значения линейных функций с числом, отличным от нуля.— «Изв. АН БССР», сер. физ.-мат. наук, 1972, № 2, 296 Библиография и примечания 13. Казучцик В. А., Л идее В. И. Комбинационные схемы сравнения абсо- лютных значений линейных функций.—«Изв. АН БССР», сер. физ.-мат. наук 1972, № 6. 14. Maitra К. К. Cascades switching networks of'two-input flexible cells.— IRE Trans. Electron. Computers, ES-11, 1962, N 2. Гл. 6 Глава 6 является вспомогательной. Поэтому из двух основных и действи- тельно интересных результатов теории конечных автоматов [9, 10]—теорем о представлении событий и длине эксперимента — в главе содержится только последнее [9]. Рассмотрен также алгоритм Ауфенкампа и Хона по обна- ружению эквивалентных состоянии [2]. В главе использована статья [З]. Что касается синтеза конечных автоматов, то сложность этой проблемы зависит от принятой формы задания конечных автоматов. В книге используется рас- смотренное в [4] задание в виде усеченных закрытых деревьев, которое близко техническому заданию на проектирование дискретных устройств. Для изуче- ния теории конечных'автоматов можно рекомендовать монографии [1, 5—8]. Подробная библиография в [8]. 1. Логика. Автоматы. Алгоритмы. М., Физматгиз, 1963. 2. Ауфенканп Д. Д., Хон Ф. Е. Анализ последовательностных машин.— В сб.: «Математика». 1. Периодич. сб. пер. иностр. ст. М., ИЛ, 1959. 3. Блох А. Ш. Эквивалентные преобразования последовательностных ма- шин.—«Автоматика и телемеханика», т. 21, 1960, № 11. 4. Блох, А. Ш. Синтез переключательных схем. Минск, «Наука и техни- ка», 1966. 5. Глушков В. М. Синтез цифровых автоматов. М., Физматгиз, 1962. 6. Гилл А. Введение в теорию конечных автоматов, М., «Наука», 1966. 7. Кобринский Н. Е„ Трахтенброт Б. А. Введение в теорию конечных авто- матов. М., Физматгиз, 1962. 8. Мелихов А. Н. Ориентированные графы и конечные автоматы. М., «Наука», 1971. 9. Мур Э. Ф. Умозрительные эксперименты с последовательностными ма- шинами.—В сб.: «Автоматы». М., ИЛ, 1956. 10. Клини С. К,. Представление событий в нервных сетях и конечных авто- матах.—В сб.: «Автоматы». М., ИЛ, 1956. Гл.7 Монография А. А. Маркова [8], статьи А. М. Тьюринга [12] и Е. Л. Поста [11] являются основополагающими трудами по теории алгоритмов. Впервые ввел в рассмотрение граф-схемы алгоритмов, по-видимому, Л. А. Калужнин [7]. В работе [6] рассматривались вопросы синтеза граф-схем алгоритмов. Статьи [1, 2, 3] и монография [5] посвящены каноническому методу синтеза граф-схем алгоритмов. В работе [4] исследована связь между граф-схемой алгоритма и его программой и излагается составление программ нормальных алгоритмов для управляющей машины, представляющей одну из детализаций машины Тьюринга. В статьях [9, 10] описан язык для управляющей машины. 1. Блох А. Ш., Неверов Г. С. Об одном методе синтеза граф-схем алгорит- мов—«ДАН БССР», т. 8, 1964, № 9. 2. Блох. А. Ш„ Горелик А. Г. Синтез граф-схем алгоритмов.— «Вычисли- тельная техника в машиностроении», 1965, № 1. 3. Блох А. Г., Горелик А. Г. Синтез граф-схем алгоритмов общей такти- ческой задачи.— «Вычислительная техника в машиностроении», 1966, № 10. 4. Блох А. Ш., Пономаренко В. К. Об одном варианте управляющей ма- шины.—«Изв. АН БССР», сер. физ.-техн., 1968, № 3. Библиография и примечания 297 5. Блох А. Ш., Неверов Г. С. В помощь авторам алгоритмов. Минск, «Беларусь», 1971. 6. Дьяченко В. Ф. Построение граф-схем алгоритмов.—В сб.: «Проблемы передачи информации». Вып. 12. М., 1963. 7. Калужнин Л. А. Об алгоритмизации математических задач.— «Про- блемы кибернетики», 1959, № 2. 8. Марков А. А. Теория алгоритмов.—В кн.: «Тр. Матем. ин-та АН СССР им. В. А. Стеклова». Т. 42. М., изд-во АН СССР, 1954. 9. Лакина Н. И. К вопросу программирования на вычислительной мо- дели.— В сб.: «Вопросы кибернетики и математики». Минск, изд-во БГУ, 1970. 10. Лакина И. И. К вопросу программирования на машинах Тьюринга.— «Изв. АН БССР», сер. физ.-мат., 1974, № 4. 11. Post E. L. Finite combinatory processesformulaton I.—«J. Symb. Logic», 1936, 1. 12. Turing A. M. Computable numbers with an application to Entscedung- sproblem.— Proc. Lond. Math. Soc. (2), v. 42, 1936. Гл. 8 Впервые алгоритм обучения для задач распознавания образов был разра- ботан Розенблатом [17], в дальнейшем были предложены более совершенные алгоритмы (см., например [1]), заключающиеся в построении поверхностей, разделяющих множества изображений, а также алгоритмы, основанные на использовании вероятностных методов [2, 15, 18]. Отличительная черта этих алгоритмов — то, что в их основу положена непрерывная модель обучения. Этим достигается возможность применения всего арсенала современного мате- матического анализа. Однако подобная идеализация не охватывает всех сто- рон процесса обучения и, кроме того, вносит многое, присущее только модели, но не обучению. Поэтому наряду с непрерывными моделями обучения следует разрабатывать и конечные модели. Конечная модель обучения, опирающаяся на экстраполяцию и интерполяцию арифметических функций, была описана в работах [3—II], а ее применение для медицинской диагностики—в работах [12-14]. 1. Теоретические основы метода потенциальных функций в задаче об обу- чении автоматов разделению ситуаций на классы.— «Автоматика и телемеха- ника», т. 25, 1964, № 6. 2. Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциаль- ных функций в теории обучения машин. М., «Наука», 1970. 3. Блох А. Ш. О дискретной интерполяции.— «Изв. АН БССР», сер. физ.- техн., 1966, № 3. 4. Блох А. Ш. Об одном алгоритме обучения для задач по распознаванию образов.—«Вычислительная техника в машиностроении», 1966, № 10. 5 Блох А. Ш. Вопросы дискретной экстраполяции.—«ДАН БССР», т. 11, 1967, № 10. 6. Блох А. Щ. Дискретная экстраполяция и машины Тьюринга.— «Вычис- лительная техника в машиностроении», 1968, № 2. 7 Блох А. Ш. Применение принципа минимума в задачах обучения.— «ДАН БССР», т. 12, 1968, № 7. 8. Блох А. Ш. Принцип минимума для алгоритмов.— «Изв. АН БССР», сер. физ.-техн., 1968, № 4. 9. Блох А. Ш. Арифметические функции и вопросы обучения.— В сб.: «Вопросы кибернетики и математики». Минск, изд-во БГУ, 1970. 10. Блох А. Ш. Обучение в классе конечных автоматов.—В сб.: «Вопросы кибернетики и математики». Минск, изд-во БГУ, 1970. 11. Блох А. Ш., Орлов В. А. Восстановление признаков при распознавании образов.—«Вестник БГУ им. В. И. Ленина», сер. мат., физ., мех., 1971, № 1. 12. Опыт использования ЭВМ для диагностики рассеянного склероза.— 298 Библиография и примечания «Журнал невропатологии и психиатрии им. С. С. Корсакова», т. 69, вып. 11, 1969. 13. Блох А. Ш., Миркин Г. И., Орлов В. А. Алгоритм обучения в диффе- ренциальной диагностике некоторых демиелинизирующих заболеваний нервной системы.—В сб.: «Демиелинизирующие заболевания нервной системы в экспе- рименте в клинике». Минск, «Наука и техника», 1970. 14. Блох А. Ш., Орлов В. А., Миркин Г. И. Вероятностный прием восста- новления неизвестных значений симптомов при машинной диагностике рас- сеянного склероза.—В кн.: «Актуальные вопросы невропатологии и нейро- хирургии». Вып. 3. Минск, «Наука и техника», 1970. 15. Васильев В. И. Распознающие системы. Киев, «Наукова думка», 1969. 16. Минский At., Пейнерт С. Персентроны. М., «Мир», 1971. 17. Rosenblatt F. Perceptron simulation experiments.—Proceedings of the IRE, v. 48, 1960, N 3. 18. Цыпкин Я. 3. Основы теории обучающихся систем. М., «Наука», 1970. Гл. 9 Различные методы синтеза контактных схем описаны в монографиях [9, 10, 19, 20, 22, 23, 26, 28]. Наиболее полно вопросы синтеза изложены в книге [22]. Канонический метод синтеза впервые был описан в работах [1, 2]. В следующих работах изложено применение канонического метода для син- теза: электронных [6, 8, 14—18], пневматических [13] схем, схем пневмоники [11, 12] и на «реальных» контактах [7], с применением вентильных элемен- тов [24]. Каноническому методу синтеза посвящены монография [3] и обзор [25]. В работе [5] излагается минимизация в классе подобных функций. Возмож- ность применения матриц для синтеза контактных схем впервые освещена в работах [21, 27]. Матричный метод синтеза с использованием промежуточных аргументов был описан в работе [4]. 1. Блох А. Ш. Канонический метод синтеза контактных схем.—«Автома- тика и телемеханика», т. 22, 1961, № 6. 2. Блох А. Ш. Канонический метод синтеза электронных схем.—В кн.: «Тр. Ин-та машиноведения и автоматизации АН БССР». Вып. 1. Минск, «Наука и техника», 1961. 3. Блох А. Ш. Синтез переключательных схем. Минск, «Наука и тех- ника», 1966. 4. Блох А. Ш. Специальный случай синтеза контактных (р, -.. 249 § 9.3. Контактные П-схемы .......••• 251 § 9.4. Логические схемы .,,,,,,. i ^ • 254 302 Оглавление § 9.5. Электронные схемы .......... 256 § 9.6. Канонический метод синтеза контактных схем . . . 258 § 9.7. Матричный метод синтеза контактных (р, ^)-полюсников § 9.8. Канонический метод синтеза логических схем . . . 270 § 9.9. Синтез логических схем на трехвходовых элементах . 275 § 9.10. Синтез электронных схем . ....... 282 § 9.11. Программные блоки управления ...... 288 Библиография и примечания 294 Блох Абрам Шлемович ГРАФ-СХЕМЫ И ИХ ПРИМЕНЕНИЕ Редактор А. А. Белянкина Обложка В. Л. Милевского Худож. редактор Г. И. Важное Техн. редактор П. В. Фрайман Корректор Е. В. Сукач AT 14517'. Сдано в набор 28/VII 1-1974 г. Подписано к печати 26/11-1975 г. Бумага 60Х90'/ц типогр. № 3. Печ. л. 19. Уч.-изд. л. 19,46. Изд. № 73—55. Тип. зак. 1186. Тираж 5000 экз. Цена 78 коп. Издательство «Вышэйшая школа» Государственного комитета Сове- та Министров БССР по делам издательств, полиграфии и книжной торговли. Редакция литературы по математике, физике и энергетике. 220600. Минск, ул. Кирова, 24. Ордена Трудового Красного Знамени типография издательства ЦК КП Белоруссии. Минск, Ленинский пр., 79. « Блох А. Ш. Б70 Граф-схемы и их применение. Минск, «Вышэйш. школа», 1975. 304 с. с ил. Изложена граф-схемная интерпретация арифметических функций, рассмотрены три аспекта применения граф-схем: структурный синтез дискретных устройств управления, модели вычислительных устройств и вопросы программирования, алгоритмы обучения машин. Приведены примеры. Учебно-вспомогательное пособие для студентов математических и инженерных факультетов вузов. 20204—040 г ю с —————————— чч 7^ Ью " M304(05)-75""•& А. Ш. БЛОХ ГРАФ-СХЕМЫ И ИХ ПРИМЕНЕНИЕ ИЗДАТЕЛЬСТВО «ВЫШЭЙШАЯ ШКОЛА» Минск 1975