STANISLAW BELLERT, HENRYK WOZNIACKt ANA LIZA I SYNTEZA UKAADOW ELEKTRYCZNYCH METODA LICZB STRUKTURALNYCH Wydawnictwa naukowo-technicsne WARSZAWA С. БЕЛЛЕРТ, Г. ВОЗНЯЦКИ АНАЛИЗ И СИНТЕЗ ЭЛЕКТРИЧЕСКИХ ЦЕПЕЙ МЕТОДОМ СТРУКТУРНЫХ ЧИСЕЛ Перевод с польского Под редакцией Проф. П. А. ИОНКИНА ИЗДАТЕЛЬСТВО «МИР» Москва 1972 УДК 621.372.061 В книге изложен новый алгебраический метод, названный авторами методом «структурных чисел». В основу этого метода положены соответствия между преобразованиями цепей и простыми алгебраически- ми операциями со структурными числами. Рассмот- рено применение метода структурных чисел для ана- лиза и синтеза активных и пассивных линейных двухполюсных и четырехполюсных электрических цепей и блочных электрических схем. Книга пред- ставляет большой теоретический и практический интерес/поскольку данный метод позволяет значи- тельно уменьшить число математических операций при анализе и синтезе, а также расширить воз- можности решения указанных задач путем при- менения ЭЦВМ и послужит базой для создания общей теории анализа и синтеза электрических цепей. Книга адресована инженерам, научным работ- никам, аспирантам и студентам электротехниче- ских, радиотехнических и энергетических специаль- Редакция литературы, по новой технике 3-3-14 132-72 Предисловие к русскому изданию В настоящее время теория электрических цепей переживает весьма бурное развитие. Это объясняется главным образом все большим усложнением как самих цепей, так и их функций. Наря- ду с этим методы теории цепей весьма полезны при изучении раз- личных процессов, например физических, химических, экономи- ческих, биологических и т. д., поскольку они поддаются моде- лированию с той или иной степенью точности электрическими схемами. Электронные цифровые вычислительные машины облегчают анализ и синтез сложных цепей. В то же время внедрение методов расчета с помощью ЭЦВМ дает еще один мощный толчок дальней- шему развитию теории цепей. Так возникает необходимость совершенствования классических методов анализа и синтеза цепей и разработки новых, более приспособленных к нуждам автоматизации вычислений с помощью ЭЦВМ. В основе многих алгоритмов машинного анализа линейных цепей лежат матричные формулировки уравнений цепи. Матри- цам присущи известные преимущества — сравнительная про- стота составления уравнений и строгая последовательность ариф- метических операций. Вместе с тем надо учесть еще и то, что при большой степени интегрализации цепей исходную информацию о схеме часто можно получить лишь в виде определенной матрицы путем измерения параметров. Однако матричные методы обла- дают существенной алгоритмической избыточностью уже при вводе информации в машину, а при расчетах определителей матриц и их алгебраических дополнений часть вычислений выпол- няется по сути дела впустую. Топологические методы анализа, основанные на поиске деревьев графа цепи, имеют определенные преимущества по сравнению с матричными: расчет определителей и их алгебраи- ческих дополнений требует меньше вычислений, особенно в слу- чае пассивных цепей. Существуют разные алгоритмы поиска деревьев, но зачастую и они состоят из многих операций. Разработка оптимальных алгоритмов машинного анализа схем — задача, безусловно, важная и сложная. Еще в большей степени сказанное относится к синтезу электрических цепей. ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ В этой связи книга С. Беялерта и Г. Возняцкого должна явно заинтересовать советского читателя, поскольку в ней систе- матически изложены основы нового метода анализа и синтеза линейных электрических цепей, названного авторами «методом структурных чисел». В первых четырех главах авторы с позиций теории множеств строго и математически последовательно обосновывают данный метод. В первой главе авторы приводят определения различных понятий цепи: абстрактной, топологической и конкретной. При этом конкретными цепями авторы называют топологические цепи, связанные с определенными физическими представлениями (элек- трические, тепловые, гидравлические, пневматические и другие). Во второй главе излагаются свойства структурных чисел и уста- навливается соответствие между столбцами структурных чисел и деревьями графов. В третьей и четвертой главах обобщается понятие структурного числа, вводятся числа второй и га-й кате- горий, излагаются соответствующие графы, а также устанавли- вается связь между блочными графами и их структурными числами. Структурные числа, введенные в книге, внешне похожи на матрицы, элементами которых служат числа натурального ряда. Однако алгебраически структурные числа существенно отличают- ся от матриц. Структурное число (первой категории) дает инфор- мацию о деревьях или дополнениях деревьев электрической цепи. В последующих трех главах книги приведены алгоритмы ана- лиза и синтеза линейных электрических цепей методом структур- ных чисел, с помощью которых можно находить входные и пере- даточные иммитансы, коэффициенты передачи напряжения и тока, анализировать разветвленные пассивные цепи, цепи, содержащие электронные лампы и транзисторы, многополюсники и блок- схемы, решать задачи синтеза двух- и четырехполюсных цепей. К тому же метод структурных чисел, как показано в приложе- нии 3, пригоден для минимизации булевых функций и синтеза переключательных схем. Вообще говоря, метод структурных чисел обладает значитель- ными возможностями. Наибольшая методическая ценность метода состоит в едином подходе к анализу различных линейных цепей: пассивных, активных, содержащих многополюсные элементы и блок-схемы. Решение задачи синтеза линейных цепей также ^> осуществляется единообразно, делая ненужным определенную «изворотливость» и интуицию проектировщика. По сравнению с классическими методами синтеза, которые ограничивают проек- тировщика той или иной топологией схемы (лестничной, мосто- вой и т. п.). метод структурных чисел таких ограничений не имеет, что важно при решении задач оптимизации синтезируемых цепей. ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ Достоинство метода структурных чисел состоит также в его приспособленности к использованию ЭЦВМ как при анализе, так и при синтезе цепей. В ряде случаев он несомненно дает эко- номию в числе операций при анализе цепей по сравнению с дру- гими. Однако оценить в целом сейчас эффективность метода оконча- тельно еще нельзя. Это можно сделать лишь в дальнейшем, когда он будет разработан более всесторонне. Так, дальнейшего уточ- нения требуют вопросы применения структурных чисел к анализу цепей с электронными элементами. Решение задачи синтеза пас- сивных цепей, как уже отмечалось, отличается общностью и воз- можностью нахождения оптимальных решений; однако даже в простых случаях объем вычислений столь велик, что не может быть выполнен без ЭЦВМ. Вопросы оптимизации цепей, а также синтеза активных цепей с помощью структурных чисел в книге не затронуты и еще ждут своего решения. Книга предназначается для специалистов, занимающихся вопросами анализа и синтеза электрических цепей, проектирова- нием радиоэлектронной, измерительной аппаратуры и аппаратуры связи, устройств управления и автоматики, а также для аспи- рантов и инженеров аналогичных профилей. При переводе книги сохранены терминология и обозначения авторов. Так, например, квантор общности обозначается /\ вместо принятого у нас обозначения у' а квантор существования обозначен V вместо д. Сокращено предисловие авторов и устра- нены замеченные опечатки. Книгу перевели Гаев Г. П., Дорух X. П., Ренч Е. И., Миронов В. Г., Соколов А. А. П. А. Ионкин Из предисловия авторов Основу современных методов топологического анализа элек- трических цепей заложил Кирхгоф, опубликовавший в 1847 г. основные законы анализа электрических цепей. Законы Кирхгофа дополнил Максвелл в 1892 г., предложивший метод узловых напряжений. В 1925 г. Франклин сформулировал законы Кирх- гофа в матричном виде. Спустя семь лет Фостер, развивая теорию линейных графов применительно к анализу электрических цепей, вывел ряд топологических формул. Однако широкое развитие топологических методов анализа и синтеза электрических цепей (систем) началось лишь после 1950 г., когда расчет цепей стали производить с помощью элек- трических цифровых машин и когда начались поиски простейших способов программирования таких расчетов. При анализе сложных разветвленных электрических цепей — и пассивных, и содержащих электронные лампы или транзисто- ры,— трудоемкость расчетов весьма велика. Обычно используют- ся методы, основанные на теории определителей или матриц. Однако им присущи свои недостатки: с одной стороны, необходи- мость кропотливых и длительных вычислений, с другой стороны, отсутствие непосредственной связи между алгоритмом расчета и топологической структурой рассчитываемой цепи. Именно последнее обстоятельство стало причиной того, что до настоящего времени общепринятые методы не привели к созданию общей методики синтеза электрических цепей, которая решила бы про- блему исчерпывающим образом. В задачу настоящей работы входит изложение основ алгебраи- ческого метода разработки нового общего алгоритма анализа и синтеза электрических цепей. Ясно, что такой алгоритм можно сконструировать по-разному. Однако при этом важно, чтобы алгоритм решал основные задачи самым простым и оперативным' способом. Изложенная здесь алгебра структурных чисел может стать, по мнению авторов, основой для разработки такого алго- ритма, представляющего собой довольно гибкий и всеобъемлющий способ решения вопросов анализа и синтеза электрических цепей. Такая алгебра дает большую экономию труда и времени при расчетах по сравнению с иными методами, что подтверждается также предыдущими работами авторов. ИЗ ПРЕДИСЛОВИЯ АВТОРОВ Сокращение и упрощение расчетов, о которых идет речь, дости- гается, конечно, за счет некоторого усложнения системы аксиом по сравнению, например, с алгеброй матриц. Но усложнение предпосылок, если благодаря ему получается более простой метод расчета, не следует .считать существенным недостатком. Метод и его предпосылки мы изучаем один раз, а расчеты произ- водим десятки и сотни раз. Преимущества метода структурных чисел состоят в сле- дующем: 1. Значительно сокращает операции при решении задач ана- лиза и синтеза электрических цепей, например при определении передаточных функций или токов и напряжений в цепях. 2. Закладывает основу для создания общей теории синтеза и анализа электрических цепей без ограничений, касающихся структуры цепи или величин используемых элементов. 3. Хорошо приспособлен для автоматизации расчета с по- мощью ЭЦВМ. 4. Дает большую экономию при записи отдельных формул в расчете. 5. Представляет собой логически обоснованный математиче- ский аппарат, открывающий широкие возможности дальнейшего развития и применения в других областях, кроме теории элек- трических цепей. При анализе электрических цепей методом структурных чисел необходимо вычислять детерминантные функции, которые в дей- ствительности представляют развернутые определители матриц полных сопротивлений или проводимостей цепи. Из этого следует первое достоинство предлагаемого метода: установив нужные зависимости, непосредственно получаем результаты без громозд- ких операций с определителями матриц с целью получения опре- делителей низкого порядка. Вторым достоинством метода структурных чисел служит использование подобных структур и графов с интересными общи- ми характеристиками. В результате получение формулы носит универсальный характер, что имеет особенно большое значение при синтезе цепей. Третье существенное достоинство метода структурных чисел — использование теории множеств. Это дает экономию в форме записи отдельных зависимостей при анализе графов и электриче- ских цепей. В основе метода структурных чисел находятся такие пре- образования цепей и графов, в соответствие которым ставятся простые алгебраические действия со структурными числами. Эти преобразования позволяют решать многие новые задачи теории графов и анализа электрических цепей, тогда как при матричном методе преобразования цепей не находят широкого применения. 10 ИЗ ПРЕДИСЛОВИЯ АВТОРОВ Метод структурных чисел позволяет сравнительно' просто ана- лизировать электрические цепи с многополюсниками, так как при матричных методах анализа решение получается менее наглядным. Большое преимущество структурных чисел — их дуальность, т. е. возможность записи формул в двух вариантах — для изобра- жения и обратного изображения структурного числа. Надо отметить, что сравнение недостаточно еще развитого метода структурных чисел с матричным методом анализа цепей не может быть полным и окончательным. Для окончательного вывода требуется дальнейшее развитие метода структурных чисел. Понятие структурного числа было впервые сформулировано Беллертом. Надо отметить, что еще в 1934 г. Ванг предложил новый метод расчета токов и напряжений в электрических цепях, основанный на применении алгебры, в которой a-\-a-=Qyia-a==„ = 0. Однако его метод не был обоснован логически и не получил широкого применения. Метод структурных чисел является логи- ческим следствием предпосылок метода Ванга. Гл. 1, 2, 5, 7 и приложение 1 написаны Беллертом, гл. 3, 4, 6 и приложения 2, 3 — Возняцким. Приступая к написанию этой книги, авторы ставили себе задачу создать монографию, предназначенную прежде всего для научных работников, аспирантов, занимающихся проблемами теоретической электротехники, в особенности теорией линейных электрических и электронных цепей. Некоторые главы книги, например гл. 1, определяющая поня- тие электрической цепи, а также гл. 2, 3, 4, содержащие основы алгебры структурных чисел, могут быть интересными для мате- матиков, занимающихся теоретической алгеброй и теорией инфор- мации. Обозначения А, В, С,. . . — структурные числа; А'1 — дополнительное структурное число; hA — структурное число /с-й категории; h'Ad — дополнительное структурное число й-й категории; е „ " А == А — соответствие структурному числу k-та. категории hA замещающего числа А; ^4, Sf, 'ё,.. . — полные структурные числа; s Л = А— равенство полного структурного числа Л и струк- турного числа А; ^ц,ц • • • — структурное число графа, образованного замы- канием вершин (J.I, р,2, ... в первоначальном графе; ^(xiex2 — структурное число графа, образованного отсоеди- нением одних концов ребер ai, Ста, ... от вершин первоначального графа; Лг — полное структурное число замещающего гра- . фа Г„ А*г — полное структурное число эквивалентного гра- фа п; 0-h.tp) — дендритный вес грани ст^ замещающего графа г 1 z(p)i Ci — структурное число цикла г; QO. _ структурное число дерева, содержащего все вер- шины графа, кроме вершин инцидентных грани к; дм- — структурное число дерева, содержащего все вер- шины графа, кроме вершины ^i; йц ц, — путь, соединяющий вершины y,i и и,з в графе; det'A — детерминантная функция структурного числа А z по отношению к множеству элементов Z; Е — напряжение источника э. д. с.; g — число ребер или блоков графа, число ветвей или многополюсников электрической 'цепи; К ас — передаточная функция напряжения, измеренная между путем а, представляющим собой вход четырехполюсника, и путем с, представляющим _ собой выход четырехполюсника; 12 ОБОЗНАЧЕНИЯ Kabcd — передаточная функция напряжения четырехпо- люсника с замкнутыми путями с, d, . . ., изме- ренная между путями а и Ъ', М — цикломатическое число графа; Р — множество вершин графа; Р — таблица порядков структурного числа ^А блоч- ного графа; -и — обозначение отношения, понимаемого как под- множества произведения множеств; Sim (A, B)v^ —функция совпадения структурных чисел А и В Z . при условиях (р и г[з; Т — число деревьев графа; Гд — число ^--деревьев графа; Тц — число скелетов блочного графа; U — множество ребер графа, напряжение; v — число вершин графа, число узлов электрической цепи; у; — число вершин замещающего графа; Уд — число зажимов многополюсника И7, число кон- цов графа Гу. W — многополюсник; Х сГг Y — включение системы Х в состав системы У; Х [Jr Y — объединение систем Х и У; Х П г "У — пересечение систем Х и У; Уц(И2 = Уа — проводимость электрической цепи между узлами ^i и (-la пути а; Yabc-'-k — проводимость электрической цепи с замкнутыми путями Ь, с, . . ., k, измеряемая относительно конечных узлов пути д; Hi — проводимость ветви; Zo — множество деревьев блоков графа; ^HiUa = Za — сопротивление электрической цепи, измеренное между конечными узлами (Xi и (ig пути а; Zabc--- h — сопротивление электрической цепи с замкнутыми путями Ь, с, . . ., k, измеренное относительно конечных узлов пути а; ZI — цепь с нулевым импедансом; z; — сопротивление ребра г; Sij — символ Кронекера; де4 -а— — алгебраическая производная структурного чис- ла А по элементу а; — обозначение импликации; /=> — обозначение отрицания импликации; А [} В — объединение множеств А и В; А [} В — пересечение множеств А и В', а ^ А — обозначение принадлежности элемента а множе- ству А; А с: В — обозначение включения множества А во множе- ство В; /\ — квантор общности; V — квантор существования; /\ — знак конъюнкции; у — знак дизъюнкции; ^ — знак симметричной разности. Глава, 1 Формальное определение системы 1, Введение Одним из основных понятий техники служит понятие «система». Однако оно иногда формулируется недостаточно ясно и пони- мается в большинстве случаев интуитивно. Чисто интуитивное толкование понятия «система» может привести к недоразумениям и противоречиям, подобно тому как в свое время интуитивное /Ал^^ ^ ^ r^S^ 1 модель j ^геометрическое] Q\ j \представ- j \ / \леиие) / '——\ Г——" ==> \ / /^\ {Лонкретная \ \ модель I \(физическое ] \ представ-1 \ ленче) у Фиг, 1.1. Модели системы. толкование понятия «множество» привело к противоречиям в тео- рии множеств. Поэтому необходимо сформулировать строгое, но вместе с тем достаточно общее определение системы, которое легло бы в основу аксиоматического метода в теории систем. Аналогично другим физическим теориям целесообразно создать абстрактную теорию систем, которой можно впоследствии дать определенную физическую и геометрическую интерпретацию, при- чем в физической интерпретации выделить понятие «конкретная система», приближенно отображающее рассматриваемую физиче- скую систему. Таким образом получаем три основные модели систем, показанные на фиг. 1.1. Эти-модели не случайны и имеют аналогии в других теориях. Придавая понятию «система» различные смысловые значения и физические интерпретации, можно применять теорию систем 16 ГЛАВА 1 при решении разнообразных задач, например в экономике, био- логии и т. д. Такой подход, в частности, используется при реше- нии проблем кибернетики. Необходимо подчеркнуть огромные заслуги кибернетики, которая дала возможность исследовать с одних и тех же позиций многие проблемы как технических, так и биологических систем. 2. Абстрактная модель системы Построение абстрактной модели системы основано на теории множеств и теории отношений. Пусть дано счетное множество М, определенное в эвклидовом пространстве Е"'. На множестве М определим бинарное отношение R как подмножество декартова произведения М Х М И с М X М. (1.1) (i.i) Следовательно, отношение R представляет собой множество упорядоченных пар {х, у} некоторых элементов множества М. Если пара (х,у)—элемент множества 7?, то это множество можно записать в виде xRy и назвать пару (а", у ) парой, приве- денной в отношение. Таким образом, имеем xRy <=> (а-,г/)е^.. (1.2) Если пара {х, у) не приведена в отношение, то можно записать «х не Ry», т. е. х не Ry <=> (х, у) ^ R. • (1,3) Можно также сказать, что «ж находится в отношении R к у» для случая xRy и «х не состоит в отношении R к г/», если х не Ry. Левосторонней областью d[R отношения R называется множество предыдущих элементов пар, принадлежащих R. Правосторонней областью dpR отношения R называется множество последующих элементов пар, принадлежащих R. Сумму этих областей определим как поле отношения R и обозначим через ,f~R. Следовательно, yR = dtR U dpR. (1.4) Для выделения понятия предыдущего и последующего элемен- тов в паре (х, у) используем обозначения Тогда (1.5) (1.6) Y.I.U/ и rf;r служит элементом левосторонней области, a d?r — элементом правосторонней области отношения R. Введем следующие определения. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ СИСТЕМЫ 17 Определение 1.1. Бинарное отношение R называется струк- турным отношением на множестве М тогда и только тогда, когда для каждой пары таких непустых множеств Х и У выполняются соотношения Х U У = М, Х П У = ф (1.7) и существуют элементы х G Хи у 6 Y, для которых справедливо по крайней мере одно из отношений xRy или yRx. (1.8) Понятие структурного отношения будет полезно при опреде- лении системы. Определение 1.2. Бинарное структурное отношение -и на множе- стве М в эвклидовом пространстве называется абстрактной У х У ^ Фиг. 1.2. Одномерные симплексы. или теоретико-множественной системой. Элементы отношения -R называются элементами теоретико-множественной системы. Согласно этому определению, понятие «система» идентично понятию «структурное отношение». Из определения 1.2 следует, что система не может содержать изолированных элементов, т. е. каждый элемент множества М состоит в определенном отно- шении R по крайней мере еще с одним элементом множества М. Таким образом, множество М служит полем структурного отно- шения R М = yR, (1.9) Элементы поля отношения R, т. е. элементы множества М, назовем вершинами системы R. Естественно, что каждая вершина системы есть элемент по крайней мере одной из областей d[R или dpR. Если элемент г представляет собой пару {х, у), то х будем считать началом, а у концом элемента г, т. е. г = (х, у) =>- х — начало элемента г; у — конец элемента г. (1.10) Необходимо выделить некоторые основные виды систем, кото- рые наиболее часто встречаются на практике. Определение 1.3. Абстрактная система называется ориенти- рованной, если определяющее ее отношение антисимметрично, 3—0298 18 ГЛАВА 1 т. е. если выполняется следующее условие: х, у б М ^- (xRy =>у ав Rx). (1.11) Если условие xRy => у не Rx выполняется не для всех эле- ментов х, у множества М, то систему будем считать ориентиро- ванной частично. Система называется неориентированной, если определяющее ее отношение симметрично на множестве М, т. е. если (1.12) С другой стороны, система считается ориентированной в слу- чае, когда R представляет собой слабо симметричное отношение на множестве М, т. е. когда х, у ^М=> (xRy и yRx=^-x=y). (1.13) Определение 1.4. Абстрактная система называется замкнутой, если определяющее ее отношение связно, т. е. если выполняется условие х, у $ М =>• (xRy или yRx). (1.14) Из этого определения следует, что каждые две вершины такой системы одновременно служат вершинами одного из элементов системы. Определение 1.5. Абстрактная система содержит собственные элементы в том случае, когда для некоторых х 6 М имеет место отношение xRx. (1.15) Примером такой системы служит система, определенная при помощи рефлексивного отношения, удовлетворяющего условию xRx. (1.16) Определение 1.6. Вершины абстрактной системы, которые представляют собой только начала ее элементов, называются входами системы, тогда как вершины, представляющие собой только концы ее элементов, называются выходами системы. Введем понятие граничных вершин и границы системы. Определение 1.7. Входы и выходы абстрактной системы назы- ваются граничными вершинами системы; остальные вершины системы называются внутренними вершинами. Множество гранич- ных вершин называется границей системы. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ СИСТЕМЫ 19 Если обозначить: Х — множество входов, У — множество выходов, В — граница системы, то получим Х == diR — dpR, Y = dpR - diR, (1.17) В = diR ^ dpR, где знаком ^ обозначена симметричная разность множеств, опре- деленная в виде diR ^ dpR == (diR - dpR) [] (dpR - diR}. (1.18) Определение 1.8. Абстрактная система, имеющая выходы и не имеющая входов, называется ,возбуждающей системой. Система, имеющая только входы, называется конечной системой, а система, имеющая как входы, так и выходы, определяется как относи- тельно обособленная система. Система, не имеющая границы, называется обособленной системой. Таким образом, система возбуждающая, если diR — dpR = ф, (1.19а) конечная, если dpR - diR = ф, (1.196) относительно обособленная, если dpR — d:R=^ ф и diR — dpR Ф <;>, (1.19в) и обособленная, если diR ^ dpR = ф. (1.19г) 3. Топологическая модель системы 3.1. Определение топологической системы Под одномерным симплексом будем понимать гомеоморфное преобразование отрезка (геометрического симплекса). На фиг. 1.2 показано несколько одномерных симплексов с вершинами (вер- шины симплекса обозначены кружками). Одномерный симплекс с вершинами х, у обозначим симво- лом (х, у). Пусть задана абстрактная (теоретико-множественная) систе- ма Л; определим преобразование Г (R) = S Г (г), гед (1.20) устанавливающее взаимно однозначное соответствие между эле- ментами г = (а;г, Уг) системы и непустым подмножеством Sr 2* 20 ГЛАВА 1 одномерных симплексов с концами в точках х^ и у^. Преобразова- ние Г будем называть геометрической интерпретацией системы R. Обозначив S = Г (R), (1.21) можно выразить преобразование Г формулой S = Г (R) ^ Г {г) == Sr с 5;. 5, ^ ф, (1.22) где б' — множество одномерных симплексов со свойствами Sr б Sr <=>Sr = (ж^г/г); г ==-<ж„ Ут-). (1.23) Определение 1.9. Множество S одномерных симплексов со свойствами, выраженными формулами (1.22) и (1.23), называется топологической системой, определенной на структурном отно- шении R. Очевидно, что в некоторых случаях подмножество Sr в выраже- нии (1.22) может содержать лишь один элемент. Тогда элементу г ставится в соответствие только один симплекс. Симплексы s ^ S называются ребрами или элементами топо- логической системы, а вершины симплексов — вершинами системы. Топологическую систему будем считать ориентированной (частично ориентированной), если все '(некоторые) симплексы s связного множества S, представляющего эту систему, ориенти- рованы. Если ни один из симплексов s С S не ориентирован, то систему будем считать неориентированной. Все понятия, введен- ные для абстрактной системы R, распространяются на ее геоме- трическую интерпретацию S = Г (R). Таким образом, если систе- ма R возбуждающая, конечная, обособленная, относительно обо- собленная и т. д., то топологической системе S = Г (R) приписы- ваем те же самые понятия. Подобно абстрактной системе R, множество всех вершин топологической системы, представляющих собой только входы элементов ориентированной системы S, будем обозначать d[S, а множество вершин-выходов элементов обозначим dpS. На множестве топологических систем можно определить неко- торые операции, например сложение и умножение. Под суммой и произведением ^i u s„ Si n s^ (1.24) двух топологических систем iS'i и «S'2 будем понимать соответствую- щие операции алгебры множеств. Очевидно, что сумма Si U •S'2 представляет собой систему только тогда, когда она образует связное множество (по определению 1.1), в противном случае она представляет собой пару систем. Понятие топологической системы близко к понятию графа или мультиграфа, но не равнозначно им. Согласно определению ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ СИСТЕМЫ 21 Бержа, граф — это упорядоченная пара {X, G} множества Х вершин и многозначного преобразования G (х) с: X, трансформи- рующего начала ребер в их концы. Очевидно, что, согласно этому определению, ориентированная топологическая система всегда представляет собой граф или мультиграф. Однако не каждый граф (мультиграф) представляет собой систему, так как для него не обязательно требуется условие связности. Существуют графы, которые не являются системами в том смысле, в котором здесь употребляется это понятие. 3.2. Структура системы Согласно принятому определению" одномерного симплекса, ребра системы можно произвольно растягивать, не изменяя топо- логических свойств, определяемых только способом соединений ее элементов. Структура системы, чаще всего понимаемая чисто интуитивно, определяется способом соединений, не изменяющимся Фиг. 1.3. Топологические системы с мостовой структурой. при любых непрерывных преобразованиях ребер. На фиг. 1.3 изображено несколько топологических систем с одинаковой так называемой мостовой структурой. Уточним теперь понятие структуры на основании свойства гомеоморфных преобразований. Две системы iS'i и Sz называются гомеоморфными, если суще- ствует неоднозначная функция f(S) = S / (s), s?S (1.25) непрерывная и имеющая непрерывное обратное значение f~1, которая отображает «S'i на (системы «S'1 и S^ гомеоморфны). (1.26) Следовательно, структура S — инвариант гомеоморфных пре- образований системы. Гомеоморфное преобразование системы (1.25) будем также называть изоструктурным преобразованием, а гомеоморфные системы — изоструктурными системами. Изоструктурные системы характеризуются одинаковой структурой. Любое негомеоморфное преобразование системы называется структурным преобразова- нием. Пусть* имеются две изоструктурные системы >S'i и S^- Легко заметить, что каждое свойство системы Si, выраженное с помощью логических понятий и отношений, определяющих эту систему, будет полностью также и свойством изоструктурной системы Sy,- Следовательно, изоструктурные системы не отличимы по свой- ствам, выраженным с помощью логических понятий и определяю- щих их отношений. 3.3. Основные структуры топологических систем Важным понятием теории систем служат понятия пути, цикла, звезды и дендрита, которые приводятся ниже. В соответствии с терминами алгебраической топологии одно- мерной последовательностью называется выражение вида L = ^si + ^2 + . • - + ^s„, (1.27) где Si, $2, . . ., s„ — одномерные ориентированные симплексы; Ki, Xg, . . ., Кп — целые числа. Последовательность (1.27) пред- ставляет собой линейную комбинацию переменных Si, . . ., s^ с коэффициентами ^1, . . ., К^- Принимаем, что умножение сим- плекса на —1 означает изменение его ориентации, т. е. —1 (х, у) = (у, ж). Следует заметить, что выражение (1.27) пред- ставляет собой коммутативную (абелеву) группу. Границей одно- мерного симплекса s = (ж, у) называется нульмерная последова- тельность вида 9s = у — х, (1.28) а граница последовательности (1.27) определяется формулой дЬ = S Д, д81. (1.29) г Операция определения границы представляет собой гомео- морфизм, преобразующий группу одномерных последовательно- стей в группу нульмерных последовательностей. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ СИСТЕМЫ 23 Рассмотрим подмножество Р элементов системы S, обозначив через Р* последовательность вида Р*= S Р.- (1.30) Определение 1.11. Если для подмножества Р элементов топо- логической системы S справедливы условия дР* == у - х; др, ^ О, (1.31) где Р* = S Рь х 6 diP, у б dpP, р^Р то подмножество Р называется, путем системы S. Геометрическое изображение пути — граф — показано на фиг. 1.4. Следовательно, путь в топологическом смысле представляет собой кривую, составленную из некоторого числа симплексов. Фиг. 1.4. Геометрическое изображение пути. Если подмножество Р с: S образует путь после изменения ориентации некоторых его элементов, то такое множество назы- вается мнимым путем. С понятием пути связано важное понятие правильной ориента- ции системы. Условимся называть систему правильно ориентиро- ванной, если существует путь из каждой его внутренней вершины к каждому из его выходов. Определение 1.12. Если путь С топологической системы S удовлетворяет условию дС* = 0, (1.32) то такой путь называется циклом (фиг. 1.5). Если путь С становится циклом лишь при изменении ориен- тации некоторых его элементов, то такой цикл называется мни- мым и обозначается С1'. Цикл, содержащий два элемента, назы- вается бинарным С ={Ci, С,}. Определение 1.13. Если все элементы системы S имеют общее начало (конец) и система не содержит мнимых циклов, то такая 24 ГЛАВА 1 ^".бГ^" расходяшейся ^ездой (или сходящейся) Определение 1.14. Система, не содепжяптяст тт„, ,.-л... ...ы„..с, ^™ (Фиг ?CrC;S°;e"cr;S /I Фиг. 1.5. Пример ци- кла. Фиг. 1.6. Примеры систем, соединен- ных звездой: а) расходящаяся звезда; б) сходящаяся звезда. Фиг. 1.7. Пример дендрита (а) и псев- додендрита (б). щая циклов, но содержащая мнимые циклы, называется псевдо- дендритом (фиг. 1.7, б). Примером псевдодендрита служит система, определенная с помощью транзитивного отношения -ff: xRy, yRz =>- xRz для произвольных х, у, z С Л^. (1.33) 3.4. Классы подобия топологических систем Инженер-электрик, изучающий теорию цепей, хорошо знает, что электрическую цепь с определенными динамическими харак- теристиками, например корректирующее устройство или электри- ческий фильтр, можно реализовать различным образом с помощью цепей с разными структурами (мостовой, цепной и т. д.). Это следует из общего принципа, согласно которому цепи с различной топологической структурой могут иметь одинаковые свойства, например идентичным образом преобразовывать сигнал. С этой точки зрения для большинства практических задач представляет интерес не столько проблема реализации той или иной структуры, сколько определение классов структур, для которых выполняются ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ СИСТЕМЫ 25 заданные условия. Оказывается, что в большинстве задач как синтеза, так и анализа электрических цепей для определения классов структур необходимо исследовать способ разложения этих структур на дендриты. Дальнейшие рассуждения посвящены именно этой проблеме. На связном множестве S одномерных симплексов, определяю- щих топологическую систему, определим многозначную функ- цию / со значениями из множества N натуральных чисел f:S-^N. (1.34) Следовательно, функция / ставит в соответствие симплексам si ^ S натуральные числа сх; / (s.) = ", (1.35) таким образом, что каждому симплексу соответствуют различные числа к;. Многозначную функцию (1.35) назовем описывающей функцией, а топологическую систему, для которой определена такая функ- ция, будем называть детерминированной системой. В этом случае можно также говорить о «детерминированном графе». Детерминированные системы далее будем обозначать пропис- ными буквами Л, •38, 'S и т. д. В соответствии с этим такие системы можно рассматривать как упорядоченные пары Л = (S,f} (1.36) множества S одномерных симплексов и описывающей функции /. Дендрит, для которого определена описывающая функция, называется детерминированным дендритом или деревом. Два дерева ^1 = <^,/i) И ^2 = <52,/2> будем считать подобными, записывая Si -~ 3)ч, если fi (Si) = = /2 (Sz), т. е. 3), ~ ^2 ^ h (5i) = h (S,). (1.37) Другими словами, два дерева подобны, если прообразы описы- вающих их функций составляют одно и то же подмножество множе- ства натуральных чисел. На фиг. 1.8 изображены два примера подобных деревьев. Из принятого определения подобных деревьев следует, что подобные деревья должны иметь одинаковое число ребер 1), т. е. 2i = ^2. (1.38) 1) Согласно символике, принятой в теории множеств, обозначения 3„ S-i представляют собой мощность множеств 3^ и Si- 26 ГЛАВА 1 Действительно, в каждой дискретной детерминиооваттпй системе можно выделить некоторое семейство дерев^^образован ных ребрами этой системы и соединяющих все еЙ вершины Если дерево Si образовано ребрами системы ^, то его моТно^азвать деревом системы А и написать можно назвать S>i 6 Л. • (1.з9) Получение всех деревьев данной системы назовем разложе нием системы на деревья. Введем понятие подобных систем! Фиг. 1.8. Примеры подобных деревьев. Две детерминированные системы •^-(•^А) и S =(S„f,) (i.4o можно считать подобными, записывая А ~ i?, если их разложе вия на деревья содержат исключительно подобные дере^я точ^е; Л ^ !S <^ (^ е ^<^.^ 6 SS} А (^л ~ ^). (1.41) Фиг. 1.9. Две системы с подобной структурой и их разложение на деревья. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ СИСТЕМЫ 27 Можно заметить, что отношение подобия систем рефлексивно симметрично и транзитивно, т. е. Л ~ ^, Л ~ S8 <=> SS ~ Л, А ~ 3S, 3S ~ ^ => Л ~ ^. (1.42) Следовательно, подобие систем представляет собой отношение эквивалентности. Таким образом, отношение подобия приводит к разделению множества детерминированных систем на отдельные классы подоб- ных систем (структур). Классы подобных структур обозначим символами ^, 96, 'ё, приняв следующее определение. Определение 1.15. Классом подобия детерминированных топо- логических систем называется объект Л, обозначающий семейство подобных систем dt, удовлетворяющих условию А = SB (системы Л и S подобны). (1.43) На фиг. 1.9 приведен пример двух систем с подобными струк- турами и разложение их на деревья. 4. Конкретная модель системы 4.1. Введение Конкретная система есть не что иное, как топологическая система, которой поставлены' в соответствие некоторые физические свойства. Следовательно, конкретная система это физическая интерпретация топологической системы. Ее можно рассматривать как более или менее точное приближение физической системы. Сущность конкретных систем может быть весьма разнообразной. Это могут быть электрические цепи, тепловые, гидравлические, пневматические, химические, биологические и другие системы. Независимо от физической сущности конкретные системы можно разделить на два основных типа: системы передачи сигнала и сете- вые системы. Эти два типа конкретных систем и будут рассматриваться в дальнейшем. 4.2. Системы передачи сигналов Определение 1.16. Системой передачи сигнала называется такая конкретная система, для которой топологическая система пра- вильно ориентирована и удовлетворяет следующим условиям: 28 ГЛАВА 1 1) вершинам топологической системы ставятся в соответствие физические величины (сигналы) д\, (: X, т. е. определяется функция f:M->X; 2) для а\, выполняются соотношения 1 •^l+l == ^J -t V^V) (1.44) (1.45) где а^, a"ft+i, . . ., х, — сигналы, соответствующие начальным вершинам всех элементов системы с общим концом, соответствую- щим сигналу а-г+i (фиг. 1.10). Операторы 7\„ преобразующие сигналы Ху а^-и, . . ., а", в сигнал a;,-i-i, называются передаточными функциями элементов системы. Принципиальное различие между сетевыми системами и систе- мами передачи сигнала состоит в том, что в случае систем передачи Фиг. 1.10. Узел .системы передачи сигнала. сигнала сигналы ставятся в соответствие только вершинам систе- мы. Роль самих элементов системы передачи сигнала, которая всегда правильно ориентирована, сводится лишь к преобразова- нию сигналов в соответствии с их операторами — передаточными функциями элементов системы 7\,- Системы передачи сигнала — широко распространенные типы систем. Например, любая электрическая линия,, линия теле- передачи, радиолиния — это системы передачи сигнала. Анало- гично каждая система автоматического регулирования, в боль- шинстве случаев рассматриваемая как блок-схема, относится к системам передачи сигнала. С точки зрения теории систем передачи сигнала каждый блок такой системы представляет собой просто единичную ориентированную ветвь системы передачи (фиг. 1.11). Такое упрощенное геометрическое представление систем в зна- чительной мере облегчает исследование сложных кибернетических ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ СИСТЕМЫ 29 систем, таких, как биологические системы и технические системы автоматического управления. В зависимости от свойств оператора Т различают большое число систем передачи сигнала. В частности, с помощью таких систем хорошо представляются логические схемы. Например, система, изображенная на фиг. 1.12, может представлять как Хц, х, т •2'г - — о——»————о Ф и г. 1.11. Элемент системы пере- дачи сигнала. Ф и г.. 1.12. Реализация ло- гической суммы и произ- ведения. элемент логического суммирования, так и элемент логического умножения. Очевидно, в данном случае рассматриваются дискрет- ные сигналы с величинами 0 или 1. Для реализации логической суммы принимаем следующее; 1) операторы Ti и Тч тождественны, т. е. Ti = Т 4 = I; 2) оператор Т^ определяется по формуле или х-г. == 1, 1 ДЛЯ Xi = 1 Т12 (a-i + жг) = для Xi = х-г. = 0. Аналогично для реализации логического произведения при- нимаем, что Ti = Т ч == I, а также Т12 (a-i + а-г) = 1 для Xi = а-г = 1, О для Xi = 0 или а-2 = 0. Особенно интересны^линейные системы передачи сигнала. Теория линейных систем, разработанная С. Мэзоном [21—24], позволяет значительно упростить и сократить расчеты в электро- нике и автоматике, связанные с анализом сложных систем. 4.3. Сетевые системы Определение 1.17. Сетевой системой назовем конкретную систе- му, соответствующую топологической системе, вершинам и ребрам которой поставлены в соответствие некоторые физические вели- чины, а именно определены функции А: М-^Х, i. ^V (1-46) /2. О —>- J , 30 ГЛАВА 1 где X и У — множества физических величин, т. е. множества, имеющие определенные размерности в конкретной системе еди- ниц, например в системе СГС. Элементы множеств Х и У в основном представляют собой функции времени; условимся называть их сигналами. Элементы ^ ^ о- б) х, xi -О 0- Фиг. 1.13. Обоз- Фиг. 1.14. Обоз- Фиг. 1.15. Гиристор (в) и начение унистора. начепие униполяр- биполярный элемент (б). ного элемента. х ^ X, соответствующие вершинам системы, будем называть сигна- лами вершин, а элементы у (: У, соответствующие элементам системы,— сигналами элементов. Элементы сетевой системы в соответствии с их свойствами можно разделить на несколько категорий: унисторные элементы (унисторы), униполярные элементы, гиристорные элементы (гири- сторы), а также биполярные элементы. Унисторным элементом или унистором называется ориенти- рованный физический элемент, сигнал которого представляет собой результат однозначного преобразования, произведенного над сигналом входной вершины. Обозначение унистора приведено на фиг. 1.13. Согласно опре- делению унистора и принятому обозначению, можно написать Vi = TtXi, (1.47) где Т'{ — оператор, определяющий свойства унистора. Следует заметить, что сигнал унисторного элемента совер- шенно не зависит от сигнала выходной вершины. Униполярным элементом называется ориентированный физиче- ский элемент, сигнал которого определяется формулой Г Т, (х, - ж,.), х, < х„ ^{о, ./>.,. (1Л8) Обозначение этого элемента г/, и значения величин ж; и х, приведены на фиг. 1.14. Из определения (1.48) следует, что этот элемент аналогичен вентилю. Следует отметить, что сигнал этого элемента зависит как от сигнала его входа, так и от сигнала его выхода. Гиристорным элементом или гиристором называется физиче- ский элемент, сигнал которого имеет вид у. = Г, (х, + х,). (1.49) ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ СИСТЕМЫ 31 Биполярным (обратимым) элементом называется такой эле- мент, сигнал которого равен у, = Т, (х, - х,). (1.50) Смысл величин у;, х^. Ху здесь тот же, что и раньше. Обозначе- ния гиристора и биполярного элемента приведены на фиг. 1.15. Системы, содержащие элементы одного типа, например только унисторы, гиристоры и т. д., соответственно называются унистор- ными, гиристорными и другими системами. Если система содержит Т +Т Фиг. 1.16. Соединения унисторов. различные типы элементов, то такая система называется сме- шанной. Оператор Г;, определяющий свойства данного элемента сете- вой системы, называется определителем элемента. Следует подчеркнуть, что гиристор и биполярный (обратимый) элементы представляют собой производные элементы от унистора, Сетевые системы Униполярные системы Унисторные системы Смешанные системы Гиристорные системы Биполярные системы Фиг. 1.17. Классификация сетевых систем. так как эти элементы можно рассматривать как соответствующие соединения унисторов (фиг. 1.16). Таким образом, гиристорные и обратимые системы представ- ляют собой частные случаи унисторных систем. Сетевые системы можно классифицировать, как показано на фиг. 1.17. Если определитель данного физического элемента удовлетво- ряет условию Т [ Г (и) = Си, (1.59) 3-0298 34 ГЛАВА 1 где Си — двумерный локально связный континуум со следующи- ми свойствами: 1) в континууме выделены некоторые граничные точки Xi, а"2, . . ., я;,, . . ., называемые вершинами, т. е. ^и = \^ii ^ti • • ч •^i) • • •)! 2) имеет место соотношение С» = Г (U) <=f> U =<Ж1, Ж2, . . ., Х„ . . .}. (1.60) На фиг. 1.19 приведен пример топологической системы второй категории, Конкретная система второй категории определяется по аналогии с конкретной системой первой категории. Таким образом, обобщенное понятие системы основано на введении понятия системы второй категории. Это рассуждение Фиг. 1.19. Топологическая система второй категории. можно повторять далее и получать, следовательно, иерархические типы систем высших категорий. Общим свойством систем, рас- смотренных в предыдущих разделах, была их «дискретность». Они состояли из счетного числа дискретных элементов и назы- вались дискретными системами. Несмотря на то что дискретные системы представляют собой очень важный распространенный тип систем, они не являются единственными системами, с кото- рыми приходится иметь дело. Глава 2 Алгебра структурных чисел 1. Основные понятия 1.1. Определение структурного числа Пусть Э! — подмножество абстрактного пространства (SF. Эле- менты множества Ш обозначим "г, Рг, Vi, ... 6 -Я". Рассмотрим систему элементов в виде таблицы С6ц Ctl2 • • • t^lTi 0^21 Й22 . . . OC2ra Л= (2.1) Будем рассматривать эту систему как совокупность столбцов ^' т- е- A •^{"^ Я2» . • ., On}, a-i^a-s (i ^ ])• (2.2) Столбцы а^ в свою очередь представляют собой неупорядоченные множества элементов ос,^ "ь ={"ift, с'2й, • • •- «т^}> "гь ^ a-jk (i^))- (2.3) Столбцы будем считать равными, если они содержат одинаковые элементы. Положим по определению, что система (2.1) не содержит одинаковых столбцов. Систему типа (2.1) будем рассматривать как элемент новой алгебры — алгебры структурных чисел. Соглас- но определениям абстрактной алгебры, алгебру структурных чисел можно отнести к категории операторных алгебр, т. е. ее можно характерлзовать упорядоченной тройкой (Е, и, е>. где Е — носитель алгебры (в нашем случае семейство множеств); и — двухэлементное множество операторов e>i, 0)2, определяющих сумму и произведение; е — результат, т. е. функция, которая выражению АшВ ставит в соответствие элемент С ^ Е, являющий- ся результатом действия. Введем вспомогательное понятие, которое используем при определении структурного числа. З* •36 ГЛАВА 2 Рассмотрим последовательность элементов а";, необязательно различных: (Я"1, 3-2, . . ., Xi, . . ., х^}. (2.4) Обозначим через г (з-д) — число одинаковых элементов после- довательности (2.4). Структурным числом называется система элементов (а ^ В) или А =В <^ /\(а^А <=> я 6 5). (2.5) а Определение 2.2. Суммой структурных чисел А и В называется структурное число С ={х ( (а-6 4) V (^ 6 5), х^А П В} ==А^В; (2.6) в этом случае можно написать С == А + В. Выражение А •й В в формуле (2.6) означает симметричную разность множеств А и В. Определение 2.3. Произведением структурных чисел А и В называется структурное число С =={й U Ъ | а П & = ф, г (a U Ь) 6{1, 3, . . .,} а 6 4, & 6 5}, (2.7) которое записывается в виде С == АВ. В соответствии с определением суммы при сложении структур- ных чисел опускаются столбцы, одновременно присутствующие в обоих числах Л и -и, а в соответствии с определением произведе- ния при умножении структурных чисел А и В опускаются те столбцы a U t>, в которых какой-либо элемент повторяется, т. е. для которых а П b ^ ф, а также опускается четное число идентичных столбцов. Можно заметить, что равенство структурных чисел пред- ставляет собой отношение эквивалентности, т. е. является реф- лексивным, симметричным и транзитивным. Далее будут приведены примеры действий со структурными числами, элементы которых а,й (: Х представляют собой нату- ральные числа (этот случай имеет большое значение для приме- нения алгебры структурных чисел), а также даны словесные фор- мулировки действий со структурными числами, которые менее точны, чем вышеприведенные, однако более понятны для читателей, не имеющих достаточной математической подготовки. АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 37 Пример 2.1. Равенство структурных чисел: Г1 1 21 _ Г5 1 11 _ Г2 2 31 1.3 2 5J == |_2 3 2J = [I 5 lJ • Два структурных числа равны, если содержат идентичные столбцы, независимо от порядка элементов в столбцах и порядка столбцов. Пример 2.2. Сложение структурных чисел: "2 3 4- 757 + '3 2 5" 7 4 •2 3 4 3 2 5 .757 74 -"3435- 57 4 Суммой двух структурных чисел A is. В называется структур- ное число, содержащее все столбцы чисел А и 5, за исключением идентичных столбцов, и не содержащее других столбцов. Пример 2.3. Умножение структурных чисел: 1 3 11 2 4 3J ГЗ 2 21 L 3J = -122-2 3 1 .3 4 3. == Г213!.4J Произведением двух структурных чисел А и В называется структурное число, столбцы которого представляют собой суммы (согласно понятиям теории множеств) всех возможных комби- наций столбцов А и 2?, за исключением наибольшего четного числа идентичных столбцов и таких столбцов, в которых какой- либо элемент повторяется (произведение других столбцов не содержит). Из определения суммы и произведения структурных чисел следует, что эти операции всегда можно выполнить на множестве этих чисел. Из тех же определений можно сделать вывод, что сложение и умножение структурных чисел коммутативны и ассо- циативны, а умножение дистрибутивно относительно сложения. Для трех произвольных структурных чисел имеют место следующие соотношения, подобные тем, которые справедливы для элементарной алгебры: А+В= В+А, АВ = ВА, А (ВС) = (АВ) С, А (В + С) = АВ + АС. (2.8) Следует различать структурное число [ф], содержащее один столбец, который является пустым множеством ф, и структурное число [ ], не содержащее ни одного столбца. 38 ГЛАВА 2 Заметим, что число [ ] служит модулем суммирования и для произвольного структурного числа А выполняется равенство А + [ ] =А, поэтому число [ 1 будем обозначать символом 0, записывая его в виде [ ] =0. (2.9) Число [] в свою очередь есть модуль умножения, так как А [ф} = А, (2.10) поэтому число [ф\ обозначим символом 1, записав [ф\ = 1. (2.11) Для любого А имеет место соотношение А[ ] = [ ]. Рассмотрим структурное число вида А ={ф, й1, из, . . ., ад,}, (2.12) т. е. число, содержащее один пустой столбец. Легко заметить, что для такого числа справедливо равенство АА == 1. Для структурных чисел, не содержащих пустого столбца, АА = 0. Если множество структурных чисел вида (2.12) обозначить как ^, а множество всех остальных структурных чисел — как 1?, то можно написать {А е^) =>АА = 1, (А ^98} ^АА =0. (2.13) Следовательно, легко заметить, что для произвольного структур- ного числа Л+^1+...+-4= [^ "рн нечетном числе слагаемых п, п~раз[0 при четном п. (2.13а) Таким образом, А + А = 0. (2.136) Из соотношения (2.13) вытекает, что равенство АВ = О АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 39 не требует в общем случае равенств А = 0 или В = 0, т. е. мно- жество структурных чисел содержит делители нуля. Пару струк- турных чисел, для которой выполняется равенство АВ = О, назовем особой парой. Пример 2.4. Особую пару представляют собой следующие структурные числа А и В: А = "1 3" 2 2 В = •I 2" "1 3" 3 4J ' так как l2 2 -1 2- 3 4 = 0. Естественно, число [ ] == 0 в сочетании с любым структурным числом дает особую пару. Обобщая изложенные свойства структурных чисел, можно сформулировать следующие теоремы. Теорема 2.1. Множество структурных чисел, на котором определены операции сложения и умножения, образует комму- тативное кольцо. Это кольцо обычно содержит делители нуля. Из определения суммы и произведения следуют соотношения, справедливые для любого структурного числа: Кц ... СТщ V,mi • • • Vim.n'n «1ft -^ h=l «1ft П ^ = Пs^' (2.14) где s^ == [oc,J — одноэлементное структурное число. Теорема 2.2. Структурное число А всегда можно представить в виде (2.15) где s^ = [aJ. Следует отметить, что выражение (2.15) в алгебре структурных чисел играет роль, аналогичную выражению z == а + ib в теории функций комплексного переменного, с помощью которой можно записать любое комплексное число г =(а, Ъ}. Структурное число s„ == [o^i/J называется структурной еди- ницей, которая служит аналогом действительной или мнимой единицы в области комплексных чисел. 40 ГЛАВА 2 1.2. Вычитание структурных чисел Рассмотрим два произвольных структурных числа А и В. Из определения равенства и суммы структурных чисел следует, что существует только одно структурное число, удовлетворяю- щее равенству В + Х = А, (2.16) которое вследствие коммутативности суммирования структурных чисел можно переписать как Х +В =Л. (2.16а) Структурное число X, удовлетворяющее равенствам (2.16) и (2.16а), называется разностью структурных чисел А и В: X = А - Д. Действие нахождения разности структурных чисел назы- вается вычитанием. Легко заметить, что разность чисел А и В есть число Х = А + В. Действительно, подставляя в выраже- ние (2.16) Х == А + В, получаем уравнение В +(А +В) =А, которое в соответствии с (2.136) представляет собой тождество. Таким образом, получаем обоснованное соотношение Л —В = А + В, (2.17) которое в случае А == 0 записывается в виде -В == В. (2.18) Из сказанного следует, что на множестве структурных чисел вычитание всегда можно заменить сложением. Вычитание, следо- вательно, определено однозначно и всегда выполнимо, поэтому множество структурных чисел замкнуто по отношению к сумми- рованию и вычитанию. Подводя итог рассмотренным свойствам структурных чисел, можно заключить, что кольцо структурных чисел 1) не содержит степеней и 2) не содержит коэффициентов (кроме 0 и 1); а 3) сложе- ние идентично вычитанию. 2. Свойства структурных чисел 2.1. Делители нуля Пусть А* — множество структурных чисел X, удовльтворяю- щее уравнению АХ = О, АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 41 пусть А* — элементы где А — некоторое структурное число, этого множества. Тогда АХ = 0 =>- Х = At 6 А*. (2.19) И Числа А* ^ А*, удовлетворяющие уравнению АХ = 0, назы- ваются сопряженными по отношению к А или делителями нуля. Следствие. Если два структурных числа Xi и Ха удовлетворяют равенству АХ = 0, то такому же равенству удовлетворяет их линейная комбинация C^Xi + C^X^i а также произведение CXiX^, где Ci, Cg, С — произвольные структурные числа, включая 0 и 1. Тогда. Xi, Xz еА*=^СА + СзХгбА*; СХАбА*. (2.20) Обоснование этого положения элементарно и предлагается выпол- нить читателю. Полагая в выражении (2.20) Ci == С 4 == С = 1, приходим к выводу, что к А* относятся сумма Xi + Хз и произведение XiX-г структурных чисел Xi и Xz, удовлетворяющих уравнению АХ == 0. Множество А* решений уравнения АХ = 0 можно в общем случае определить с помощью выражения, записанного в символах математической логики: (ЛХ=0)^ Л {[a(}x^^y[r(a[Jx)e{0,2, ...]}. (2.21) аел х^Х Свойство (2.21) следует непосредственно из определения про- изведения структурных чисел. 2.2. Делимость структурных чисел Если для двух структурных чисел А и В существует такое число X, что А == ХВ, (2.22) то А делится на В, или В — делитель числа Л, т. е. В \ А и А ^ 0. _ (2.23) Очевидно, каждое структурное число А =/= 1 и А ^- 0 имеет самое малое два делителя, а именно 1 и А; число 1, в свою оче- редь, имеет лишь один кратный делитель. Структурные числа А ^ ф, содержащие только один дели- тель А, называются простыми числами; любое другое структурное число называется сложным. Каждый делитель, представляющий собой однострочное структурное число, называется основным делителем. 42 ГЛАВА 2 Теорема 2.3. Структурное число В представляет собой дели- тель структурного числа А тогда и только тогда, когда оно удо- влетворяет следующим условиям: 1) АД-0; 2) все столбцы числа А являются подмножествами некоторых столбцов числа В. Доказательство. Если число В есть делитель числа Л, то существует такое X, что ВХ = А. Но это уравнедие имеет решение тогда и только тогда, когда все столбцы числа А представляют собой подмножества некоторых столбцов числа В, а. В — элемент, сопряженный с А. Следова- тельно, Д|Л<=>(Л5=0)А [Д, V (^=>М. (2.24) Ь^Вч^А ^- Следует заметить, что деление, определенное на множестве структурных чисел, обладает свойством А \В и В \С => А \С. (2.25) Деление также представляет собой слабо симметричное отно- шение, т. е. (А \ В и В | Л) => Л = В, .что вытекает из следую- щей теоремы. Теорема 2.4. Если структурное число В — делитель структур- ного числа А, а число А — делитель В, то А == В. Доказательство. Положим, что одновременно имеет место В \А и А \В. Из теоремы 2.3 следует, что тогда могут быть одновременно выпол- нены условия (Л \/(^=^);л(Л V (&й^)}, а^А Ь^В а^А Ь^В что может иметь место только при А -= В. Для структурных чисел имеет место правило сокращения, т. е. если С А = С В, то Л == В. Это положение можно обосновать. Теорема 2.5. Уравнение АВ -= АХ имеет общее решение на множестве структурных чисел Х =В + А*, где А* — произвольный сопряженный элемент А. Тогда (АВ == АХ) <^> (X = В + А*; Л* С А*). (2.26) Доказательство. Из уравнения АВ = АХ следует, что Л(.В+Х)==Ои5+Х— число, сопряженное с Л, а соответ- АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 43 ственно и Х = В + А*, где А* — произвольный элемент множе- ства решений уравнения АХ = 0. Подставляя число Х = В + А* в уравнение АВ = АХ, убеждаемся, что это число действительно удовлетворяет данному уравнению. Теорема 2.6. Каждое сложное структурное число имеет по крайней мере один делитель, представляющий собой простое число, не равное единице. Доказательство. В соответствии с определением сложное число А имеет делители, отличные от 1 и Л. Положим в таком случае, что В — один из этих делителей, т. е. А = Хо5, Х„ ^ 1, В =^ 1. (2.27) Если В — непростое число, то его можно представить как В = XiBi. При этом получим А == B[XoX^X^ . . . Х [. (2.28) Но для А =^- 0 должно выполняться очевидное неравенство I < тд, (2.29) где ГП.А — число элементов в столбце числа Л, содержащем наи- меньшее количество элементов. Множество натуральных чисел {1, 2, . . ., 1} имеет наибольший элемент ^макс; поэтому 5; макс есть простой делитель числа Л. Для Л = 0 неравенство (2.29) не должно выполняться, но, согласно изложенному, из произ- вольного делителя числа Л (сложного, ненулевого) можно извлечь простой делитель, что и доказывает теорему 2.6. Теорема 2.7. Каждое структурное число представляет собой простое число или произведение простых чисел. Правильность этого положения следует из теоремы 2.6. Дей- ствительно, если структурное число Л можно представить в виде (2.28) с простым делителем В;, то на простые делители можно раз- ложить каждый дополнительный делитель Хо, Xi, Xz, . . ., X;. Тогда структурное число можно всегда представить в виде про- изведения простых чисел Л = PiPs . . . РГ- (2.30) В случае, когда Л само будет простым числом (не равным единице), произведение сводится к одному сомножителю. Раз- ложение числа Л на простые числа запишем тогда в следующем виде: Pi ?2 РГ А (2.31) 44 ГЛАВА 2 Нетрудно заметить, что структурные числа имеют следующие свойства: 1. Любое структурное число, состоящее из разных (неповто- ряющихся) элементов и содержащее более одного столбца, есть простое число. 3. Каждое структурное число, состоящее из одной строки, простое. 3. Каждое структурное число, состоящее из одного столбца, сложное (п >• 1). 4. Сумма простых чисел может быть сложным числом, сумма сложных чисел может быть простым числом. Пример 2.5. Г" " "i1 , , , г" та " ^ J^^kp. ["I [pi PJ, "1 + h' -pJ'bi. ' a a.1' -P Pi. В данном примере, суммируя вначале два простых структур- ных числа, получаем сложное число; затем, суммируя сложное число, получаем простое число. Следствием второго свойства структурных чисел является то, что множество простых струк- турных чисел бесконечно, если бесконечно множество X, из которого взяты элементы структурных чисел. Оказывается, раз- ложение структурных чисел на простые имеет специфические особенности, отличные, например, от особенностей разложения в области натуральных чисел. Одна из этих особенностей рассма- тривается в следующей теореме. Теорема 2.8. Каждое сложное число имеет бесконечное множе- ство способов разложения на простые числа. Доказательство. Положим, что А = Pi Р^ . . . Рг- Легко заметить, что величина этого Произведения не изменится, если любое из чисел Р^ дополнить столбцами, содержащими некоторые элементы всех столбцов одного из оставшихся сомножителей. Так как число таких возможных дополнений бесконечно, то каждое сложное структурное число можно разложить на простые бесконечно большим числом способов. Пример 2.6. [1] [2] = [1] [2 1] = [1] P i] = [I] f2 l] = . . . . I "J L °J Рассмотрим свойства структурных чисел с одинаковым числом элементов в строках и одинаковым числом элементов в столбцах, которые представляют наибольший интерес для применения алгебры структурных чисел. АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 45 Определение 2.4. Разложение структурного числа с одинако вым числом элементов в строках на простые числа также с одина- ковым числом элементов в строках, содержащих только элементы числа Л, называется каноническим разложением. Очевидно, что каждое структурное сложное число с равным числом элементов в строках имеет конечное число канонических . разложений. Это имеет большое практическое значение, напри- мер, в случае применения алгебры структурных чисел к синтезу электрических цепей. Теорема 2.9. Если структурное число с одинаковым числом элементов в строках А =/= 0 (с m строками) имеет каноническое разложение m А - Ц А-, (2.32) то все остальные канонические разложения числа А на простые однострочные числа имеют вид m m А = П S е^-А, (2.33) ;=i i=i где числа е^- принимают только значения 0 или 1. Доказательство. Положим, существует разложение A=gP'„ отличное от (2.32). Тогда, йеремножая А и любое Р^, получим т АР;--Р;-ДР.=О. Далее, P'j = (PiP^ • • • Pm)*ii T- e- P'j — сопряженный элемент по т отношению к Д Pi. Однако можно заметить, что в классе одно- i=sl строчных структурных чисел Pi справедливо соотношение (PiP, ... Рт)^ = S е„Л-, 4ij =0,1. i=l (2.34) Тогда, действительно, А= П Se,,P,, ^={°i. )=1 i=l Непосредственно из теоремы 2.9 следует, что двустрочное сложное структурное число имеет лишь три возможных канони- ческих разложения на однострочные числа А = Л"2 = Л ("i + PV = PZ (PI + Ру. (2.35) 46 ГЛАВА 2 Несмотря на то что известен общий вид канонического раз- ложения, определение общего числа возможных канонических разложений то-строчного сложного структурного числа — доволь- но трудная комбинационная задача. Теорема 2.10. Число возможных канонических разложений отличного от нуля сложного структурного числа с т строками на однострочные сомножители удовлетворяет неравенству Д ^.^ , ,. , k(k-l) , k(k-i)(k-2) , k(k-l) (k-2) ... т ^m1. (2.38) Однако эта оценка дает худшие результаты по сравнению с неравенством (2.36). 3 Геометрическое изображение структурного числа До сих пор мы рассматривали структурные числа как эле- менты переменного кольца и его общие свойства, исходя из опре- деления действий сложения, умножения и т. д. Попробуем дать геометрическую интерпретацию структурного числа. Следует отме- тить, что геометрическая интерпретация встречается также и в дру- гих случаях, например в случае комплексных чисел, которым ставятся в соответствие некоторые точки плоскости Гаусса. Геометризация структурного числа имеет значение прежде всего для его применения при анализе и синтезе электрических цепей. Определение 2.5. Если столбцы структурного числа А взаимно однозначно соответствуют деревьям'графа Г так, что каждый столбец представляет собой множество значений описывающей функции соответствующего дерева, то граф Г называется геоме- трическим изображением числа А и записывается в виде Г = ob (А), "- (2.39) Следовательно, геометрическим изображением структурного чис- ла А служит любой детерминированный граф, удовлетворяющий условию (2.39), или класс графов подобных структур. Из приня- того определения следует, что геометрическое изображение струк- турного числа — не однозначное понятие, так как структурному числу может соответствовать многоэлементное семейство графов, составляющих класс с подобной структурой. Однако это в изве- стном смысле является достоинством метода, так как становится возможным, например в задачах синтеза цепей, нахождение не одного, а множества вариантов цепи, удовлетворяющей заданным условиям. Не каждое структурное число изображается связным графом — топологической цепью. Определение условий, при которых суще- ствует изображение структурного числа в виде связного графа, 48 ГЛ\ВА 2 имеет принципиальное значение для применения метода структур- ных чисел. Эти условия будут сформулированы в теореме 2.12. Теорема 2.11. Структурное число А с одинаковым числом эле- ментов в строках, геометрическим изображением которого служит связный граф с вершинами pi, р^, . . ., р„, равно произведению п — 1 простых однострочных сомножителей А =АР2. . . -Pn-i, (2.40) причем сомножители состоят из значений описывающей функции ребер, инцидентных произвольно выбранной вершине pi (pi ^= pj, если i ^ J) графа Г. Доказательство. Равенство (2.40), очевидно, справедливо в слу- чае графов с одной и двумя вершинами. Рассмотрим произвольный связный граф с га вершинами. Соединим в нем две произвольные вершины ребром о^. Положим, что выражение (2.40) справедливо для образованного таким образом графа Г*, т. е. что структурное число равно А* = (Pi + Р^) Рз . . . Pn-i = (Р\ + Р',) AV, где Pi = Р[ + Ш, Рз = Р'2 + [»J. 2 ^ ^ftl Найдем число А' = Р^Р^А** = (Р[ + Р',) А** [с^] + Р[Р',А** = А* [а^+А". (1) Структурное число А графа Г с несоединенными верши- нами и висячим ребром ос,, можно представить в виде А = Л* [сс^1 + А°, (2) поскольку множество деревьев графа Г* (с замкнутым ребром а^}, дополненное элементом к,, представляет собой множество всех деревьев графа Г с ребром а,у В выражении (2) символ А° обозна- чает структурное число, составленное из всех столбцов числа А, не содержащих о^. Просуммировав равенства (1) и (2), получим А + А' = А° + А". (3) Так как левая часть этого равенства не зависит от выбора реб- ра сс^, а правая часть не содержит сс^, значит, для каждого из следующих уравнений имеем A+A[=A°,+A"^ai, А+А,=А°,+А'^а„ АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 49 Отсюда левая часть равенства (3) не содержит обозначений ребра графа Г и равна нулю. Тогда А =Л' =Pi^2. . -Pn-i, что и требовалось доказать. Сформулируем теорему об условиях, при которых структурное число имеет связное изображение. Теорема 2.12. Необходимые и достаточные условия существо- вания геометрического изображения структурного числа в виде связного графа состоят в том, чтобы структурное число А имело разложение на простые однострочные сомножители А = Л?2 • • . Лп, (2.41) причем произвольный элемент а,л должен встречаться самое большее в двух простых числах Р„ Р]. Доказательство. Разложение (2.41) непосредственно следует из теоремы 2.11 и не требует специального обоснования. Условие того, что элемент a,k встречается максимум в двух числах Р;, Pj, тоже очевидно, так как в графе имеют место лишь ребра с двумя концами (одномерные симплексы). В задачах синтеза при определении алгоритма образования структурных чисел на цифровой машине удобно добавить к при- веденным условиям следующие дополнительные условия, под- тверждающие отличие структурного числа от нуля: 1) в произведении Л = Р\Ръ • • • Рт не может быть одинако- вых сомножителей, т. е. Pi ^P„ i, J = 1, 2, . . ., т (i^JY, (2.42) 2) любой сомножитель Р^ произведения (2.41) не может быть равен сумме произвольного числа остальных сомножителей, т. е. Pi^^Pk, h k=i, 2, ..., т (k^i). (2.43) Из теоремы 2.12 следует, что структурное число, у которого число элементов в строках различно, не имеет связного геоме- трического изображения. Условие имеет не только теоретическое значение. Оно однозначно условию физического соответствия матрицы полных проводимостей и пассивной электрической цепи. По сравнению с другими способами определения условий реализации матрицы полных проводимостей определение, осно- ванное на теории структурных чисел, особенно просто и ло- гично. 4—0298 50 ГЛАВА 2 4. Дополнительное структурное число и геометрическое обратное изображение Определение 2.6. Дополнительным структурным числом для данного структурного числа А называется структурное число А'1, столбцы которого представляют собой дополнения столбцов чис- ла А до множества элементов aih, из которых состоит структур- ное число А. Если обозначить множество элементов о,;;;, из которых состоит число А, через L, то столбцы Cf числа А'1 определим как разность (в смысле понятий алгебры множеств) C^L-C^ d=L-C„ ...,С^Ь-Сп, (2.44) где Ci, C^i • • ., С^ — столбцы числа А. Дополнительное структурное число можно в таком случае записать в виде Ad ={\ 1 (\ = L -а.) А (^ (= А)} или иначе a-ih (E L, a^^A}. Ad ={{^ih} — apk (2.44а) (2.446) Следует отметить справедливость такого свойства (А + В)'1 = Ad + В^ L = LA U LB, (2.45) которое означает, что дополнение — операция аддитивная. Допол- нительное структурное число можно также определить по отноше- нию к другому множеству L*, такому, что L cr L*, и тогда AL* ={L* -а^\а^А}. (2.44в) Способ получения дополнительного структурного числа иллю- стрирует следующий пример. Пример 2.7. Определить структурное число 4й по отношению к структурному числу -2 6 9- А = 328 . .5 8 3. Множество элементов числа L таково: L ={2, 3, 5, 6, 8, 9}. • Дополнительное структурное число равно -6 3 2 А'1 = 855 . ,996 АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 51 Оказывается, что для структурного числа удобно иметь дуаль- ное геометрическое изображение, поэтому введем понятие обрат- ного изображения геометрического структурного числа. Определение 2.7. Граф Г называется обратным изображением структурного числа А, если столбцы числа А взаимно однозначно соответствуют дополнениям деревьев графа Г так, что столбец числа А .представляет собой множество значений описывающей функции соответствующего дополнения дерева. Тогда напишем Г = cob (Л). (2.46) Нетрудно заметить, что обратное изображение дополнитель- ного числа А'1 одновременно служит изображением числа А и наоборот. Обратное изображение — это граф дуальной структуры в пони- мании Кауэра по отношению к геометрическому изображению данного структурного числа. Связное обратное изображение суще- ствует для любого структурного числа, имеющего связное изо- бражение. Таким образом, структурному числу ставится в соответствие пара графов дуальной структуры. Один из них служит геоме- трическим изображением, другой — обратным изображением. Примеры изображений простейших структурных чисел приведены в конце книги. Для обратного изображения имеет место следующая теорема. Теорема 2.13. Структурное число А с одинаковым числом эле- ментов в строках, геометрическое обратное изображение которого суть связный граф Г, характеризующийся цикломатическим чис- лом ?га, равняется произведению т простых однострочных сомно- жителей А = Р,Р, . . . Р,„, соответствующих линейно независимым контурам графа G. Доказательство. Докажем эту теорему методом индукции. Фиг. 2.1. Граф с двумя циклами. )Теорема справедлива для графа с одним и двумя контурами. Действительно, такой граф всегда может быть упрощен и при- веден к виду, показанному на фиг. 2.1, д или 2.1, б, где ребра 1, 2,3— суммы соответствующих ребер графа с двумя контурами. 4* 52 ГЛАВА 2 Для графа (фиг. 2.1, д) имеем л Г1 1 21 л = [2 3 3J ' т. е. действительно А = [1 2][1 З]. Для случая, изображенного на фиг. 2.1, б, теорема также справедлива, так как А == П = [1] [2]. L"J Можно доказать, что теорема справедлива и тогда,•когда ребра 1, 2, 3 заменены последовательным соединением произволь- ного числа ребер. Положим, что теорема справедлива для графа с цикломатиче- ским числом т — 1. Тогда можно доказать, что она справедлива и для графа с числом контуров т. Таким образом, теорема справедлива для графов с произволь- ным числом независимых контуров я произвольной структурой. Теоремы 2.11 и 2.13 особенно важны для применения метода структурных чисел к анализу электрических цепей. Они служат основой расчета структурных чисел, соответствующих заданным графам, представляющим структуру рассматриваемой цепи. 5. Алгебраическая производная и обратная производная структурного числа На множестве структурных чисел можно определить различ- ные операции; одна из них — операция алгебраической произ- водной. Определение 2.8. Алгебраической производной структурного числа называется число дА/да, определенное как дА _ . столбцы, не содержащие "да^ элемент а,- исключены. (2.47) Если структурное число представить как совокупность множеств, то производная дА -^---={6ft|6ft=aft—M, » 6 aft, a.k^A}. (2.47a) Легко доказать правильность следующих зависимостей, аналогич- ных «обычной» производной: д , . . . дA^ дА, -^(А,+А,)=^+^, д , . . > дA^ . , дА, , (2Л^) ^(ЛА)=^^+^А,. АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 53 Алгебраическую производную обозначим как Лд, т. е. ЭА _ A I") /Q\ да, —/1"' ^.49) Следует заметить, что для одноэлементного структурного числа ^М=1. (2.50) Пример 2.8. Нахождение алгебраической производной струк- турного числа: А [23 ^ з1 дл Г2 3 4! дл Г13] ^27 i[ ^b^J- -W[2i\- По аналогии с математическим анализом нахождение произ- водной будем называть дифференцированием. Дифференцирование структурного числа имеет весьма про- стую геометрическую интерпретацию, сформулированную ниже. Свойство 1. Геометрическое изображение структурного чис- ла дА/да представляет собой геометрическое изображение струк- турного числа А с замкнутым ребром ее. Свойство 1 обосновано теоремами 2.11 и 2.13. Действительно, если положить, что опорным узлом служит любой узел цепи, неинцидентный с ребром ее, то элемент а будет встречаться в двух простых сомножителях Pi и -Pg, т. е. А = Pi (а) Р^ (ст) Рз . • . Л»-1, где п — число вершин графа. Отсюда ^^^...р„_,4^АРз...Лг-1. да да ' да, 1 •' • Так как для однострочных простых чисел Pi и Pg справедливо, что OPi/Oa = дР^да = 1, то . ^-(P,+P,)Ps...Pn-i. (2.51) Это означает замыкание ребра ос в геометрическом изображении или отключение (или однополюсное отключение) ребра к в обрат- ном геометрическом изображении (тогда п —1 = т — цикло- матическое число графа). Поскольку величина структурного числа не зависит от выбора опорного узла, полученный результат носит общий характер. Кроме алгебраической производной, сформулируем для струк- турных чисел еще одно понятие (в известном смысле дуальное 54 ГЛАВА. 2 по отношению к производной) — понятие обратной алгебраиче- ской производной. Алгебраической обратной производной структурного числа называется структурное число бЛ/б«, равное 6А _ . столбцы, содержащие да ~ элемент а, опущены. (2.52) 6Л Воспользовавшись способом записи структурного числа в виде семейства множеств, можно записать обратную производную как (2.52а) Для обратной алгебраической производной имеют место соот- ношения 6 / , , . > SA (Ai+As)-= 6к А 6« 6А, ^^^-•бсГ^^^а 6ff. ' 6А — Ai+AiAz, (2.53) справедливые для произвольных чисел Ai и А^. Кроме того, 6 I А А 1 &Ai длу- ~^{AiA2^=~^^' , Для одноэлементного структурного числа имеем -6[a]=0. 6к l J (2.53а) ^[«1=0. (2.54) Соотношение алгебраических производной и обратной производ- ной можно записать следующим образом: -^(Л[«])--^. (2.536) Алгебраическую обратную будем обозначать как ^^•- (2 Пример 2.9. Расчет алгебраической обратной производной: -1 2 1 5- 2 5- [-1 5-1 - А-= 3 4 2 4 6Л 4 4 6А 3 4 ' 61 - ' 62 • -5 7 3 8. -7 8.. -5 8. Алгебраическая обратная производная имеет простую геометриче- скую интерпретацию. АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 55 Свойство 2. Геометрическое изображение структурного числа 6Л/6« представляет собой геометрическое изображение числа Л, в котором ребро отключено в одной вершине и замкнуто в петлю. Обратное геометрическое изображение структурного числа бЛ/ба, представляет собой обратное изображение геометрического числа Л с замкнутым ребром а. Правильность, этого свойства следует из определений изображения, обратного изображения структур- ного числа и обратной производной. Вследствие простых соотношений между алгебраическими дей- ствиями, выраженными через операции производной и обратной производной, и действиями на графе, который является геоме- трической интерпретацией структурного числа, эти операции особенно важны в применениях алгебры структурных чисел, например, к анализу электрических цепей. Отметим, что для структурного числа Л всегда имеет место соотношение . 64 , - , дА А =-- -о— + Г" -г- 6 ex ' l - да, 64 дА Л-^-+[«]^-, (2.56) где к — элемент числа Л. 6. Детерминантная функция структурного числа Аналогично с матричным исчислением на множестве струк- турных чисел можно определить различные функции, например детерминантную функцию. Определение 2.9. Детерминантной функцией структурного числа Л называется функция "ац «ц • . . «Ira 71 mh. det Л --= det «2t «22 •• • • «2Д - S П ^ik' (2 57) z z .CXml «пг2 • • • «ттг^- fe=l г=1 где Z — заданное множество комплексных чисел ^ т. e. Za ^ С Z. Определение этой функции весьма просто. Нужно пере- множить комплексные числа, поставленные в соответствие индек- сам столбцов, и просуммировать полученные выражения, соот- ветствующие столбцам. Эта функция может быть кратко названа определителем или детерминантом структурного числа. По аналогии с теорией матриц для ее обозначения используем также символ det Л z а„ Ki2 ... din \А «21 «22 «2ll (2.58) или «>щ1 «тз2 • • • «mnii 56 ГЛАВА 2 Пример 2.10. Нахождение определителя. П 2 1 2-j Вычислить определитель числа А == 3443 .7 5 8 4J по отношению к комплексным числам Zi, Zg, 23, 24, Zo, Zg, Zy, Zg (E Z. det Л = z^Zy + ZgZ4Z5 + z^Zg + ZaZ3Z4. z Очевидно, что раскрытие определителя матрицы немного сложнее, чем раскрытие определителя структурного числа. Определитель структурного числа имеет следующие свойства: {Ai = Лз) => (det Az ---- det Ai), z z 1 , дА д ,-, , ., det —=-.— [det А}. Z да, дга- ц 7. Функция совпадения структурного числа Кроме ранее введенных операций сложения и умножения структурных чисел, определим еще одну операцию — конъюнкцию. Определение 2.10. Конъюнкцией А [} В структурных чисел А и В называется структурное число, содержащее общие столбцы чисел А и В и не содержащее других столбцов. Пример 2.11. А= ~1 3 5- 246 524' 3 1 1 П" Определим на множестве структурных чисел еще одну функ- цию, важную для применения алгебры структурных чисел,— функцию совпадения и обозначим яп|) Sim (А, 5) z Функция совпадения равна Sim/ л р\^. Sim {A, Bf^ = det (A [\ В) при (р-. z z —det (А О В) при •ф. (2.59) Очевидно, имеется в виду случай Л [} В =^=0. Формула (2.59) дает общее определение функции совпадения, однако в прикладном значении этой функции наиболее важна частная форма записи функции совпадения: эта функция относит- АЛГББРА СТРУКТУРНЫХ ЧИСЕЛ 57 ся к структурному числу Л, геометрическое обратное изображе- ние которого содержит два ориентированных ребра ст и р. Определение 2.11. Функцией совпадения Sim z I дА дА \ \~д^' №1 ' (2.60) структурного числа Л, обратное геометрическое изображение которого имеет два ориентированных ребра а и р, называется функция, обладающая следующими свойствами: 1) функция (2.60) — линейная комбинация выражений, имею- щихся в определителях det (дА/да) и det (дА/д^>); z z 2) если исключить из обратного изображения ребра, опре- деленные данным выражением, получим цикл, в котором ребра ее Фиг. 2.2. Пояснение оп- ределения функции совпа- дения. и Р ориентированы согласно или встречно, то слагаемое имеет соответственно коэффициент +1 или —1 (фиг. 2.2). Функцию совпадения (2.60) можно в таком случае записать о. / дА дА \ _, , / дА - дА \ „ „ slm [~да1 м)^ е [~да n ^) ' когда реора " и Р ориентиро- z v 2, vi ваны согласно, , . / дА . дА \ , „ —det 1-д— П —„1 , когда ребра и и р ориентиро- 2 ваны встречно. (2.61) «=/ Фиг. 2.3. 58 ГЛАВА 2 Пример 2.12. Определить функции совпадения структурного числа А, обратное изображение которого есть граф ц. I дА дА\ slm (^' ж)' изображенный на фиг. 2.3 (а, = 1, Р = 7). Решение. Структурное число определим по выраже- нию (2.13) как произведение простых чисел, соответствующих всем независимым контурам обратного изображения. Имеем 257 X 238 ''4786 136 -222222222222225555555555555555 333333888888882222222222233333 447788444777664447778886644778 .161616136136131361361361316161 5555555555777777777777777777- 3388888888222222223333388888 8644477766444888664488644466 6113613613136136131616113613. Далее определим алгебраические производные 2 2222555 дА ~W 3 3388222 4 7846478 255 5 5 5 5 ядч Л 'W 499U 1J <&.< 9^J 3 ч0 06 1 1 3 6 1 6 1 7777777 2233388 4648646 I 5 5 5 555 ^ 2 3 3 3 388 8 6 4 7 8 647 6 2223333388888 4664488644466 6131616113613 Столбцы, общие для дА/д1 и дА/д7, взяты в рамки. При рассмотрении графа на фиг. 2.3 легко заметить, что при исключении ребер 526,536,583,556 граф сводится к графу с одним контуром, в котором ребра а = 1 и (3 = 7 ориентированы согласно. С другой стороны, при исключении из графа ребер 234 в полученном контуре ребра 1 и 7 ориентированы встречно. АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 59 Поэтому выражения z^z^Zg, Z,,Z^ZQ, z-yZgZ;}, z^z^, имеют знак плюс, z^ZyZit — знак минус. • Окончательно получим дА дА Sim z - I — ^Z^Zg — Z5Z3Zg 4" ZyZ^Zy "Г ZsZ^Zy —— Z2ZЗZ^• д1 ' Можно также обосновать свойство, согласно которому при исключении из обратного изображения структурного числа ребер, определенных столбцами дА/да. f| ЗЛ/йр, граф всегда сводится к такому графу, у которого цикломатическое число т =- 1. Опре- деление ориентации ребер а и (3 по отношению друг к другу не встречает трудностей. Не каждый граф отображает электрическую цепь, в которой не могут присутствовать лишние элементы (обесточенные или на которых нет напряжения). Для определения класса графов, с которыми будем иметь дело при анализе электрических цепей, введем общее определение соответственного или сильно связ- ного графа. Определение 2.12. Граф называется соответственным, если каждые две его вершины принадлежат хотя бы одному элемен- тарному контуру. Для соответственного графа справедливо следующее свойство. Свойство 3. Граф (мультиграф) будет соответственным тогда и только тогда, когда он служит обратным изображением струк- турного числа А, удовлетворяющего условию V Л 'д- П И-^О]- (2.62) ЩА КА -оа "Р . J Справедливость этого свойства следует из определения функции совпадения, согласно которому столбцы ~дА дА "да • '""ар" соответствуют ребрам, исключение которых приводит к упроще- нию графа обратного изображения к одному циклу с ребрами ст и (3. На фиг. 2.4 показано несколько графов, из которых только' один граф соответственный. Если применить условие (2.62), например к графу, показанному на фиг. 2.4. б, получим П 1 2 2-| А-[12][34]^434.|' ^-[34], ^--[34], 4- [12], дА "аГ [1 2]. Тогда 60 ГЛАВА 2 а также дА_ ЭА_ да " йЗ т. е. условие (2.62) не выполняется для графа (фиг. 2.4, б) и этот граф не соответственный. Очевидно, что применение условия (2.62) для определения характера графа излишне, если известна его ^ <х=/ )2 ^2 <7 ., /I(З^Л < )4 .4 б Ф и г. 2.4. Примеры графов: а) соответственный; б, в, г) несоответственные. структура. Из рассмотрения контуров графа можно непосред- ственно сделать вывод о том, выполняется ли условие (2.62). Однако это условие весьма ценно, если известно только структур- ное число, не разложенное на первичные сомножители, а также для использования при синтезе электрических цепей с помощью структурных чисел на ЭЦВМ. 8. Понятие ряда и последовательности структурных чисел Если натуральным числам поставить в соответствие структур- ные числа, то можно сказать, что таким образом определена последовательность • структурных чисел, записываемая в виде <Л„}= Ai, Аг, Ay, . . ., Лд, .... Понятия сходимости и границы последовательности структур- ных чисел основываются на понятии метрики. Положим, дано структурное число А ={ffft I v-ij 6 a^ i, j, k == 1, 2, 3, . . .}, где мощность множеств а, и А конечная, а гщ — элементы норми- рованного пространства. АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 61 Введем сначала понятие нормы множества а, которую обозна- чим как |[ а ||. Примем определение а = {ai, ад, . . ., ст„} => || а \\ --= ^|| ^ Ц^Ц Кг] где ||стг||—норма элемента ст,. Норму структурного числа определим как таГ II «Н^ где К проходят все столбцы, имеющиеся в числе А, Метрику на множестве структурных чисел определим как р (Л, В) = ]| А ^В ||, где — означает симметричную разность множеств. Из этого опре- деления следует, что метрика р (А, В) удовлетворяет следующим основным условиям: р (А, В) = 0 <=> А ==5, р(А,В) =р(5,Л), р(А,В) +p(5,C)>p(A,Q. Для двух произвольных структурных чисел справедливо также неравенство 11 АВ |[ < |[ А 11115Ц, которое следует из неравенства Буняковского — Шварца. Если для последовательности структурных чисел Лд суще- ствует структурное число А, удовлетворяющее равенству lim р (4„, А) = О, П->со то структурное^число А называется границей последовательности структурных чисел Лд и записывается в виде А = lim Лд." П-»-оо Последовательность Лд называется сходящейся, если имеет границу, и, наоборот, расходящейся, если таковая отсутствует. Кроме сходимости по отношению к метрике, введем и другие понятия сходимости последовательности структурных чисел, кото- рые обозначаются Lim ob Ar Lim cob A,. n—^oo 62 ГЛАВА 2 и определяются с помощью изображения и обратного изображения структурного числа: (ЫшоЬЛп=Л)<=> [Lim ob (An) = о] л ]o==ob(4)], П—>-00 П—>00 (Lim cob Лд = Л) [Lim cob (Ап)= о] Л [о=соЬ(4)]. П->оо П->оо Примером сходимости последовательности 4д 110 отношению к обратному изображению может служить цепь, метрический /25 v n-f ') п п п п п i 2 5 в И 14 3 6 9 12. /5 4 7 Ю 13 16 Ф и г. 2.5. Лестничный граф с равномерно распределенными вер- Граф которой имеет ступенчатую структуру с равномерно распре- деленными на отрезке [О, 1] вершинами (фиг. 2.5). Если увеличить число делений отрезка [О, 1], то при п —- оо граф преобразуется в структуру с густым (однако четным) множе- ством ребер. Нумеруя грани графа, например, как показано на фиг. 2.5, можно определить следующую последовательность струк- турных чисел: Ai = [1 2 3 4], Аз = [1 2 3 4][3 5 6 71, As - [1 2 3 4][3 5 6 7][6 8 9 101, .................. J. . обратным изображением которой и служит наш граф. Эта последовательность сходится к обратному изображению структурного числа А == cob"1 (Т, (т = Lim Sn- П~>оо где Sn — последовательность цепей (метрических графов) вида изображенных на фиг. 2.5. Рядом структурных чисел называется выражение 00 А^Аг+А,^- ...+Л„- ...= ^ An. п=1 АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ 63 Структурные числа Ai, A^, Ay, ... называются составляющими ряда, числа же Si =Ai, S^=Ai+A^ 83 ==Ai +Л2 +А^ •S' = А, Аз + . . . А, есть частные суммы ряда. Бесконечный ряд структурных чисел называется сходящимся, если последовательность частичных сумм сходится. Предел последовательности частичных сумм называется суммой ряда структурных чисел. Если limSn==S, П->00 ТО п=1 Глава 3 Структурные числа и графы высшей категории 1. Введение Физические системы состоят из элементов, взаимодействую- щих друг с другом различным образом. Например, электрические цепи могут состоять из многополюсных элементов (многополюс- ников); их также можно рассматривать как системы, состоящие из блоков или подцепей. Топологические модели таких систем представим в виде графов второй категории, построенных из дву- мерных континуумов (блоков) с выделенными точками, называе- мыми полюсами. Блоки соответствуют ребрам линейных графов первой категории. Структурные числа блок-графов назовем струк- турными числами высших категорий — второй, третьей и т. д. Эти числа, подобно матрицам, состоящим из подматриц, представ- ляют собой семейства структурных чисел низшей категории. Основываясь на определении операций над числами первой кате- гории, определим в соответствии с теорией множеств и элементами математической логики 1) операции над структурными числами высшей категории. 2. Определение структурного числа второй категории В общем определении структурных чисел не уточнялись харак- терные черты множеств элементов, из которых состоит это число, поэтому можно рассмотреть случаи, когда эти элементы также являются структурными числами. В связи с этим введем понятие структурного числа ^А второй категории следующим образом. Определение 3.1. Структурное число второй категории ^А есть семейство множеств ^a, где А Л AU i ] *А =={4,},^ 2, • • ., п> а] ={Aij}i=l, &, • • ч mi структурное число первой категории. (3.1) 1) Slupecki J.,Borkowski L., Elementy logiki inatematycznej i teorii mnogosci, PWN, 1963. СТРУКТУРНЫЕ ЧИСЛА ВЫСШЕЙ КАТЕГОРИИ Структурное число второй категории можно также записать в виде ~Ац . . . Ai„ ^21 ... 42n ^А = (3.2) или ^^[A^^i.a,...,^, 3=1, 2, .. ,,п (3.3) где элементы Ац — структурные числа первой категории. Введем понятие замещающего числа для структурного числа второй категории. Определение 3.2. Замещающим числом для структурного числа второй категории ^А называется структурное число первой кате- гории А, полученное применением операций алгебры структур- ных чисел над элементами Ац числа ^А: А= S П^' '^I^]^!^,...,,». ,=1 г-1 г-1,2, ...,n (3.4) Обозначим соотношение соответствия замещающего числа А числу ^А через А = ^А или М ^ А. (3.5) Пояйним способ нахождения замещающего числа следующим примером? ~ Г1Л гт 1.2 3J 2 L3J [1 2 4] Г151 1.2 6J if11!1.2 3J Г1I-5J ж •I 1 2 3 = 4 4 =Л 5 5 6 6 ззр24]^ 2 Lo. '1 5- 2 6 LгA=A. 66 ГЛАВА 3 Определим для структурных чисел второй категории понятие равенства, а также операции сложения и умножения: (2,4 = 2Д) <^ (А =В), (3.6) ^А +2B = А +В, (3.7) (3.8) представляет собой гомео- М-2^ = АВ, где А ^ М, Д ^ ^ Таким образом, соотношение = морфизм. Для структурных чисел второй категории справедливы сле- дующие соотношения: {^А с 2^) л (^ с М)} =^ (М = "б), (3.9) {^С = (2Д 4 2^)} =^ (^ == М + "В), . (3.10) ['с ^fc | ^с = ч u ^л (^ е2^) А (^ е 'Д) л д(2д л 2^ = ^) ^ (г (2д u ^ = 2& - 1)}] ^ (^ - ^ ^Д), (3.11) где ^ означает симметричную разность, г — функция повторе- ний, а А" — натуральное число. Легко заметить, что равенство структурных чисел второй категории рефлексивно, симметрично и транзитивно, операции сложения и умножения коммутативны и ассоциативны, а умноже- ние дистрибутивно по отношению к сложению. Заметим, что модуль сложения Ч ] == 0 структурных чисел второй категории есть всякое структурное число второй катего- рии, замещающее число которого служит модулем сложения [ ] структурных чисел первой категории; а модуль умножения 2[^>] == 1 структурных чисел второй категории представляет собой всякое структурное число второй категории, замещающее число которого служит модулем умножения [] структурных чисел первой категории. При этом справедливы следующие соотношения: 1. 2. [АА ... А] == J = А при нечетном п, 1 2 ... га 1=0 при четном п; А~\ Г==о при A^U, А J =1 при A^Vl, п четное, : | е 'A i = Л при A(:Vl, п нечетное, (3.12) (3.13) где U — множество структурных чисел вида А =={[^-], а,, да, . . .} СТРУКТУРНЫЕ ЧИСЛА ВЫСШЕЙ КАТЕГОРИИ 67 3. ([Ai ... А, ... AJ =0)<^ <=> {(A] =.[Ai . . . Aj^Aj+i . . . AJ) v V (4i = A2 = . . . = A, = . . . = A„ = 0)}, (3.14) (3.15) (3.16) (3.17) j = 1, 2, . . ., п. , /PI" = 0 /=> (Ai ^OvAz^ 0). (LA. 5. Равенство- = о w L^2. не имеет единственного решения для Ai и Az. 6- (ЙНЯ)-'^- .W ^ ГА.- \Щ 1А,_ Структурное число второй категории 2Лcг, элементы которого — дополнительные числа Ai,, назовем дополнительным числом вто- рой категории. Для дополнительных чисел второй категории при- меняем те же самые операции, что и для структурных чисел второй категории, поэтому приведенные выше определения и соот- ношения справедливы также и для дополнительных чисел второй категории ^^ Если в числе "'Л все элементы Л„ заменить на их дополнитель- ные числа Ац, то получим дополнительное число второй катего- рии (М)^, замещающее число которого А'1* в общем случае не равно дополнению А'1 замещающего структурного^числа А для числа ^А, т. ь. А'1* ^ А\ Л"* 1 (2Л)J*, А ^ ^А, а следовательно, ^ ^ (М)^. 2.1. Алгебраическая производная и обратная производная структурного числа второй категории Алгебраическую производную и обратную производную опре- делим на основе понятий производной и обратной производной замещающего структурного числа. Определение 3.3. Алгебраической (обратной) производной д ^А}1да-[^ ^А)!^} структурного числа второй категории М по элементу а, называется всякое структурное число второй кате- гории, замещающее число которого дА /да • (6А /бк) есть произ- 5* 68 ГЛАВА 3 водная (обратная производная) замещающего числа А для числа ^А по элементу к. Это определение соответственно можно пред- ставить в виде соотношений ^.Л^. Af^'l^. 2/1,4 /318) да -да' So, - fia ' А - л- ^•10-' На основании правил для производной и обратной производ- ной суммы и произведения структурных чисел первой категории можно написать следующие соотношения для структурных чисел второй категории: д г л л i Г дА\ дА, 1 ,n in» ^[^4-^-^-J- (3-19) Г ал1 л 1 a pit ^ л1 „ ^kr л^' ( 0) L '?» J -^-М/И-Г641-6'12'! (321} 6й 1Л1Л2] - L 6a "SaTi' ^•"^ r^ii ^Г^Г ^ /322) 6« [_AJ- &А^ • (°-22) L sec J . Следовательно, обратная производная б (^/бст — операция аддитивная и мультипликативная. На основе этих соотношений можно определить алгебраиче- ские производную и обратную производную по элементу к любого структурного числа второй категории. Пример 3.1. rWAi . дАу . -1 ^ г^ м Г^г ^ -^ ^ Л да U A.] A, ^ A, ^ ' .. " йк 4 (?« J Если, например, структурные числа Ai и Ag не содержат элемента я, то ^ p1 ^1 = гл1 л2 a« \ А А \ ^з aл4 L^3 ^4J —— —— L 1,. m > I): (".^"^^(A^B), , е е е '^-(-'"^Л+Д, Л="Л, .^'"б. (3.36) ^ ^."^^лд. Подобно структурным числам второй категории, равенство чисел /с-й категории рефлексивно, симметрично и транзитивно, операции сложения и умножения коммутативны и ассоциативны, а умножение дистшбутивно относительно сложения. Поэтому можно написать следующие соотношения: Г^Л Г^Л^ЛП Г Г^ /1^/1 Л ^ Л Л \^- Л ^- Л ^- Л Л [ Ai [ Лз АЗЛ = II ^1 А^ Лз] = ( Ai Лз Пз]. [fa/| —1 ГГ^ЛП"! r'^A"! 1 1 ГГ '11 Г 't rMz-i = L'^J = % . г ч i r44i fe/l ft/I ''J r^/l'^ 1 — ''/I''/1 L ^зЛ -л '- ^з -1 i- ^з-1 LI ^2 ^aJJ L ^2 ^isJ Модуль сложения ''[ ] = 0 структурных чисел /с-й категории есть всякое структурное число k-& категории, замещающее число которого служит модулем сложения [ ] структурных чисел первой категории. Модуль умножения h[ф] ==1 структурных чисел k-й категории есть всякое структурное число /г-й категории, замещающее число которого служит модулем умножения [<^] структурных чисел первой категории. Из этого вытекают следующие соотношения и соответствия: . е k . , . ,, [ -^ А при нечетном ге, 1. [hAhA ...ltA}={ . (3.37) i2 n ( ~-=0 при четном re. 72 • ГЛАВА 3 Г ( ^А~\ g ^ Г 0 при ^Я, 2. S,< . == ^ 1 "Р11 ^(ESt, п четное, (3.38) а | • |''А при ^'A^'S, n нечетное, - I л J где ^Я — множество структурных чисел k-й категории ^^{^{ф], ^, ka^ .... fta„}. 3. ([Ч ... hAj ... hAn}=0)^> ^ {("А/^^А, ... ^.^ .. . ^п]) V V('{Лl=%=...=^4,==...=fcЛ„-0)}, /=1,2, ...,п. (3.39) 4. ([^"LoL^A^OV^-O). (3.40) \L ^2 J / а Г "Ai •} 5. Равенство д. =° (зл1) L ^2 J не имеет единственного решения. 6. (Т Л11 - Г Л' 1) /^ (^2 = '^з). (3.42) \L ^ J L ^з J/ Если элементы структурного числа А-й категории ^А'1 являют- ся дополнительными числами (& — 1)-й категории >i~lAC[ "Л^а^.з,...,,,, ^={'-^=1,2,...,^, (3.43) то число ''А'1 называется дополнительным структурным числом А-й категории или, короче, дополнительным числом /с-й кате- гории. Для дополнительных чисел /с-й категории справедливы те же операции, что и для структурных чисел k-w. категории. 3.1. Алгебраическая производная и обратная производная структурного числа k-й категории Подобно структурным числам второй категории, определим алгебраическую производную и обратную производную струк- турного числа k-Ts. категории с помощью понятий производной и обратной производной замещающего числа. Определение 3.6. Алгебраической производной (обратной про- изводной) [д (kA)/дoi] [6 (kA)/f:la,] структурного числа А--Й катего- рии kA по элементу ст называется всякое структурное число k-та. категории, замещающее число которого (дА/да) (бЛ/ба) есть алгебраическая производная (обратная производная) замещаю- СТРУКТУРНЫЕ ЧИСЛА ВЫСШЕЙ КАТЕГОРИИ 73 щего числа А для структурного числа hA по элементу ее. Это опре- деление можно представить в виде следующих соотношений: д ^А) ^ дА 6 ("А) ^ 6Л ^A'-A П 44\ ~доГ~~д^' ~6^~~6сГ' A-л• ^•^i На основании правил для производной и обратной производ- ной суммы и произведения структурных чисел первой категории можно записать следующие соотношения для структурных чисел А-й категории: ^-^-^=[^^], (3.45) Г6 С"1-4!) fe-in п д Г h-lAi -1 да л1 \ ,„ ,д, ^Ь-^J- . „-х, д^А,) • (3-46) л2 —te—J 6 r^A^Al-r-6^1^-6-^^1^! Ц 47^ -^1 Ai A2l-[ ^ ^ J- (d.4Q г 6(fe-iAi) -1 6 Г ''"^l IS" /Q /QX ^["-Ц^" б('1-^.) • ('j•40) бк J Из правил (3.23) для алгебраической производной структур- ных чисел по сумме и произведению одноэлементных структурных чисел имеем д(^) ^га^Л) д^А)^ д^А^+^Аг) L д (^i) д (^Ла) J' ' / __^-=__^^__, (3.50) д {^А^Аг) д (^Ai} д (^Аз) д ^А) с дА / л(1р>\<1 ЛekA R e''R 1'Ч^'П у^-=-^-=(Л5) , А^ А, В= В. (3.51) Эти зависимости представляют собой обобщения формул (3.24) и (3.25). Обобщения формул (3.19) и (3.20) в виде д [^А^А,] ^ Г д {^At} д (fei^) 1 /352) д (^А) L д (^А) д (^А) J ' \ ' ' д^ ^Л, д Г hlAt 1 3(h2л) ^ ^^ 3-(^L^.J ,. . (ft^) ^•^ -^-lo ————I'———— " д(^А) также справедливы. 326 ПРИЛОЖЕНИЕ 3 Проверим выполнение неравенства (П311): л+6=6,&+1=6. Неравенство (П3.11) соблюдается, следовательно, применима процедура а). Число вершин графа и = л + 1 = 4, а структурное число графа А равно А = [xyy'][xz][yzz'i. Определяем производную •=[yy'z] (первая вершина). . д[В 1s 1 2 миц1 4:.] ^s Суммируем все [А^мин!, получаем [хуу'] + [a"z] + [г/zz'] == [y'z'] (вторая вершина). Примем структурное число [К^ мин! = [a"z] в качестве струк- турного числа третьей вершины. Структурное число четвертой Ф и г. П3.4. Фиг. П3.5. вершины — это сумма структурных чисел предыдущих трех вершин: [yy'z} + [y'z] + [xz] = [xyz'\ (четвертая вершина). Граф переключающей цепи, реализующий заданную булеву функ- цию, изображен на фиг. П3.4. Изменим стандартизацию, приведенную в примере 4, на сле- дующую: '. {^мин}={У', У}, {^Тмин}={у,2}, {Ki^}={x, z, х'}, {Dt^}={x, z, z', x'}, {^1мип}={У, Z'}, {^мин}={у, Z'}. В результате получим структурные числа вершин графа [xz'\, [x'y], [xyz} и их сумму [a-zz',1, что соответствует последовательно-параллельной цепи фиг. П3.5. Приведенный метод синтеза переключающих цепей позволяет получить минимальные последовательно-параллельные и мосто- вые цепи. Метод применим и для цепей со многими выходами. Примеры геометрических изображений и обратных изображений структурных чисел К1 Структурное уисм\ Геометрическое изображение \ ^^^^g^g^e^""^ ~ Литература 1.Bellert S., Topological analysis and synthesis of linear systems J. Franklin Inst., № 6 (1962). , 2. Bellert S., Topological considerations and synthesis of linear networks by means of the method of structural numbers, Arch. Elektrot., .№ 3 (1963). 3. Bellert S., Computer four-pole synthesis based on the method of structural numbers, Arch. Elektrot., № 3 (1964). 4. В е 1 1 e r t S., La formalisation de la notion du systeme cybernctique. Actes des Colloques Philosophiqucs Internationaux de Royaumont, Paris, 1964. 5. Bellert S., Topologiczna analiza i synteza uktadow liniowych, Zesz. Nauk. Pol. Warsz. Elektryka, № 37 (1964). 6. В e r g е С., Theorie des graphes et ses applications, Paris, 1958; русский перевод: Б ерж К., Теория графов и ее применение, ИЛ, 1962. 7. В е r s A., The degrees of freedom in RLC networks, Trans. IRE, CT-6, № 1 (1959). 8. В r у a n t Р. R., Order of complexity of electrical networks, Inst. Electr. Engrs (London) Monograph № 335E, J-une 1959. 9. С а и е r W., Theorie der linearen Wechselstromschaltungen, Berlin 1954. и , , 10. С о a t e s С. L., General topological formulae for linear network functions, Trans. IRE, CT-5 (March 1958). 11. Coates C.L., Flow graph solutions of linear algebraic equations, Trans. IRE, CT-6 (June 1959). 12. Coates С. L., General topological formulas for linear network func- tions, General Electric Res. Lab. Rep. № 57-RL-1746, Schenectady, N.Y. 13. F о s t e r R. M., Geometric circuits of electrical networks. Bell System Monograph, № B-653, Trans. AIEE, 51 (Apr. 1932). 14. Foster R. M., The number of series parallel networks, Proc. Int. Congr. Math. I, 1952. 15. F о s t e r R. M., Topologic and algebraic considerations in network synthesis, Proc. Polytechn. Inst. Brooklyn Symposium on Modern Network Synthesis I, Apr. 1952. 16. Foster R. M., Passive network synthesis, Proc. Polytechn. Inst. Brook- lyn Symposium on Modern Network Synthesis 5, 1955. 17. F о s t о r R. M., An extension of a network theorem, Trans. IRE, CT-8 (March 1961). 18. F r a n k 1 i n P., The electric currents in a network, J. Mathematics and Physics, 4 (Apr. 1925). 19. G u i 1 1 e m i n E. A., Introductory circuit theory, New York, 1953. 20. К i r с h h о f f G., ГЬег die Auflosung der Gleichungen, auf welche man bei der. Untersuchungen der linearen Verteilung galvanischer Strome gefuhrt wird, Poggendorf Ann. Physik, 1847. 21. Mason S.J., Feedback theory — some properties of signal flow graphs, Proc. IRE (Sept. 1953). ЛИТЕРАТУРА 329 22. Mason S. J., Feedback theory — further properties of signal flow graphs, Proc. IRE (July 1956). 23. Mason S. J., Topological analysis of linear non-reciprocal networks, Proc. IRE (June 1957). 24. Mason S.J.,Zimmerinann H.J., Electronic circuits, signals and systems, New York — London, 1960; русский перевод: M э з о н С., Циммерман Г., Электронные цепи, сигналы и системы, ИЛ, 1963. 25. Maxwell J. С., Electricity and magnetism, Oxford 1892, Clarendon Press. 26. Mayeda W., Topological formulas for active networks, Inst. Techn. Rpt., № 8, US Army Contract № DA-11-022-ORD-1983, Univ. of Illinois, Jan. 1958. 27. Mayeda W., Applications of mathematical logic to network theory. Ph. D. thesis Univ. of Illinois, 1958. 28. Mayeda W., S e s h u S., Topological formulas for network functions, Bull. № 446, Univ. of Illinois Engineering Experiment Station, 1957. 29. Mayeda W., Van V a 1 k e n b u r g M. E., Network analysis and synthesis by digital computer, Inst. Radio Engrs Convent. Rec., pt. 2, № 5, 1957. 30. Mayeda W., Van V a 1 k e n b u r g M. E., Analysis of non-reciprocal networks by digital computers, Inst. Radio Engrs Natl. Convent. Rec., pt. 2, 1958. 31. Okada S.,0nodera R., On network topology. II Bull., Yamagata U. 2, 1953. 32. 0 k a d а S., О n о d e r a R., M i у a z a k i Y., Linear geometry and topology of networks, Proc. Polytechn. Inst. Broklyn Symposium on Modern Network Synthesis, 5, 1955. 33. 0 k a d а S., О n о d e r a R., О г u i H., К о n d о K., I r i M., Mizoo Y.,Su n.a g а Т., Linear geometry and topology of networks. RAAG Memoirs of the unifying study of basic problems in engineering and physical sciences by means of geometry Y, II, Tokyo, 1953. 34. P е г с i v a 1 W. S., Solution of passive electrical networks by means of mathematical tress., /. I EE, London (1953). 35. P e r с i v a 1 W. S., Graphs of active networks. Inst. Electr. Engrs (Lon- don) Monograph № 125, 1955. 36. R e z a F. M., Order of complexity and minimal structures in network analysis, Univ. of Illinois Symposium on Circuit Analysis, 1955. 37. R e z a F. M., Some topological considerations in network theory, Trans. IRE, CT-S (March 1958). 38. S e s h u S., Topological considerations in the design of driving point functions, Trans. IRE, CT-2 (Dec. 1955). 39. Seshu S.,Balabamian N., Linear network analysis, New York, 1959; русский перевод: С е ш у С., Б а л а б а м я и Н., Анализ линей- ных цепей, Госэнергоиздат, 1963. 40. S e s h u S., R e e d M. R., Singular transformations in networks theory, Proc. Natl. Electronics Conf., 1955. 41. Seshu S., R e e d M. В., On cut sets of electrical networks. Proc. 2nd Midwest Symposium on Circuit'Theory Mich. State Univ., 1956. 42. Seshu S., Reed M. В., Linear graphs and electrical networks, Beading Massachusetts (USA), 1961; русский перевод: Се шу С., P и д M., Линейные графы и электрические цепи, изд-во «Высшая школа», 1971. 43. С и г о р с к ий В. П,, Методы анализа электрических схем с много- полюсными элементами, Киев, 1958. 44. С и г о р с к и и В. П., Анализ электрических схем, Киев, 1963. 45. Trent H. M., Note on the enumeration and listing of all possible trees in a connected linear graph, Proc. Natl. Acad. Sci. U.S., Oct. 1954. 46. W a n a t a b e H., A method of tree expansion in network topology, Trans. IRE, CT-8 (March 1961). ЛИТЕРАТУРА 47. W a n g К. Т., On a new method for the analysis of electrical networks, Natl. Res. Inst. for Engineering, Acadomia Sinica Memoir № 2, 1934. 18. W о z n i а с k i H., Obliczanie i analiza sieci elektrycznych metoda wielomianow characterystycznych, Arch. Elektrot., № 1 (1961). '19. Wozniacki H., Automatyczne programowanie obliczen i analizy liniowych sieci elektrycznych. Materialy Konferencji Krajow Socjalistycz- nych na temat automatycznego programowania maszyn cyfrowych, War- szawa, 1961. 50. Wozniacki H., Sposob tworzenia algorythmow i programowania obliczen sieci elektrycznych oraz urzadzenie do stosowania tego sposobu, zwane algorytmizatorem sieciuwym, пат. ПНР 49830, 19 янв. 1963. 51. Wozniacki H., Topologiczne metody analizy liniowych sieci elektryc- znych, Skrypt w 2-ch tomach, Warszawa, 1963. 52. Wozniacki H., Analiza grafow i elektrycznych sieci ztozonych metodq liczb strukturalpych, Praca doktorska, 1965. 53. W о z n i а с k i H., Analiza blokowych uktadow elektrycznych metodq liczb strukturalnych, Arch. Elektrot., № 1, 2 (1966). 54. Wozniacki H., Analiza uktadow elektrycznych za pomocq uktadow przetaczaja,cych. Biuletyn WAT 1967, №11. 55. Wozniacki H., Minimalizacja funkcji boolowskich i sinteza ukladow przeta.czajqcych metodq liczb stmcturalnyclr. Materialy Sympozjum «Automatyczne projektowanie maszyn cyfrowych», Warszawa, 1968. Оглавление Предисловие к русскому изданию ................. 5 Из предисловия авторов ..................... 8 Обозначения .......................... 11 Глава 1. Формальное определение системы ............. 15 t. Введение ........................ 15 2. Абстрактная модель системы ............... 16 3. Топологическая модель системы .............. 19 4. Конкретная модель системы ................ 27 5. Обобщение понятия системы ................ 32 Глава 2. Алгебра структурных чисел ............... 35 1. Основные понятия .................... 35 2. Свойства структурных чисел ............... 40 3. Геометрическое изображение структурного числа ...... 47 4. Дополнительное структурное число и геометрическое обратное изображение ....................... 50 5. Алгебраическая производная и обратная производная струк- турного числа ...................... 52 6. Детерминантная функция структурного числа ........ 55 7. Функция совпадения структурного числа ......... 56 8. Понятие ряда и последовательности структурных чисел ... 60 . Глава 3. Структурные числа и графы высшей категории ...... 64 1. Введение ........................ 64 2. Определение структурного числа второй категории ..... 64 3. Структурные числа /с-й категории ............. 69 4. Контурные правила графа ................ 75 5. Правила сечений графа ................. 77 6. Структурное число графа с замкнутыми вершинами ... 79 7. Структурное число разомкнутого графа .......... 82 8. Преобразование графа .................. 83 9. Графы второй категории (блок-графы) ........... 89 10. Графы k-ц категории .................. 117 Глава 4. Полные структурные числа и замещающие графы ..... 119 1. Введение ........................ 119 2. Полные структурные числа ..."............. 119 ** 3. Замещающие графы .................... 127 4. Полное структурное число блок-графа ........... 141 5. Деревья и деревья высших категорий блок-графа ..... 156 ОГЛАВЛЕНИЕ Глава 5. Анализ электрических цепей методом структурных чисел . . 163 1. Введение ........................ 163 2. Анализ пассивных цепей ................. 164 3. Анализ активных цепей ..................' 187 Глава 6. Анализ электрических блок-схем методом структурных чисел 209 1. Введение ........................ 209 2. Детерминантная функция блок-схемы ........... 211 3. Входной иммитанс блок-схемы .............. 219 4. Коэффициент передачи напряжения блок-схемы ....... 226 5. Схемы замещения ..................... 246 6. Преобразование активных блок-схем. ........... 252 Глава 7. Синтез электрических цепей методом структурных чисел . . 255 1. Введение ........................ 255 2. Синтез пассивного двухполюсника ............ 257 3. Синтез пассивного RLC-четырехполюсника ......... 262 Приложение 1. Программа расчета элементов четырехполюсника . . 285 1. Данные .......................... 285 2. Результаты ....................... 287 3. Метод решения ...................... 289 4. Время решения ...................... 293 Приложение 2. Анализ электрических цепей с помощью переключаю- щих схем и методом циклов ........... 294 1. Введение ........."............'... 294 2. Анализ электрических цепей с помощью переключающих схем 294 3. Анализ электрических схем методом циклов ........ 309 Приложение 3. Минимизация булевых функций и синтез переключаю- щих цепей методом структурных чисел ...... 312 1. Минимизация булевых функций .............. 312 2. Синтез переключающих цепей методом структурных чисел 319 Литература .......................... 328 Уважаемый читатель^ Ваши замечания о содержании книги, ее оформлении, качестве'пере- вода и другие просим присылать по адресу: 129820 Москва, И-110, 1-й Рижский пер., д. 2, издательство «Мир» С. Беллерт Г. Возняцки АНАЛИЗ И СИНТЕЗ ЭЛЕКТРИЧЕСКИХ ЦЕПЕЙ МЕТОДОМ СТРУКТУРНЫХ ЧИСЕЛ Редактор Т. Б. Моисеева Художник В. Е. Карпов Художественный редактор Н. Г. Блинов Технический редактор Т. А. Максимова Корректор О. Ф. Иванова Сдано в набор 29/IV 1972 г. ' Подписано к печати 4/Х 1972 г. Бумага кн.-журн. 60x90l/ie=10,50 бум. л. Печ. л. 21. Уч.-изд. л. 17,66. Изд. №20/6350. Цена 1 р. 43 к. Зап. 0298 ИЗДАТЕЛЬСТВО «МИР» Москва, 1-й Рижский пер., 2 Ордена Трудового Красного Знамени Московскан типография № 7 «Искра революции» Главполиграфпрома Государственного комитета Совета Министров СССР по делам издательств, полиграфии и книжной торговли г. Москва, Трехпрудный пер., 9 ИЗДАТЕЛЬСТВО «.МИР* в 1973 году выпускает следующие книги: БЕНДАТ Дж., ПИРСОЛ А., Измерение и анализ случай- ных процессов Книга представляет собой переработанное и дополненное издание монографии этих же авторов «Измерение и анализ случайных процессов», вышедшей в русском переводе («Мир'>,. 1971). Ее можно рассматривать как практическое пособие по применению современных аналоговых и численных методов анализа случайных процессов. В отличие от предыдущего изда- ния в нее включены, кроме стационарных и нестационарных процессов, переходные случайные процессы и более, широко описаны многомерные процессы. Серьезное внимание уделено вопросам получения и регистрации данных измерений, подго- товки их к анализу и оценке свойств процессов. Приведены новые рекомендации по определению спектральной плотности и корреляционной функции быстрым преобразованием Фурье. Выводы иллюстрируются многочисленными примерами. Книга представляет значительный интерес для инженеров и научных работников, занимающихся измерением и анализом различного рода случайных процессов, а также для преподава- телей, аспирантов и студентов соответствующих специальностей. ДИМО П., Узловой анализ электрических систем Книга акад. АН СРР Димо посвящена изучению режимов электрических систем. Помимо обычных методов исследования, описываемых и в других работах, в ней изложены и оригинальные методы. Так, разобран метод узлового анализа, идея которого основана на том, что любую рассматриваемую электроэнерге- тическую систему во всех случаях можно привести к такой экви- валентной схеме, в которой сохранится часть узлов исходной сети, причем каждый из этих узлов будет непосредственно свя- зан с остальными. Книга содержит общие сведения о работе энергосистем и возможных методах исследования их режимов; рассмотрены как методы анализа без использования цифровых машин, так и методы, основанные на их применении. Для воз- можности непосредственной оценки физического состояния сети при узловом анализе описаны элементы матричного исчисления и теории графов; использованы классические геометрические представления. Книга предназначена для специалистов в области энерге- тики, а также для научных работников, аспирантов и студентов энергетических и электротехнических специальностей.