«Математический аппарат инженера»

Математический аппарат инженера (fb2) - Математический аппарат инженера 1031K (книга удалена из библиотеки) скачать: (fb2) - (epub) - (mobi) - Виталий Петрович Сигорский

Математический аппарат инженера

Сигорский В.П.

1977.

Глава 1

Введение

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

М. А. Лаврентьев

Эта глава начинается с рассмотрения общих вопросов применения математики в инженерном деле. Математический аппарат инженера определяется как взаимосвязанная совокупность языка, моделей и методов математики, ориентированная на решение инженерных задач. Цель настоящей книги - помочь инженеру в освоении некоторых практически важных разделов математического аппарата, пока еще не нашедших должного отражения в вузовском курсе высшей математики.

Основное внимание уделяется множествам, матрицам, графам, логике и вероятностям. Все эти разделы тесно связаны между собой, поэтому во вводной главе приведены краткие сведения по каждому из них, которые затем используются при более глубоком изложении материала. Внутренние ссылки даются тремя цифрами в скобках, означающими соответственно номера главы, параграфа, пункта. При ссылках на материал внутри главы ее номер опускается, а в пределах параграфа ссылка содержит только номер пункта.

При изучении вводной главы важно понять смысл основных определений, привыкнуть к соответствующей символике, научиться выполнять простейшие операции над математическими объектами. Этой цели должны способствовать приведенные в конце каждого параграфа задачи и упражнения, решение которых позволит закрепить и расширить изложенный материал. Даже если читатель отложит изучение специальных глав на будущее, то и тогда материал вводной главы может пригодиться при чтении специальной литературы и справочных пособий. Разумеется, каждый читатель в зависимости от его подготовки и целей наметит свой подход к использованию книги.

- 5 -

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

1. Математика в инженерном деле

1. Взаимодействие математики и техники. Технические науки развиваются в тесном взаимодействии и сотрудничестве с математикой. Это проявляется, с одной стороны, в использовании математического аппарата для решения научно-технических задач. С другой стороны, инженерная практика в значительной мере ориентирует и стимулирует развитие самой математики. Можно привести множество примеров, иллюстрирующих это положение.

Исследование различных типов дифференциальных уравнений с самого начала тесно связывалось с решением технических и физических проблем. Метод наименьших квадратов, ставший одним из эффективных средств обработки результатов наблюдений возник из потребностей геодезической практики. Начертательная геометрия развилась под влиянием строительного дела, архитектуры и механики. Огромный арсенал численных методов сформировался и продолжает развиваться благодаря практическим потребностям.

Взаимодействие математических и прикладных дисциплин приводит к их взаимному обогащению, причем этот процесс носит двусторонний характер. Нередко идеи и методы, разработанные для решения частных задач в какой-либо конкретной области, приобретают в процессе развития столь общее значение, что их строгое обоснование становится делом математиков. Те идеи и методы, которые выдерживаются всесторонние и подчас весьма длительные испытания, развиваются в математические теории, обслуживая затем более широкий класс задач, чем те, из которых они возникли.

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

- 6 -

Можно привести много других примеров, когда математические теории, возникающие и развивающиеся из внутренних потребностей математики, находят затем широкое практическое применение в других отраслях науки и техники. Так обстояло дело, например, с математической логикой, аппарат которой стал одним из основных средства проектирования автоматов и моделирования дискретных систем. Неэвклидовы геометрии, служившие первоначально целям аксиоматического обоснования математики, нашли применение при конструировании самолетов и ракет. Теория электромагнитных волн была разработана за несколько десятилетий до их обнаружения и практического использования.

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

Одним из наиболее эффективных результатов взаимодействия математики и техники явилось создание современных вычислительных машин. Симбиоз математических методов и технических средств электроники, магнитной техники, прикладной оптики и механики уже весьма высоко зарекомендовал себя в этом отношении и открывает необозримые перспективы в будущем. Развитие вычислительной техники позволяет привести в действие более мощные ресурсы математики и усиливает ее роль как непосредственной производительной силы общества, способствуя тем самым прогрессу самой математики.

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

Так, трехмерное геометрическое пространство обобщается на любое число измерений, и в этом многомерном пространстве изучаются пространственно подобные отношения (длина, расстояние, ортогональность). Алгебраические операции абстрагируются и распространяются на объекты любой природы, которые образуют различные структуры в зависимости от приписываемых им свойств (группа, кольцо, тело, поле). Под переменными понимаются не только обычные величины, но и функции, которые рассматриваются как объекты функциональных пространств. Изучаемые математикой объекты объединяют совокупности величин, для представления которых используются такие понятия как множества, матрицы, графы.

- 7 -

Математика развивается как единая наука с присущими ей методами. Но в зависимости от точки зрения на ее предмет математику подразделяют на содержательную математику, формальную математику, метаматематику и прикладную математику.

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

Формальная математика отвлекается от конкретной природы объектов и сосредотачивает свое внимание на отношениях в чистом виде (например, отношение параллельности не связывается с понятием линии). Первоначально вводится совокупность символов (алфавит), которые различаются только по форме, а также задаются правила построения из этих символов терминов и предложений. Исходные положения формальной теории (аксиомы) принимаются в виде предложений, в которые входят определяемые термины. Из этих предложений на основе установленных правил преобразования выводятся другие предложения (теоремы) данной теории.

Метаматематика изучает формализованные теории как системы терминов и предложений. Объектами исследования метаматематики являются конечные последовательности (строчки) символов с операциями, которые представляют термины и предложения (в том числе аксиомы и теоремы). Метаматематику можно считать содержательной наукой, если системы символов рассматривать как материальные объекты.

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

- 8 -

Так, двузначная логика интерпретируется в технике как теория контактных и логических схем, а в науке о мышлении — как исчисление высказываний.

В отличие от прикладной математики, остальные математические теории часто относят к «чистой» математике. Однако между чистой и прикладной математикой невозможно провести четкую грань, да в этом и нет потребности. Ясно, что чисто математическая теория при определенных условиях может получить эмпирическую интерпретацию и стать основой для прикладной теории. В то же время теория, зародившаяся в недрах прикладных наук, может заслужить право на обобщение до уровня чисто математической теории.

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

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

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

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

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

- 9 -

процессов, результаты контроля выпускаемой продукции, технико-экономические показатели работы участка, цеха, предприятия. На основе анализа этих данных принимают решения, направленные на совершенствование технологии, увеличение производительности труда и повышение качества выпускаемой продукции. Принятие решений при проектировании основывается на анализе технических условий путем расщепления сложной задачи на более простые, использовании научно-технического опыта при теоретической и экспериментальной проверке выдвигаемых гипотез, всестороннем учете возможностей и ограничений технологии, экономических, социальных и психологических факторов. Участие в научных исследованиях возлагает на инженера принятие решений, направленных на обеспечение надежного функционирования технических средств и получение достоверных данных об исследуемых объектах. Инженеры участвуют также в планировании эксперимента, обработке данных и оформлении научных результатов.

Процессы обработки данных и принятия решений требуют привлечения математических методов и вычислительных средств, уровень которых зависит от сложности решаемых задач. Разумеется, успех дела в значительной мере определяется личными качествами инженера, его профессиональной и теоретической подготовкой. Важнейшую роль в этом отношении играет умение инженера выбрать соответствующий его задаче математический аппарат и наиболее эффективно использовать его для получения требуемого результата.

4. Математический аппарат инженера. По словам академика А. Н. Крылова, математика для инженера есть инструмент такой же, как штангенциркуль, зубило, напильник для слесаря. Инженер должен по своей специальности уметь владеть инструментом, но он вовсе не должен уметь его делать, подобно том, как слесарь не должен сам насекать напильник, но зато — уметь выбрать тот напильник, который ему нужен.

К математическому аппарату инженера можно отнести все то из математики, что используется в инженерном деле. В каждой конкретной области основу математического аппарата составляют математические теории, интерпретированные на совокупности объектов из данной области. Для математика такая интерпретация идет от теории к реальным системам, иллюстрирующим практичность теории и представляющим интерес как область ее приложения. Для инженера исходной является реальная система, при проектировании или исследовании которой он должен найти и использовать подходящую или, как говорят, адекватную математическую теорию. После эмпирической интерпретации адекватная математическая теория приспосабливается к решению задач данной конкретной области и развивается как прикладная.

- 10 -

Ясно, что для поиска и понимания математических теорий необходимо, прежде всего, знать язык математики. Без этого невозможно ни чтение математической литературы, ни общение с математиками. Более того, язык математики все больше приникает в прикладные области и широко используется в специальной литературе, т.е. в значительной мере становится и языком инженера.

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

Замена реальной системы соответствующей моделью позволяет использовать для ее исследования методы адекватной математической теории. В рамках прикладной теории эти методы, как правило, получают дальнейшее развитие в соответствии с характером решаемых задач и интерпретируются в терминах реальных объектов.

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

5. Язык математики. В математике, как и в других науках, наряду с естественными языками, используются искусственные языки, формализация которых достигает такого уровня, что при некоторых условиях саму математику рассматривают как специально организованный язык (формальная математика).

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

Присущие естественным языкам недостатки устраняют построением формального языка, словарем которого служит система символов, обозначающих математические объекты и переменные, а также операции над объектами и отношения между ними. Формулы и любая совокупность символов, отвечающая определенным требованиям, играют роль предложений такого языка. Важнейшая особенность формального языка математики состоит в том, что переход от одних формул к другим совершается по строго определенным правилам, не допускающим двусмысленного толкования.

- 11 -

Естественные и формальные языки взаимно дополняют друг друга и каждый из них используется по своему назначению. На естественных языках осуществляется часть рассуждений, даются дополнительные пояснения, обсуждаются полученные результаты и т.п. Кроме того, естественный язык играет роль метаязыка, при помощи которого задаются свойства и правила (синтаксис) формального языка и вводятся содержательные определения объектов.

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

Применение формального языка математики оправдано всегда, если речь идет о сложных вещах, изложение которых на естественном языке требует синтаксически сложных предложений и может привести к неточному их толкованию. Важно также и то, что работа с формальными языками развивает способности к логическому мышлению в любой прикладной области.

6. Математические модели. Реальные объекты, с которыми имеет дело инженер, обладают бесконечным множеством свойств и характеризуются бесконечным множеством связей как внутри самого объекта, так и вне его (связи с другими объектами и окружающей средой). Переход к соответствующим моделям является наиболее сложным и ответственным этапом применения математического аппарата в инженерном деле. В значительной мере успешное решение этой задачи определяется опытом и интуицией специалиста в данной конкретной области. В то же время можно указать и ряд общих требований, которые обычно предъявляются к математической модели: достаточная точность, предельная простота и стандартная форма.

Обеспечить достаточную точность модели — это значит учесть при идеализации реального объекта все существенные свойства и связи, отвлекаясь от второстепенных. Несущественных свойств и связей. Решение этого вопроса зависит не только от характера самого объекта, но и от поставленной задачи. Поэтому для одного и того же объекта может потребоваться не одна, а несколько моделей, обслуживающих различные задачи при его проектировании или исследовании. Например, усилительная электронная цепь при определении начального режима описывается нелинейными алгебраическими уравнениями, а в режиме усиления слабых сигналов — линейными дифференциальными уравнениями.

- 12 -

Для определения нелинейных искажений такой цепи в ее модели необходимо учесть нелинейность характеристик электронных ламп или транзисторов.

Представляя реальный объект с достаточной точностью, математическая модель в то же время должна быть оп возможности проще, так как дальнейшая работа со сложной моделью не только затруднительна, но может оказаться и практически невозможной. Противоречивость этих требований нередко вынуждает поступиться точностью в интересах простоты, однако такой компромисс допустим только в тех пределах, при которых модель еще отражает существенные свойства реального объекта. Разработка методов упрощения реальных объектов и систем с целью построения предельно простых математических моделей является одной и центральных задач любой прикладной области.

При моделировании реальных объектов целесообразно ориентироваться на математические модели стандартного вида, которые обеспечены соответствующим аппаратом. Физические процессы характеризуются пространственно-временными соотношениями и в общем случае описываются дифференциальными уравнениями в частных производных. Важным методом упрощения модели является представление объекта или совокупности объектов в виде системы таких ее частей (компонентов), связь между которыми можно с достаточной точностью охарактеризовать функциями только одно переменной (времени). В одних случаях этот путь предсказывается самой структурой объекта (например, электронные цепи или системы управления), в других случаях требуется искусственное расчленение объекта на отдельные части (например, балку с распределенной нагрузкой представляют в виде участков с сосредоточенными нагрузками). Если известны модели компонентов в виде некоторых зависимостей относительно их внешних связей, то модель системы можно представить обыкновенными дифференциальными уравнениями. Тем самым осуществляется переход от модели с распределенными параметрами к более простой модели с сосредоточенными параметрами.

Моделирование компонентов системы само по себе может представлять серьезные трудности, однако эта задача всегда проще, чем рассмотрение системы в целом. Кроме того, несмотря на огромное разнообразие систем, набор различных компонентов весьма ограничен, и их модели, полученные один раз в стандартной форме, могут затем многократно использоваться при моделировании сложных систем. В общем случае модели компонентов характеризуются нелинейными зависимостями. Однако многие задачи допускают их линеаризацию, что соответственно сильно упрощает и модели систем, которые в таких случаях описывается линейными уравнениями. Если параметры компонентов можно считать не зависящими от времени, то система представляет стационарной моделью

- 13 -

в виде дифференциальных уравнений с постоянными коэффициентами.

Параметры системы и приложенные к ней воздействия можно рассматривать как детерминированные или случайные величины, что приводит соответственно к детерминированным или стохастическим моделям. Выбор той или иной модели зависит от характера протекающих процессов и поставленной задачи исследования.

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

Реальные физические процессы протекают в непрерывно изменяющимся времени, которое является аргументом соответствующих им функций. Роль непрерывного аргумента в различных задачах исследования или проектирования могут играть и другие физические величины (расстояние, объем, масса, температура и т.п.). При этом математические модели, типичными представителями которых являются дифференциальные уравнения, также называют непрерывными. Однако во многих случаях целесообразно рассматривать состояние системы только для последовательности дискретных значений независимой переменной (времени), отвлекаясь от характера происходящих процессов в промежутке между этими значениями. Этот подход обслуживают различные типы дискретных моделей.

Важным типом дискретных моделей являются конечно-разностные дифференциальные уравнения, которые описывают процессы в исследуемой системе относительно конечных (не обязательно равных)приращений независимой переменной. Такая модель представляет собой как бы моментальные фотографии состояний системы, выполненные последовательно через некоторые промежутки времени (или другой независимой перемененной). Ясно, что точность моделирования тем выше, чем меньше приращения независимой переменной, но уменьшение интервалов между дискретными значениями неизбежно приводит к увеличению объема вычислений. Представление непрерывных систем дискретными моделями всегда связано с решением вопроса об оптимальном выборе шага дискретности как компромисса между точностью и простотой.

Для многих систем дискретность является основным свойством их функционирования. В некоторые моменты времени происходит переход их одного состояния в другое, последовательно которых представляет наибольший интерес, а процессы между этими состояниями либо отодвигаются на второй план, либо и вовсе не имеют

- 14 -

значения. В таких случаях дискретная модель представляет собой естественное отображение системы в том смысле, что дискретные моменты времени определяются изменением ее состояний. Более того, вместо времени (или другой независимой переменной) можно рассматривать последовательность состояний, различающихся каким-либо другим признаком. Типичным представителем дискретных моделей этого типа являются, например, конечные автоматы.

Для представления математических моделей широко используется аппарат теории множеств, матриц и графов. Соответственно различают теоретико-множественные, матричные и топологические модели. В последнее время в качестве математических моделей реальных объектов находят применение различные алгебраические структуры: группы, кольца, поля и т.п.

7. Математические методы. После того как математическая модель построена, дальнейшая работа состоит в применении соответствующих математических методов с целью получения необходимых характеристик данной модели, а значит. И исследуемого реального объекта. Большое разнообразие математических методов можно свести к тем основным видам: аналитическим, графическим и численным.

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

Графические методы обладают наглядностью и успешно используются как для иллюстрации аналитических методов, так и непосредственно в инженерных расчетах. Они особенно удобны, если не требуется высокая точность или если интерес представляет качественная картина происходящих процессов. Например, графические построения на фазовой плоскости позволяют судить

- 15 -

о характере колебаний в системе, ее устойчивости и т.п. Графические методы используются при решении теоретико-множественных уравнений, минимизации логических функций, статистической обработке результатов наблюдений и во многих других случаях. Инженеры привыкли пользоваться графиками нелинейных характеристик компонентов и протекающих в системах процессов, полученных теоретически или экспериментально. К сожалению, графические методы ограничены возможностями построений на плоскости или в трехмерном пространстве, вследствие чего они применимы только для простых моделей. Особое место занимают методы теории графов, но и они теряют наглядность при усложнении модели. В практике инженерных расчетов графические методы часто используются совместно с аналитическими. В таких случаях их называют графоаналитическими методами.

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

При использовании прямых методов результат получается путем последовательных операций над числами и его точность зависит исключительно от точности промежуточных вычислений. В итерационных метода результат получается путем последовательных приближений, начиная от некоторых начальных значений. Каждое последующее значение (итерация) вычисляется по одной и той же схеме, представляющей собой цикл вычислительного процесса. Необходимым условием работоспособности итерационного метода является сходимость последовательности итераций к искомой величине или совокупности величин, т.е. возможность получения результата с требуемой точностью. Практически требуется также достаточная скорость сходимости итерационного процесса, т.е. достижение требуемой точности таким количеством итераций, которое реализуется в данных конкретных условиях. Часто прямые методы называют точными, а итерационные — приближенными. Однако эти названия не связаны непосредственно с точностью получаемых результатов. Нередко, как раз наоборот, результаты, полученные прямыми методами, уточняются с помощью итерационных процессов.

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

- 16 -

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

8. Использование вычислительных машин. Пока вычислительные средства ограничивались арифмометром и логарифмической линейкой, инженер мог использовать в своей работе только сравнительно простой математический аппарат. В современных условиях все большее значение приобретает применение развитого математического аппарата в сочетании с высокопроизводительной вычислительной техникой.

Возрастающая роль математического моделирования в инженерном деле обусловлена характерными особенностями развития техники. Это, прежде всего, усложнение технических проектов, жесткие технико-экономические условия, требования высокого качества и надежности в условиях массового производства, сжатые сроки проектирования и освоения новых изделий. В то же время математическое моделирование опирается на большой парк вычислительных машин, отличающихся принципом действия и уровнем специализации, производительностью и объемом памяти, способами программирования и организацией связей с внешними устройствами.

Области применения двух основных типов машин — аналоговых и цифровых — определяются их характерными особенностями. Аналоговые машины имеют большие преимущества по скорости, а цифровые — по точности выполнения математических операций. Положительные стороны обоих типов машин объединяются в гибридных вычислительных комплексах, включающих цифровые и аналоговые устройства, связанные через цифро-аналоговые преобразователи. Развитию таких комплексов способствуют, по крайней мере, два обстоятельства. Во-первых, повышение точности и компактности аналоговых устройств за счет совершенствования решающих компонентов (в частности, операционных усилителей) на основе интегральной технологии. Во-вторых, снижение эффективности применения цифровых устройств из-за возможного уменьшения точности при очень большом количестве операций.

Моделирование на вычислительных машинах может осуществляться двумя основными способами: в режиме пакетной обработки данных и в режиме оперативного взаимодействия.

В режиме пакетной обработки общение с машиной при решении некоторой задачи сводится к вводу исходных данных и получению требуемых результатов. Каждый раз такое общение происходит по однотипной схеме и оформляется как отдельный заказ. Часто пользователь вообще непосредственно не участвует в вычислительном процессе. Который обслуживается персоналом вычислительного центра.

В режиме оперативного взаимодействия пользователь может вмешиваться в ход решения задачи,редактировать исходные и

- 17 -

промежуточные данные в зависимости от получаемых результатов, уточнять и изменять постановку задачи. На практике такое взаимодействие осуществятся на различных уровнях технического оснащения — от цифропечатающих устройств и графопостроителей до специально организованных пультов, называемых терминалами и дисплеями. Типичный дисплей состоит из электронно-лучевого индикатора, на котором отображается информация в цифровой и графической форме, и клавиатуры для ввода данных (или печатающего устройства, которое также используется для контроля и вывода). Часто дисплей снабжается световым пером, позволяющим осуществлять операции ввода исходных данных и команд

Рис. 1. Математическое моделирование на вычислительной машине в режиме оперативного взаимодействия.

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

Моделирование в режиме оперативного взаимодействия является наиболее привлекательным и перспективным методом использования вычислительных машин, позволяет достигнуть высокой степени автоматизации при проектировании, организации производства и научных исследований. Это, однако, не умаляет значения режима пакетной обработки данных при решении инженерных задач на вычислительных машинах различной сложности — от малых с простейшими методами программирования до больших универсальных с развитым математическим обеспечением.

Многие инженерные задачи могут решаться на машинах с помощью стандартных методов и программ. В таких случаях инженеру достаточно быть осведомленным о возможностях, которые могут быть предоставлены в его распоряжение вычислительным

- 18 -

центром или персоналом, эксплуатирующим и обслуживающим конкретную вычислительную машину. Однако рано или поздно возникнет необходимость написания программ для решения специальных задач и хорошо, если инженер подготовлен к этому. Как минимум, нужно ознакомиться хотя бы с начальными сведениями по программированию, чтобы иметь возможность общаться с программистами и совместно работать с ними. Но лучше всего самому овладеть методами программирования. Обретенная независимость в общении с машиной и большое эмоционально удовлетворение компенсируют с избытком сравнительно набольшую затрату времени и усилий, необходимых для изучения подходящего языка программирования.

В сложном процессе проектирования математическое моделирование сочетается с экспериментами над реальными объектами. Эксперимент служит источником исходных данных и критерием правильности выбранной модели. В то же время само моделирование является как бы экспериментом в чистом виде, в котором представлены наиболее существенные свойства и связи исследуемых объектов.

9. Математическое образование инженера. Значение математического образования в подготовке инженеров за последние десятилетия сильно возросло. Совершенствованием содержания и методики преподавания высшей математики в вузах постоянно занимаются крупнейшие ученые и педагоги. Однако существующее положение вещей оставляет желать много лучшего. «Обучают ли наших студентов всему тому, что им нужно или что им может быть нужно?» - ставит вопрос академик С. Л. Соболев и отвечает: «Этого сказать нельзя. Даже в университетах программы не поспевают за жизнью, но особенно это заметно во втузах.»

Складывается необычная ситуация. Благодаря глубокой реформе преподавания математики в средней школе многие школьники теперь изучают такие разделы, о которых инженеры даже не слышали в свои студенческие годы. В школьные программы вводятся важные разделы современной математики — теория множеств, математическая логика и др. А начальное знакомство с некоторыми положениями теории графов в порядке опыта проводится даже в старших группах детских садиков (об этом свидетельствует книга «Дети и графы» супругов Папи, перевод которой вышел в 1974 г. в издательстве «Педагогика»).

Вузовский курс высшей математики в значительной мере дополняется при изучении специальных инженерных дисциплин, в которых излагается необходимый математический аппарат. По существу изучение математики в вузах на различных уровнях продолжается в течение всего периода учебы студентов. Большую роль в математической подготовке инженеров играют спецкурсы и учебные

- 19 -

пособия по тем разделам, которые не нашли должного отражения в основном курсе высшей математики.

Конечно, под влиянием требований все более усложняющейся инженерной практики изучение математики в вузах с каждым годом совершенствуется и углубляется. Постепенно видоизменяются учебные программы, пересматриваются традиционные методы преподавания, изменяется отношение к многим классическим разделам, которым приходится потесниться, чтобы освободить место и время для важнейших разделов современной математики. Но как бы ни были совершенны программы и учебники, каким бы мастерством не владели преподаватели, сколько бы ни отводилось для математических дисциплин часов в учебных планах, невозможно изучить впрок все то, что потребуется из математики для будущей инженерной деятельности. Математическое образование инженера не заканчивается в вузе, более того, оно не заканчивается никогда.

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

Следует учитывать также и психологические аспекты математического образования. Ясно, что интерес к изучению какого-либо раздела математики существенно зависит от того, заготавливаются ли знания впрок или же они требуются для решения конкретной прикладной задачи. В последнем случае овладение знаниями, навыками и умением проходит значительно эффективнее и глубже, так как процесс обучения подогревается острой практической потребностью.

Итак, постоянное совершенствование математических знаний должно рассматриваться как естественный процесс в творческой деятельности инженера.

2. Множества

1. Что такое множество? Ответить на этот вопрос не так просто, как это кажется на первый взгляд. В повседневной жизни и практической деятельности часто приходится говорить о некоторых совокупностях различных объектов: предметов, понятий, числе, символов и т.п. Например, совокупность деталей механизма, аксиом

- 20 -

геометрии, чисел натурального ряда, букв русского алфавита. На основе интуитивных представлений о подобных совокупностях сформировалось математическое понятие множества как объединения отдельных объектов в единое целое. Именно такой точки зрения придерживался основатель теории множеств немецкий математик Георг Кантор.

Множество относится к категории наиболее общих, основополагающих понятий математики. Поэтому вместо строгого определения обычно принимается некоторое основное положение о множестве и его элементах. Так, группа выдающихся математиков, выступающая под псевдонимом Н. Бурбаки, исходит из следующего положения: «Множество образуется из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств».

2. Множество и его элементы. Утверждение, что множество А состоит из различимых элементов а1, а2, ... , аn (и только из этих элементов), условно записывается A= {а1, а2, ... , аn}. Принадлежность элемента множеству (отношение принадлежности) обозначается символом ∈ ,т.е. а1 ∈ A, а2 ∈ A,... аn ∈ A, или короче . Если b не является элементом A, то пишут b ∉ A или b ∈̅ A

Два множества A и B равны (тождественны), A = B, тогда и только тогда, когда каждый элемента А является элементом В и обратно. Это значит, что множество однозначно определяется своими элементами.

Множество может содержать любое число элементов — конечное или бесконечное. Соответственно имеем конечные (множество цифр 0, 1, ..., 9 или страниц в книге) или бесконечные (множество натуральных чисел или окружностей на плоскости) множества. Не следует, однако, связывать математическое понятие «множество» с обыденным представлением о множестве как о большом количестве. Так, единичное (одноэлементное) множество содержит только один элемент. Более того, вводится также понятие пустого множества, которое не содержит никаких элементов. Пустое множество обозначается специальным символом ∅.

Роль пустого множества ∅ аналогична роли числа нуль. Это понятие можно использовать для определения заведомо несуществующей совокупности элементов (например, множество зеленых слонов, действительных корней уравнения x2 + 1 = 0). Более существенным мотивом введения пустого множества является то, что заранее не всегда известно (или неизвестно вовсе), существуют ли элементы, определяющие какое-то множество. Например, множество выигрышей в следующем тираже спортлото на купленные билеты может оказаться пустым. Никто еще не знает, является ли

- 21 -

пустым или нет множество всех решений в целых числах уравнения x3 + y3 + z3 = 30. Без понятия пустого множества во всех подобных случаях, говоря о каком-нибудь множестве, приходилось бы добавлять оговорку «если оно существует».

3. Множество и подмножества. Множество А, все элементы которого принадлежат и множеству В, называется подмножеством (частью) множества В. Это отношение между множествами называют включением и обозначают символом ⊂, т.е. А ⊂ В (А включено в В) или В ⊃ А (В включает А). Например, множество конденсаторов электронной цепи является подмножеством всех ее компонентов, множество положительных чисел — это подмножество множества действительных чисел.

Отношение А ⊂ В допускает и тождественность (А = В), т.е. любое множество можно рассматривать как подмножество самого себя (А ⊂ А). Полагают также, что подмножеством любого множество является пустое множество ∅ т.е. ∅ ⊂ А. Одновременное выполнение соотношения А ⊂ В и В ⊂ А возможно только при А = В. И обратно А = В, если А ⊂ В и В ⊂ А. Это может служить определением равенства двух множеств через отношение включения.

Наряду с А ⊂ В, в литературе можно встретить и другое обозначение А ⊆ В. При этом под А ⊂ В понимают такое отношение включение, которое не допускает равенства А и В (строгое включение). Если допускается А = В, то пишут А ⊆ В (нестрогое включение). Мы будем придерживаться принятого ранее обозначения как для строгого, так и для нестрогого включения.

4. Множество подмножеств. Любое непустое множество А имеет, по крайней мере, два различных подмножества: само А и пустое множество ∅. Эти подмножества называются несобственными, а все другие подмножества А называют собственными(эта терминология связана со словами «собственно подмножества», а не со словом «собственность»). Конечные собственные подмножества образуются всевозможными сочетаниями по одному, два, три и т.д. элементов данного множества.

Элементы множества сами могут являться некоторыми множествами. Например, книга из множества книг в шкафу может рассматриваться как множество страниц. Здесь следует обратить внимание на то, что речь идет об элементах множества, а не о подмножествах (никакая совокупность страниц не может рассматриваться как подмножество множества книг).

Множество, элементами которого являются все подмножества множества А, называют множеством подмножеств (множеством-степенью) А и обозначают через 𝓟(А). Так, для трехэлементного множества A ={a, b, c} имеем 𝓟(А) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

- 22 -

В случае конечного множества А, состоящего из n элементов, множество подмножеств 𝓟(А) содержит 2n элементов. Доказательство основывается на сумме всех коэффициентов разложения бинома Ньютона или на представлении подмножеств n-разрядными двоичными числами, в которых 1 (или 0) соответствует элементам подмножеств.

Следует подчеркнуть различия между отношением принадлежности и отношением включения. Как уже указывалось, множество A может быть своим подмножеством (A ⊂ A), но оно не может входить в состав своих элементов (A ∉ A). Даже в случае одноэлементных подмножеств следует различать множество A={a} и его единственный элемент а. Отношение включения обладает свойством транзитивности: если A ⊂ B и B ⊂ C, то A ⊂ C. Отношение принадлежности этим свойством не обладает. Например, множество A={1, {2,3} ,4} в числе своих элементов содержит множество {2, 3}, поэтому можно записать: 2,3 ∈ {2, 3} и {2, 3} ∈ A. Но из этого вовсе не следует, что элементы 2 и 3 содержатся в A (в приведенном примере мы не находим 2 и 3 среди элементов множества A, т. е. 2, 3 ∉ A.

5. Задание множеств.

Множество A = {a1, a2, ... an} можно задать простым перечислением его элементов. Например, спецификация задает множество деталей изделия, каталог — множество книг в библиотеке. Но этот способ не пригоден для задания бесконечных множеств и даже в случае конечных множеств часто практически нереализуем.

Рассмотрим в качестве примера фасад 16-этажного дома с 38 окнами в каждом этаже. В вечернее время каждое из окон дома может быть освещено или затемнено, т. е. 2608 ≈ 10183 находиться в двух состояниях. Определенные совокупности освещенных окон можно рассматривать как некоторые образы. Считая все окна (их число равно 38*16=608) различными по их расположению на фасаде, каждый такой образ можно связать с соответствующим подмножеством освещенных окон. Тогда количество всех образов равно количеству элементов множества подмножеств всех окон, т. е. . Полученное число настолько большое, что его трудно даже представить. Оно несравнимо больше числа атомов во всей видимой вселенной, которое равно примерно 1037. Если бы каждый атом превратился во вселенную, то и тогда на один атом приходилось бы 1037 образов 10183 = 1037 *1037 * 1037). Поэтому, хотя множество всех образов конечно и любой из них можно легко определить, о задании подобных множеств перечислением их элементов не может быть и речи.

Определяющее свойство. Другой способ задания множества состоит в описании элементов определяющим свойством Р(х) (формой от х), общим для всех элементов. Обычно Р(х) — это высказывание, в котором что-то утверждается об х, или некоторая функция

- 23 -

переменной х. Если при замене х на а высказывание Р(а) становится истинным или функция в заданной области определения удовлетворяется, то а есть элемент данного множества. Множество, заданное с помощью формы Р(х), обозначается как Х={х | Р(х)}, или Х={х :Р(х)}, причем а {х | Р(х)}, если Р(а) истинно. Например {х | х2 = 2} - множество чисел, квадрат которых равен двум, {х | х есть животное с хоботом} - множество слонов.

Обычно уже в самом определении конкретного множества явно или неявно ограничивается совокупность допустимых объектов. Так, множество слонов следует искать среди млекопитающих, а не среди рыб и тем более не среди планет. Если речь идет о множестве чисел, делящихся на 3, то ясно, что оно является подмножеством целых чисел. Удобно совокупность допустимых объектов зафиксировать явным образом и считать, что рассматриваемые множества являются подмножествами этой совокупности. Ее называют основным множеством (универсумом) и обычно обозначают через U. Так, универсумом арифметики служат числа, зоологии - мир животных, лингвистики - слова и т.п.

Если множество выделяется из множества A с помощью формы Р(х), то запись {х | х ∈ А, Р(х)} часто упрощается: {х ∈ А | Р(х)}. Запись {f(х) | Р(х)} означает множество всех таких у=f(х), для которых имеется х, обладающий свойством Р(х). Например, {х2 | х - простое число} означает множество квадратов простых чисел.

7. Операции над множествами. Множества можно определять также при помощи операций над некоторыми другими множествами. Пусть имеются два множества A и B.

Объединение (сумма) А ∪ В есть множество всех элементов, принадлежащих A или В. Например, {1, 2, 3} ∪ (2, 3, 4} = {1, 2, 3, 4}.

Пересечение (произведение) А ∩ В есть множество всех элементов, принадлежащих одновременно как A, так и В. Например, {1, 2, 3} ∩ {2, 3, 4} = {2, 3}. Множества, не имеющие общих элементов (A ∩ В = ∅), называют непересекающимися (расчлененными).

Разность А \ В (или A - В) есть множество, состоящее из всех элементов A, не входящих в В, например, {1, 2, 3} \ {2, 3, 4} = {1}. Ее можно рассматривать как относительное дополнение В до A. Если A ⊂ U, то множество U \ A называется абсолютным дополнением (или просто дополнением) множества A и обозначается через A̅. Оно содержит все элементы универсума U, кроме элементов множества A. Дополнение A определяется отрицанием свойства Р(х), с помощью которого определяется A. Очевидно, А \ В = A ∩ В̅.

- 24 -

Дизъюнктивная сумма (симметрическая разность) А + В (или A ⊕ В) есть множество всех элементов, принадлежащих или A, или В (но не обоим вместе). Например, {1, 2, 3} + {2, 3, 4} = {1, 4}. Дизъюнктивная сумма получается объединением элементов множеств за исключением тех, которые встречаются дважды.

8. Круги Эйлера. Для наглядного изображения соотношений между подмножествами какого-либо универсума и используют круги Эйлера (рис. 2). Обычно универсум представляется множеством точек прямоугольника, а его подмножества изображаются в виде кругов или других простых областей внутри этого прямоугольника.

Рис. 2. Круги Эйлера для основных операций над множествами.

Множества, получаемые в результате операций над множествами A и В, изображены на рис. 2 заштрихованными областями. Непересекающиеся множества

изображаются неперекрывающимися областями, а включение множества соответствует области, целиком располагающейся внутри другой (рис. 3). Дополнение множества A (до U), т. е. множество A̅ изображается той частью прямоугольника, которая лежит за пределами круга, изображающего A.

9. Отношения. В начале этого параграфа речь шла о том, что элементы множества могут находиться в некоторых отношениях между собой или с элементами других множеств.

Рис. 3. Круги Эйлера для непересекающихся множеств, отношения включения и дополнения.

В самом общем смысле отношение означает какую-либо связь между предметами или понятиями. Отношения между парами объектов называют бинарными (двуместными). Выше же были рассмотрены два таких отношения - принадлежность (а ∈ A) и включение A ⊂ B. Первое из них определяет связь между множеством и его элементами, а второе - между двумя множествами. Примерами бинарных отношений являются равенство (=), неравенства (< или ⩽ ), а также такие выражения как «быть братом», «делиться (на какое-то число)», «входить в состав (чего-либо)» и т. п.

- 25 -

Для любого бинарного отношения можно записать соответствующее ему соотношение (для отношения неравенства соотношением будет х < у, для отношения «быть братом» соотношение запишется как «х брат у»). В общем виде соотношение можно записать как хАу, где А - отношение, устанавливающее связь между элементом х из множества Х (х ∈ X) и элементом y из множества Y (y ∈ Y). Ясно, что отношение полностью определяется множеством всех пар элементов (х, у), для которых оно имеет место. Поэтому любое бинарное отношение А можно рассматривать как множество упорядоченных пар (х, у).

Отношения могут обладать некоторыми общими свойствами (например, отношение включения и отношение равенства транзитивны). Определяя эти свойства и комбинируя их, можно выделить важные типы отношений, изучение которых в общем виде заменяет рассмотрение огромного множества частных отношений.

10. Функции как отношения. Функция f, ставящая каждому числу х (аргументу) в соответствие определенное число (значение функции) у=f(х), также является бинарным отношением.

Обобщая это понятие, можно считать функцией такое бинарное отношение f, которое каждому элементу х из множества Х ставит в соответствие один и только один элемент из множества Y, т. е. хfу. При этом считают, что элементами множеств Х и Y могут быть объекты любой природы, а не только числа.

Функцией в таком общем понимании будет, например, соответствие между деталями какого-либо механизма и их массой (каждой детали соответствует ее масса), между человеком и его фамилией и т. п. В то же время такие отношения как неравенство (<) или «быть братом» функциями не являются, так как для каждого числа можно указать бесконечные множества превышающих его чисел, а человек может иметь несколько братьев или совсем их не иметь.

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

Задачи и упражнения

1. Какие из приведенных ниже соотношений неверны и почему?

а) x ∈ {2, a, x}; б) 3 ∈ {1, {2, 3}, 4}; в) x ∈ {1, sinx}; г) {x, y} ∈ {a, {x, y}, b}.

2. Равны ли между собой множества А и В (если нет, то почему)?

а) A = {2, 5, 4}, B = {5, 4, 2};

б) A = {1, 2, 4, 2}, B = {1, 2, 4};

в) A = {2, 4, 5}, B = {2, 4, 3};

г) A = { 1, {2, 5}, 6}, B = {1, {5, 2}, 6};

д) A = { 1, {2, 5}, 6}, B = {1, 2, 5, 6};

3. Связаны ли множества А и В отношением включения (если да, то укажите, какое из них является подмножеством другого)?

- 26 -

а) A = {a, b, d}, B = {a, b, c, d};

б) A = {a, c, d, e}, B = {a, e, c}

в) A = {c, d, e}, B = {c, a}

4. В каких отношениях народятся между собой следующие три множества:

A = {1,3}; B — множество нечетных положительных чисел; C — множество решений уравнения x2 — 4x + 3 = 0?

5. Образуйте множество праздничных дней 1975 г. Пересекается ли это множество с множеством воскресных дней того же года? Если да, то запишите элементы пересечения этих двух множеств.

6. К каким видам относятся следующие множества: A — множество конденсаторов в радиоприемнике; B — множество квадратов целых чисел; C — множество решений уравнения 2x — 3 = 0; D — множество деревьев на Луне?

7. Приняв множество первых 20 натуральных чисел в качестве универсума, запишите следующие его подмножества: A — четных чисел; B- нечетных чисел; C — квадратов чисел; D — простых чисел. В каких отношениях находятся эти подмножества?

8. Запишите множества, получаемые в результате следующих операций над множествами из задачи 7: A ∪ B, A ∩ B, A ∩ C, A ∩ D, C\A, C\D, C + D̅. Сформулируйте определяющие свойства каждого из полученных множеств.

9. Три прибора x, y, z сравнивают по двум показателям, причем выделяют тот из приборов, у которого данный показатель наилучший (случаи одинаковых показателей исключаются).

а) Образуйте множество U всевозможных исходов такого сравнения, обозначив элементы этого множества упорядоченными парами букв для приборов с наилучшими показателями (например, исход yx означает, что по первому показателю лучшим оказался прибор y, а по второму — прибор x).

б) Сколько элементов содержит множество всевозможных исходов сравнения m приборов по n показателям?

в) Перечислите элементы множеств возможных исходов, при которых прибор оказывается лучшим по первому показателю (A), по второму показателю (B), хотя бы по одному показателю (C), по обоим показателям (D), не является лучшим ни по одному показателю (E).

10. Для множеств A, B, C, D, E из задачи 9в дайте ответы на следующие вопросы:

а) Какие множества выражаются через объединение, дополнение, пересечение других множеств?

б) Какому множеству соответствует разность А \ В и каков его смысл?

в) Какие множества связаны между собой отношением включения?

г) Какому множеству соответствует дизъюнктивная сумма А+В и каков его смысл?

11. На примере множеств А и В из задачи 9в покажите справедливость соотношения A\B = A ∩ B̅ и проиллюстрируйте его с помощью кругов Эйлера.

12. Что можно сказать от отношениях между множествами A, B, C, представленными кругами Эйлера на рис. 4? Запишите с помощью операций над множествами выражения для множеств, соответствующих заштрихованными областями.

13. Для написания цифр почтового индекса используют множество из девяти элементов, которые обозначены буквами на рис. 5, а, а сами цифры изображены на рис. 5, б.

а) Сколько различных фигур можно изобразить с помощью всевозможных комбинаций из элементов исходного множества, считая, что в каждой такой комбинации может участвовать от 0 до 9 элементов? Какой процент этих комбинаций используется для начертания цифр?

- 27 -

б) Запишите множества Ak (k = 0,1, ... , 9) элементов каждой из десяти цифр ( например, A7 = {a, c, f}). Имеются ли среди них непересекающиеся множества?

в) Запишите для каждого из элементов s ( s = a, b, ... , i) множество Bs, состоящее из цифр, в написании которых используется элемент s (например, Bf = {0, 6, 7, 8}). Какие элементы используются наиболее редко и наиболее часто?

Рис. 4. Круги Эйлера к задаче 12.

г) Считая мерой близости цифр количество общих элементов, укажите цифры, наименее и наиболее близкие цифре 3. Какой операции над множествами Ak соответствует множество, определяющее меру близости цифр?

14. В химическом продукте могут оказаться примеси четырех видов, обозначенных через a, b, c, d. Приняв в качестве исходного множества A = {a, b, c, d}, образуйте множество всех его подмножеств Р(А). Дайте содержательное истолкование этого множества и его элементов. Каким ситуациям соответствуют, в частности, несобственные подмножества?

Рис. 5. Начертание цифр почтового индекса:

а- элементы исходного множества; б — цифры.

15. Докажите, что для конечного множества, состоящего из n элементов, множество всех его подмножеств содержит 2n элементов.

16. Проверьте свойство транзитивности отношения включения на примере множеств X = {b, c}, Y = {a, b, c}, Z = {b}.

17. Дайте словесное описание каждому из следующих множеств:

а) {x|x — точка плоскости, находящаяся на расстоянии r от начала координат};

б) {x|x2 — 4x + 3 = 0};

в) {x|x — инженер нашего отдела};

г) {x|x ∈ A и z ∈ B }; A — множество транзисторов; В — множество деталей радиоприемника;

д) {x ∈ R |x = 3k, k ∈ N} N — множество натуральных чисел;

е) {x2 + 1 |x - целое число}

18. Покажите, что для любых множеств А и В справедливо соотношение ∅ ⊂ A ∩ B ⊂ A ∪ B

19. Покажите, что для любого множества А справедливы соотношения: A + A = ∅; A + ∅ = A.

20. Покажите, что из соотношения A ∩ B = C следует C ⊂ A и C ⊂ B.

21. Пусть M1 и M2 — соответственно множества деталей первого и второго механизмов, а Р — множество пластмассовых деталей. Запишите в виде теоретико-множественных соотношений следующие условия.

- 28 -

а) Среди деталей первого механизма имеются все пластмассовые детали.

б) Одинаковые детали, входящие в оба механизма, могут быть только пластмассовыми.

в) Во втором механизме нет пластмассовых деталей.

22. Является ли совокупность полученных в предыдущей задаче соотношений (Р ⊂ M1, M1 ∩ M2 ⊂ P, M2 ∩ P = ∅) непротиворечивой? Если да, то можно ли ее упростить? Для ответа на поставленные вопросы проведите сначала логические рассуждения, а затем воспользуйтесь кругами Эйлера. Сформулируйте выводы, соответствующие полученному результату.

23. Запишите множество упорядоченных пар (x, y), выражающих отношение «x — делитель y» на множестве целых чисел от 2 до 10 включительно. Является ли это отношение функцией? Обладает ли оно свойством транзитивности?

24. Запишите отношение между элементами множества цифр из задачи 13, выражающееся как «x имеет больше двух общих элементов с y».

25. Пусть x ∈ X, y ∈ Y и A — отношение между элементами множеств X и Y, выражаемое соотношением xAy. Укажите, в каких случаях А можно рассматривать как функцию:

а) X — множество студентов, Y - множество учебных дисциплин, xAy - «x изучает y»;

б) X - множество спортсменов, Y - рост в единицах длины, xAy - «x имеет рост y»;

в) X — множество компонентов электрической цепи, Y- множество узлов цепи, xAy - «x связан с y».

3. Матрицы

1. Матрица как таблица. Матрица – это совокупность чисел или объектов другой природы, расположенных в виде прямоугольной таблицы:

Такая таблица, состоящая из m строк и n столбцов, содержит mn клеток (позиций). При этом говорят, что матрица имеет размер m × n и ее называют ( m × n )-матрицей. Позиция на пересечении i -й строки и j -го столбца называется ij -клеткой.

Числа или любые другие объекты, расположенные в клетках таблицы, называют элементами матрицы. Положение элементов строго фиксировано: в каждой клетке должен располагаться только один элемент и ни одна клетка не должна оставаться свободной.

- 29 -

В общем обозначении элемента aij первый индекс i всегда указывает номер строки, а второй – номер столбца. Элемент, расположенный в ij -клетке, называют ij -элементом.

Матрица обозначается одной буквой (часто буквы, обозначающие матриц, набирают жирным шрифтом или снабжают какими-либо дополнительными символами). Однако независимо от принятого способа обозначения матрица всегда является совокупностью таблично упорядоченных элементов. Две матрицы равны, если и только если равны их соответствующие элементы, т.е. А = В при условии aij = bij (i = 1, 2, ... , n). Ясно, что сравнивать можно только матрицы одного и того же размера, между элементами которых определено отношение равенства.

Матрицы, элементами которых являются вещественные или комплексные числа, называют соответственно вещественными или комплексными. Пусть А — комплексная (m × n)-матрица с элементами aij = αij + iβij. Матрица A̅ того же размера с элементами a*ij = αij + iβij называется комплексно-сопряженной с А.

Часто для упрощения нулевые элементы в таблицу не записывают, но при этом имеют в виду, что пустые клетки тоже содержат числа (нули).

Кроме приведенной выше клеточной записи, используют и другие способы представления матриц, например:

Матрицы впервые появились в середине прошлого столетия в работах английских математиков А. Кэли и У. Гамильтона. Представление совокупностей элементов в виде матриц и разработанные правила операций над ними оказались весьма плодотворными в математике и нашли широкое применение в физике, технике, экономике. Существенный вклад в разработку общей теории матриц и ее приложений внесли советские математики И. А. Лаппо-Данилевский, А. Н. Крылов, Ф. Р. Гантмахер, М. Г. Крейн.

2. Типы матриц. Матрица может иметь любое количество строк и столбцов (конечное или бесконечное). В дальнейшем при отсутствии оговорок будут рассматриваться конечные матрицы с числовыми элементами.

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

- 30 -

Столбцевую и строчную матрицы называют также векторами и сокращенно обозначают как x = (x1, x2, ..., xn) y = (y1, y1, ..., y1). Обычно из контекста ясно, идет ли речь о векторе-столбце или о векторе-строке. В противном случае используют приведенные выше обозначения.

Матрица, количество строк и столбцов которой одинаково и равно n, называется квадратной матрицей порядка n. Совокупность ii-клеток (i = 1, 2, ..., n) образуют главную диагональ квадратной матрицы. Матрица, все элемента которой вне главной диагонали равны нулю, т.е.

называется диагональной и более кратко записывается D = diag(d1, d2, ..., dn). Если в диагональной матрице d1 = d2 = ...= dn = 1, то имеем единичную матрицу n-го порядка

- 31 -

которая часто обозначается также через 1n или просто цифрой 1 (не следует принимать это обозначение за число, равное единице).

Матрица, все элементы которой равны нулю, называется нулевой и обозначается цифрой 0. Заметим, что нулевая матрица может иметь любой размер m × n, в то время как единичная матрица всегда квадратная. Матрица, состоящая только из одного элемента, обычно отождествляется с этим элементом.

Квадратная матрица зазывается верхней (нижней) треугольной, если равны нулю все элементы, расположенные под (над) главной диагональю:

Диагональная матрица является частным случаем как верхней (А), так и нижней (В) треугольных матриц.

3. Сложение матриц. Сумма двух матриц А и В одинаковых размеров определяется как матрица С тех же размеров, каждый элемент которой равен сумме соответствующих элементов матриц, т.е. C = A +B, если cij = aij + bij. Пример:

Из приведенного определения следует, что операция сложения матриц коммутативна, т.е. А+В = В+А, и ассоциативна, т.е. (А+В)+С = А+(В+С). Она естественным образом распространяется на любое число слагаемых. Очевидно также, что матрица А не изменяется при суммировании ее с нулевой матрицей тех же размеров, т.е. А + 0 = А.

4. Умножение матрицы на число. По определению произведением матрицы А на число α (в отличие от матриц и векторов, числа часто называют скалярами) является матрица С = αА, элементы которой получаются умножением соответствующих элементов матрицы А на это число α, т.е. cij = αaij. Пример:

- 32 -

Очевидно, справедливы следующие соотношения: α(A + B) = αA +αB; (α + β)A = αA + βA; (αβ)A = α(βA), где A и B — матрицы одинакового размера; α и β — числа (скаляры). Общий множитель элементов можно выносить за знак матрицы, считая его скалярным множителем.

Разность двух матриц одинаковых размеров сводится к уже рассмотренным операциям соотношением A — B = A + (-I)B, т.е. C = A — B, если cij = aij — bij.

5. Умножение матриц. По многим соображениям целесообразно определить эту операцию следующим образом: Произведением матрицы A размера (m × n) на матрицу B размера (n × r) является матрица C = AB размера (m × r), элемент cij которой, расположенный в ij-клетке, равен сумме произведений элементов i-й строки матрица A на соответствующие элементы j-го столбца матрицы B, т.е.

Умножение А на В допустимо (произведение АВ существует) если число столбцов А равно числу строк В ( в таких случаях говорят, что эти две матрицы согласуются по форме). Пример:

- 33 -

Для матриц A (m × n) и B(n × m) существует как произведение АВ размера m × m, так и произведение BA размера n × n. Ясно, что при m × n эти произведения не могут быть равными уже вследствие различных размеров результирующих матриц. Но даже при m = n, т.е. в случае квадратных матриц одинакового порядка, произведения АВ и ВА не обязательно равны между собой. Например, для матриц

имеем:

Отсюда следует, что вообще операция умножения матриц не подчиняется коммутативному закону (AB ≠ BA). Если же выполняется соотношение AB = BA, то матрицы А и В называю коммутирующими или перестановочными. Ассоциативный и дистрибутивный законы для матричного умножения выполняются во всех случаях, когда размеры матриц допускают соответствующие операции: (AB)C = A(BC) = ABC (ассоциативностью), A(B + C) = AB + AC и (A +B)C = AC +BC (дистрибутивность умножения слева и справа относительно сложения).

Умножение (m × n) — матрицы А на единичную матрицу m-го порядка слева и на единичную матрицу n-го порядка справа не изменяет этой матрицы, т.е. EmA = AEn = A. Если хотя бы одна из матриц произведения АВ является нулевой, то в результате получим нулевую матрицу.

Отметим, что из АВ = 0 не обязательно следует, что А = 0 или В = 0. В этом можно убедиться на следующем примере:

6. Транспонирование матрицы. Преобразование матрицы А, состоящее в замене строк столбцами ( или столбцов строками) при

- 34 -

сохранении их нумерации, называется транспонированием. Полученная в результате такого преобразования матрица называется транспонированной к матрице А и обозначается At или A':

Произвольная (m × n) — матрица при транспонировании становится ( n × m ) - матрицей, а элемент aij занимает ji — клетку, т.е. aij = atji.

Если матрица (квадратная) совпадает со своей транспонированной, т.е. A = At, то она называется симметричной и ее элементы связаны соотношением aij = aji (симметрия относительно главной диагонали). Матрица, для которой A = -At, называется кососимметричной, и ее элементы связаны соотношением aij = -aji . Она, как и симметричная матрица, всегда квадратная, но диагональные элементы равны нулю, т.е. aii = 0 (i = 1, 2, ..., n). Ниже приведены примеры симметричной и кососимметричной матриц:

Ясно, что не все элементы таких матриц могут быть выбраны произвольно. Можно убедиться, что из n2 элементов для симметричной матрицы независимыми могут быть только 1/2 n (n + 1), а для кососимметричной -1/2 n (n + 1) элементов.

- 35 -

Комплексно-сопряженная и транспонированная матрица (A)t называется сопряженной с А и обозначается A*. Матрица, равная своей сопряженной, т.е. A = (A̅)t = A*, называется эрмитовой. Если A = -(A̅)t, то А — косоэрмитова матрица.

Легко показать, что транспонирование произведения АВ равно произведению транспонированных матриц, взятых в обратном порядке: (AB)t = BtAt. Дважды транспонированная матрица равна исходной, т.е. (At)t = A.

7. Матричная запись системы линейных уравнений. Первоначально матрицы были введены для упрощения записи систем линейных уравнений, что и обусловило и определение основных матричных операций. Система линейных уравнений:

записывается одним матричным равенством

Действительно, перемножив в правой части равенства ( m × n ) - матрицу на столбцевую матрицу, получим

- 36 -

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

то матричное равенство запишется еще короче

y = Ax.

Такое представление системы линейных уравнений оказалось возможным благодаря правилу умножения матиц, которое наилучшим образом подходит для этой цели. Однако исторически дело обстояло как раз наоборот: правила действий над матрицами определялись, прежде всего, исходя из удобства представлений систем линейных уравнений.

8. Линейные преобразования. Систему уравнений, записанную в начале предыдущего пункта, можно рассматривать как линейное преобразование совокупности величин x1, x2, ..., xn в совокупность y1, y2, ..., ym. Это преобразование полностью определяется коэффициентами aij (i = 1, 2, ..., m; j = 1, 2, ..., n). На языке матриц линейное преобразование y = Ax означает преобразование столбца х в столбец у, которое определяется матрицей преобразования А.

Пусть величины x1, x2, ..., xn получаются из некоторой совокупности величин z1, z2, ..., zn посредством линейного преобразования x = Bz, где x и z — столбцы соответствующих величин; В — матрица их преобразования. Тогда формальной подстановкой х в первое матричное уравнение получаем

y = Ax = A(Bz) = (AB)z = Cz,

где C = AB — матрица преобразования величин z и y. К этому же результату можно прийти путем подстановки значений x1, x2, ..., xn из второй системы уравнений в первую с учетом введенного ранее правила умножения прямоугольных матиц.

9. Обратная матрица. В обычной алгебре два числа, произведение которых равно единице, называют взаимно обратными. Число, обратное числу a обозначают через a-1 и по определению aa-1 = 1

- 37 -

Аналогично в матричной алгебре две квадратные матрицы, произведение которых равно единичной матрице, т.е. AA-1 = A-1A = 1, называют взаимно обратными ( A-1 обратна A). Однако дальше этого аналогия не проходит.

Выражение a-1b, где a и b — числа, можно представить как частное от деления b на a, но для матриц такое представление не имеет смысла и в общем случае A-1B ≠ BA-1. Поэтому вместо операции деления В на А различают левое частное A-1B и правое частное BA-1, которые сводятся к умножению слева или справа на обратную матрицу A-1.

Способ обращения матрицы проще всего установить, рассматривая решение системы n линейных уравнений с n неизвестными:

В матричной форме эта система уравнений запишется как Ax = q, где А — квадратная матрица n-го порядка, называемая матрицей системы: x и q — столбцевые матрицы неизвестных переменных и свободных членов:

Матричное уравнение Ax = q решается умножением обеих его частей слева на обратную матрицу A-1 т.е. A-1Ax = A-1q в результате получаем x = A-1q.

В соответствии с правилом Крамера неизвестные xk(k = 1, 2, ..., n) определяются соотношением:

где Δ — определитель системы уравнений Δsk — алгебраические дополнения.

- 38 -

Определитель Δ представляет собой числовую функцию, которая вычисляется по определенным правилам на основании квадратной таблицы, состоящей из коэффициентов системы уравнений

Табличное представление определителя Δ по форме совпадает с матрицей системы уравнений, т.е. состоит из тех же элементов и в том же порядке, что и матрица А. В таких случаях его называют определителем матрицы А и записывают Δ = detA.

Алгебраическое дополнение Δsk вычисляется как определитель матрицы, полученной удалением из матицы A s-й строки и k-го столбца, причем этот определитель умножается еще на (-1)s+k. Величину Δsk называют также алгебраическим дополнением элемента ask матрицы A. Часто определитель матрицы А обозначается через |A|, а алгебраическое дополнение — через Ask.

Записав для всех элементов столбцевой матрицы x выражения по правилам Крамера, получим решение системы уравнений в виде:

- 39 -

откуда, сравнивая с A-1q, имеем

Из полученного выражения следует правило определения обратной матрицы: 1) элементы aij данной матрицы A n-го порядка заменяются их алгебраическими дополнениями Δij: 2) матрица алгебраических дополнений транспонируется, в результате чего получаем присоединенную или взаимную матрицу к А ( она обозначается через AdjA); 3) вычисляется определитель Δ матрицы А и присоединенная матрица AdjA умножается на величину, обратную этому определителю.

Обратная матрица существует для матрицы А при условии, что detA ≠ 0. Такие матрицы называются неособенными, в отличие от особенных (вырожденных), определитель которых равен нулю. Ниже вычисление обратной матрицы иллюстрируется примером:

- 40 -

Матрица, обратная произведению двух матриц, равна переставленному произведению матриц, обратных исходным, т.е. (AB)-1 = B-1A-1. Действительно, умножив обе части этого равенства на АВ, приходим тождеству E = B-1A-1(AB), так как B-1(A-1A)B = B-1EB = B-1B =E, где E — единичная матрица n-го порядка.

10. Блочные матрицы. Часто матрицу удобно разбить вертикальными и горизонтальными линиями на блоки которые являются матрицами меньших размеров и при выполнении операций рассматриваются как элементы исходных матриц. Операции над блочными матрицами выполняются по сформулированным выше правилам при условии, что эти операции допускаются размерами соответствующих матриц.

Пусть, например, матрицы А и В разбиты на блоки (жирными линиями) так, чтобы для соответствующих блоков имела смысл операция умножения, т.е.

По правилу умножения прямоугольных матриц можно записать:

Вычислим блоки C11 и C21 матрицы C:

- 41 -

В результате имеем

Конечно, тот же результат получается и при непосредственном перемножении матриц. Но разбиение на блоки позволяет оперировать с матрицами меньших размеров ( это бывает необходимо, например, когда не хватает места на бумаге или ячеек оперативной памяти машины) и особенно удобно, если можно выделить нулевые блоки.

Задачи и упражнения.

1. Любая матрица является прямоугольной таблицей. Справедливо ли обратное утверждение, т.е. можно ли считать всякую прямоугольную таблицу матрицей? Если нет,то какие дополнительные требования выдвигаются с позиций матричной алгебры?

2. Какие из приведенных ниже совокупностей объектов представляют собой матрицы:

3. Укажите, какие из приведенных ниже матриц являются равными между собой (при x=2)%

4. При каком значении x матрицы А и В равны:

5. Найти сумму А + В и разность А — В матриц:

6. Найти произведения АВ и ВА и сравнить полученные результаты для матриц:

- 42 -

7. Проверить дистрибутивность умножения слева А(В + С) = АВ + АС и справа (А + В)С = АС + ВС относительно сложения для следующих матриц:

8. Найти все матрицы, перестановочные с матрицей

9. Каким условиям в общем случае должны удовлетворять элементы квадратных матиц А и В второго порядка, чтобы они были перестановочными (АВ = ВА)? Как выглядят эти условия для случая, когда А симметричная матрица?

10. При каких условиях справедливы матричные соотношения:

(A + B)2 = A2 + 2AB +B2; (A-B)(A+B) = A2 — B2?

11. Каким условиям должны удовлетворять элементы ненулевых квадратных матриц А и В, чтобы АВ = 0?

12. К каким типам относятся матрицы:

13. Построить транспонированную At, комплексно-сопряженную A̅ и сопряженную А* для матрицы

14. Показать, что матрица

является эрмитовой. Что можно сказать о диагональных элементах любой эрмитовой матрицы?

15. Какого типа должна быть квадратная матрица А, чтобы она была перестановочной с диагональной матрицей D того же порядка, т.е. чтобы AD = DA?

16. К какому типу относятся треугольные матрицы, если они кроме того: а) симметричные, б) кососимметричные?

17. Показать, что (A̅B̅) = A̅ B̅ и (AB)* = B* A*.

18. Проверить соотношение (AB)* = B*A* для матриц задачи 6в.

19. Показать, что произведение AAt существует для любой матрицы А и является симметричной матрицей.

- 43 -

20. Для заданных матриц найти обратные и проверить соотношение AA-1 = 1:

21. Найти матрицы, обратные заданным, и проверить соотношение (AB)-1 = B-1A-1:

22. Дана система уравнений:

Записать эту систему в матричной форме Ax = q, вычислить обратную матрицу А-1 и записать решение системы.

23. Зависимости между токами и напряжениями четырехполюсника (рис. 6, а) можно представить одной из систем уравнений:

Рис. 6. Соединение четырехполюсника: а — четырехполюсник; б — последовательное соединение; в — параллельное соединение.

а) Записать эти уравнения в матричной форме и установить зависимости между элементами матриц:

б) Показать, что матрица А последовательного соединения четырехполюсников (рис 6. б) равна произведению их матриц A' и A'', т.е. A = A' A'' (в порядке следования).

в) Показать, что матрица Y параллельного соединения четырехполюсников (рис. 6, в) равна сумме их матриц Y' и Y'', т.е. Y = Y' + Y''.

- 44 -

24. Выполнить умножение матриц, воспользовавшись разбиением их на блоки:

Проверить результат непосредственным умножением матриц.

4. Графы

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

В подобных случаях удобно рассматриваемые объекты изображать точками, называемыми вершинами, а связи между ними - линиями (произвольной конфигурации), называемыми ребрами. Множество вершин V, связи между которыми определены множеством ребер Е, называют графом и обозначают 0 = (V, Е).

Первая работа по графам была опубликована двадцатилетним Леонардом Эйлером в 1736 г., когда он работал в Российской Академии наук. Она содержала решение задачи о кенигсбергских мостах

Рис. 7. К задаче о кенигсбергских мостах:

а — план города; б — граф.

(рис. 7, а): можно ли совершить прогулку таким образом, чтобы выйдя из любого места города, вернуться в него, пройдя в точности один раз по каждому мосту? Ясно, что по условию задачи не имеет значения, как проходит путь по частям суши а, b, с, d, на которых расположен г. Кенигсберг (ныне Калининград), поэтому их можно представить вершинами. А так как связи между этими частями осуществляются только через семь мостов, то каждый из них изображается ребром, соединяющим соответствующие вершины. В результате

- 45 -

получаем граф, изображенный на рис. 7, б. Эйлер дал отрицательный ответ на поставленный вопрос. Более того, он доказал, что подобный маршрут имеется только для такого графа, каждая из вершин которого связана с четным числом ребер.

С тех пор поток задач с применением графов нарастал подобно снежной лавине. Наряду с многочисленными головоломками и игграми на графах, рассматривались важные практические проблемы, многие из которых требовали тонких математических методов. Уже в середине прошлого века Кирхгоф применил графы для анализа электрических цепей, а Кэли исследовал важный класс графов для выявления и перечисления изомеров насыщенных углеводородов.

Однако теория графов как математическая дисциплина сформировалась только к середине тридцатых годов нашего столетия благодаря работам многих исследователей, наибольшая заслуга среди которых принадлежит Д. Кенигу. Значительный вклад в теорию графов внесли советские ученые Л. С. Понтрягин, А. А. Зыкоз, В. Г. Визинг и др.

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

2. Ориентированные графы.Часто связи между объектами характеризуются вполне определенной ориентацией. Например, на некоторых улицах допускается только одностороннее автомобильное движение, в соединительных проводах электрической цепи задаются положительные направления токов, отношения между людьми могут определяться подчиненностью или старшинством. Ориентированные связи характеризуют переход системы из одного состояния в другое, результаты встреч между командами в спортивных состязаниях, различные отношения между числами (неравенство, делимость).

Для указания направления связи между вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное таким образом ребро называют дугой, а граф с ориентированными

- 46 -

ребрами - ориентированным графом или короче орграфом (рис. 8, а).

Если пара вершин соединяется двумя или большим числом дуг, то такие дуги называют параллельными. При этом две дуги, одинаково направленные по отношению к данной вершине, называют строго параллельными, а различно направленные — нестрого параллельными. Ясно, что нестрого параллельные дуги, отображающие ориентацию связи в обоих направлениях, по существу равноценны неориентированной связи и могут быть заменены ребром. Произведя такую замену в орграфе, придем к смешанному графу, который содержит ребра н дуги (рис. 8, б). Обратно, любой неориентированный или смешанный граф можно преобразовать в ориентированный заменой каждого ребра парой нестрого параллельных дуг.

Рис. 8. Ориентированный (а) и смешанный(б) графы.

Изменив направления всех дуг орграфа на противоположные, получаем орграф, обратный исходному. Если направления дуг орграфа не учитываются и каждая дуга рассматривается как неориентированное ребро, то он называется соотнесенным (неориентированным) графом.

3. Взвешенные графы. Дальнейшее обобщение отображения связей между объектами с помощью графов состоит в приписывании ребрам и дугам некоторых количественных значений, качественных признаков или характерных свойств, называемых весами.

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

Вес можно приписывать не только ребрам и дугам, но и вершинам. Например, вершины, соответствующие населенным пунктам на карте автомобильных дорог, могут характеризоваться количеством мест в кемпингах, пропускной способностью станций техобслуживания. Вообще, вес вершины означает любую характеристику соответствующего ей объекта (атомный вес элемента в структурной формуле, цвет изображаемого вершиной предмета, возраст человека и т. п.).

- 47 -

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

4. Типы конечных графов.Если множество вершин графа конечно, то он называется конечным графом. В математике рассматриваются и бесконечные графы, но мы заниматься ими не будем, так как в практических приложениях они встречаются редко. Конечный граф G = (V, E), содержащий р вершин и q ребер, называется (р, q)-графом.

Рис. 9. Типы графов:

а - псевдограф; б - полный граф (шестиугольник); в - двудольный граф (биграф).

Пусть V = { v1, v2, ..., vp } и E = { e1, e2, ..., eq } - соответственно множества вершин и ребер (р, q)-графа. Каждое ребро ek ∈ E соединяет пару вершин vi ∈ V являющихся его концами (граничными вершинами). Для ориентированного ребра (дуги) различают начальную вершину, из которой дуга исходит, и конечную вершину, в которую дуга заходит. Ребро, граничными вершинами которого является одна и та же вершина, называется петлей. Ребра с одинаковыми граничными вершинами являются параллельными и называются кратными. В общем случае граф может содержать и изолированные вершины, которые не являются концами ребер и не связаны ни между собой, ни с другими вершинами. Например, для (5, 6)-графа на рис. 9, а V={ v1, v2, v3, v4, v5 }; Е= {e1, e2, e3, e4, e5} ребра e2 и e3 параллельны, ребро e6 является петлей, а v4 - изолированная вершина.

- 48 -

Число ребер, связанных с вершиной vi (петля учитывается дважды), называют степенью вершины и обозначают через δ(vi) или deg (vi). Так, для графа на рис. 9, а δ(v1) =1, δ(v2) = 4 и т. д. Очевидно, степень изолированной вершины равна нулю δ(v4) = 0). Вершина степени единицы называется концевой или висячей вершиной ( δ(v1) =1). Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно. В орграфе различают положительные δ+(vi) и отрицательные δ-(vi) степени вершин, которые равны соответственно числу исходящих из vi и заходящих в vi дуг. Например, для вершины d орграфа (см. рис. 9, а) имеем δ+(d) = 2 и δ-(d) = 3. Очевидно, суммы положительных и отрицательных степеней всех вершин орграфа равны между собой и равны также числу всех дуг.

Граф без петель и кратных ребер называют простым или обыкновенным. Граф без петель, но с кратными ребрами называют мультиграфом. Наиболее общий случай графа, когда допускаются петли и кратные ребра, называют псевдографом. Так, граф на рис. 7,б - это мультиграф, а на рис. 9, а - псевдограф. Если граф не имеет ребер (Е = ∅), то все его вершины изолированы (V ≠ ∅), и он называется пустым или нульграфом. Простой граф, в котором любые две вершины соединены ребром, называется полным (на рис. 9, б приведен пример полного графа с шестью вершинами). Если множество вершин V простого графа допускает такое разбиение на два непересекающихся подмножества V1 и V2 (V1 ∩ V2 = ∅ ), что не существует ребер, соединяющих вершины одного и того же подмножества, то он называется двудольным или биграфом (рис. 9, в). Ориентированный граф считается простым, если он не имеет строго параллельных дуг и петель.

Граф, степени всех вершин которого одинаковы и равны r, называется однородным (регулярным) r-й степени. Полный граф с n вершинами всегда однородный степени n-1, а пустой граф-однородный степени 0. Граф третьей степени называют кубическим. Он обладает рядом интересных свойств и, в частности, всегда имеет четное число вершин.

5. Смежность.Две вершины vi и vi ∈ V графа G = (V, Е) называются смежными, если они являются граничными вершинами ребра ek ∈ E. Отношение смежности на множестве вершин графа можно определить, представив каждое ребро как пару смежных вершин, т. е. ek = (vi, vj) k = 1, 2, …, q. Для неориентированных графов такие пары неупорядочены, так что ek = (vi, vj) = (vj, vi) а для орграфов — упорядочены, причем и, vi и vj означают соответственно начальную и конечную вершины дуги ek. Петля при вершине vi , в обоих случаях представляется неупорядоченной парой (vj, vi). Ясно, что множество вершин V вместе с определенным на нем отношением смежности полностью определяет граф.

- 49 -

Граф можно представить также матрицей смежности. Строки и столбцы этой матрицы соответствуют вершинам графа, а ее (ij) - элемент равен числу кратных ребер, связывающих вершины vi и vj, (или направленных от вершины vi к вершине vj, для орграфа). Например, для графов, приведенных на рис. 8, а и 9, а, имеем соответственно следующие матрицы смежности:

Матрица смежности неориентированного графа всегда симметрична а орграфа - в общем случае несимметрична. Неориентированным ребрам соответствуют пары ненулевых элементов, симметричных относительно главной диагонали матрицы, дугам - ненулевые элементы матрицы, а петлям - ненулевые элементы главной диагонали. В столбцах и строках, соответствующих изолированным вершинам, все элементы равны нулю. Элементы матрицы простого графа равны 0 или 1, причем все элементы главной диагонали нулевые.

Для взвешенного графа, не содержащего кратных ребер, можно обобщить матрицу смежности так, что каждый ее ненулевой элемент равняется весу соответствующего ребра или дуги. Обратно, любая квадратная матрица n-го порядка может быть представлена орграфом с n вершинами, дуги которого соединяют смежные вершины и имеют веса, равные соответствующим элементам матрицы. Если матрица симметрична, то она представима неориентированным графом.

6. Инцидентность. Если вершина vi, является концом ребра ek то говорят, что они инцидентны: вершина vi инцидентна ребру ek и ребро ek, инцидентно вершине vi. В то время как смежность представляет собой отношение между однородными объектами (вершинами), инцидентность — это отношение между разнородными объектами (вершинами и ребрами). При рассмотрении орграфов различают положительную инцидентность (дуга исходит из вершины) и отрицательную инцидентность (дуга заходит в вершину).

Рассматривая инцидентность вершин и ребер (p и q) - графа, можно представить его матрицей инцидентности размера p × q, строки которой соответствуют вершинам, а столбы - ребрам. Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-элемент равен 1, если вершина vi, инцидентна ребру ei, и равен нулю, если vi, и ei, не инцидентны.

- 50 -

В случае орграфа ненулевой ij-элемент равен 1, если vi начальная вершина дуги ei, и равен - 1, если vi - конечная вершина дуги ei.

Например, матрица инцидентности графа, приведенного на Рис. 9, а, имеет вид:

Каждый столбец матрицы инцидентности содержит обязательно два единичных элемента (для орграфа эти элементы всегда имеют различные знаки и равны соответственно 1 и —1). Количество единиц в строке равно степени соответствующей вершины (для орграфа количество положительных единиц определяет положительную степень, а количество отрицательных единиц — отрицательную степень). Нулевая строка соответствует изолированной вершине, а нулевой столбец - петле.

Рис. 10. Изоморфные графы

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

7. Изоморфизм. На Рис. 10 изображены три графа, которые с геочетрической точки зрения совершенно различны (пересечение ребер, если оно не отмечено точкой, не является вершиной). Но по существу они различаются лишь начертанием, а отношения инцидентности (при соответствующем обозначении вершин и ребер) для них одинаковы. Графы, для которых сохраняется отношение инцидентности, называются изоморфными.

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

- 51 -

Если существенные свойства графа не связаны со способом его изображения на плоскости или нумерацией вершин и ребер, то изоморфные графы, как правило, не различают между собой.

8. Маршруты. Нередко задачи на графах требуют выделения различных маршрутов, обладающих определенными свойствами и характеристиками. Маршрут длины m определяется как последовательность т ребер графа (не обязательно различных) таких, что граничные вершины двух соседних ребер совпадают. Маршрут проходит и через все вершины, инцидентные входящим в него ребрам. Примерами маршрутов на графе Рис. 9, а могут служить последовательности ( e1, e3, e2, e3, e5 ), ( e5, e6, e4, e4). Первый маршрут проходит через последовательность вершин ( v1, v2, v3, v2, v3, v5 ) и соединяет вершины v1 и v5 a второй — через последовательность вершин ( v3, v5, v5, v2, v5 ) и соединяет вершины v3 и v5. Замкнутый маршрут приводит в ту же вершину, из которой он начался.

Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью. Замкнутая цепь называется циклом, а простая цепь - простым циклом. Так, на графе Рис. 9, а ( e2, e5, e6 ) - цепь, ( e1, e2, e5 ) -простая цепь, ( e2, e3, e4, e5 ) - цикл, ( e2, e4, e5 ) - простой цикл.

Цикл, который содержит все ребра графа, называется эйлеровым циклом (задача о кенигсбергских мостах сводится к выяснению существования такого цикла), а граф, в котором имеется такой цикл, называется эйлеровым графом. Простой цикл, который проходит через все вершины графа, называют гамильтоновым. Если критерий существования эйлерового цикла очень прост (необходимо, чтобы степени всех вершин были четными), то для гамильтоновых циклов никакого общего правила не найдено.

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

- 52 -

Понятия цепи и цикла применимы и к ориентированным графам. При этом направления дуг не учитываются, т. е. по существу вместо орграфа рассматривают неориентированный соотнесенный ему граф.

9. Части графа. Граф G' = (V', Е') является частью графа G = (V, Е), если V' ⊂ V и Е' ⊂ Е, т. е. граф содержит все вершины и ребра любой его части. Часть, которая, наряду с некоторым подмножеством ребер графа, содержит и все инцидентные им вершины, называется подграфом. Часть, которая наряду с некоторым подмножеством ребер графа, содержит все вершины графа (V’=V, Е' ⊂ Е), называется суграфом. Рассмотренные графы показаны на Рис. 11.

Рис. 11. Граф и его части:

а - граф; б - часть графа; в - подграф; г – суграф.

Исходный граф по отношению к его подграфу называют надграфом, а по отношению к суграфу - сверхграфом. Совокупность всех ребер графа, не принадлежащих его подграфу (вместе с инцидентными вершинами), образует дополнение подграфа. Говорят, что подграфы G' = (V', Е') и G" = (V", Е") разделены ребрами, если они не имеют общих ребер (Е' ∩ Е" =∅) и разделены вершинами, если у них нет общих вершин (V' ∩ V" =∅).

10. Связность. Две вершины графа называют связанными, если существует маршрут, соединяющий эти вершины. Граф, любая пара вершин которого связана, называют связным графом. Очевидно, в связном графе между любыми двумя вершинами существует простая цепь, так как из связывающего их маршрута всегда можно удалить циклический участок, проходящий через некоторую вершину более одного раза (Рис. 12, где маршрут между вершинами vi и vj, изображен жирными линиями).

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

- 53 -

Таким образом, несвязный граф представляет собой совокупность отдельных частей (подграфов), называемых компонентами. На Рис. 13 показан подграф, состоящий из трех компонент (изолированная вершина считается компонентой).

Часто отношение связности усложняется дополнительными условиями. Граф называют циклически связным, если любые две различные вершины содержатся в цикле (например, граф на Рис. 11, а циклически связный, а граф на Рис. 12 - нет, так как вершина и, не содержится ни в каком цикле с другими вершинами). Граф называют R - связным, если любая пара различных вершин связана, по крайней мере R цепями, которые не имеют общих вершин (кроме начальной и конечной). Так, граф на Рис. 11, а двусвязный, а на Рис. 12 - односвязный.

Рис. 12. Связный граф.

Рис. 13. Несвязный граф, состоящий из трех компонент (G1, G2, G3

Связность ориентированных графов определяется так же, как и для неориентированных (без учета направлений дуг). Специфичным для орграфа (или смешанного графа) является понятие сильной связности. Орграф называют сильно связным, если для любой пары его вершин vi и vj существует путь из vi в vj и из vj в vi , (например, граф на Рис. 8, а сильно связный). Граф, представляющий план города с односторонним движением по некоторым улицам, должен быть сильно связным, так как в противном случае нашлись бы вершины (площади и перекрестки), между которыми нельзя было бы проехать по городу без нарушения правил движения.

11. Разделимость. Связный граф может быть разделен на несвязные подграфы удалением из него некоторых вершин и ребер (при удалении вершин исключаются и все инцидентные им ребра, а при удалении ребер вершины сохраняются). Если существует такая вершина, удаление которой превращает связный граф (или компоненту несвязного графа) в несвязный, то она называется точкой сочленения (Рис. 14, а). Ребро с такими же свойствами называется мостом (Рис. 14, б). Ясно, что при наличии моста в графе имеется, по крайней мере, две точки сочленения.

- 54 -

Граф называется неразделимым, если он связный и не имеет точек сочленения (например, граф на Рис. 11, а неразделим). Граф, имеющий хотя бы одну точку сочленения, является разделимым и называется сепарабельным. Он разбивается на блоки, каждый из котооых представляет собой максимальный неразделимый подграф (на Рис. 14, в показаны блоки B1,B2,B3 графа Рис. 14, б).

Каждое ребро графа, как и каждая вершина (за исключением точек сочленения), принадлежат только одному из его блоков. Более того, только одному блоку принадлежит и каждый простой цикл. Отсюда следует, что совокупность блоков графа представляет собой разбиение множеств ребер и простых циклов на непересекающиеся подмножества.

Рис. 14. Разделимые графы:

а - с точкой сочленения; б - с мостом; в - блоки B1 - B3 графа с мостом

В ряде приложений теории графов блоки можно рассматривать как компоненты. Это обычно допустимо, когда связи блоков посредством точки сочленения несущественны или когда существенные свойства графа связаны только с его простыми циклами (контурами). В таких случаях можно рассматривать несвязный граф как связный разделимый граф, который образуется путем такого объединения компонент, чтобы каждая из них была блоком (это всегда можно сделать, объединив, например, по одной вершине каждого блока в точку сочленения). Подобные операции используются при рассмотрении графов электрических цепей.

12. Деревья и лес.Особый интерес представляют связные ациклические графы, называемые деревьями. Дерево на множестве р вершин всегда содержит q = р - 1 ребер, т. е. минимальное количество ребер, необходимое для того, чтобы граф был связным. Действительно, две вершины связываются одним ребром, и для связи каждой последующей вершины с предыдущими требуется ребро, следовательно, для связи р вершин необходимо и достаточно р - 1 ребер.

При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты, каждая из которой представляет собой также дерево или изолированную вершину. Несвязный граф, компоненты которого являются

- 55 -

деревьями, называется лесом (лес из к деревьев, содержащий р вершин, имеет в точностир - к ребер). Сказанное иллюстрируется на примере дерева (Рис. 15, а), которое превращается в циклический граф добавлением ребра (Рис. 15, б) и распадается на лес из двух деревьев T1 и T2 при удалении ребра е (Рис. 15, в).

Рис. 15. Дерево (а), образование цикла при введении дополнительного ребра (б) и лес, который образуется после удаления ребра е (в).

Обычно деревья считаются существенно различными, если они не изоморфны. На Рис. 16 показаны все возможные различные деревья с шестью вершинами. С увеличением числа вершин количество различных деревьев резко возрастает (например, при р = 20 их насчитывается около миллиона). Среди различных деревьев выделяются два важных частных случая: последовательное дерево, представляющее собой простую цепь, и звездное дерево, в котором одна из вершин (центр) смежна со всеми остальными вершинами.

Рис. 16. Существенно различные деревья с шестью вершинами.

Рис. 17. Прадерево с корнем v0.

Рассматриваются также деревья с ориентированными ребрами (дугами). Ориентированное дерево называется прадеревом с корнем v0 , если существует путь между вершиной v0 любой другой его вершиной (Рис. 17). Ясно, что прадерево имеет единственный корень.

До сих пор рассматривались деревья как минимальные связные графы на множестве р вершин. Важное значение имеет и другая точка зрения, когда деревья или лес являются частями некоторого графа, т. е. образуются из его ребер. Любая связная совокупность ребер, не содержащая контуров, вместе с инцидентными им вершинами образует дерево графа (Рис. 18, а). Если такое дерево является суграфом (содержит все вершины графа), то оно называется покрывающим деревом или остовом (Рис. 18, б). Так как петля

- 56 -

представляет собой простейший цикл, состоящий из единственного ребра, то она не может входить в состав любого дерева графа.

Ребра графа, которые принадлежат его дереву, называют ветвями. Если дерево покрывает граф, то множество ребер графа разбивается на два подмножества: подмножество ветвей и подмножество ребер дополнения дерева, называемых хордами. При этом связный (р, q) - граф содержит v = р - 1 ветвей и σ = q - р + 1 хорд. Если граф несвязный, то совокупность, остовов R его компонент образует покрывающий лес. В этом случае ν = р - R и σ = q - р + R.

Рис. 18. Дерево как часть графа (выделено жирными линиями):

а — дерево; б — остов (покрывающее дерево).

Деревья играют важную роль в различных прикладных задачах, когда, например, речь идет о связи каких-либо объектов минимальным числом каналов (линий связи, дорог, коммуникаций) с определенными свойствами. С помощью дерева определяется система координат при моделировании цепей и систем различной физической природы. Деревья используются в качестве моделей при рассмотрении иерархических систем объектов, структурных формул органических соединений и т. п.

13. Планарность. Граф называют плоским (планарным), если существует изоморфный ему граф (геометрическая реализация), который может быть изображен на плоскости без пересечения ребер. Например, хотя в одном из графов на Рис. 10 ребра пересекаются, изоморфные ему не имеют пересечений, следовательно, он плоский.

На Рис. 19 показаны два неплоских графа, играющие фундаментальную роль в теории планарности и называемые графами Понтрягина - Куратовского. Полный пятиугольник (Рис. 19,а) представляет собой простой неплоский графе минимальным числом вершин (полный графе четырьмя вершинами - плоский, а удаление из пятиугольника хотя бы одного ребра также превращает его в плоский граф). Двудольный граф (Рис. 19, б) является моделью известной задачи о трех домах и трех колодцах: можно ли проложить от домов к каждому колодцу дороги так, чтобы они не пересекались (враждующие соседи должны иметь возможность пользоваться всеми колодцами, но не хотят встречаться на дорогах).

- 57 -

Рис. 19. Графы Понтрягина - Куратовского:

а - полный пятиугольник; б — двудольный граф.

Свойства планарности не нарушаются, если некоторое ребро разбить на два введением новой вершины второй степени или заменить два ребра, инцидентные вершине второй степени, одним ребром, удалив эту вершину. Два графа называют гомеоморфными (изоморфными с точностью до вершин второй степени), если после удаления из них вершин второй степени и объединения инцидентных этим вершинам ребер, они оказываются изоморфными (Рис. 20). Очевидно, граф, гомеоморфный плоскому графу, также плоский.

Строго доказывается, что граф является плоским тогда и только тогда, когда он не содержит подграфа, гомеоморфного одному из графов Понтрягина - Куратовского.

Рис. 20. Гомеоморфные графы.

Планарность является существенным свойством графов, которые моделируют коммуникации и связи между объектами на плоскости (дороги между населенными пунктами, водопроводные и газопроводные сети, линии передач электроэнергии, межсоединения на печатных платах электронных устройств и кристаллах интегральных схем). Плоскими графами представляются различные карты, с которыми, в частности, связана известная проблема четырех красок: всегда ли можно раскрасить области, на которые плоский граф делит поверхность, так, чтобы никакие две смежные области не были окрашены в одинаковый цвет и чтобы при этом было использовано не более четырех цветов? Доказано, что для такой раскраски в любом случае достаточно пяти красок, но никто еще не привел примера, когда пять красок действительно необходимы. Проблема остается нерешенной, несмотря на огромные усилия многих выдающихся математиков, которые штурмуют ее более столетия.

14. Графы и отношения.Пусть на множестве Х задано бинарное отношение А. Ему соответствует ориентированный граф, вершины которого отображают элементы из X, а дуга (хi, xj), где (хi, xj ∈ X), существует тогда и только тогда, когда(хiАxj). Обратно, множество ориентированных дуг графа (без строго параллельных дуг), заданных упорядоченными парами (хi, xj), можно рассматривать как бинарное отношение на множестве X.

Если бинарное отношение хАy устанавливает связь между элементами х из множества Х и элементами у из множества Y (х ∈ X, у ∈ У), то граф такого отношения будет ориентированным биграфом.

Следует заметить, что в общем случае орграф представляет нечто большее, чем бинарное отношение. Любое бинарное отношение, определенное на некотором множестве, можно представить соответствующим орграфом, вершины которого соответствуют элементам этого множества. Однако орграф с параллельными дугами позволяет отражать более общие связи между объектами, чем бинарные отношения.

- 58 -

Задачи и упражнения

1. Какие части города (см. рис. 7) нужно соединить мостами, чтобы задача о кенигсбергских мостах имела положительное решение? Достаточно ли для этого одного дополнительного моста?

2. Постройте граф отношений между сотрудниками Вашего подразделения: а) xi связан по работе с xj; б) xi подчинен xj ( xj, xj ∈ X, где X — множество сотрудников подразделения). Охарактеризуйте полученные графы: что в них общего и чем они различаются? В каких случаях может получиться несвязный граф?

3. Постройте граф района, в котором Вы живете, отметив направления ребер для улиц с односторонним движением. Преобразуйте полученный граф в орграф. Можно ли проложить путь между любыми двумя вершинами, не нарушая установленных направлений движения и не выезжая за пределы района?

4. На графе, построенном в задаче 3, укажите (хотя бы приблизительно) расстояния между смежными вершинами. Найдите кратчайшие маршруты, соединяющие интересующие Вас вершины.

5. Существует ли эйлеров цикл для графа, построенного в задаче 3, и что он означает? Попытайтесь найти для этого графа гамильтонов цикл (если он существует).

6. Пометьте вершины и ребра графа (см. рис. 14, а) буквами или цифрами и выполните следующие упражнения:

а) Запишите все ребра как неупорядоченные пары вершин и отметьте кратные ребра и петли.

б) Определите степени всех вершин, а также суммы степеней всех вершин и всех нечетные вершин графа (что можно сказать об этих суммах?).

в) Является ли граф однородным (если нет, то добавлением ребер преобразуйте его в однородный)?

г) К какому типу относится рассматриваемый граф (простой, мультиграф, псевдограф)?

д) Запишите матрицу смежности графа.

7. Пометьте вершины и ребра орграфа (см. рис. 8, а) буквами или цифрами и выполните следующие упражнения:

а) Запишите все ребра как неупорядоченные пары вершин и отметьте параллельные ребра.

б) Определите положительные и отрицательные степени всех вершин и соответственно их суммы (что можно сказать об этих суммах?).

в) Запишите матрицу инцидентности графа.

8. Докажите, что кубический граф имеет четное число вершин. Обобщается ли свойство четности вершин на однородные графы высших степеней?

9. Постройте графы, соответствующие следующим матрицам смежности:

- 59 -

Охарактеризуйте полученные графы и запишите для них матрицы инцидентности.

10. Расположите на плоскости четыре вершины, как в графе на рис. 11, а, но обозначения вершин v2 и v3 взаимно переставьте. На множестве обозначенных таким образом вершин постройте граф, изоморфный исходному.

11. Выполните следующие упражнения с графом (см. рис. 11, а):

а) Найдите все ориентированные маршруты от вершины а к вершине е.

б) Найдите все пути и простые пути от вершины а к вершине е.

в) Определите все простые контуры графа.

13. В орграфе (см. рис. 8, а) измените направления дуг таким образом, чтобы он преобразовался в ациклический граф. Постарайтесь найти общее правило такого преобразования.

14. Для графа (см. рис. 12) простойте:

а) часть, состоящую из четырех вершин и пяти ребер;

б) суграф с четырьмя, пятью и шестью ребрами.

15. Два графа G' = (V', E') и G" = (V", E") называются непересекающимися, если V' ∩ V" = ∅ и E' ∩ E" = ∅. Постройте непересекающиеся подграфы графа рис. 12, содержащие по три вершины.

16. Постройте блоки, на которые разбивается сепарабельный граф (см. рис. 14, а).

17. Постройте все различные деревья с восьмью вершинами (их должно быть 23).

18. Постройте все покрывающие деверья и их дополнения для графа (см. рис. 11, а). Сколько имеется существенно различных деревьев?

19. Постройте покрывающий лес несвязанного графа (см. рис. 13).

20. Постройте все прадеревья оргарфа (см. рис. 8, а) с корнем в вершине d.

21. Рассматривая компоненты несвязанного графа (см. рис. 13) как блоки, постройте соответствующий сепарабельный граф. Сколько возможно различных вариантов (без учета изолированной вершины G2)?

22. Покажите, что приведенные на рис. 21 графы неплоские. Какое минимальное число ребер необходимо удалить из графа на рис. 21, а, чтобы он превратился в плоский? Сколько имеется различных способов такого превращения с точностью до изоморфизма?

23. Покажите, что графы на рис. 21, а и в гомеоморфные.

- 60 -

24. Докажите, что при удалении ребра граф остается связным тогда и только тогда, когда это ребро содержится в некотором цикле.

25. Докажите, что (p, p — k) — граф при k ≥ 2 всегда является несвязным и состоит не менее, чем из k компонент.

26. Изобразите все неизоморфные простые графы с пятью вершинами (изолированные вершины допускаются), содержащие три, пять восемь, девять и десять дуг (всего их должно быть 14).

27. Покажите, что число ребер полного графа равно 1/2 p(p — 1), где p — число его вершин.

28. Найдите общее выражение для числа ребер, при котором граф с p вершинами может быть несвязным.

29. Покажите, что любое дерево можно представить как двухдольный граф. Какие деревья являются полными двудольными графами?

Рис. 21. Неплоские графы.

30. Докажите: а) кубический граф имеет точку сочленения тогда и только тогда, когда он содержит мост; б) наименьшее число вершин в кубическом графе, имеющем мост, равно 10.

31. Постройте граф, изоморфный графу Понтрягина-Куратовского (см. рис. 19, б), в котором внешние ребра образуют шестиугольник. Рассматривая его как подграф полного шестиугольника, нарисуйте дополнение этого подграфа. Укажите характерные свойства полученного дополнения.

32. Покажите, что следующие свойства дерева Т равносильны:

а) Т связно и не содержит циклов;

б) Т не содержит циклов и имеет p — 1 ребер, где p — число вершин;

в) Т связно и имеет p — 1 ребер;

г) Т не содержит циклов, но добавление ребра между любыми двумя несмежными вершинами приводит к появлению цикла;

д) Т связно, но утрачивает это свойство при удалении любого ребра;

е) всякая пара вершин в Т соединена цепью и притом только одной.

5. Логика

1. Чем занимается математическая логика? Логика как искусство рассуждении зародилась в глубокой древности. Начало науки о законах и формах мышления связывают с именем Аристотеля. Прошло два тысячелетия, прежде чем Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал в прошлом столетии Джордж Буль и тем самым заложил основы математической (символической) логики.

- 61 -

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

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

В последние десятилетия логика находит все более широкое применение в технике при исследовании и разработке релейно-контактных схем, вычислительных машин, дискретных автоматов. Ее методы используются в теории преобразования и передачи информации, теории вероятностей и комбинаторном анализе. Математическая логика начинает внедряться в такие нематематические области, как экономика, биология, медицина, психология, языкознание, право. Интенсивно развиваются специальные разделы математической логики, призванные обслуживать конкретные области науки и техники.

Столь энергичный выход математической логики за пределы математики объясняется тем, что ее аппарат легко распространяется на объекты самой общей природы, лишь бы только они характеризовались конечным числом состояний.

Двузначная логика имеет дело с такими объектами, которые принимают одно из двух возможных значений (истинное или ложное высказывание, высокое или низкое напряжение, наличие или отсутствие заданного признака у объекта и т. п.). Объекты, которые могут принимать значения из конечного множества, содержащего больше двух элементов, называют многозначными. Они либо сводятся каким-нибудь способом к двузначным объектам, либо обслуживаются аппаратом многозначной логики.

Устоявшееся представление о математической логике как науке, изучающей законы мышления с применением аппарата математики, главным образом, для нужд самой математики, в современных условиях становится слишком узким. С расширением областей применения и дальнейшим развитием математической логики изменяется и взгляд на нее. Объектами математической логики являются любые дискретные конечные системы, а ее главная задача – структурное моделирование таких систем.

2. Булевы функции. Объекты с двумя возможными состояниями характеризуются булевыми переменными, которые способны принимать лишь два различных значения. Для обозначения этих двух значений обычно используются цифры 0 и 1 или буквы Л (ложно) и И (истинно).

- 62 -

Отношения между булевыми переменными представляются булевыми функциями, которые подобно числовым функциям могут зависеть от одной, двух и, вообще, n переменных (аргументов). Запись у = f(x1, x2, …,xN) означает , что у - функция аргументов x1, x2, …,xN. Важнейшая особенность булевых функций состоит в том, что они, как и их аргументы, принимают свои значения из двухэлементного множества {0,1}, или (И, Л}, т. е. характеризуются одним из двух возможных состояний.

Функции небольшого числа переменных можно задавать с помощью таблиц, подобных таблицам сложения и умножения одноразрядных чисел. Для этого нужно только указать значения функции для каждой комбинации значений ее аргументов. Основными в двузначной логике являются следующие три функции.

Отрицание - функция у = f(х), принимающая значения 1, когда х = 0, и значение 0, когда х = 1; она обозначается у = x̅ (читается «не х»).

Дизъюнкция — функция у = f(x1, x2), принимающая значение 0 тогда и только тогда, когда оба аргумента имеют значение 0; она обозначается у = x1 ∨ x2 (читается «у = x1 или x2»).

Конъюнкция—функция у = f(x1, x2), принимающая значение 1 тогда и только тогда, когда оба аргумента имеют значение 1; она обозначается у = x1 ∧ x2 («у = x1 и x2»).

Таблицы для этих функций имеют вид:

3. Логические операции и формулы.Булевы функции можно рассматривать как логические операции над величинами, принимающими два значения - 0 и 1. Отрицание - это одноместная операция, а дизъюнкция и конъюнкция — двухместные операции. При этом выражения x̅ , x1 ∨ x2, x1 ∧ x2 являются логическими формулами.

Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив x1 = a̅ и x2 = b ∧ c из x1 ∨ x2,имеем ( a̅ ) ∨ (b ∧ c).

- 63 -

Каждая формула определяет некоторую булеву функцию. Ее значение при различных значениях переменных определяется на основании таблиц функций, приведенных в (2). Так, при а = 0, b = 1 и с = 0 имеем:

x1 = a̅ = 0̅ =1, x2 = b ∧ с = 1 ∧ 0 = 0 и x1 ∨ x2 = a̅ ∨ (b ∨ c) = 1 ∨ 0 = 1. Аналогично получаем значения функции и при других комбинациях значений аргументов.

Две функции (как и определяющие их формулы) считаются равносильными,если при любых значениях аргументов эти функции (формулы) принимают одинаковые значения. Равносильные функции соединяются знаком равенства, например: (х ∧ у) ∨ z̅ = ( ) ∧ z или ((х ∨ x̅ ) ∧ у) ∨ (у ∨ х) == х ∨ у. Равносильность функций проверяется по таблицам основных операций, причем необходимо сравнить их значения для всех комбинаций значений переменных.

Множество всех булевых функций вместе с операциями отрицания, конъюнкции и дизъюнкции образует булеву алгебру.

На основе определения основных операций нетрудно убедиться в справедливости следующих тождеств (свойств) булевой алгебры:

коммутативность

х ∨ y = y ∨ х, х ∧ y = y ∧ х;

ассоциативность

х ∨ ( y ∨ z) = (х ∨ y) ∨ z, х ∧ ( y ∧ z) = (х ∧ y) ∧ z;

дистрибутивность

х ∧ ( y ∨ z) = (х ∧ y) ∧ (х ∨ z), х ∨ ( y ∧ z) = (х ∧ y) ∧ (х ∨ z);

свойство констант

х ∨ 0 = x, х ∧ 1 = x;

свойство отрицания

х ∨ x̅ = 1, х ∧ x̅ = 0.

Приведенные свойства позволяют получить ряд других важных законов и тождеств уже без обращения к таблицам соответствия: (законы де Моргана), х ∨ (х ∧ у) = х ∧ (х ∨ у) = х (законы поглощения) х ∨ х = х ∧ х = х (законы идемпотентности), а также тождества x ∨ (x̅ ∧ y) = x ∨ y; (x ∧ y) ∨ (x ∧ z) ∨ (x ∧ z̅ ); = (x ∧ z) ∨ (y ∧ z̅ ); x̅ = x; 1̅ = 0;

0̅ = 1; x ∨ 1 =1; x ∧ 0 = 0 и т. д.

- 64 -

Так, законы идемпотентности доказываются следующими преобразованиями:

х ∨ х = (х ∨ х) ∧ 1 = (х ∨ х) ∧ (х ∨ x̅ ) = х ∨ (х ∧ (х ∨ х)) = х ∨ 0 = х;

х ∧ х = (х ∧ х) ∨ 0 = (х ∧ х) ∨ (х ∧ x̅ ) = х ∧ (х ∨ x̅ ) = х ∧ 1 = х.

Используя полученные соотношения, имеем:

х ∨ 1 = x ∨ ( x ∨ x̅ ) = (х ∨ х) ∨ x̅ = х ∨ x̅ = 1; x ∧ 0 = x ∧ ( x ∧ x̅ ) = x ∧ x̅ = 0.

Доказательство законов поглощения имеет вид:

x ∨ (x ∧ y) = (x ∧ 1) ∨ (x ∧ y) = x ∧ (1 ∧ y) = x ∧ 1 = x;

x ∧ (x ∨ y) = (x ∨ 0) ∧ (x ∨ y) = x ∨ (y ∧ 0) = x ∨ 0 = x.

Соотношение = х доказывается следующим образом:

из х ∨ x̅ = 1 по закону коммутативности следует x̅ ∨ x = 1, откуда сравнением с = 1 имеем х = .

Интересно доказательство закона де Моргана. На основании свойств отрицания равенство функций x̅ ̅∨̅ ̅y̅ и x̅ ∧ y̅ должно означать, что

(х ∨ у) ∨ ( x̅ ∧ y̅ ) = 1 и (х ∨ у) ∨ ( x̅ ∧ y̅ ) = 0.

Действительно,

(х ∨ у) ∨ ( x̅ ∧ y̅ ) = ((х ∨ у) ∨ x̅ ) ∧ ((х ∨ у) ∨ y̅ ) = (( x ∧ x̅ ) ∨ y ) ∧ (x ∨ (y ∨ y̅ )) =

= (1 ∨ y) ∧ (x ∨ 1) = 1 ∧ 1 = 1, а также

(х ∨ у) ∧ ( x̅ ∧ y̅ ) = (х ∧ ∨ ( x̅ ∧ y̅ ) = (у ∧ ( x̅ ∧ y̅ ) = ((x ∧ x̅ ) ∧ y̅ ) ∨ ((y ∧ y̅ ) ∧ x̅ ) =

= (0 ∧ y̅ ) ∨ ( x̅ ∧ 0) = 0 ∨ 0 = 0.

Следовательно, соотношение x̅ ̅∨̅ ̅y̅ = x̅ ∧ y̅ доказано. Аналогично доказывается и второй закон.

Упрощение записи формул.Операции дизъюнкции и конъюнкции удовлетворяют законам коммутативности и ассоциативности. Поэтому если переменные или формулы связаны только посредством одной из этих операций, то их можно выполнять в лгсбом порядке, а формулы записывать без скобок. Например:

((х1 ∨ x2) ∨ (х3 ∨ x4) ∨ х5 = х1 ∨ x2 ∨ х3 ∨ x4 ∨ х5,

а также (х1 ∧ x2) ∧ (x3 ∧ (х4 ∧ x5) = х1 ∧ x2 ∧ x3 ∧ х4 ∧ x5.

Если считать, что операция конъюнкции должна предшествовать операции дизъюнкции (конъюнкция связывает сильнее дизъюнкции), то можно опустить скобки, в которые заключены формулы со знаком конъюнкции. При наличии скобок в первую очередь должны выполняться операции внутри скобок, независимо от их старшинства. Обычно опускают также скобки, в которые заключены формулы со знаком отрицания.

Еще одно упрощение связано с символикой. Знак конъюнкции в формулах можно опустить и вместо х ∧ у писать ху. Операцию конъюнкции часто называют логическим умножением, а операцию дизъюнкции - логическим сложением.

С учетом приведенных условий запись существенно упрощается. Например, формуле (x ∧ (y ∧ z̅ )) ∨ (( x̅ ̅∨̅ ̅y̅ ) ∧ z) соответствует запись xyz̅ ∨ x̅ ̅∨̅ ̅y̅ z.

7. Переключательные схемы. В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей (х1 и x2). Ключи управляются кнопками с двумя состояниями: кнопка нажата (1) и кнопка отпущена (0). Если в исходном состоянии ключ разомкнут, то при нажатии кнопки он замыкается.

- 65 -

Ключ может быть сконструирован и так, что в исходном состоянии он замкнут, тогда нажатие кнопки означает его размыкание, т. е. приводит к противоположному результату. Поэтому нормально замкнутые ключи обозначим через x̅1 и x̅2.

При соответствующих состояниях кнопок лампочка принимает одно из двух состояний: горит (1) и не горит (0). Состояния кнопок отождествляются со значениями булевых переменных х1 и x2, а состояние лампочки — со значением функций этих переменных.

Рис. 22. Переключательные схемы, соответствующие операциям отрицания (а), дизъюнкции (б) и конъюнкции (в)

Операции отрицания соответствует схема с одним нормально замкнутым ключом (рис. 22, а). Если кнопка нажата (х = 1), ключ разомкнут и лампочка не горит, т. е. f(х) = 0; при отпущенной кнопке (х = 0) ключ замкнут и лампочка горит, т. е. f(x) = 1. Операциям дизъюнкции и конъюнкции соответствуют схемы с двумя нормально разомкнутыми ключами (рис. 22, б, в). Легко убедиться, что в схеме рис. 22, б лампочка горит при нажатии хотя бы одной из кнопок, а в схеме рис. 22, в - только при нажатии обеих кнопок одновременно.

Рис. 23. Переключательная схема, реализующая логическую функцию (а), и упрощенная схема(б).

Любую сложную булеву функцию можно представить некоторой переключательной схемой. На рис. 23,а показана схема, реализующая функцию у = х1 x̅2 ∨ x̅1 x2x3 ∨ x3x4. Та же функция представляется равносильной формулой у = х1 x̅2 ∨ ( x̅1 x2 ∨ x4)x3, которой соответствует другая более простая схема (рис. 23, б). Следует иметь в виду, что ключи, обозначенные одинаковыми буквами (х или x̅ ), связаны между собой и управляются общей кнопкой.

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

- 66 -

Существенными свойствами контактных схем являются исходные положения ключей (нормально разомкнуты или нормально замкнуты) и способ их соединения между собой и внешними устройствами. Эта информация полностью отображается графом, ребра которого соответствуют ключам, а вершины - точкам их соединения. Ребра нормально разомкнутых ключей обозначаются соответствующей переменной (х), а нормально замкнутых - отрицанием переменной (х). Например, контактная схема (рис. 23, б) изображается графом, как показано на рис. 24, а.

При изображении контактных схем графами принимаются некоторые специфические условия и упрощения. Обычно переменные обозначаются в разрывах линий, изображающих ребра.

Рис. 24. Граф переключательной схемы (а) и его упрощенное изображение (б).

При этом ребрами считаются только такие линии, которые обозначены какой-либо переменной или ее отрицанием. Другие линии, не являющиеся ребрами графа, могут изображать входы и выходы схемы, связи с другими схемами и т. п. Кроме того, вершины второй степени могут не изображаться, так как им инцидентны пары последовательно соединенных ребер, из которых каждое обозначено соответствующей переменной.

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

8. Высказывания.Пусть х1 и x2 - некоторые высказывания, которые могут быть истинными (1) или ложными (0), например: «Я пойду в театр» (х1) и «Я встречу друга» (x2). Дизъюнкцией х1 ∨ x2 является сложное высказывание «Я пойду в театр или встречу друга», а конъюнкцией х1 ∧ x2 - высказывание «Я пойду в театр и встречу друга».

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

Итак, высказывания можно рассматривать как двоичные переменные, а связки «не», «или», «и», с помощью которых образуются сложные высказывания, - как операции над этими переменными.

- 67 -

В алгебре высказываний используются еще две операции: импликация х1 → x2, соответствующая связке «если, то» и эквиваленция х1 ~ x2, соответствующая связке «если и только если». Они задаются следующими таблицами:

В нашем примере импликацией будет высказывание: «Если пойду в театр, то встречу друга», а эквиваленцией – пойду в театр, если и только если встречу друга». Как видно из таблиц, импликация высказываний ложна только в случае, когда первое из простых высказываний истинно, а второе ложно. Эквиваленция является истинным высказыванием, если оба простые высказывания истинны или ложны одновременно.

Обозначив буквами простые высказывания, можно представить сложное высказывание формулой с помощью соответствующих связок. Например, высказыванию «Если давление масла на шарик клапана больше усилия его пружины (х1), то масло открывает клапан (х2) и частично перетекает из нагнетательной полости во впускную (х3)» соответствует формула х1 → х2 х3.

9. Предикаты. Обычно высказывания выражают свойства одного или нескольких объектов. Содержательная часть высказывания играет роль определяющего свойства совокупности объектов, для которых это высказывание истинно, и называется предикатом. Например, высказывание «Иванов - отличник» истинно или ложно в зависимости от оценок, которые имеет данный студент. В то же время предикат «х - отличник» определяет подмножество отличников на некотором множестве студентов (группа, курс, факультет). Подставив вместо х фамилии студентов, получим множество высказываний. Совокупность истинных высказываний и будет соответствовать подмножеству отличников.

Предикат представляет собой логическую функцию Р(х), принимающую, как и булевы функции, значение 0 или 1, но в отличие от них, значения аргумента х выбираются из некоторого множества М объектов (х ∈ М). В общем случае такая функция может зависеть от многих аргументов х1, х2, . . .,хn, принимающих значения из одного и того же или различных множеств. Ее записывают Р(х1, х2, ...,хn) и называют n-местным предикатом. Например: «х - четное число», «х - компонент цепи» - одноместные предикаты Р(х);

- 68 -

«х брат у», «х меньше у» — двуместные предикаты Р(х, у); «х и у - родители z»,

«х - сумма y и z» - трехместные предикаты Р(х, y, z) и т. д. Если аргументы х1, х2, ... ,хn замещены конкретными значениями (объектами), то предикат переходит в высказывание, которое рассматривают как 0 - местный предикат.

Так как предикаты способны принимать только значения 0 и 1, то их, как и булевы переменные, можно связывать логическими операциями. В результате получаем формулы, определяющие более сложные предикаты. Так, если Р(х) означает «х - инженер», а Q(х) - «x - сотрудник нашего отдела», то Р(х) ∧ Q(х) = R(х) есть одноместный предикат «х - инженер и сотрудник нашего отдела» или проще «х - инженер нашего отдела». Очевидно, если Р - множество инженеров, а 0 - множество сотрудников данного отдела, то этот предикат соответствует пересечению Р ∩ Q. Таким образом, имеет место тесная связь между логикой предикатов и операциями над множествами.

10. Двоичная арифметика. В позиционной системе счисления с основанием m любое целое неотрицательное число a записывается последовательностью различных цифр x1x2 ... xn, что означает a = x1mn-1 + x2mn-2 + ... + xnm0. Десятичная система использует цифры 0, 1, ..., 9, например: 2907 = 2·103 + 9·102 + 0·101 + 7·100. Для двоичной системы счисления достаточно двух цифр, которые обозначаются 0 и 1. При этом последовательность x1x2 ... xn таких цифр является записью двоичного n-разрядного числа x1·2n-1 + x2·2n-2+ ... + xn·20.

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

Действительно, проверяя полученный результат, получаем 1·24 + 1·23 + 0·22 + 1·21 + 0·20 = 16 +8+2 = 26.

Дробное число переводится в двоичную систему счисления методом последовательного умножения на два. При этом каждый раз

- 69 -

после запятой двоичного числа записывается 0 или 1 соответственно целой части результата умножения. Последовательное умножение продолжается до тех пор, пока дробная часть не обратится в нуль или пока не получим требуемое количество двоичных знаков после запятой. Например, двоичное представление числа 0,3125 получается следующим образом:

Проверка полученного результата дает: 0·2-1 + 1·2-2 + 0·2-3 + 1·2-4 = 1/4 +1/16 = 5/16 = 0,3125.

Если число является смешанным, т.е. его целая и дробная части отличны от нуля, то оно переводится в двоичную систему раздельно: целая часть- последовательным делением, а дробная — последовательным умножением.

Арифметические операции над числами сводятся к операциям сложения и умножения одноразрядных чисел. В двоичной системе счисления умножение задается таблицей конъюнкции: 0·0=0; 1·0=0; 0·1=0 и 1·1=1. Сложение выполняется по правилу: 0 + 0 = 0; 1+0=1; 0+1=1 и 1+1=10 (10 — это двоичное число, соответствующее десятичному числу 2). Операции над двоичными числами выполняются по правилам, аналогичными для десятичных чисел, но эти правила предельно упрощаются (особенно для умножения). Например, десятичные операции 41 + 27 = 68 и 41·5= 205 выглядят следующим образом:

- 70 -

Как видно, умножение двоичных чисел сводится к сложению чисел, образованных сдвигом влево первого сомножителя. Поразрядное сложение осуществляется в соответствии с таблицей

причем в случае x1 = x2 = 1 образуется единица переноса в старший разряд. Операция, задаваемая этой таблицей, называется сложением по модулю 2. Если при сложении перенос не учитывается, то эта операция вместе с операцией умножения определяет на множестве двоичных чисел арифметику по модулю 2.

Задачи и упражнения

1. Подстановкой в формулу a ∨ b переменных запишите новые формулы и упростите их, если это возможно: а) a = x̅y, b = z. б) a = xy, b = xy̅; в) a = x, b = xy; г) a = x, b = x̅y; д) a = xy, b = c ∨ d, c = xz, d = yz̅.

2. Запишите таблицы соответствия для следующих формул: а) xx̅; б) xy ∨ x̅; в) (p ∨ q)(p̅ ∨ q̅); г) x̅∨̅y̅.

3. Проверьте с помощью таблиц соответствия следующие тождества: а) x̅∨̅y̅ = x̅ y̅; б) x ( x ∨ y) = x; в) x ∨ x̅ y = x ∨ y.

4. Постройте переключательные схемы для обеих частей приведенных ниже тождеств и убедитесь в том, что эти схемы функционируют одинаково:

а) xy∨x̅y∨x̅y̅=y ∨ x̅y̅

б) (x∨y)(x∨z) = x ∨ yz;

в) xyz∨xyz̅∨xy̅ = x.

5. Упростите следующие формулы:

а) x̅yz∨xy̅z̅∨xyz̅;

б) xy∨z∨x̅y̅∨̅z̅(zv∨x);

в) xy̅z̅∨xyz̅∨x̅yz∨xyz;

г) (x∨y)(x̅y̅∨z)∨z̅∨(x∨y)(u∨v).

6. Комитет, состоящий из трех членов, принимает решения большинством голосов. Постройте такую схему, чтобы голосование каждого члена комитета производилось нажатием своей кнопки и чтобы лампочка загоралась, если и только если решение принято. Какое наименьшее количество ключей необходимо?

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

- 71 -

8. Преобразуйте формулы к такому виду, чтобы операция отрицания применялась только к логическим переменным:

9. Убедитесь с помощью таблиц соответствия в справедливости выражений для импликации и эквиваленции:

а) x1→ x2 = x̅1∨x2;

б) x1 ∼ x2 = x1x2∨ x̅1x̅2 = (x1∨x̅2)(x̅1∨x2);

в) x1 ∼ x2 = ( x1→ x2 )( x2→ x1 ).

10. Постройте переключательные схемы для импликации и эквиваленции в соответствии с тождествами, приведенными в задаче 9.

11. Запишите формулу, соответствующую переключательной схеме рис. 25. Упростите эту формулу и постройте более простую схему.

Рис. 25. Граф переключательной схемы к задаче 11.

12. Постройте переключательные схемы по формулам:

а)(x1 ∨ x2x̅3)(x1x2 ∨ x3x4)

б) (x̅1 (x2 ∨ x̅3) ∨ x̅4)x1.

13. Из простых высказываний x1 - «испытания проведены» и x2 - «программа выполнена» образуйте сложные высказывания по формулам а) x1∨x̅2; б) x1x2; в) x1→ x2 ; г) x1 ∼ x2.

14. Запишите формулы для следующих высказываний, обозначив буквами входящие в них простые высказывания:

а) Давление падает и система не работает.

б) Вычисления выполнены точно или конструкция несовершенна.

в) Проект разработал Андрей или Петр, а эксперимента выполнил Иван.

г) Если будет хорошая погода, мы отправимся на стадион или пойдем за грибами.

д) Программа может быть выполнена, если и только если материалы поступят своевременно.

е) Если я поеду на автобусе, то опоздаю на работу или я воспользуюсь такси.

ж) Андрей помогает Петру или Петр помогает Андрею, или они помогают друг другу.

15. Запишите формулу, соответствующую высказыванию: «Программа будет выполнена тогда и только тогда, когда закончатся испытания и показатели будут удовлетворительны; если программа не будет выполнена, сотрудники не получат премию или будут пересмотрены технические условия».

16. Даны простые высказывания: x1 - «идет дождь), x2 - «очень жарко».

а) Запишите формулу сложного высказывания «Неверно, что идет дождь и очень жарко».

б) Преобразуйте формулу по закону де Моргана и составьте соответствующее высказывание.

в) Убедитесь в тожественности исходного и преобразованного высказываний.

17. Путешественник остановился у развилки дорог, ведущих в пункты А и В, и ему нужно выяснить, в какой именно пункт ведет каждая из дорог. Находившиеся у развилки два человека заявили, что они могут ответить только на один вопрос и что один из них всегда правдив, а другой лжец. Какой вопрос должен задать путешественник, чтобы в любом случае ответ на него содержал необходимою информацию?

а) Решите задачу путем непосредственных рассуждений без применения алгебры логики.

- 72 -

б) Представьте ситуацию в виде сложного высказывания, составленного из простых.

в) Запишите соответствующую формулу и таблицу соответствия.

г) По таблице соответствия сформулируйте искомый вопрос.

18. Высказывание является логически истинным, если соответствующая ему формула тождественно равна единице, и логически ложным, если формула равна нулю. Определите с помощью таблиц соответствия, каким высказываниям соответствуют приведенные ниже формулы (истинным, ложным или ни тем и не другим): а) p ∼ p; б) p → p̅; в)(p∨q) ∼ pq; г)(p→q̅) → (q → p̅); д)(p→ q)→ p; е) ((p→ q)→ p)→ p; ж) p̅∨̅q̅ ∼ pq .

19. При x1 = 1; x2 = 0; x3 = 0 и x4 = 1 найдите значения каждой из следующих функций:

20. Пусть X — множество сотрудников отдела и на этом множестве определены относительно переменной x ∈ X одноместные предикаты P(x), Q(x), R(x), означающие соответственно: x — занимается спортом, изучает иностранный язык, имеет изобретения. Расшифруйте предикаты, образованные с помощью следующих логических операций: а) P(x) ∨ Q(x); б) P(x) Q(x); в) P̅(x) Q(x); г) Q(x) ∼ P(x); д) P̅(x) ∼ (Q(x) ∨ R(x)).

21. Пусть V — множество вершин и E — множество ребер графа, причем ребро e ∈ E соединяет вершины x,y ∈V. Что означают предикаты P(x,y), Q(e, x, y), R(x,e)?

22. Каким десятичным числам соответствуют следующие двоичные числа: а) 1011; б) 1000110; в) 110100111?

23. Переведите в двоичную систему счисления десятичные числа: а) 51; б) 64; в) 125; г) 1000.

24. Выполните в двоичной системе следующие операции над десятичными числами: 21 + 37; 31 + 105; в) 25 · 8; г) (8 + 19) · 11; д) 24 · 8 — 17. Проверьте полученные результаты в десятичной системе.

25. Переведите в двоичную систему счисления с точностью до пяти двоичных знаков после запятой числа: а) 0,131; б) 0,25; в) 175,26.

26. Дайте обоснование правил перевода десятичных числе в двоичные.

27. Сложите двоичные числа 11001110 и 11010111 по обычному правилу и по модулю два. Найдите разность полученных результатов и объясните ее смысл.

6. Вероятности

1. Случайные события. Познание закономерностей объективного мира позволяет выявлять связи между событиями (или явлениями) и условиями, которые определяют их появление. Если можно указать комплекс условий, при каждой реализации которого событие неизбежно происходит, то это событие называется достоверным. Событие, которое заведомо не может произойти при реализации данного комплекса условий, называется невозможным. Очевидно,

- 73 -

невозможность события равносильна достоверности противоположного события.

Однако предсказать с полной определенностью наступление того или иного события удается далеко не всегда. Это связано с тем, что часто указываемый комплекс условий не отражает всей совокупности причинно-следственных связей между явлениями. Либо вызывающие данное событие причины еще недостаточно изучены, либо учет всей совокупности причин настолько сложен, что практически целесообразно ограничить комплекс условий наиболее существенными и поддающимися контролю. Возникающая при этом неопределенностью является признаком случайных событий.

Случайное событие относительно некоторого комплекса вполне определенных условий может произойти, а может и не произойти. Примеры случайных событий: перегорание лампочки через 1000 ч работы, попадание в цель при обстреле тремя снарядами, выпадание пяти очков при бросании игральной кости, победа киевского «Динамо» в предстоящем футбольном чемпионате и т.п.

2. Вероятность. Возможность появления случайного события А при реализации комплекса условий S оценивается количественной мерой, которая называется вероятностью и обозначается как P(A/S) или короче P(A). Обычно вероятность достоверного события принимается равной единице, а невозможного события нулю. Тогда для любого события 0 ≤ P(A) ≤ 1, а вероятность случайного события выражается положительным числом, меньшим единицы.

Интуитивно ясно, что событие тем более вероятно, чем чаще оно происходит в рассматриваемых условиях. Таким образом, вероятность P(A/S) непосредственно связана с частотой появления события А при многократном повторении комплекса условий S. С увеличением числа таких повторений, называемых испытаниями, частота все более точно характеризует значение вероятности.

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

Существует много различных подходов к определению вероятности, которые обычно сводятся к описанию практических приемов ее вычисления. Основные из них рассматриваются ниже.

3. Классическое (комбинаторное) определение. Если из общего числа n равно возможных и несовместных исходов (случаев) событию А благоприятствуют m исходов, то вероятность события А

Например, при подбрасывании монеты возможны два исхода — выпадение герба (Г) и цифры (Ц). Эти исходы можно считать равно

- 74 -

возможными (никакой из них не имеет преимущества перед другим) и несовместными (они не могут появиться вместе). Поэтому вероятность герба равна 1/2. Такая же вероятность и выпадания цифры. Полученный результат говорит о том, что при многократных подбрасываниях монеты примерно в половите случаев выпадает греб, причем этот результат тем ближе к действительности, чем больше число испытаний. При подбрасывании двух монет число всех исходов равно четырем {ГГ, ГЦ, ЦГ, ЦЦ}. Вероятность выпадения двух гербов (как и двух цифр) равна 1/4, но герб и цифра будут появляться с вероятностью 2/4 = 1/2, поскольку этому событию благоприятствую два исхода {ГЦ, ЦГ}.

В более сложных случаях для подсчета числа исходов используются комбинаторные методы. Пусть, например, известно, что в партии из r изделий имеется s бракованных. Найдем вероятность того, что из выбранных наугад v изделий w окажутся бракованными (событие А). Общее число исходов равно количеству сочетаний из r изделий по v, т.е. Crv. Благоприятствующие исходы соответствуют сочетаниям из w бракованных и v — w годных изделий. Так как w бракованных можно выбрать Csw различными способами, а v-w годных изделий можно выбрать Cr-sv-w способами, то число исходов, благоприятствующих событию А, будет CswCr-sv-w и следовательно,

Комбинаторное определение возникло в самом начале развития теории вероятностей в связи с изучением шансов в выигрыш в азартных играх. Оно удобно в тех случаях, когда заведомо применимо положение о равновозможности исходов наблюдений (подбрасывание монет и игральных костей, извлечение шаров из урны или карт из колоды, случайная выборка объектов из некоторой их совокупности при статистических исследованиях, распределения и взаимодействия физических частиц и т.п.). В то же время изложенных подход нельзя считать определением вероятности в строгом смысле, так как используемое в нем понятие равновозможности по существу означает равновероятность (вероятность определяется через равновероятность). Кроме того, он оказывается практически бесполезным, если неясно, какие исходы следует считать равновозможными.

4. Статистическое (частотное) определение. Статистический подход основан на регистрации появления события при многократных

- 75 -

наблюдениях в одинаковых условиях. Если событие А появляется в m исходах наблюдений из их общего числа n, то вероятность этого события

Разумеется, бесконечное число наблюдений n можно представить лишь теоретически, а на практике приходится довольствоваться конечным и часто весьма ограниченным числом наблюдений. Получаемое при этом значение для частоты события m/n называют статистической вероятностью. При небольшом числе наблюдений частота события может существенно отклоняться в различных сериях экспериментов, но с увеличением числа наблюдений она все более стабилизируется, сосредоточиваясь вблизи истинного значения вероятности. Так, никто не удивится, если при десятикратных бросаниях монеты герб выпадает 3, 7 или 8 раз. Но если бы при 1000 бросаний герб выпал 300, 700 или 800 раз, то это заставило бы полностью пересмотреть предположение о равновозможности выпаданий герба и цифры или искать какой-то скрытый изъян в проведении экспериментов (известны, например, следующие результаты выпадания герба в десяти сериях, каждая из которых состояла из 1000 подбрасываний монеты: 502, 511, 497, 529, 504, 476, 507, 528, 504, 529).

Статистические вероятности широко используют на практике. Например, при изучении большого числа данных установлено, что частота рождения девочек равна 0,482. Если известно, что из 10000 конденсаторов бракованных оказалось 116, то в аналогичных условиях следует ожидать появление негодного конденсатора с вероятностью 0,0116 или 1,16%.

5. Множество событий. Совокупность всех возможных исходов при данном комплексе условий образует множество элементарных событий. Любое событие рассматривается как подмножество этого основного множества (универсума).

Например, множество всех исходов при бросании двух игральных костей содержит 6·6 = 36 элементов. Каждый из них переставляет собой упорядоченную пару (a, b), где a и b — числа очков, выпавших соответственно при бросании первой и второй кости. Событию, заключающемуся в выпадании дубля, соответствует А (дубль) = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6) } а выпаданию в сумме меньше шести очков — подмножество В (меньше 6 очков) = {(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (3,1), (3,2), (4,1) }.

Выбор трех из пяти кандидатов {a, b, c, d, e} имеет C53 = 10 исходов, которые и образуют множество элементарных событий. Выбору кандидата a (среди трех кандидатов) соответствует событие

- 76 -

A (выбор a) = {(abc), (abd), (abe), (acd), (ace), (ade) }, выбору кандидатов b и d — событие B (выбор b и d) = {(abd), (bcd), (bde)}, выбору только одного из кандидатов b или d (но не обоих вместе) — событие С (выбору или b или d) = {(abc), (abe), (acd), (ade), (bce), (cde)}.

6. Несовместные события. События А и В называют несовместными, если соответствующие им подмножества не пересекаются, т.е. A∩B = ∅ (например, выпадение пр бросании двух игральных костей дубля и нечетного числа очков). Если из осуществления события А неизбежно следует событие В, то А является подмножеством В, т.е. A ⊂ B или A ∩ B = A (например, из выпадания дубля следует событие, заключающееся в выпадании четного числа очков). Подобные события всегда совместные.

Событие, заключающееся в реализации несовместных событий А или В, соответствует их объединению A ∪ B или дизъюнктивной сумме A + B и его вероятность равна сумме вероятностей P(A) и P(B), т.е.

P(A + B) = P(A) + P(B).

Действительно, если mA и mB — числа исходов, благоприятствующих событиям А и В, то появлению события А или В будет благоприятствовать mA + mB исходов из общего числа n исходов, поэтому

Этот вывод естественно обобщается на любое число несовместных событий, т.е.

P(A1 + A2 + ... + An) = P(A1) + P(A2) + ... + P(An).

Если объединение попарно несовместных событий составляет основное множество, то появление одного из них является достоверным событием, т.е. P(A1 ∪ A2 ∪ ... ∪ An) = P(A1 + A2 + ... + An) = 1. Говорят, что такие события образуют полную систему событий, а их вероятности удовлетворяют нормирующему условию

P(A1) + P(A2) + ... + P(An) = 1.

В частности, P(A ∪ A̅) = P(A) + P(A̅) = 1, откуда следует выражение для вероятности противоположного события

P(A̅) = 1 - P(A) .

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

- 77 -

очков (А), выпадение четырех или пяти очков (В) и выпадение больше пяти очков (С). Число благоприятствующих им элементарных событий mA = 3, mB = 7, и mC = 26, следовательно, имеем:

7. Независимые события. События А и В называются независимыми, если вероятность одного из них не зависит от исхода другого. Так, число выпавших очков при каждом бросании игральной кости не зависит от результатов предыдущих испытаний. Вероятность вынуть белый шар из урны, в которой находится белых и черных шаров, не зависит от цвета шара, вынутого в предыдущем испытании, если каждый раз он возвращается в урну. Однако если ранее вынутый шар не возвращается, то эта вероятность изменяется после каждого испытания и, следовательно, вероятность его исхода будет зависеть от предыдущего исхода. Пусть например, в урне находится 2 белых и 3 черных шара. Вероятность вынуть белый шар до испытания равна 2/5, а после него она становится 1/4, если был вынут белый шар, и 1/2, если был вынут черный шар.

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

P(A ∩ B) = P(A)P(B).

Это соотношение можно доказать на основе классического определения вероятности (3). Пусть P(A) = m1/n1 и P(B) = m2/n2. Если события А и В независимы, то при каждом из m1 исходов, благоприятствующих событию А, будет также m2 исходов, благоприятствующих событию В. Значит, число исходов, благоприятствующих свершению как события А, так и события В, будет m1 m2. Аналогично выводим, что общее число возможных исходов равно n1 n2. Поэтому

Для нескольких независимых событий формула принимает вид:

P(A1 ∩ A2 ∩ ... ∩ An ) = P(A1)P(A2)...P(An).

Пусть, например, устройство состоит из трех блоков, вероятности безотказной работы которых в течение времени t равны

- 78 -

соответственно P(A1) = 0,7; P(A2) = 0,8; P(A3) = 0,9. Отказ в работе хотя бы одного из блоков приводит к отказу всего устройства, причем отказы блоков происходят независимо. Тогда вероятность безотказной работы устройства P(A) = P(A1)P(A2)P(A3) = 0,7 · 0,8 · 0,9 = 0,504.

8. Условная вероятность. Если события А и В зависимы, то как указывалось в (7), после наступления одного из них, например А, вероятность другого будет отличаться от его вероятности P(B), вычисленной без учета наступления события А. Вероятность события В при условии, что уже произошло событие А, называют условной вероятностью и обозначают через PA(B) или P(B/A). Поэтому формула для вероятности одновременного наступления двух зависимых событий должна быть записана в виде:

P(A ∩ B) = P(A)PA(B).

Например, вероятность вынуть два белых шара из урны, в которой находятся 2 белых и 3 черных шара (предполагается, что вынутый шар не возвращается в урну) равна произведению вероятности вынуть белый шар первый раз (событие А) на вероятность вынуть белый шар второй раз (событие В) при условии, что первым был белый шар (произошло событие А)б т.е. P(A ∩ B) = 2/5 · 1/4 = 1/10. Если вынутый шар возвращается в урну, то А и В независимы и P(A ∩ B) = 2/5 · 2/5 = 4/25. Из приведенной выше формулы следует выражение

которое часто рассматривается как определение условной вероятности, если каким-либо способом определены P(A ∩ B) и P(A). Ясно, что для независимых событий PA(B) совпадает с P(B).

Вероятность одновременного наступления нескольких зависимых событий выражается формулой

P(A1, A2, ... , An) = P(A1)PA1 (A2)

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

Здесь - условная вероятность события Ai, вычисленная при условии, что произошли события A1, A2,..., Ai-1.

9. Объединение событий. Простая формула для вероятности появления одного из несовместных событий (6) нуждается в обобщении, если события совместны. Пусть из n равновозможных исходов событию А благоприятствуют mA исходов, а событию B — mB исходов. Так как множества совместных событий пересекаются, то сумма mA + mB, кроме исходов, благоприятствующих появлению

- 79 -

одного из событий А или В, дважды учитывает mAB исходов, благоприятствующих одновременному появлению А и В. Поэтому из общего числа исходов n появлению событий А или В (или обоих вместе) будут благоприятствовать mA + mB - mAB исходов, на основании чего имеем

Эта формула получена из каких-либо ограничений относительно характера событий А и В:

для зависимых событий

P(A ∪ B) = P(A) + P(B) -P(A)PA(B),

для независимых событий

P(A ∪ B) = P(A) + P(B) -P(A)(B).

10. Независимость и несовместность. При использовании приведенных соотношений необходимо четко понимать смысл таких свойств событий, как независимость и несовместностью. Условиями независимости событий можно рассматривать каждое из соотношений

P(A ∩ B) = P(A) + P(B); PA(B) = P(B)

Так, при бросании двух игральных костей вероятности событий А(дубль) и В(меньше 6 очков) равны соответственно P(A) = 6/36 = 1/6 и P(B) = 10/36 = 5/18. Одновременному появлению этих событий соответствует подмножество A ∩ B = {(1,1),(2,2)} и его вероятность P(A ∩ B) = 2/36=1/18. Так как P(A ∩ B) B≠ P(A)P(B), то рассматриваемые события являются зависимыми. С другой стороны, событие В при условии наступления события А определяется как подмножество {(1,1),(2,2)} основного множества {(1,1),(2,2), (3,3),(4,4}{(5,5),(6,6)}, и PA(B) = 2/6 = 1/3, т.е. не совпадает с P(B)= 5/18. По соответствующим формулам имеем:

P(A ∩ B) = P(A)PA(B) = 1/6 · 1/3 = 1/18;

P(A ∪ B) = P(A) + P(B) — P(A)PA(B) = 1/6 + 5/18 -1/6 · 1/3 = 7/18.

Очевидно, те же результаты получим, если пример В в качестве дополнительного условия для А. Так как множество {(1,1),(1,2),

- 80 -

(1,3),(1,4),(2,1),(2,2),(2,3),(3,1),(3,2),(4,1)}, соответствующее событию В, служит основным для события А, то

PB(A) = 2/10 = 1/5,

и следовательно получаем:

P(A ∩ B) = P(B)PB(A)= 5/18 · 1/5 = 1/18;

P(A ∪ B) = P*A) + P(B) — P(B)PB(A) = 1/6+5/18-5/18· 1/5=7/18.

Общее условие несовместности событий выражается как

P(A ∩ B) = 0,

что соответствует A ∩ B = ∅. Так, в рассматриваемом примере A ∩ B = {(1,1),(2,2)} ≠ ∅, следовательно, события А и В совместны.

Независимые события А и В при ненулевых вероятностях P(A) и P(B) всегда совместны. Действительно, из соотношения P(A ∩ B) = P(A)(B) имеем P(A ∩ B) ≠ 0, а значит и A ∩ B ≠ ∅, что свидетельствует о совместности независимых событий. Однако совместность событий не обязательно влечет их независимость. Из условия A ∩ B ≠ ∅ при P(A ∩ B) ≠ 0 следует лишь, что P(A ∩ B) ≠ 0 и условная вероятность PA(B) ≠ 0. Но может иметь место неравенство PA(B) = P(B), что означает зависимость рассматриваемых совместных событий.

Зависимые события А и В при ненулевых вероятностей P(A) и P(B) могут быть как совместными, так и несовместными. В первом случае A ∩ B ≠ ∅, и поэтому условные вероятности PA(B) и PB(A) не равна нулю, т.е. одно из событий может наступить при условии, что произошло другое событие. Во втором случае A ∩ B = ∅, следовательно, условные вероятности зависимых и несовместных событий PA(B) = PB(A) = 0. Это значит, что пир наступлении события А событие В произойти уже не может, а наступлении события В не может произойти событие А. В то же время из несовместности событий (A ∩ B = ∅) следует их зависимость, что выражается равенством нулю условных вероятностей PA(B) и PB(A). Иначе говоря, если события А и В несовместны, то при наступлении одного из них другое произойти не может, т.е. несовместные событие не могут быть независимыми.

Несовместность совокупности событий A1, A2, ..., An, следует из их попарной несовместимости, т.е. из условия

Ai ∩ Aj = ∅ (i,j = 1,2,..., n; i ≠ j).

- 81 -

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

P(Ai ∩ Aj) = P(Ai)P(Aj) (i,j = 1,2,..., n; i ≠ j),

должны выполняться также аналогичные условия для любых сочетаний по 3, 4, ... , n событий. Например, для трех событий условие полной независимости выражается системой соотношений:

P(A1 ∩ A2) = P(A1)P(A2);

P(A1 ∩ A3) = P(A1)P(A3);

P(A2 ∩ A3) = P(A2)P(A3);

P(A1 ∩ A2 ∩ A3) = P(A1)P(A2)P(A3).

Невыполнение хотя бы одного из этих соотношений свидетельствовало бы о том, что события A1, A2 и A3 в совокупности зависимы. На практике, однако, попарная независимость обычно влечет за собой и независимость в совокупности.

Задачи и упражнения

1. Какова вероятность угадать все шесть номеров (из 49) в спортлото?

2. Из урны, содержащей 8 белых и 12 черных шаров, вынимают один шар. Какова вероятность того, что он будет белым; что он будет черны?

3. Найдите на основе рассмотрения множества событий при бросании двух игральных костей (каждая кость имеет шесть равноправных граней, пронумерованных от 1 до 6) вероятность следующих событий:

а) на одной кости четыре очка, а на другой — меньше четырех;

б) на одной кости число очков вдвое больше, чем на другой;

в) сумма очков меньше пяти;

г) сумма очков больше восьми.

4. Какова вероятность открыть замок автоматической камеры хранения при случайном наборе цифр (замок открывается только при определенных значениях четырех десятичных цифр)?

5. Оцените вероятность того, что в группе из 23 студентов, по крайней мере, у двух студентов дни рождения совпадают.

6. Партия из 10 телевизоров принимается в магазине при условии, что случайно выбранные два из них окажутся исправными. Какова вероятность того, что магазин примет партию, содержащую 4 неисправных телевизора?

7. Два стрелка проводят по одному выстрелу, причем вероятности попадания в цель для них равны соответственно 0,8 и 0,9. Найдите вероятность поражения цели обоими стрелками и вероятность поражения цели хотя бы одни из них.

8. Исследуйте на независимость события А и В при следующих испытаниях:

а) из колоды в 52 карты выбирают одну: А - «туз»; В - «бубна»;

б) бросают две игральные кости: А - «одно очко на первой кости»; В - «четное число очков на второй кости»;

в) бросают три монеты: А - «выпало два герба»; В - «выпало три герба».

- 82 -

9. Исследуйте на несовместность события А и В при бросании игральной кости, если:

а) А - «четыре очка»; В - «четное число очков»;

б) А - «четное число очков»; В - «нечетное число очков».

10. Пять карточек, помеченные цифрами от 1 до 5, тщательно перетасовывают. Какова вероятность того, что:

а) трехзначное число, определяемое номерами трех извлеченных наугад карточек, окажется четным;

б) при случайной раскладке всех карт пять мест с номерами от 1 до 5 ни одна карточка не займет места, отмеченного ее номером;

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

11. Из 30 выстрелов по цели отмечено 25 попаданий. Найти относительную частоту попаданий в цель.

Данный текст я (w_cat) набираю руками, опечатки LibreOffice Writer, как положено, выделяет красной волнистой, но если «опечатанное» слово совпадает с существующим в словаре (базе) то опечатку я не замечу и не исправлю, вычислите вероятность такой ошибки :).

Список литературы

Великолепный обзор основных идей и методов современной математики дан в трехтомной монографии «Математика, ее содержание, методы и значение», написанной выдающимися советскими математиками и вышедшей в издательстве АН СССР в 1956 г. под редакцией академиков А.Д. Александрова, А.Н. Колмогорова и М.А Лаврентьева. Эта книга является, пожалуй, лучшим образцом сочетания глубины, строгости и доступности изложения. Можно только пожалеть, что изданная сравнительно небольшим тиражом она стала библиографической редкостью.

Аналогичным по содержанию, но более популярным и кратким является сборник статей видных американских ученых «Математика в современном мире» (М. «Мир», 1967). Обращают на себя внимание прекрасно выполненные иллюстрации, которые помогают уяснить смысл сложных математических понятий. Живо и доступно написана книга Дж. Кемени, Дж. Снелла и Дж. Томпсона «Введение в конечную математику» (М. Изд. иностр. лит., 1963), в которой изложение идей и методов современной математики переплетается с большим количеством примеров из жизни, техники, экономики, биологии. Большое удовольствие может доставить читателю увлекательная и остроумная книга У.У. Сойера «Прелюдия к математике» (М. «Просвещение», 1965), которая аннотирована автором как «рассказ о некоторых любопытных и удивительных областях математики с предварительным анализом математического склада ума и целей математики».

Интересна и полезна для инженеров книга французских математиков Р. Фора, А Кофмана и М. Дени-Папена «Современная математика» (М., «Мир», 1966). По словам акад. А.Н. Колмогорова, под редакцией которого издан перевод этой книги, особенно ценной в ней является «достаточно стройная и в то же время простая система основных понятий». Сами авторы представляют ее как справочник по современной математике. Специально на инженеров рассчитаны книга Т. Кармана и М Био «Математические методы в инженером деле» (М., Гостехиздат, 1946), коллективная работа под ред. Э.Ф. Беккенбаха «Современная математика для инженеров» (М., Изд. иностр. лит., 1958), А. Анго «Математика для электро- и радиоинженеров» (М., «Наука», 1965). Математические теории и методы в этих книгах рассматриваются в тесной связи с конкретными прикладными задачами.

Имеется много фундаментальных монографий, содержание которых выходит за пределы программы высших технических учебных заведений по математике, но весьма полезных для инженеров. Среди них, прежде всего, необходимо назвать вышедший многими изданиями пятитомный «Курс высшей математики» В.И. Смирнова. Следует также обратить внимание на

- 83 -

трехтомное пособие Г. Джеффриса и Б. Свирлс «Методы математической физики» (М., «Мир», 1969/70).

Из общих курсов прикладной математики можно указать: Я.Б. Зельдович, А.Д. Мышкис «Элементы прикладной математики» (М., «Наука», 1972); В.А. Иванов, Б.К Чемоданов, В.С. Медведев «Математические основы теории автоматического регулирования» (М., «Высшая школа», 1971); И.А. Большаков, Л.С. Гуткин, Б.Р. Левин, Р.Л. Стратонович «Математические основы современной радиоэлектроники» (М., «Советское радио», 1968); Г.Т. Марков, Е.Н. Васильев «Математические методы прикладной электродинамики» (М., «Советское радио», 1970); Ю.М. Коршунов «Математические основы кибернетики» (М., «Энергия», 1972); В.Г. Лапа «Математические основы кибернетики» (Киев, «Вища школа», 1971); Н. Бейли «Математика в биологии и медицине» (М., «Мир», 1970).

Вопросы математического образования инженеров в современных условиях обсуждаются в сборнике статей видных советских математиков «Математическое образование сегодня» (М., «Знание», 1974).

Среди справочников, пожалуй, наиболее близок к современным потребностям инженера «Справочник по математике для научных работников и инженеров» Г. Корна и Т. Корн (М., «Наука», 1968). Он широко охватывает материал классических и новых разделов математики, являющихся необходимым орудием для инженеров-исследователей. Много внимания уделяется связи рассматриваемых математических вопросов с прикладными задачами. Разумеется, не нуждаются в рекомендации «Справочник по высшей математике» М.Я. Выгодского и «Справочник по математике» И.Н. Бронштейна и К.А, Семендяева, выдержавшие по несколько изданий и широко используемые инженерами и учащимися.

Глава 2 Множества

Элементами множеств могут быть самые разнообразные предметы: буквы, атомы, числа, функции, точки, углы и т.д. Отсюда с самого начала ясна чрезвычайная широта теории множеств и ее приложимость к очень многим областям знания.

Н. Н. Лузин

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

Алгебраические операции над множествами и их свойства излагаются с применением кругов Эйлера и диаграмм Венна, а бинарные отношения иллюстрируются на матрицах и графах. Благодаря этому основные понятия теории множеств получают наглядное представление в привычной для инженера графической или табличной форме.

Центральное место в этой главе занимает теория отношений, которая оказалась простым и удобным аппаратом для самых разнообразных задач. На ее основе обобщается понятие функции, применимое не только к числовым множествам, но и к множествам объектов любой природы. Особо выделяются три типа бинарных отношений: эквивалентность, упорядоченность и толерантность, которые наиболее часто встречаются в практике.

Большое значение в математике имеют отношения, называемые законами композиции, которые ставят в соответствие паре каких-либо элементов третий элемент из одного и того же или из различных множеств. Определяя не некотором множестве один или два таких закона и наделяя их некоторыми свойствами, получаем различные алгебраические системы: группы, кольца, поля, тела и т.д. Эти и подобные им абстрактные понятия являются обобщениями самых разнообразных объектов исследования как в самой математике, так и в специальных областях науки и техники. В качестве примеров рассматриваются наиболее интересные с прикладной точки зрения алгебраические системы (группы подстановок, кольцо многочленов, тело кватернионов, поле комплексных чисел и др.).

- 85 -

Результатом далеко идущих обобщений обычного трехмерного пространства явилось понятие абстрактного пространства, которое в самом общем виде определяется как некоторое множество с заданными на нем отношением или законами композиции. Конкретизация множеств, свойств отношений и законов композиции приводит к различным типам пространств: метрическим и топологическим, линейным и евклидовым и т.д.

В заключительном параграфе настоящей главы излагаются основные понятия и методы комбинаторики. Ее основная задача состоит в исследовании расположения, упорядочения или выборки элементов конечных множеств в соответствии со специальными правилами и нахождении числа способов, которыми это может быть сделано. Комбинаторные методы находят все более широкое применение в инженерном деле, например, при решении транспортных задач, составлении расписаний, планировании производства, организации снабжения и сбыта, статистических методах контроля, составлении и декодировании шифров для передачи сообщений и т.п.

Восприятие использование абстрактного языка теории множеств и других разделов современной математики позволяют объединять и исследовать с единых позиций такие понятия и явления, которые ранее казались далекими и различными. При этом важно уметь применять к реальным явлениям те математические понятия и методы, которые наиболее близки к ним, и научиться за общими абстрактными понятиями видеть конкретные образы окружающего мира.

1. Алгебра множеств

1. Свойства операций над множествами. Операции над множествами, сформулированные в (1.2.7), как и операции над числами, обладают некоторыми свойствами (табл. 1). Эти свойства выражаются совокупностью тождеств, справедливых независимо от конкретного содержания входящих в них множеств, являющихся подмножествами некоторого универсума U.

Тождества (1а)-(3а) выражают соответственно коммутативный, ассоциативный и дистрибутивный законы для объединения, а тождества (1б)-(3б) — те же законы для пересечения. Соотношения (4а)-(7а) определяют свойства пустого множества ∅ и универсума U относительно объединения, а соотношения (4б) — (7б) — относительно пересечения.

Выражения (8а) и (8б), называемые законами идемпотентности, позволяют записывать формулы с множества без коэффициентов и показателей степени. Зависимости (9а) и (9б) представляют законы поглощения, а (10а) и (10б) — теоремы де Моргана.

- 82 -

Таблица 1

Основные свойства операций над множествами

1 а) A ∪ B = B ∪ A

1 б) A ∩ B = B ∩ A

2 а) A ∪ (B∪ C)=(A∪ B)∪ C

2 б) A ∩ (B∩ C)=(A∩ B)∩ C

3 а) A∪ (B∩ C)=(A∪ B) ∩ (A∪ C)

3 б) A∩ (B∪ C)=(A∩ B) ∪ (A∩ C)

4 а) A ∪ ∅ = A

4б) A ∩ U = A

5 а) A ∪ A̅ = U

5 б) A ∩ A̅ = ∅

6а) A ∪ U = U

6 б) A ∩ ∅ = ∅

7 а) ∅̅ = U

7 б) U̅ = ∅

8а) A ∪ A = A

8 б) A ∩ A = A

9 а) A ∪ (A ∩ B) = A

9 б) A ∩ (A ∪ B) = A

10 а)

10 б)

11) если A ∪ B =U и A ∩ B = ∅, то B = A̅

12) A̅ = U \ A

13) A̿ = A

14) A \ B = A ∩ B̅

15) A + B = (A ∩ B̅) ∪ (A̅ ∩ B)

16) A + B = B + A

17) (A + B) + C = A + (B + C)

18) A + ∅ = ∅ + A = A

19) A ⊂ B, если и только если A ∩ B = A или A ∪ B = B или A ∩ B̅ = ∅

20) A = B, если и только если (A ∩ B̅ ) ∪ (A̅ ∩ B ) = ∅

Соотношения (11)-(20) отражают свойства дополнения, разности, дизъюнктивной суммы, включения равенства.

2. Принцип двойственности. Первые десять свойств в табл. 1 представлены парами двойственных (дуальных) соотношений, одно из которых получается заменой в другом символов: ∪ на ∩ и ∩ на ∪, а также ∅ на U и U на ∅. Соответствующие пары символов ∪, ∩ и ∅, U называются двойственными (дуальными) символами.

При замене в любой теореме входящих в нее символов дуальными получим новое предложение, которое также является теоремой (принцип двойственности или дуальности). Тождества (11) и (12) не изменяются при замене символов дуальными, поэтому их называют самодвойственными.

Принцип дуальности можно распространить на разность и дизьюктивную сумму, если использовать тождества (14) и (15). Аналогично

- 87 -

в соответствии ...........

- !!!!!!!!!!!!!!!!!!!!! -

- Продолжение следует... -

- Содержание продолжения -

...

2. Отношения

3. Отображения и функции

4. Отношение эквивалентности

5. Отношение порядка

6. Отношение толерантности

7. Законы композиции

8. Примеры алгебраических систем

9. Пространства

10. Комбинаторика

Список литературы

Глава 3. Матрицы

1. Действия над матрицами

2. Определители

3. Обращение матриц

4. Линейные уравнения

5. Дифференциальные уравнения

6. Функции от матриц

7. Матричные преобразования

8. Пространство переменных состояния

Список литературы

Глава 4. Графы

1. Деревья

2. Анатомия графов

3. Полюсные графы

4. Многополюсные компоненты

5. Системы координат

6. Неоднородный координатный базис

7. Сокращенный координатный базис

Список литературы

Глава 5 Логика

Одной из основных задач математической логики является анализ оснований математики. Но в настоящее время она уже вышла из рамок этой задачи и оказала существенное влияние на развитие самой математики. Из ее идей возникло точное определение понятия алгоритма, что позволило решать многие вопросы, которые без этого остались бы в принципе неразрешенными. Возникший в математической логике аппарат нашел приложение в вопросах конструкций вычислительных машин и автоматических устройств.

П.С. Новиков

В начале этой главы излагаются основные положения, относящиеся к логическим функциям. Подробно исследуются булевы функции двух переменных, зависимости между ними и методы построения функционально полных систем. Наряду с булевой алгеброй, рассматривается алгебра Жегалкина, что позволяет глубже проникнуть в структуру логических функций.

Аппарат математической логики в значительной степени сложился под влиянием прикладных проблем, в рамках которых развились его специфические особенности. Пробным камнем среди технических приложений была задача анализа и синтеза контактных схем. Успехи в этой области послужили стимулом для использования аппарата математической логики и в других областях.

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

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

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

- 503 -

мизации булевых функций и их применение к синтезу контактных и логических схем.

В последнее время, наряду с двоичными функциональными элементами, разработаны и находят практическое применение многозначные элементы, характеризующиеся рядом положительных особенностей. В связи с этим сильно возросло значение многозначной логики, изложению основных положений которой посвящен специальный параграф. Там же кратко представлены другие логики, развившейся в связи с техническими и биологическими проблемами: пороговая, мажоритарная, нейронная, потенциально-импульсная и фазоимпульсная.

Значительное внимание в настоящей главе уделяется логике высказываний и логике предикатов. Символический язык этих разделов математической логики широко используется не только в самой математике, но и в технической литературе. Кроме того можно полагать, что формальные методы логического обоснования станут со временем необходимым элементом при решении практических задач, а значит, и составной частью математического аппарата инженера. Этому в значительной мере способствует развитие автоматизации проектирования с применением вычислительной техники.

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

1. Логические функции

1. Логические функции как отображения. Отличительная особенность логических функций состоит в том, что они принимают значения в конечных множествах. Иначе говоря, область значений логической функции всегда представляет собой конечную совокупность чисел, символов, понятий, свойств и, вообще, любых объектов. Если область значений функции содержит k различных элементов, то она называется k-значной функцией.

Чтобы различать элементы области значений функции, их необходимо как-то отметить. Удобнее всего элементы перенумеровать числами от 1 до k или обозначить какими-нибудь символами (например, буквами). Перечень всех символов, соответствующих области значений, называют алфавитом, а сами символы — буквами этого алфавита (буквами могут служить как собственно буквы латинского, русского или другого алфавита, так и порядковые числа или любые другие символы).

- 504 -

Логические функции могут зависеть от одной, двух и, вообще, любого числа переменных (аргументов) x1, x2, ..., xn. В отличие от самой функции, аргументы могут принимать значения из элементов как конечных, так и бесконечных множеств.

В теоретико-множественном смысле логическая функция n переменных y = f(x1, x2, ..., xn) представляет собой отображение множества наборов (n-мерных векторов, кортежей, последовательностей) вида (x1, x2, ..., xn), являющегося областью ее определения, на множестве ее значений N = {α1, α2, ..., αn}. Логическую функцию можно также рассматривать как операцию, заданную законом композиции X1, X2, ..., Xn где - множества, на которых определены аргументы x1 ∈ X1, x2 ∈ X2, ..., xn ∈ Xn.

2. Однородные функции. Если аргументы принимают значения из того же множества, что и сама функция, то ее называют однородной функцией. В этом случае X1 = Х2 = ... = Хn = N и однородная функция, рассматриваемая как закон композиции Nn → N определяет некоторую п-местную операцию на конечном множестве N.

Областью определения однородной функции у = f(х1, х2, ..., xn) служит множество наборов (х1, х2, ..., xn), называемых словами, где каждый из аргументов х1, х2, ..., xn замещается буквами k-ичного алфавита {0, 1, ..., k -1}. Количество n букв в данном слове определяет его длину.

Очевидно, число всевозможных слов длины n в k-ичном алфавите равно kn. Так как каждому такому слову имеется возможность предписать одно из k значений множества N, то общее количество однородных функций от n переменных выражается числом k(kn).

Если буквами алфавита служат числа от 0 до k - 1, то каждое слово (х1, х2, ..., xn) символически представляется упорядоченной последовательностью n таких чисел и рассматривается как запись n-разрядного числа в позиционной системе счисления с основанием k, т. е. x1kn -1 + x2kn –2 + … + xn -1k1 + xnk0 = q. Числа q = 0, 1, ..., kn - 1 служат номерами слов и тем самым на множестве всех слов вводится естественная упорядоченность (отношение строгого порядка). Аналогично номерами функций можно считать kn -разрядные числа в той же системе счисления.

Различные слова длины n в данном алфавите образуются как n-перестановки с повторениями (2. 10. 1). Так, в трехзначном алфавите {0, 1, 2} словами длины 4 будут все четырехразрядные числа с основанием k = 3, т. е. 0000, 0001, 0002, 0010, 0011, ..., 2221, 2222, которые соответствуют десятичным числам от 0 до 80 = 2 · З3+ 2 · З2+ 2 · З1 + 2 · 30. Поставив каждому такому четырехразрядному числу в соответствие одну из букв алфавита {0, 1, 2}, получим некоторую функцию четырех переменных

- 505 -

fi(х1, х2, x3, x4), причем количество таких функций выражается огромным числом 381.

Пусть алфавит состоит из трех букв русского алфавита {о, п, т}. Множество пятибуквенных слов в этом алфавите состоит из 35 = 243 элементов. Наряду с такими имеющими прямой смысл словами, как «топот» и «потоп», оно также включает все другие 5-перестановки, например: «ооппт», «поппп», «тттоп» и др.

Примерами однородных логических функций двух переменных могут служить операции сложения и умножения одноразрядных m-значных чисел по модулю т (2. 8. 7), внутренние операции поля Галуа (2. 8. 9) с четырехзначным алфавитом {0, 1, А, В} и т. п.

3. Табличное задание функций. Как и бинарный закон композиции (2. 7. 2), однородная функция двух переменных может быть задана таблицей соответствия (матрицей), строки и столбцы которой соответствуют буквам алфавита. Таким способом представлялись функции одной и двух переменных в (1. 5. 2),(1. 5. 8) и (1. 5. 10). Для представления функций трех и большего числа переменных потребовались бы трехмерные и, вообще, n-мерные таблицы. Этого можно избежать, если столбцы матрицы поставить в соответствие не буквам алфавита, а словам, т. е. образовать kn столбцов. Для каждой функции отводится строка, клетки которой заполняются буквами из данного алфавита. Матрица всех функций n переменных в k-значном алфавите содержит kkn строк и называется общей таблицей соответствия. Например, для k = 3 и n = 2 такая матрица имеет вид:

Номера столбцов определяются расположенными над ними n-разрядными числами с основанием k, каждое из которых читается сверху вниз. Номера функций отождествляются с kn-разрядными числами, которые соответствуют строкам матрицы в той же системе счисления.

4. Двузначные однородные функции. Наиболее простым и в то же время важнейшим классом однородных функций являются двузначные (булевы) функции, частично рассмотренные в (1.5. 2) и последующих пунктах.

- 506 -

Областью определения булевых функций от n переменных служит множество слов длины n. Они представляют собой всевозможные наборы из n двоичных цифр и их общее количество равно 2n.

Число всевозможных булевых функций n переменных v = 2n быстро возрастает с увеличением n (при n = 3 оно равно 256, а при n = 5 превышает 4 миллиарда). Но функции одной и двух переменных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при n = 2).

Булевы функции одной переменной. Общая таблица соответствия для булевых функций одной переменной имеет вид (справа указаны обозначения функций):

x

|

0

1

|

y

---

|

---

---

|

---

y0

|

0

0

|

0

y1

|

0

1

|

x

y2

|

1

0

|

x̅

y3

|

1

1

|

1

Две функции у0 = 0 и у3 = 1 представляют собой функции-константы (тождественный нуль и тождественная единица), таккакони не изменяют своих значений при изменении аргумента. Функция y1 = х повторяет значения переменной х и потому просто совпадает с ней.

Единственной нетривиальной функцией является у2 = x̅ , называемая отрицанием или инверсией ( x̅ читается «не х»). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

- !!!!!!!!!!!!!!!!!!!!! -

- Продолжение следует... -

- Содержание продолжения -

...

2. Алгебра логики

3. Контактные схемы

4. Логические схемы

5. Минимизация булевых функций

6. Конечные автоматы

1. Основные определения. В контактных и логических схемах значения выходных переменных определяются только комбинацией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значении входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи, с чем схемы с такими свойствами называют последовательностными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы.

Пусть Xi - алфавит входной переменной хi, а Yi – алфавит выходной переменной yi. Конечный автомат с n входами и m выходами характеризуется входным алфавитом Х = Х1 × Х2 × ... Хn и выходным алфавитом Y = Y1 × Y2 × ... Ym, причем символами входного алфавита служат слова x = (x1, x2, …, xn) длины n, а символами выходного алфавита - слова y = (y1, y2, …, ym) длины m, где xi ∈ Xi и yi ∈ Yi. Особого внимания заслуживают конечные автоматы с двузначным структурным алфавитом, зависимости между входными и выходными переменными которых выражаются булевыми санкциями. Их значение обусловлено тем, что любая информация может быть представлена в двоичных кодах (двоично-десятичные коды чисел, телетайпный код в технике

- 564 -

связи и т.п.). В то же время при технической реализации автоматов используются преимущественно двоичные элементы и двузначная логика.

В реальных условиях сигналы представляются непрерывными функциями времени, поэтому для надежного различения сигналов требуется, чтобы новые значения на входах появлялись после окончания переходных процессов, связанных с предыдущими значениями. При рассмотрении логической структуры автоматов обычно отвлекаются от существа этих процессов и считают, что переменные изменяются не непрерывно, а мгновенно в некоторые моменты времени, называемые тактами. Интервалы между тактами могут быть различными, но без потери общности их можно считать равными Δt . Предполагается, что тактовые моменты tν + 1 =tν + Δt определяются синхронизирующими сигналами. Таким образом, вводится понятие дискретного автоматного времени tn(n = 1, 2, ...), причем переменные зависят не от физического времени, а от номера такта ν, т. е. вместо непрерывных функций x(t) рассматриваются дискретные значения х(ν).

2. Состояния. Кроме входных и выходных переменных, можно выделить некоторую совокупность промежуточных переменных, которые связаны с внутренней структурой автомата. В комбинационных схемах промежуточные переменные непосредственно не участвуют в соотношениях вход - выход. Напротив, выходные функции последовательностных схем в качестве своих аргументов, кроме входных переменных, обязательно содержат некоторую совокупность промежуточных переменных s1, s2, …, sk, характеризующих состояние схемы. Набор всех возможных состоянии, которые присущи данной схеме, называется множеством состояний. Если S1, S2, …, Sk - конечные алфавиты переменных состояния s1, s2, …, sk, то множество состояний S = S1 × S2 × … × Sk также является конечным множеством.

Строгое определение понятия состояния связывается с той ролью, которое оно играет при описании конечных автоматов. Во-первых, значения совокупности выходных переменных на ν-м такте у(ν) = (y1(ν), y2(ν), …, ym(ν)), однозначно определяется значениями входных переменных x(ν) = (x1(ν), x2(ν), …, xn(ν)) и состоянием s(ν) = (s1(ν), s2(ν), …, sk(ν)), на том же такте, т.е. у(ν) = λ (x(ν), s(ν)). Во-вторых, состояние s(ν + 1) в следующем (ν + 1)-м такте однозначно определяется входными переменными х(ν) и состоянием s(ν) в предыдущем такте, т.е. s(ν + 1) = δ (x(ν), s(ν)).

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

- 565 -

Ясно, что последовательностные схемы должны обладать способностью сохранять предыдущее состояние до следующего такта, в связи с чем их называют также автоматами с памятью или последовательностными машинами. В качестве памяти могут использоваться элементы задержки, на выходах которых повторяются входные воздействия со сдвигом во времени на интервал между тактами Dt. Широко применяются также различные запоминающие элементы, например, триггеры, способные сохранять состояния на выходах до тех пор, пока оно не изменяется в результате воздействия на их входы.

3. Типы конечных автоматов. В технике с понятием автомата обычно связывается некоторое устройство, способное выполнять определенные функции без вмешательства человека или с его ограниченным участием. Однако такое понимание является слишком узким. В широком смысле конечный автомат - это математическая модель, отображающая физические или абстрактные явления самой разнообразной природы. Такая модель успешно используется как в технике (проектирование электронных вычислительных машин, систем управления и связи), так и в других областях - психологии и физиологии (исследование деятельности нервной системы человека и простейших видов поведения животных), лингвистике (анализ синтаксиса русского, английского или других языков, расшифровка древних рукописей), теории и практике административного управления и т.п. Универсальность теории автоматов позволяет рассматривать с единой точки зрения различные объекты, устанавливать связи и аналогии между ними, переносить результаты из одной области в другую.

Рис. 235. Блок-схема конечного автомата.

Конечный автомат М определяется как система с конечным входным алфавитом Х = { ξ1, ξ2, ... , ξp}, конечным выходным алфавитом Y = {v1, v2, …, vq}, конечным множеством состояний S = {σ1, σ2, ..., σi}, и двумя характеристическими функциями:

s(ν + 1) = δ (x(ν), s(ν));

у(ν) = λ (х(ν), s(ν)),

называемыми соответственно функцией переходов и функцией выходов. Общая блок-схема конечного автомата (рис. 235) может быть представлена в виде комбинационной схемы, реализующей характеристические функции δ и λ, и памяти, сохраняющей на один такт предыдущее состояние автомата.

В определении автомата участвует три конечных множества X, Y, S и две функции δ и λ, задающие некоторые отношения между

- 566 -

элементами этих множеств. Следовательно, конечный автомат можно обозначить упорядоченной пятеркой М = (X, Y, S, δ, λ). Мощности множеств X, Y, S равны соответственно:

где pi, qi, ri - количество символов в алфавитах входной переменной xi, выходной переменной yi и переменной состояния si. При двоичном структурном алфавите р = 2n, q = 2m и r = 2k. Если желают подчеркнуть мощности множеств X, Y и S, на которых определен конечный автомат, то его называют (р, q, r)-автоматом.

Характеристические функции δ и λ можно рассматривать как некоторые отображения множества X × S или его подмножества D ⊂ X × S соответственно на множества S и Y. Если δ : X × X → S и λ : X × S → Y, автомат называется полным; если только δ : X × S → S, автомат называют полным по переходам. В случае, когда функции δ и λ определены не для всех наборов из множества X × S, автомат называют неполным или частично определенным.

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

Между автоматами этих двух типов имеется взаимная связь и один из них может быть преобразован в другой. Положив в характеристических функциях автомата Мили s'(ν) = (x(ν), s(ν)), получим у(ν) = λ '(s'(ν)) и s'(ν + 1) = (x(ν + 1), s(ν + 1)) = (x(ν + 1); δ (x(ν), s(ν))) = δ (x(ν + 1), s'(ν)), т. е. приходим к автомату Мура. Обратный переход осуществляется подстановкой s(ν) = s'(ν - 1), в результате чего получаем у(ν) = λ '(s'(ν)) = λ '( δ (x(ν), s'(ν - 1))) = λ (x(ν), s(ν)), а также s(ν + 1) = s'(ν) = δ (x(ν), s'(ν - 1)) = δ (x(ν), s(ν)).

Для комбинационных схем функция перехода не имеет смысла, а функция выходов вырождается к виду y(ν) = λ (x(ν)). Их называют автоматами без памяти или тривиальными автоматами.

4. Представления конечных автоматов. Автомат может быть задан различными способами, например, путем словесного описания его функционирования или перечислением элементов множеств X, Y, S, с указанием отношений между ними. При анализе и синтезе конечных автоматов используются стандартные формы представления: таблицы, графы и матрицы. Элементы множеств X, Y, S удобно пронумеровать порядковыми числами, начиная с нуля, например: Х = {0, 1, 2, 3}, Y = {0, 1} и S = {0, 1, 2, 3}. Тогда характеристические функции δ и λ можно представить двумя

- 567 -

таблицами, строки которых соответствуют состояниям, а столбцы - входам. Первая таблица, называемая таблицей переходов, соответствует функции s(ν + 1) = δ (x(ν), s(ν)), и ее клетки заполняются номерами состояний s(ν + 1), в которые переходит автомат при

воздействии х(ν), и состоянию s(ν) в данный тактовый момент. Вторая таблица, называемая таблицей выходов, соответствует функции у(ν) = λ (x(ν), s(ν)), и ее клетки заполняются номерами выходов y(ν) в данный тактовый момент, которые соответствуют воздействию x(ν) и состоянию s(ν) в тот же момент. Например, для заданных множеств X, Y, S такие таблицы могут иметь вид:

Обе таблицы можно объединить в общую таблицу переходов, если условиться записывать в клетках пары чисел (номер следующего состояния в числителе и номер выхода в знаменателе), т.е.

Граф автомата строится таким образом, что его вершины соответствуют состояниям, а направленные дуги обозначаются как дизъюнкции входов, под воздействием которых совершается переход из одного состояния в другое по направлению дуги. В знаменателях записываются номера выходов, соответствующие этим переходам.

На рис. 236 показан граф, построенный в соответствии с приведенной выше общей таблицей переходов. Так как из состояния 0 автомат переходит в состояния 1, 2 и 3, то из вершины О графа исходят дуги в вершины 1, 2 и 3. При этом переход в состояние 1 совершается под воздействием 2 нему соответствует выход 0,

- 568 -

поэтому дуга из вершины 0 в 1 помечается как 2/0. Переход в состояние 2 совершается под воздействием 1 и ему соответствует выход 0, поэтому дуга из вершины 0 в 2 помечается как 1/0. Переходы в состояние 3 совершаются под воздействиями 0 и 3 и им обоим соответствует выход 0, поэтому дуга из вершины 0 в 3 помечается как дизъюнкция 0/0 Ú 3/0. Аналогично определяются и другие дуги графа. Петли соответствуют переходам, при которых состояния не изменяются. Так, рассматриваемый автомат переходит из состояния 2 в 2 под воздействиями 1 и 2, которым соответствуют выводы 0 и 1. Следовательно, петля при вершине 2 помечается как дизъюнкция 1/0 Ú 2/1.

Рис. 236. Граф конечного автомата.

Матрица соединения автомата М (или матрица переходов) представляет собой квадратную таблицу в которой номера строк и столбцов соответствуют номерам состояний. Клетка матрицы на пересечении i-й строки и j-го столбца заполняется дизъюнкцией пар «вход — выход», которая приписана дуге графа исходящей из i-й в j-ю вершину. При отсутствии такой ветви клетка заполняется нулем или остается свободной. Так для рассматриваемого примера имеем:

5. Анализ конечных автоматов. Полное описание поведения автомата заключается в определении последовательности выходных сигналов при возбуждении его в тактовые моменты времени некоторой последовательностью входных сигналов. Входная и выходная последовательности представляются наборами символов (или их номеров) из алфавитов Х и Y одинаковой длины l. Для такого описания, кроме характеристических функций, необходимо определить или задать начальное состояние автомата.

Наиболее удобно определять реакцию автомата на входною последовательность по его графу. Для этого достаточно проследить

- 569 -

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

Так, из графа на рис. 236 для входной последовательности (2, 0, 1, 1, 2, 3) и начального состояния 0 имеем выходную последовательность (0, 1, 0, 0, 1, 1) и смену состояний автомата (1, 3, 0, 2, 2, 3). При начальном состоянии 2 и той же входной последовательности получаем соответственно (1, 1, 0, 0, 1, 1) и (2, 3, 0, 2. 2, 3).

С помощью графа автомата легко выделить следующие характерные типы его состояний:

1) преходящее состояние, из которого можно перейти, но крайней мере, в одно другое состояние, но после этого уже нельзя возвратиться в него ни при каком воздействии (соответствующая вершина не имеет заходящих дуг, но имеет хотя бы одну исходящею дугу);

2) тупиковое состояние, в которое можно перейти, по крайней мере, из одного другого состояния, но после этого уже нельзя выйти из него ни при каком воздействии (соответствующая вершина не имеет исходящих дуг в другие вершины, но имеет хотя бы одну входящую дугу из другой вершины);

3) изолированное состояние, из которого нельзя перейти ни в какое другое состояние и в него нельзя попасть ни из какого другого состояния (соответствующая вершина содержит только петлю).

Аналогичные определения можно дать для некоторых совокупностей состояний, рассматриваемых как подавтоматы. Если начальное состояние автомата М принадлежит непустому множеству Si состояний, которое составляет тупиковый или изолированный подавтомат, то M можно упростить исключением всех состояний, которые не принадлежат множеству Si, и всех дуг, начинающихся в этих состояниях.

Пусть М1, М2 и M3 - соответственно преходящий, тупиковый и изолированные подавтоматы автомата М, которые характеризуются множествами состояний S1, S2 и S3. Очевидно, выделение таких подавтоматов соответствует разбиению множества S состояний автомата М на непересекающиеся подмножества S1, S2 и S3, представляющие собой классы эквивалентности ( S1 ∪ S2 ∪ S3 = S и S1 ∩ S2 ∩ S3 = ∅ ). Как следует из обобщенного графа (рис. 237), матрица соединения автомата может быть представлена в виде:

,

- 570 -

где μ11, μ22, μ33 - матрицы подавтоматов М1, М2 и М3; μ12 - матрица, характеризующая переходы от состояний преходящего автомата М1 к состояниям тупикового автомата М2. Отсюда следует, что разбиение автомата М на подавтоматы М1, М2 и М3 можно осуществить преобразованием его матрицы соединений к стандартному виду путем перестановки соответствующих строк и столбцов. Например, для автомата, граф которого изображен на рис. 238, имеем:

Рис. 237. Обобщенный граф конечного автомата.

Рис. 238. Граф конечного автомата к примеру разбиения на подавтоматы.

Отсюда следует, что S1 = {3, 6} составляет преходящий подавтомат, S2 = {2, 4, 7} - тупиковый подавтомат и S3 = {1, 5} - изолированный подавтомат. Если начальное состояние принадлежит множеству S2, то можно упростить автомат, исключив состояния S1 ∪ S3 = {3, 6, 1, 5}, а в случае принадлежности начального состояния множеству S3 автомат упрощается исключением состояний S1 ∪ S2 = {3, 6, 2, 4, 7}.

6. Синтез конечных автоматов. Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные x(ν) и s(ν) в выходные переменные y(ν) и s(ν + 1) в соответствии с заданными характеристическими функциями s(ν + 1) = δ (x(ν), s(ν)) и y(ν)= λ (x(ν), s(ν)). Для сохранения состояний s(ν + 1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.

При реализации автоматов в двоичном структурном алфавите можно использовать рассмотренные ранее методы синтеза

- 571 -

комбинационных схем. Но для этого необходимо закодировать состояния схемы н представить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осуществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите. Если элементы множеств X, Y и S пронумерованы порядковыми числами, начиная с нуля, то им соответствуют коды, представляющие собой двоичные эквиваленты этих чисел. Например, для автомата, заданного в (4), таблицу переходов можно преобразовать к виду:

Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s(ν + 1) и у(ν) представлены двоичными кодами:

Рис. 239. Структурная схема конечного автомата

Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x1(ν), х2(ν) и переменным состояния s(ν), s2(ν), а также три выхода, соответствующие переменным состояния s1(ν + 1), s2(ν + 1) и выходной переменной у1(ν). Синтезировав комбинационную схему, соответствующую полученной таблице и введя два элемента задержки З1 и З2, получим структурную схему автомата (рис. 239).

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

- 572 -

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

Рис. 240. Граф конечного автомата (а) и его сокращенная форма (б)

Минимизация числа состоянии полных автоматов связана с отношением эквивалентности. Пусть автоматы М1 и М2, находящиеся соответственно в начальных состояниях, σi и σj (обозначения М1 и М2 могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М1 и М2 в данных состояниях σi и σj неразличимы по внешним выходам. Такое отношение между состояниями одного и того же или двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:

1) состояния σi и σj автомата явно различимы, если различаются соответствующие, им строки в таблице выходов;

2) состояния σi и σj автомата явно эквививалентны, если соответствующие им строки в таблице переходов и таблице выходов одинаковы или становятся одинаковыми при замене каждого номера σi на номер σj (или наоборот).

Например, для автомата, граф которого изображен на рис. 240, а, общая таблица переходов имеет вид:

- 573 -

Из этой таблицы следует, что состояния из множества {0, 3, 4}являются явно различимыми с любым состоянием из множества {1, 2, 5, 6}. Поэтому следует искать эквивалентные состояния только среди элементов, принадлежащих одному из этих множеств. Так как строки 0 и 4 одинаковы, а строки 1 и 5 становятся одинаковыми при замене цифры в числителе 1 на 5 (или 5 на 1), то явно эквивалентными являются пары состояний {0,4} И {1,5}.

Объединяя эквивалентные состояния в автомате М1, получаем эквивалентный автомат М2 с меньшим числом состоянии, который в любом состоянии нельзя отличить от исходного, наблюдая сигналы на выходах. Очевидно, автоматы М1 и М2 являются эквивалентными, если каждому состоянию σi , автомата М1 соответствует, по крайней мере, одно эквивалентное ему состояние автомата M2, и если каждому состоянию σj , автомата М2 соответствует хотя бы одно эквивалентное ему состояние автомата М1.

Эквивалентные состояния, например, σi и σj , удобно объединять по общей таблице переходов, вычеркивая строку σj , и заменяя везде в числителе числа σj на σi . После объединения пар явно эквивалентных состояний может оказаться возможным снова обнаружить такие состояния, которые также объединяются с помощью аналогичной процедуры. В результате последовательного объединения приходим к сокращенной таблице переходов, которой соответствует сокращенный автомат, эквивалентный исходному, но имеющий меньшее число состоянии. Так, для рассматриваемого примера получаем последовательно:

- 574 -

Первая таблица соответствует объединению пар эквивалентных состоянии {0,4} и {1, 5}, а вторая - объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния (рис.240, б).

8. Эквивалентное разбиение. Если известны все пары эквивалентных состояний конечного автомата, то тем самым на множестве S его состояний определено отношение эквивалентности, которому соответствует некоторое разбиение на классы эквивалентности S = {S1, S2 ..., Sν}. При этом состояние, не имеющее эквивалентного ему состояния, составляет класс эквивалентности, единственным элементом которого является это состояние. Обозначим через σ'0, σ'1, ..., σ'ν представители классов эквивалентности и через М' – автомат, множеством состояний которого является семейство представителей S' = {σ'0, σ'1, ..., σ'ν}. Можно утверждать, что автоматы М и М' эквивалентны (М ~ М'), причем М' имеет минимальное число состояний, т. е. является минцмальной формой автомата.

Объединение эквивалентных состояний в классы эквивалентности осуществляется весьма просто. Если σi ~ σj и σj ~ σk, то на основе свойства транзитивности следует, что σi ~ σk, и, значит, пары {σi , σj}и {σj , σk} входят в общий для них класс эквивалентности. Но для выявления всех пар эквивалентных состояний требуется более громоздкая процедура, так как множество таких пар не исчерпывается явно эквивалентными состояниями и не всегда может быть полностью обнаружено и объединено способом, изложенным ранее.

Для эквивалентного разбиения множества S состояний автомата предложен ряд способов. Один из них основан на последовательном рассмотрении всевозможных пар состояний и исключении тех из них, которые не являются эквивалентными. При этом пары одинаковых состояний {σi , σi}, являющиеся в силу свойства рефлективности заведомо эквивалентными {σi~σi}, не рассматриваются. Процедура эквивалентного разбиения осуществляется по таблице пар состояний, которая получается на основе общей таблицы переходов автомата. Так как явно различимые пары состояний (для таких состояний строки в таблице выходов различные) не могут быть эквивалентными, то они в таблицу пар не включаются. Для каждой пары отводится строка, для каждого входа – столбец, ав клетках на основании таблицы переходов указывается пара состояний, в которые переходит автомат из данной пары состояний при данном входном воздействии (порядок записи состояний в каждой паре безразличен). Исключаемые пары отмечаются каким-либо способом (набираются жирным шрифтом, подчеркиваются или снабжаются меткой). Далее приведены общая таблица переходов (табл. 10) и полученная из нее таблица пар состояний некоторого автомата.

- 575 -

Так как одинаковые строки таблицы выходов соответствуют множествам состояний {0, 2, 4, 6, 7} и {1, 3, 5, 8}, то в первом столбце таблицы пар указаны только попарные комбинации таких состояний, которые входят в одно и то же множество, т. е. не являются явно различимыми.

Исключение пар основано на следующем положении: если состояния σi и σj эквивалентны, то эквивалентными являются и состояния, в которые автомат переходит под любым входным воздействием. Это значит, что на первом шаге необходимо отметить те пары, которые переходят в пары, состоящие из различных состояний и отсутствующие в первой графе таблицы. Так как обозначенные пары не могут быть эквивалентными, то на следующем шаге отмечаются все те пары, которые переходят в пары, отмеченные на предыдущем шаге и т. д. Процесс заканчивается тогда, когда среди неотмеченных пар уже нет таких, которые можно отметить в соответствии с изложенным правилом. После этого неотмеченные пары и представляют собой попарно эквивалентные состояния.

В приведенном примере на первом шаге отмечаются пары {1, 8}, {3, 8} и {5, 8}, на втором – {1, 5} и {3, 5}, на третьем – {0, 4}, {0, 6}, {2, 4}, {2, 6}, {4, 7} и {6, 7}. Эквивалентными являются неотмеченные пары {0, 2}, {0, 7}, {1, 3}, {2, 7} и {4, 6}, образующие классы эквивалентности S0 = {0, 2, 7}, S1 = { 1, 3} и S2 = { 4, 6}. Кроме того, не вошедшие в эти множества состояния 5 и 8 образуют классы эквивалентности S3 = {5} и S4 = {8}. Обозначив представителей полученных пяти классов соответственно числами от 0 до

- 576 -

4, получим для рассматриваемого автомата минимальную форму с пятью состояниями и общей таблицей переходов:

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

Рис. 241. Граф неполного автомата (а) и его минимальная форма (б).

Если М' – минимальная форма автомата М, то она единственна и несократима.

9. Неполные автоматы. В практике встречаются случаи, когда не каждый символ из входного алфавита может быть подан на автомат, находящийся в определенном состоянии (ограничения на входе), или его выходы при некоторых входных воздействиях не представляют интереса (неопределенность выходов). Тогда приходится иметь дело с неполными автоматами, общая таблица переходов которых содержит прочерки вместо состояний и выходов для запрещенных входов, а также вместо неопределенных выходов.

Например, таблица для неполного автомата, граф которой изображен на рис. 241, a, имеет следующий вид:

- 577 -

Здесь вход 0 в состояниях 1 и 5, а также вход 1 в состояниях 0 и 5 являются запрещенными. Кроме того, в состоянии 3 при воздействии 0 и в состоянии 4 при воздействии 1 выходы не определены.

Входная последовательность называется допустимой для автомата в состоянии si, если она не нарушает ограничений на входе ни в каком состоянии автомата М и порождаемый ею выход определен на заключительном такте. На других тактах входной последовательности выходы могут быть и не определены, но последовательность состояний обязательно должна существовать. Например, для приведенного автомата в состоянии 0 допустимая входная последовательность {0, 1,0} порождает последовательность состояний {1, 4, 5} и заключительный выход 0. В то жевремя последовательность {0, 1, 1} не допустима, так как заключительный выход не определен.

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

Сокращенная форма неполного автомата М – это такой автомат М', который по отношению к допустимым для М входным последовательностям ведет себя на выходах так же, как и исходный автомат М, но имеет меньшее число состояний. Автомат М' квазиэквивалентен автомату М. Отношениеквазиэквивалентности рефлексивно и транзитивно, но не симметрично, т. е обладает всеми свойствами отношения включения. Поэтому говорят также, что М' включает М и записывают М ⊂М'. При этом из М ⊂М' вовсе не следует М' ⊂М, что иногда выражают словами: М' делает столько же и, быть может, больше, чем М.

10. Минимизация неполных автоматов. Эта задача сводится к поиску квазиэквивалентного автомата, который имеет наименьшее число состояний, и решается следующим образом.

Сначала на множестве состояний S = {σ1, σ2, ..., σr} исходного автомата определяется отношение совместимости. Состояния σi и σj называют совместимыми, если любая допустимая для этих состояний входная последовательность не порождает различных заключительных выходов при начальных состояниях σi и σj автомата. Отношение совместимости рефлексивно и симметрично, однако оно не обязательно транзитивно. Отсюда следует, что совместимость является отношением толерантности. Все совместимые между собой состояния объединяются в классы толерантности S'0, S'1, ..., S'w, которые образуют некоторое покрытие множества состояний

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

- 578 -

символа отсутствуют различные выходы. Клетки, соответствующие запрещенным входам для данной пары состояний, заполняются прочерком и при исключении пар, как это описано в (8), не учитываются. Так, для автомата, заданного табл. 12, имеем:

Отмеченная на первом шаге пара {0, 2} является единственной несовместимой парой в таблице, так как она не содержится ни в каких других строках. Следовательно, всенеотмеченные пары являются совместимыми. Построив матрицу толерантности для совместимых пар и переставив в ней строки и столбцы, имеем:

Отсюда выделяем кассы толерантности S'0= {0, 1, 4, 5}, S'1= {0, 3, 4, 5} S'2= {2, 3, 4, 5}, объединяющие совместимые между

- 579 -

собой состояния. Здесь, в частности, можно убедиться в том, что совместимость не обладает свойством транзитивности. Например, пары состояний {0, 1} и {0, 3} совместимы, но состояния 1 и 3 не входят в один и тот же класс толерантности и, следовательно, они несовместимы.

Из определения совместимости и способа получения классов толерантности следует, что при воздействии любого не запрещенного входного символа автомат из совместимых состояний переходит в одно и то же или в совместимые состояния, а выходы (если они определены) при этом будут одинаковы.

Так, в нашем примере при воздействии 0 классы S'0 и S'1 переходят в {1, 5}, а S'2 – в {3, 5}; при воздействии 1 класс S'0 переходит в {4, 5}, S'1 – в {5} и S'2 – в {1, 5}. Следовательно, исходный автомат можно представить квазиэквивалентным ему автоматом, в котором классам совместимости S'1, S2,..., S'w соответствуют состояния σ'0, σ'1, ..., σ'w . Однако такой автомат не всегда будет минимальным. Для получения минимальной формы автомата необходимо отобрать наименьшее число таких классов совместимости, которые образуют покрытие множества состояний S и в то же время включают множества состояний, следующих за состояниями каждого класса при всех незапрещенных воздействиях. Для рассматриваемого примера этим требованиям удовлетворяют классы S'0 и S'1, так как S'0 ∪ S'2 = S, и все множества последующих состояний {1, 5}, {3, 5}, {4, 5} и {5} являются подмножествами S'0 и S'2. Соответствующая минимальная форма показана на рис. 241, б, где состояния 0и 1 соответствуют классам S'0 и S'2.

Дальнейшие упрощения относятся не к числу состояний, а к структуре множеств, образующих минимальное покрытие S. Если из отобранных классов толерантности можно исключить некоторые состояния так, что полученные подмножества удовлетворяют приведенным выше требованиям, то эти подмножества также определяют другой вариант минимальной формы автомата. Так, из S'0 или из S'2 можно исключить состояние 4, поскольку оно входит только в множество последующих состояний {4, 5}. Тогда получим еще два варианта минимальных покрытий: {0, 1, 5}, {2, 3, 4, 5} и {0, 1, 4, 5}, {2, 3, 5}. Но состояние 5 нельзя исключить ни из одного класса, хотя оно и содержится в каждом из них, так как множества последующих состояний {1, 5} и {3, 5} показывают, что состояние 5 должно содержаться как в S'0, так и в S'2.

- !!!!!!!!!!!!!!!!!!!!! -

- Продолжение следует... -

- Содержание продолжения -

...

7. Многозначная логика

8. Логика высказываний

9. Логика предикатов

10. Алгоритмы

Список литературы

Глава 6. Вероятности

1. Случайные события

2. Случайные величины

3. Преобразования случайных величин

4. Обработка наблюдений

5. Процессы массового обслуживания

6. Надежность и восстановление

7. Информация и связь

Список литературы

Предметный указатель

Оглавление

Математический аппарат инженера

  Глава 1

    Введение

    1. Математика в инженерном деле

    2. Множества

    Задачи и упражнения

    3. Матрицы

    Задачи и упражнения.

    4. Графы

    Задачи и упражнения

    5. Логика

    Задачи и упражнения

    6. Вероятности

    Задачи и упражнения

    Список литературы

  Глава 2 Множества

    1. Алгебра множеств

  Глава 5 Логика

    1. Логические функции

    6. Конечные автоматы Fueled by Johannes Gensfleisch zur Laden zum Gutenberg