ББК 32.844 М80 УДК 621.396.6 Морозов К. К., Одинокое В. Г., Курейчик В. М. М80 Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учеб. пособие для ву- зов. — М.: Радио и связь, 1983. — 280 с., ил. В пер.: 1 р. В книге рассмотрены математические методы компоновки, размещения и трассировки радиоэлектронной аппаратуры реализованных на печатных платах и интегральных микросхемах повышенной степени интеграции. Даны особенности подготовки и выдачи конструкторской и технологической до- кументации с использованием ЭВМ. Описаны современные комплексные системы автоматизации конструкторского проектирования печатных плат и интегральных микросхем. Для студентов специальности «Конструирование и производство ра- диоаппаратуры» . 2402020000—057 М————————————43—83 046(01)—83 ББК 32.844 6Ф2.1 РЕЦЕНЗЕНТЫ: КАФЕДРА КОНСТРУИРОВАНИЯ И ТЕХНОЛОГИИ ПРОИЗВОДСТВА РЭА МОСКОВСКОГО АВИАЦИОННОГО ИНСТИТУТА, ДОКТОР ТЕХН. НАУК И. П. НОРЕНКОВ Редакция литературы по конструированию и технологии производства радиоэлектронной аппаратуры Константин Константинович Морозов, Валентин Григорьевич Одиноков, Виктор Михайлович Курейчик АВТОМАТИЗИРОВАННОЕ ПРОЕКТИРОВАНИЕ КОНСТРУКЦИИ РАДИОЭЛЕКТРОННОЙ АППАРАТУРЫ Редактор Н. Н. Кузнецова Художник Н. М. Ковалева Художественный редактор Г. Н. К о в а н о в Технический редактор Г. И. Колосова Корректор Т. В. Покатова ИБ № 524 Сдано в набор 1.11.82 г. Подписано в печать 3.03.83 г. Т-05166 Формат 60Х90/16 Бумага кн-журн. Гарнитура литературная Печать высокая Усл. печ. л. 17,5 .Усл. кр.-отт. 17,5 Уч.-изд. л. 19.0 Тираж 14 000 экз. Изд. № 19500 Зак. № 144 Цена 1 р. Издательство «Радио и связь». 101000 Москва, Главпочтамт, а/я 693 Типография издательства «Радио и связь» Госкомиздата СССР iOIOOO Москва, ул. Кирова, д. 40 © Издательство «Радио и связь», 1983 ПРЕДИСЛОВИЕ Научно-технический прогресс в области создания новых средств радиоэлектроники и вычислительной техники стал во многом зави- сеть от успешного решения проблемы автоматизации проектирова- ния—важной народнохозяйственной задачи. Уровень сложности современной аппаратуры радиоэлектронной и вычислительной тех- ники приблизился к границе, за которой эффективность труда чели- века-проектировщика резко падает, а число ошибок возрастает. Это особенно наглядно на этапе создания рабочего проекта устрой- ства, когда конструктору приходится выполнять значительный объ- ем нетворческой работы. Автоматизация конструирования—это не только способ повышения производительности труда конструктора, но и надежный способ снижения стоимости и повышения качества конструкторской документации. Проблемами автоматизации кон- струирования в нашей стране занимаются более 20 лет, однако и сегодня эта проблема актуальна. др Значительный вклад в развитие теории и практики автоматиза- ции конструирования внесли советские ученые В. М. Глушков, Н. Я. Матюхин, Л. Б. Абрайтис, В. И. Анисимов, Р. П. Базилевич, Б. В. Баталов, Б. Ф. Высоцкий, Ю. X. Вермишев, Б. Н. Деньдобренко, А. В. Каляев, А. М. Карапетян, С. А. Майоров, А. Н. Мелихов, В. Н. Лошаков, И. П. Норенков, Г. В. Орловский, А. И. Петренко, М. И. Песков, Г. Г. Рябов, Л. П. Рябов, К. А. Сапожков, В. А. Селютин, М. А. Штейн, О. Н. Юрин. В предлагаемом учебном пособии авторы предприняли попытку восполнить пробел в учебной литературе по автоматизации конст- ^, руирования. Содержание книги в наибольшей степени соответству- ||^ ет программе курса «Автоматизация конструирования» для высших учебных заведений по специальностям «Конструирование и произ- водство радиоаппаратуры», «Конструирование и производство электронно-вычислительной аппаратуры» и «Конструирование и производство технических средств САПР». В книге авторы обобщи- ли свой опыт по чтению лекций в течение ряда последних лет в Мо- сковском институте радиотехники, электроники и автоматики, Мо- сковском энергетическом институте, Таганрогском радиотехниче- ском институте. В книге кроме оригинальных и апробированных материалов ав- торов приводятся научные и учебно-методические материалы совре- менных исследований советских и зарубежных ученых. Основное внимание в учебном пособии авторы уделили совре- менным методам и перспективам автоматизации конструирования аппаратуры на интегральных микросхемах 4-й и 5-й степеней ин- теграции и печатных платах со сверхплотной упаковкой с исполь- зованием математических методов теории графов и гиперграфов. Учебное пособие дополняет учебник Б. Н. Деньдобренко, А. С. Ма- лика «Автоматизация конструирования РЭА» (М.: Высшая шко- ла, 1980). . „ ,. с о 1 о о Глава 1, § 3.2 и гл. 5 написаны К. К. Морозовым, § 3.1, 3.3 и 3.4, гл. б—В. Г. Одиноковым, гл. 2, 4, введение, заключение — В. М. Курейчиком. Авторы благодарны 'профессорам А. В. Каляеву, В. Ь. Пестря- кову А Н Мелихову, кандидатам техн. наук В. А. Калашникову, В В'. Лисяку, Б. К. Лебедеву, а также А. Л. Перельману за по- мощь и полезные советы при подготовке рукописи к изданию. Улучшению содержания книги способствовали обстоятельные за- мечания рецензентов профессора И. П. Норенкова и сотрудников кафедры конструирования МАИ. Авторы приносят им глубокую благодарность. Авторы ВВЕДЕНИЕ Современные достижения атомной энергетики, точного прибо- ростроения, промышленных средств связи, медицинской техники и других наук невозможны в настоящее время без широкого ис- пользования электронно-вычислительной аппаратуры (ЭВА) и ра- диоэлектронной аппаратуры (РЭА). Далее будем использовать термин электронная аппаратура (ЭА). Электронная аппаратура—это сложные комплексы устройств, предназначенные для электронной обработки информации, т. е. для хранения, преобразования и отображения ее в форму, удоб- ную для восприятия человеком в соответствии с заданной прог- раммой. В настоящее время во всем мире наблюдаются резкое увели- чение производства ЭА и повышение ее возможностей. Особенно это связано с последними успехами в области микроэлектроники. Разработка и внедрение ЭА является одними из основных по- казателей современной нучно-технической революции. Прогресс в области создания ЭА определяется повышением надежности, эко- номичности, качества и эффективности устройств, совершенство- ванием схем, конструкций, технологии. Процесс создания ЭА условно разделяется на три основных этапа: схемотехническое проектирование, конструкторское проек- тирование, технологическое проектирование. На первом этапе раз- рабатывается архитектура будущей ЭА. Материализация же ос- новных идей ЭА осуществляется на стадии конструирования и технологии производства. Практика показала, что именно здесь обеспечиваются возможность воплощения электронных схем в ми- кроэлектронные конструкции, рождение жизнеспособных изделий, отвечающих современным требованиям науки, техники и произ- водства. В процессе создания ЭА тесно переплетаются вопросы разра- ботки математической логики, конструкции и технологии. Даже небольшие изменения в логике ЭА без учета конструкторско-тех- нологических факторов приводят к ухудшению ее основных ха- рактеристик. Расширение функциональных возможностей и усложнение ЭА поставили ученых и инженеров перед необходимостью поиска но- вых принципов конструирования и технологии, коренного измене- ния методики конструирования на основе использования совре- менных средств вычислительной техники. Электронная аппара- тура 'четвертого и пятого поколений содается сейчас на базе ин- тегральных микросхем (ИМС) 4-й и 5-й степеней интеграции. 5 Сегодня конструкторы и технологи ЭА участвуют в разработ- ках ИМС, на кристалле которых размером 3Х4 мм и менее раз- мещаются сотни тысяч элементов, реализующих функции транзи- сторов, резисторов и др. На основе прогнозирования науки ожи- дается, что следующие поколения ЭА будут реализованы на ги- гантских ИМС с голографической и оптической памятью, будут иметь программируемую перестраиваемую архитектуру, электрон- ную коммутацию и будут способны принимать и выдавать реше- ния в расплывчатых условиях. Конструкторы ЭА четвертого и пятого поколений приступили к разработкам методологии построения поисковых алгоритмов, все более приближаясь к созданию искусственного интеллекта. Недалек тот день, когда каждая ЭВМ .будет иметь специальные «интеллектуальные процессоры», способные играть в шахматы на уровне гроссмейстера, управлять сложным производством, разы- грывать модели .военных сражений, следить за недоступными для человека технологическими операциями и вообще являться по- мощником, подчеркиваем помощником, человека при принятии решений в неопределенных условиях. Многие конструкторские бюро приступили к разработке промышленных интеллектуальных роботов. Не является фантастической посылка таких роботов в космос для выполнения недоступных человеку работ. Конструкто- ры недалекого будущего приступят к разработке многопроцессор- ных систем искусственного интеллекта и вплотную подойдут к построению эффективных моделей человеческого мозга. Конструирование сейчас и в будущем—это непрерывный твор- ческий процесс, основанный на диалоге человека с вычислитель- ной машиной. Уже сейчас кульманы в конструкторских бюро, на заводах и в научно-исследовательских институтах меняют на ав- томатизированные рабочие места, оборудованные периферийными устройствами, в частности электронными дисплеями, позволяющи- ми нетворческие, рутинные операции выполнять на ЭВМ, а рабо- ту, требующую мышления, взлета фантазии, оставлять конструк- тору. Всего лишь 15—20 лет назад появился новый термин «автома- тизация проектирования и конструирования», обозначающий новое бурно развивающееся направление науки и техники. Методы авто- матизированного и автоматического конструирования и проекти- рования обладают огромными преимуществами по сравнению с методами неавтоматизированного проектирования. Сокращаются сроки проектирования ЭА, снижается стоимость, повышается на- дежность устройств. Конструктор-технолог ЭА, вооруженный современной аппарату- рой, знаниями в области микроэлектроники, электронной техники и автоматизации конструирования, в настоящее время—это вы- сококвалифицированный специалист, способный сочетать творче- скую фантазию с возможностями современных вычислительных машин. 1. ОБЩИЕ ВОПРОСЫ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ И КОНСТРУИРОВАНИЯ 1.1. ЭТАПЫ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ И КОНСТРУИРОВАНИЯ В общем случае процесс автоматизации проектирования схем ЭА, как и любых дискретных устройств, состоит из трех основных этапов: системотехнического, схемотехнического и конструктор- ского. 7. Системотехническое проектирование 1.1. Системное проектирование 1.2. Структурное проектирование Z. Схемотехническое проектирование 2.1. Логическое проектирование Z.Z. Моделирование Z.3. Контроль и Выработка диагностических тестов 3. Конструкторское проектирование 3.1. Техническое проектирование J.Z. Технологическое проектирование Первый этап включает в себя системное и структурное проек- тирование. Схемотехническое проектирование состоит из модели- рования, логического проектирования, а также контроля и пост- роения диагностических тестов. Конструкторский этап вклю- чает техническое и технологи- ческое проектирование. Одна из возможных укруп- ненных структурных схем про- цесса автоматизированного проектирования ЭА показана на рис. 1.1. При системном проектиро- вании используются идеи и ме- тоды системного анализа. На основе многочисленных факто- ров проводится всесторонний анализ технического задания на разработку ЭА и принима- ется решение относительно ме- тодики построения и путей реа- лизации вычислительного про- цесса. При структурном проекти- ровании разрабатываются об- щая структурная схема ЭА И Рис. I.I. Структурная схема процесса алгоритмы выполнения отдель- автоматизированного проектирования ных операций. Для выбора структуры необходимо учиты- вать требования технологичности, надежности, возможности более широкого использования однородных и квазиоднородных унифи- цированных узлов. Системотехнический этап проектирования в основном пока яв- ляется неформализованным процессом. Здесь используются твор- 7 4'еские возможности инженера. Электронная вычислительная ма- шина просматривает варианты решений, принимаемых разработ- чиком, и выбирает из них оптимальный. На этом этапе исполь- зуются специальные языки, формальные методы генерации вари- антов вычислительного процесса по исходному заданию методом автоматического получения структурных схем. На этапе схемотехнического проектирования широко исполь- зуются логические и вычислительные возможности ЭВМ. Целью логического проектирования ЭА является автоматический или ав- томатизированный формализованный абстрактный и структурный синтез узлов, выбранных в результате структурного проектирова- ния, при котором проверяется эквивалентность исходного задания конечному результату. В теоретическом плане здесь имеются су- щественные достижения: автоматически синтезируются управля- ющие и специального вида операционные устройства. На практи- ке при автоматизации логического проектирования схем требуется решение большого числа задач. К ним относятся: разработка эф- фективных языков описания исходных заданий и языков струк- турного проектирования, алгоритмов построения формальных мо- делей устройств и др. При логическом проектировании важней- шими критериями оптимизации являются: минимизация числа ТИ- РОВ логических узлов, достижение максимальной однотипности логических блоков, возможность эффективного моделирования и диагностирования схем, максимальный учет требований конструк- торского и технологического проектирования. Задачей моделиро- вания являются построение карты состояний для логических сиг- налов, проверка временных соотношений при прохождении вход- ных сигналов, анализ функциональных схем на соответствие за- данной системе булевых функций. Различают физическое и мате- матическое моделирование. Для схем ЭА более важным является математическое моделирование, так как использование сложных интегральных микросхем в основном исключает возможность фи- зического моделирования. Отметим, что согласно ГОСТ 17021—75 в книге под интеграль- ной микросхемой понимается микроэлектронное изделие, выполня- ющее определенную функцию преобразования и обработки сигна- ла и имеющее высокую плотность упаковки электрически соеди- ненных элементов и кристаллов, которое с точки зрения требова- ний к испытаниям, приемке, поставке и эксплуатации рассмат- ривается как единое целое. Интегральная микросхема 1-й степени интеграции (ИМС1) — это микросхема, содержащая до 10 элементов и компонентов включительно. Интегральная микросхема 2-й степени интеграции (ИМС2) — это микросхема, содержащая свыше 10 до 100 элементов и ком- понентов включительно. Интегральная микросхема 3-й степени интеграции (ИМСЗ) — это микросхема, содержащая свыше 100 до 1000 элементов и ком- понентов включительно. 8 Интегральная микросхема 4-й степени интеграции (ИМС4)— это микросхема, содержащая свыше 1000 до 10000 элементов и компонентов включительно. Интегральная микросхема 5-й степени интеграции (ИМС5) — это микросхема, содержащая свыше 10000 до 100000 элементов и компонентов включительно. Интегральная микросхема 6-й степени интеграции (ИМС6) — это микросхема, содержащая свыше 100 000 до 1000000 элемен- тов и компонентов включительно. Большая интегральная микросхема — это интегральная микро- схема, содержащая 500 и более элементов, изготовленных по би- полярной технологии, 1000 и более элементов, изготовленных по МДП-технологии. Микропроцессор—это программно-управляемое устройство, осуществляющее процесс обработки цифровой информации и уп- равление им, построенное на основе одной или нескольких боль- ших интегральных микросхем. Элемент интегральной микросхемы—это часть ИМС, не выде- ляемая как самостоятельное изделие, выполняющее функцию ка- кого-либо электрорадиоэлемента (транзистора, диода и т. п.). Компонент интегральной схемы —это часть ИМС, реализую- щая функции какого-либо электрорадиоэлемента, которая может быть выделена как самостоятельное изделие. Развитием подэтапа моделирования являются контроль и ди- агностика. При этом определяется методика построения схем ап- паратного контроля, разрабатываются системы тестового обслу- живания, определяются необходимые степень и уровень резерви- рования для выбора минимальной ремонтируемой единицы. Это связано с увеличением надежности используемых элементов и ук- рупнением типовых элементов замены в устройствах. Функциональные схемы, полученные в результате логического синтеза и моделирования, служат входной информацией для кон- структорского (технического, монтажно-коммутационного, фи- зического) проектирования. При этом необходимо решать следу- ющие основные задачи: покрытие функциональной схемы ячейка- ми из заданного набора, т. е. переход к принципиальной электри- ческой схеме устройства; компоновка элементов схемы в типовые элементы замены (ТЭЗ) —ремонтопригодные конструктивные еди- ницы, панели, блоки, стойки и т. д.; размещение элементов в кон- структивных единицах по различным критериям; распределение цепей по слоям—многослойная или двухслойная трассировка и контроль правильности полученной топологии. Цель технологического проектирования состоит в автоматизи- рованной выдаче технологических документов, разработке алго- ритмов управления координатографами и другими периферийными устройствами и методов автоматического получения фотошабло- нов, служащих руководящими материалами в системе производ- ства. Одной из важнейших задач проблемы автоматизации проекти- рования, конструирования и изготовления схем является автома- тизация конструкторского проектирования. В книге обсуждаются вопросы разработки и исследования ме- тодов, алгоритмов и систем автоматизации проектирования с ис- пользованием методов современной математики. Основу проекти- рования составляют математическое описание задач проектиро- вания на заданном формальном языке, разработка основных тео- рем и алгоритмов, структуры системы, запись программ на алго- ритмическом языке и решение их на универсальной или специа- лизированной ЭВМ с дальнейшим выходом на автоматизирован- ные рабочие места (АРМ) и другое 0'борудование. Для большинства задач проектирования формальное разбие- ние процесса поиска часто затруднительно. Если задачи проекти- рования сформулировать в теоретико-множественном плане, то обычно приходится встречаться с вопросами, которые могут быть решены, только если перебрать большое число вариантов. Поэтому актуальным является вопрос нахождения экономичных способов сокращения перебора. При этом существенную роль играет воп- рос о формальном описании тех или иных неформально постав- ленных задач, методах их расчленения на отдельные шаги, а так- же об организации оптимальных в том или ином смысле процедур поиска вариантов проектирования. Использование аппарата теории графов в настоящее время для решения задач автоматизации проектирования и конструиро- вания самых различных объектов находит все более широкое применение. Объясняется это тем, что язык теории графов во мно- гих случаях адекватен в той или иной мере объектам проектирова- ния, описывает их естественным образом и в то же время позволя- ет абстрагироваться от конкретных объектов и иметь дело с аб- страктными моделями. Это в свою очередь дает возможность строить математически обоснованные алгоритмы проектирования, находить простые и высококачественные решения, рационально и эффективно использовать ЭВМ. Следует отметить, что точное ре- шение задач проектирования большой размерности связано с пе- ребором большого числа вариантов, который затруднителен даже для ЭВМ. Поэтому в работе наравне с точными методами проек- тирования, основанными на методах исследования операций, рас- сматриваются алгоритмы направленного поиска, которые не дают оптимальных решений, но позволяют получать достаточные для практических целей результаты. 1.2. ЗАДАЧИ ПОСТРОЕНИЯ СИСТЕМ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ Главными проблемами при создании систем автоматизирован- ного проектирования (САПР) являются улучшение качества кон- струирования и создание средств, обеспечивающих решение прин- ципиально новых задач, выдвигаемых техническим прогрессом. 10 В общем случае системой автоматизированного проектирова- ния или конструкторского проектирования можно считать некото- рый комплекс алгоритмов с диспетчером, реализованный в виде множества программ, объединенных в пакеты, библиотеки или модули, и автоматизированных рабочих мест, включающих необ- ходимое для выпуска конструкторской документации оборудование. Идеальная система автоматизированного проектирования предпо- лагает такой порядок работ, когда техническое задание, сформу- лированное конструктором, полностью обрабатывается с помощью ЭВМ. Система программ определяет порядок их следования и тем самым последовательность выполнения отдельных этапов. На выходе ЭВМ индуцируется модель топологии устройства в виде документации для системы автоматизированного управления тех- нологическими процессами. Однако даже самые современные ЭВМ не могут заменить кон- структора, а лишь способны дополнить его, выполняя нетворче- ские, рутинные операции. Поэтому в настоящее время наиболь- шее распространение получили интерактивные системы «человек— машина», работающие в режиме диалога конструктора с ЭВМ. Они особенно эффективны при анализе и решении комбинаторно-ло- гических задач этапа конструкторского проектирования схем. Ин- терактивные системы должны иметь такую организацию, при ко- торой оптимальным образом сочетаются процессы автоматизиро- ванного проектирования с указаниями конструктора, творчески направляющего процесс разработки. Следующим, не менее важ- ным фактором, влияющим на структуру системы, является опре- деление области ее применения и выбор методологии конструиро- вания. Такая постановка задачи связана с неэффективностью уни- версализации используемых в системе алгоритмов и программ с целью их применения к различным конструкциям. Поэтому целе- сообразно включение в систему программ-диспетчеров, с помощью которых производится управление остальными программами. На- личие диспетчера позволяет также решить следующие важные вопросы организации системы: возможность свободного «входа» •в систему на всех этапах конструирования с целью корректировки промежуточных результатов, возможность использования как па- кетов, так и единичных программ, организация наиболее рацио- нальной последовательности этапов разработки. Выполнение рассмотренных выше требований становится необ- ходимым при поэтапной организации процесса конструирования. При этом работоспособность системы будет во многом зависеть от надежности и удобства стыковки отдельных этапов. Это дости- гается с помощью унификации входной и выходной информации, единства методов ее записи на носителях, распределения памяти ЭВМ и т. д. Значительное место при организации САПР отводится выбору алгоритмического языка, достаточно простого для описа- ния входной, первичной информации и доступного конструктору. Отметим, что определяющим фактором создания САПР является обязательный количественный или качественный выигрыш от ав- 11 томатизации, существенно превосходящий те дополнительные за- траты труда, которые она вызывает. Система должна обладать высокой жизнеспособностью, т. е. легкой настраиваемостью, воз- можностью изменения критериев оптимизации, способностью к расширению и дополнению библиотеки программ, стыковки с дру- гими системами проектирования и процессами автоматизирован- ного производства. В настоящее время САПР развивается в двух направлениях: с одной стороны, широко используются мини- и микро-ЭВМ и микропроцессоры с непосредственным участием конструктора. С другой стороны, создаются системы автоматического проектиро- вания на основе многопроцессорных вычислительных структур без участия человека. Считается, что последнее направление наиболее перспективное. В обоих направлениях определяющими остаются вопросы оптимизации алгоритмов, формализации задач конструи- рования, представления информации в ЭВМ, организации библио- тек программ и др. Система автоматизированного проектирования должна иметь возможности: автоматического хранения информации о проекти- руемом устройстве; последовательного расширения и совершенст- вования системы, активной связи «конструктор—система»; опе- рировать оптимальными взаимозаменяемыми алгоритмами конст- руирования, специализации систем на конструирование ЭА на ИМС любой степени интеграции; увеличения мощности системы применением многопроцессорных вычислительных структур и пе- риферийных устройств; стыковки со специальными автоматами (координатографами, графопостроителями и т. д.); изготовления конструкторской и технологической документации. Качество САПР характеризуется не только возможностью ис- пользования системы для проектирования широкого класса ЭА без существенных изменений, но и оптимальностью алгоритмов и способом представления информации. Основным требованием к размещению информации в памяти ЭВМ является свободный доступ к данным, т. е. такая организа- ция их хранения, при которой разработчик получит возможность на всех этапах конструирования быстро просматривать все имею- щиеся параметры с целью выбора требуемых. Не менее важна правильность построения языка проектирова- ния (ЯП), т. е. языка, предназначенного для представления и пре- образования описаний объектов при проектировании. Согласно ГОСТ 22487—77 различают: входной язык проектирования, пред- назначенный для представления задания на проектирование; ба- зовый язык проектирования, предназначенный для представления дополнительных сведений к первичному описанию объекта проек- тирования, проектных решений, описаний проектных процедур и их последовательности; выходной язык проектирования, предназ- наченный для представления какого-либо проектного решения, включая результат проектирования в форме, удовлетворяющей требованиям его дальнейшего применения. 12 Правильность выбора алгоритмов является одним из факто- ров, определяющим экономическую эффективность использования САПР. Такая постановка вопроса требует проведения работ, на- правленных на дальнейшее совершенствование математического, информационного, технического, лингвистического, методического, организационного и программного обеспечении САПР. Математическое обеспечение (МО) автоматизированного про- ектировани (МОАП)—это совокупность математических методов, моделей и алгоритмов проектирования, необходимых для его вы- полнения. Техническое обеспечение (ТО) автоматизированного проекти- рования — это совокупность взаимосвязанных и взаимодействую- щих технических средств, предназначенных для его выполнения. Программное обеспечение (ПО) автоматизированного проек- тирования (ПОАП)—это совокупность машинных программ, пред- ставленных в заданной форме. Соответственно пакет прикладных программ (ППП)—это совокупность представленных в заданной форме машинных программ, необходимых для выполнения проект- ной процедуры. Часть ПО АП, предназначенная для управления проектированием, называется операционной системой (ОС) авто- матизированного проектирования. Информационное обеспечение (ИО) автоматизированного про- ектирования — это совокупность представленных в заданной форме сведений, необходимых для выполнения АП. Составной частью информационного обеспечения САПР явля- ются автоматизированные банки данных (АБД), которые состоят из базы данных (БД) и системы управления базами данных (СУБД). Автоматизированные банки данных создаются как об- служивающие подсистемы САПР и предназначены для автомати- зированного обеспечения необходимыми данными подсистемы САПР. Управление АБД осуществляется специалистами, обеспечива- ющими целостность, правильность, эффективность использования и функциональные возможности. К АБД предъявляются требования гибкости, надежности, на- глядности и экономичности. Лингвистическое обеспечение (ЛО) автоматизированного про- ектирования — это совокупность языков, представленных в задан- ной форме проектирования с терминами и определениями, правил формализации естественного языка и методы сжатия и разверты- вания текстов, необходимые для выполнения АП. Методическое обеспечение (МТО) автоматизированного проек- тирования — это совокупность документов, устанавливающих со- став и правила отбора и эксплуатации средств обеспечения про- ектирования. Организационное обеспечение (00) автоматизированного про- ектирования—это совокупность документов, устанавливающих со- став проектной организации и ее подразделений, связи между ними, их функции, а также форму представления результата про- 13 ектирования и порядок рассмотрения проектных документов, необ- ходимых для выполнения автоматизированного проектирования. Тогда под комплексом средств автоматизации проектирования понимается совокупность различных видов его обеспечения (рис. 1.2). КСАП Е ? j МО ) 1 ПО 1 L" pE ? [мто] J оо 11-,-J 1———J 1—^{п11?0)j< | KCAnt—-—I ППрОг|—*- : - / -JnnpO^J Подразделения Проектной- организации Рис. 1.2. Комплекс средств автоматизации проектирования Рис. 1.3. Система автоматизиро- ванного (автоматического) про- ектирования Теперь можно формально определить, что такое САПР (рис. 1.3). Система автоматизированного проектирования—это комплекс средств автоматизации проектирования, взаимосвязанных с необ- ходимыми подразделениями проектной организации или коллек- тивом специалистов (пользователем системы). Для достижения целей создания эффективных САПР ЭА необ- ходимо осуществлять: автоматизацию процесса поиска, обработки и выдачи информа- ции; совершенствование проектирования на основе применения ма- тематических методов и средств вычислительной техники; использование методов оптимизационного и многовариантного проектирования; создание единых банков данных, содержащих систематизиро- ванные сведения справочного характера; <ц повышение качества оформления проектной документации и до- ли творческого труда конструкторов за счет автоматизации не- ^ творческих работ; унификацию и стандартизацию методов проектирования; взаимодействие с САПР различного уровня и функционального назначения. Составными структурными частями САПР являются подсисте- мы, обладающие всеми свойствами систем и создаваемые как са- мостоятельные системы. По назначению подсистемы САПР разделяются на два вида: проектирующие и обслуживающие. К проектирующим относятся подсистемы, выполняющие проектные процедуры и операции, а к обслуживающим относятся подсистемы, предназначенные для под- держания работоспособности проектирующих подсистем. 14 В зависимости от отношения к объекту проектирования разли- чают два вида проектирующих подсистем: объектные и инвари- антные. К объектным относятся подсистемы, выполняющие одну или несколько проектных процедур или операций, непосредственно зависимых от конкретного объекта проектирования. К инвариант- ным относятся подсистемы, выполняющие унифицированные про- ектные процедуры и операции. Рассмотрим существующие согласно ГОСТ 23501.8—80 клас- сификации САПР. По типам объектов проектирования различают САПР: изделий машиностроения и приборостроения; технологических процессов в машиностроении и приборострое- нии; объектов строительства; организационных систем. По сложности объектов проектирования различают САПР: простых объектов, проектирующих объекты до 102 составных частей; объектов средней сложности, проектирующих объекты свыше 102 до 103 составных частей; сложных объектов—свыше 103 до 104 составных частей; очень сложных объектов—свыше 104 до 106 составных частей; объектов очень высокой сложности—свыше 106 составных ча- стей. По уровню автоматизации проектирования различают САПР: низкоавтоматизированного проектирования, в которых количе- ство автоматизированных проектных процедур (АПП) составля- ет до 25% общего количества проектных процедур; среднеавтоматизированного проектирования, в которых количе- ство АПП составляет свыше 25 до 50% общего количества про- ектных процедур; высокоавтоматизированного проектирования, в которых коли- чество АПП составляет свыше 50% общего количества проектных процедур. По комплексности различают САПР: одноэтапные; многоэтапные; комплексные. По характеру выпускаемых проектных документов различают САПР: текстовых документов; текстовых и графических документов; документов на машинных носителях (перфокартах, перфолен- тах, магнитных лентах, дисках, барабанах); документов на фотоносителях; документов на двух типах носителей данных; документов на всех типах носителей данных. По производительности различают САПР: •15 малой производительности. Выпускает до 105 проектных доку- ментов (ПД) за год (в пересчете на 11-й формат); средней производительности. Выпускает свыше 105 до 106 ПД за год; высокой производительности. Выпускает свыше 106 ПД за год. По количеству уровней в структуре технического обеспечения различают САПР: одноуровневые, построенные на основе ЭВМ среднего или высо- кого класса с набором периферийных устройств; двухуровневые, построенные на основе ЭВМ среднего или высо- кого класса и одного или нескольких автоматизированных рабочих мест (АРМ) с мини-ЭВМ; трехуровневые, построенные на основе ЭВМ высокого класса, одного или нескольких АРМ и периферийного программно-управ- ляемого оборудования. Интегрированная САПР — это система, имеющая альтернатив- ное программное обеспечение и операционную систему автомати- зированного проектирования, позволяющую выбирать совокуп- ность машинных программ применительно к заданному объекту или классу объектов проектирования. Основными критериями при выборе алгоритмического языка (АЯ) можно считать: затраты машинного времени на реализацию программы, записанной в символах АЯ; удобство стыковки отдель- ных программ; наличие в языке средств описания информации специального вида; наличие современного математического обес- печения для выбранного языка; популярность языка; наличие трансляторов выбранного языка для широкого класса ЭВМ. Опыт создания САПР свидетельствует в пользу АЯ ФОРТРАН или подобных ему, как наиболее удовлетворяющих указанным Устройство подготовки данных MffCfEC ЭВМ) Реализация пакетов прикладных программ компоновки., разме щения, трассировки, контроля \ \ Сверлильные автоматы с ЧПЫ АРМ МФНУ Коне тру кторско- технологи. - \ ч е екая документация Технологическая линия произ- водства печатных плат, ин- тегральных микросхем Рис. 1:4. Техническое обеспечение САПР 16 критериям. Очевидно, требование наличия в языке средств описа- ния информации специального вида влечет к созданию специаль- ного входного и выходного языка, который должен связать от- дельные этапы конструирования, согласовать расположение ин- формации внутри массива. Техническое обеспечение САПР представлено на рис. 1.4. Ос- новой ТО является многопроцессорная вычислительная система (МВС) или, в частном случае, ЕС ЭВМ. Периферийное оборудо- вание ТО САПР можно условно разделить на четыре группы (рис. 1.5): 7. Дисплей. Z. Гртропо- З.АВонент- V. Координато- ноордикато- строитель чые гртр, сВерлиль сноп, АРМ пункты ныи аотомат •ГТ^ '—Г-" --Г-Г t 1Многопроцессорная Вычислительная система. ЕСЗВМ Рис. 1.5. Периферийное оборудование САПР для получения и обработки эскизной документации и диалога с МВС или ЭВМ 1; для получения выходной документации 2; для внутренних передач при работе САПР или для работы по линиям связи 3; для изготовления фотошаблонов и технологическое 4. Программное обеспечение САПР включает в себя специальные вычислительные программы, используемые для получения необхо- димой инженеру конструкторской документации. Особенностью таких программ является наличие модульной структуры. Каждый программный модуль имеет заданное целевое назначение, прост для разработки, гибок и надежен. Управление и координация использования модулей обеспечиваются наличием программы дис- петчера. Информация, используемая при автоматизированном проекти- ровании, располагается на нескольких уровнях и организуется в некоторую иерархическую систему. Эта система называется ар- хивом или банком данных. Основная функция архива заключается в выдаче информации по запросу заказчика. Информация выда- ется в виде чертежей, графиков, таблиц и т. п. Успешное применение программных модулей возможно только при наличии в ПО специальных программ, предусматривающих «гибкие» средства управления вводом, редактированием, хране- нием, пересылкой и выводом необходимой информации, а также средствами обработки пакетов прикладных программ, предназна- ченных для реализации отдельных этапов конструирования. Упрощенная схема вычислительного процесса конструкторско- го проектирования показана на рис. 1.6. Одна из возможных схем распределения информации в САПР показана на рис. 1.7. 17 Взаимодействие конструктора с системой выполняется на языке директив. С помощью входного транслятора эти директивы преоб- разуются в форму внутреннего представления и записываются в банк данных. На первом этапе производится запись директив, опи- ^~___-/' -—I Программные ^банк ^*" модули. /^—\ Г7————————| ^анны^ | Уормальная \ (Вх\^- Транслятор ——Г"--——--^-, модель \_^ Входного языка v^ ^-/ ' ' ' ' \ Компоновка | (Вы\^- Документиро- -——— | Размещение \ \_^/ вание —————' _ •———:———' 11 . __'____ —J управление \——1 *—- [Контроль| Рис. 1.6. Схема вычислительного процесса конструктор- ского проектирования Подсистема кон- троля и коррек- ции. результатов ^_^ биоли- < * отека —*' Подсистема Вы- дачи. нонструк- торско- техноло- гической доку- ментации Архив результатов Диспетчер г*—— Подсистема реше- ний задач кон- струирования Подсистема под- готовки входной информации Рис. 1.7. Распределение информации в САПР сывающнх объекты конструирования, при этом в банке данных производится формирование библиотеки. Набор директив включа- ет в себя задание на вызов из библиотеки всех элементов, входя- щих в объект конструирования, и задания на компиляцию необ- ходимого разработчику набора программных модулей. Другими словами, задаются состав программных модулей и последователь- ность их реализации. Результаты всех промежуточных решений, а также окончательное решение хранятся в банке данных. С помо- щью специального программного модуля «Документирование» производится преобразование рабочих массивов и выходной ин- формации из формы внутреннего представления в форму конст- рукторской и технологической документации. Программные моду- ли каталогизируются в создаваемой библиотеке. Организация вы- 18 числительного процесса и связь конструктора с банком данных осуществляются с помощью управляющей программы. Директива- ми служат операторы управления заданиями управляющей прог- раммы, по которым модули вызываются из библиотеки на испол- нение. Информация о разрабатываемой ЭА, хранящаяся в банке дан- ных, делится на три области. Первая область предназначается для хранения конструкторской информации, вторая—для хране- ния промежуточной информации, передаваемой от модуля к моду- лю, третья—для обеспечения режима прерывания. Здесь хранит- ся вся информация, необходимая для продолжения конструирова- ния с этапа, на котором произошло прерывание. Это позволяет производить параллельное конструирование нескольких устройств одновременно. Формирование документации производится в соответствии с требованиями рисующих автоматов (координатографов, графопо- строителей, дисплеев и т. д.). При этом используются данные из хранящихся в памяти ЭВМ таблиц, форматов и т. п. Кроме того, данные о результатах конструирования заносятся в архив систе- мы. При реализации задач конструкторского проектирования мож- но условно выделить следующие крупные блоки (рис. 1.8): ввод и контроль информации, построение формальной модели схемы, т. е. переход от схемы к графу, компоновка, размещение, трасси- ровка, выдача конструкторской документации. Блок компоновки обычно включает в себя модули, обеспечивающие покрытие схемы заданным комплексом элементов, а также различные алгоритмы разбиения графа схемы на конструктивно законченные части. Блок размещения составляется из модулей точного, итерационного и последовательного размещения с минимизацией суммарной длины и внутрисхемных пересечений. Блок трассировки включает модули определения планарности, планарного разбиения схемы, построе- ния кратчайших связывающих деревьев, распределения фрагмен- тов цепей по магистралям, получения координат трасс. Основные требования, предъявляемые к программным моду- лям в САПР,— это универсальность, адаптируемость, возможность параллельного решения нескольких задач конструирования, совме- стимость автоматического, автоматизированного и интерактивного режимов, развитие базы данных. Каждый блок в САПР в соответствии с иерархическим прин- ципом обработки информации образует подсистему. Исходная ин- формация в САПР делится на три типа: описание схемы, описание конструкции и управляющая информация. С помощью управляю- щей информации задаются режимы работы программных моду- лей конструирования. Блок ввода и контроля осуществляет ввод информации, формирование информации, необходимой для рабо- ты последующих программных модулей, контроль и размещение сформированной информации в банке данных. 19 Важнейшим вопросом при автоматизации конструирования ЭА является выбор альтернативных вариантов. При автоматизации конструирования (АК) цель задана и ее записывают обычно в виде f(\)=>max (min), где f—некоторая скалярная функция, на- 1————————I ® /.Описание ___"г___ схемы | ю. Размещение (конструктор) вершин грааза '————]————— на плоскости. 2. Контроль[ .^Га^у^^ \——————| описания \ <гхем'ы Ьан^ ,————1 , Т^^рен?^^ 15. Минимизация .^^^.Да ^^г^пп пересечений ^^.7 Схема^^_ ,————1—Ш.——ребер ^-^верна?^^ fZ.Tpaccu ровна ————,————i -^^'- печатнях i————I—————. гнет соединений '°- Разнесение I————1————i '————,—————1 цепей по сло- 4. Коррен тиров- ,———_»4»————— ям ко. схемы ,J^ •————]————' ' Ч fe^T^> \\'7-Трассиро6ка ,————1————, -••-^.waawZ-^ многослойного 5. Переход от -v^/ монтажа схемы к граан/ .————Г 11ет ————i—————• •————|————\_ 1Ч.Корректира8ка. I————'————| " трассировки 6. Покрытие схе- '——————————• мы номплен- •————t————————————' сом элементов i————1————i '————i————• 18. Компоновка |————|——-,——i ffT33 7. Тестовый •————i————' ^Р"^ I ^.Размещение \ \ч————, гээ____ в. Разбиение\ ,————I————, граааа схемы ZO. Трассировка на части проводных со- _____ ————т———единении \—————\ ^^Ра^би'^"' | 1 | i ZZ. Вы дача кон-] <.ение праВилу——1 21. Контроль {структорсмй ^^ное?^' информации 1а'окцментации [•^^ ^r L»———I i————-—————/ улд _____I uo) Рис. 1.8. Основные этапы автоматизированного конструк- торского проектирования пример надежность конструкции, диагностируемость ЭА и т. п.; х— вектор, определяющий управляемые (изменяемые) параметры, например число типовых элементов конструкции, причем Х={х'}, Os^x'sSx. Задачи такого вида решаются путем нахождения экстремума функции f(x} на некотором множестве X, т. е. f(x) => max(min). хех При автоматизации конструирования перед конструктором стоит задача с помощью ЭВМ выбирать способ действия, т. е. век- 20 тор, дающий максимальное (минимальное) значение нескольким функционалам: MX), fz(x), ,.., f^(x). Для решения задач такого типа обычно используются методы линейной свертки, контрольных цифр, компромиссы Парето и др. При использовании методов линейной свертки вместо v различ- ных критериев учитывают один комплексный ^(х)=|^,(х), где Ki — положительные числа, нормированные заданным образом. Коэффициенты Ki отражают представление конструктора о содер- жании компромисса, который он должен принять. Рассмотрим использование контрольных цифр. При автомати- зации конструирования ЭА на ИМС4 и ИМС5 часто задают систе- му нормативов, имеющих вид f*i, f*^, ..., f*v- Они означают, что па- раметры ЭА должны быть такими, что fi{\}=>ma\ при fi{\)^.f*i. В этом случае целевую функцию представляют в виде F(x)= =:mmfi{x}/f*i, а затем производят поиск вектора х, который дает возможность определить наибольшее значение ^"(х). Условие F(x) =?-max означает выбор такой системы значений х, которая максимизирует отношение i-го значения критерия к его контроль- ному значению. Отметим, что значения f*i обычно определяются в результате экспертного опроса или задаются конструктором из опыта работы. Компромиссы Парето. При решении многокритериальных задач прибегают к сокращению подмножества заведомо «плохих» реше- ний. Пусть сделан выбор х' и имеется другой выбор х" — такой, что для всех критериев справедливо MX") ^f,(x'). Тогда видно, что выбор х" предпочтительнее, чем выбор х'. Следовательно, век- торы х', удовлетворяющие неравенству, следует исключить из рас- смотрения. Предлагается исследовать только те векторы х, для которых не существует х" для всех критериев, удовлетворяющих приведенному неравенству. Множество таких векторов х называ- ется множеством Парето. Например, пусть цели автоматизации конструирования опреде- ляются двумя функциями: L(G)=^min и P(G)==^min, где L(G) — суммарная длина соединений в типовом элементе замены (ТЭЗ); P(G) —количество пересечений соединений в ТЭЗ. Тогда допустимому значению переменной x<=G будет соответ- ствовать одна точка на плоскости (L, Р). Равенства L==L(G) и P=P(G) определяют некоторую кривую У|г/2УзУ4 (рис. 1.9). К мно- р^ жеству Парето относится участок ' У2»/з. Участки у\уч и г/з5», «ИМС5-Й степени интеграции содержит меньше элементов на та- ком же кристалле, чем ИМС4-Й степени интеграции» являются ложью. В алгебре высказываний они рассматриваются с точки зрения их логических значений независимо от содержания. К основным логическим операциям над высказываниями отно- сятся: отрицание, конъюнкция, дизъюнкция, импликация, эквива- лентность. Отрицанием высказывания А называется новое высказывание, обозначаемое А, которое считается истинным, если Л ложное, и ложным, если Л истинно. Операция отрицания соответствует логи- ческой частице «не». Например, для истинного высказывания «ЕС ЭВМ состоят из ТЭЗ» отрицанием будет ложное высказывание «неверно», что ЕС ЭВМ состоят из ТЭЗ». Конъюнкцией высказываний А, В называется новое высказы- вание, обозначаемое А/\В (читается Л и В), которое считается ис- тинным, если А и В истинны, и ложным, если хотя бы одно из них ложно. Например, для двух высказываний: «2>0», «ИМС4 содер- жит больше элементов, чем ИМСЗ» — конъюнкция «2>0 и ИМС4 содержит больше элементов, чем ИМСЗ» будет истинным выска- зыванием. Дизъюнкцией высказываний А, В называется новое высказыва- ние, обозначаемое AVB (читается Л или В), которое считается истинным, если хотя бы одно из высказываний Л, В истинно, и ложным, если они оба ложны. Например, для двух высказываний: 27 «ТЭЗ содержит меньше интегральных микросхем, чем панель из нескольких ТЭЗ» и «З^Э» — дизъюнкция «ТЭЗ содержит меньше интегральных микросхем, чем панель 'из нескольких ТЭЗ или 32=Q» будет истинным высказыванием. Импликацией высказываний А, В называется высказывание, обозначаемое А->-В (читается «Л влечет В» или «если Л, то В»), которое ложно, если Л истинно и В ложно, и истинно для всех других логических значений Л, В. Например, высказывание «если 5х5=/= 25, то ЭВА третьего поколения строятся на основе ТЭЗ» истинно. Эквивалентностью высказываний А, В называется высказыва- ние, обозначаемое Л ^ В (читается «Л равносильно В» или «для того чтобы Л, необходимо и достаточно, чтобы 5»), которое счи- тается истинным, когда оба высказывания Л, В либо истинны, либо ложны, и ложным в остальных случаях. Например, выска- зывание «для того чтобы автоматически конструировать современ- ную ЭА, необходимо и достаточно иметь действующую систему автоматизированного проектирования» истинно. На рис. 2.1 показаны таблицы истинности для рассмотренных высказываний. Здесь и — истина, л — ложь. А А и. л Л U Отрицание ~А \ В ЦААВ U U U U Л Л лил л | л 1 л _ А в \ AVB и и и и л и л и и л л л Конъюнкция Дизъюнкция А В А—В 11 и и и л л л и и л л и А в А—В и и и и л л л и л л л и Импликация Эк В и Валентности Рис. 2.1. Таблицы истинности высказываний Дадим понятие квантора существования и квантора общности. Запись {^х(=Х)В(х) означает, что для любого элемента из мно- жества Х истинно высказывание В(х) об элементе х. Знак V на- зывают квантором общности. Запись {•^x(=X)B{x} означает, что существует хотя бы один элемент х^Х, для которого истинно высказывание В(х) об этом элементе. Знак э называют квантором существования. Объединением множеств А и В называется множество С, состоя- щее из элементов как множества Л, так и множества В. Обозна- чается C=AUB. Высказывание г/еЛиВ эквивалентно ye=Avy<=B. Например, при Л={транзистор, резистор}, В = {конденсатор, ин- дуктивность}, то С =AU 5= {транзистор, резистор, конденсатор, 28 индуктивность}. Если Л—множество точек левого прямоугольни- ка (рис. 2.2), а В — множество точек правого прямоугольника, то заштрихованная область есть Л U В. Рис. 2.2. Объединение мно- жеств С==А[}В Рис. 2.3. Пересечение мно- жеств С=А[\В Объединение множеств А\, Аг, An обозначается U Ai. Оно i=i состоит из всех элементов, которые принадлежат хотя бы одному из множеств Ль Ai, ••; An- „ Пересечением множеств Л 'и В называется множество С, состоя- щее из элементов, принадлежащих одновременно и множеству В, и множеству Л Обозначается С=ЛПВ. Следовательно, г/е=ЛПВ^ нмно^ст^ ^ л=<имc4•ЛMC5ллэмTЛPT^ naLa,pene},B={HMC4,HMC3}, то С=ЛПВ={ИМС4}. Если Л—множество точек левого прямоугольника (рис. 2.6), a D множество точек правого прямоугольника то зaштPиxoвaннaяoб- ласть есть Л П В. Пересечение множеств Ль Лз, ..., Л„ обозначает- ся П" Ai. Оно состоит 'из всех элементов, принадлежащих одновре- 1=1 я л Л менно множествам Ль Ai, •-, Лп- АПЛ—А Из определения пересечения множеств, следует, что ЛПА-л. Если множества Л и В не имеют общих элементов, то их пересе- чение представляет собой пустое множество. Разностью множеств А и В называется множество С, состоя- щее из элементов, принадлежащих Л и не "Р.™^^"^5,000" значается С=Л\В. Тогда уеЛ\ В <^е=ЛАу ^ В. Например, ес- ли Л^{ИМС4, ИМС5, ТЭЗ}, а В = {ИМС4, транзистор}, то Л \ В - = ШМС5 ТЭЗ} Если Л — множество точек левого прямоугольни- ка, а В-множество точек правого прямоугольника (рис. 2.4), то заштрихованная область есть множество С-Л\ о. Очевидно что Л \ BsA, В \А<=В. Когда Л°=В, то множество А=В\Л называется дополнением множества А до В. Для произвольного множества Л^_ можно определить дополнение до универсального множества М =/\ М. Для чюбого множества можно определить дополнение до любого другого мужества, включающего его. Если это не оговорено, то считаете? что дополнение берется до универсального множества /. Пример показан на рис. 2.5. Здесь заштрихованная область представляет собой Л=/\Л. 29 Рассмотрим основные свойства операций U, П, \ . Законы коммутативности AU5=BUA; ЛП5=ВПЛ. Законы ассоциативности AU(5UC)=(AUB)UC; ЛП(5ПС)=(ЛПВ)ПС. Законы дистрибутивности. ЛП(ВиС)=(ЛПВ)и(ЛПС); Ли(5ПС)=(ЛиВ)П(ЛиС). Законы идемпотентности лил=л; лпл=л. Законы де Моргана Л \ (5ПС) = (Л \5)U(A \С); Л \ (5UC) = (Л \5)П(Л \ С). Основным методом доказательств тождеств с множествами яв- ляется метод двух включений (или взаимного включения). Для доказательства E=F необходимо показать, что ?=FAF??. Чтобы У///////// Рис. 2.4. Разность множеств С=Л\Й Рис. 2.5. Дополнение Л=/\Л доказать, что Е^Р, требуется из истинности высказывания аеЯ вывести истинность высказывания asF. И, наоборот, для доказа- , тельства F^E необходимо из истинности высказывания ae.F вы- вести истинность высказывания ае=Е. Например, докажем справедливость ЛП(5иС)=(ЛП5)и(ЛПС); ^. -у Обозначим левую часть через Е, а правую — через F. Теперь не- обходимо доказать, что E=F. Это равносильно доказательству E^FAF^E. Пусть истинно высказывание ае.Е, тогда а(=г-^аеЕЛП(ВиС)-^ае=ЛЛае=(ВиС) ->- аеЛЛ(агВУаеС)-^ае | еЛЛаейУаеЛЛаеС -> ае (ЛПВ)Уае(ЛПС) -^ ае=(ЛП5)и и(ЛПС)-^аеР. 39 Пусть теперь истинно высказывание aef, тогда аe/7-^as(Лn5)U(ЛnC) -^ае:ЛЛае=ВУа<=ЛЛй(=:С ->- ас=ЛЛ(ае= (ЕЕ5УаеЕС)->-аеЕЛП (В[)С}->ае^Е, что и требовалось доказать. Иногда требуется доказать не равенство двух множеств, а ра- венство множества пустому множеству, т. е. Л=0. Обычно дока- зательство проводят методом от противного, т. е. предполагают что Л=т^0, следовательно, существует хотя бы один элемент а^Л, и тогда пытаются доказать, что предположение А=/= 0 является ложным и приводит к противоречию, на основании чего заклю- чают, что Л = 0 . Выше мы рассматривали неупорядоченные множества. Для за- дания упорядоченных множеств используется термин кортеж. По- нятие кортежа, как и понятие множества, является неопределяе- мым 'понятием. Кортеж состоит из компонент, для которых задает- ся местоположение. Обычно кортежи обозначаются греческими буквами, а их компоненты — латинскими. Например, а=^а, Ь, с, с, с). Такая запись означает, что кортеж а состоит из пяти компо- нент: а—расположенной на 1-м месте, Ь—на 2-м месте, с—на 3-м месте, с — на 4-м месте и с — на 5-м месте. Компонентами кортежей могут быть любые объекты, в том числе множества и кортежи. Кортежи а и |3 называются равными, если каждая компонен- та а совпадает с компонентой р с тем же номером. Например, а= =<9,5>=р=<9,5> и а=<5,9)^=р=<9,5). Следовательно, <а, Ь>= =^с, d)'—^{a=c)/\(b=d). Число компонент кортежа называют его длиной. Декартовым (прямым) произведением множеств A v. В назы- вают множество С, состоящее из всех различных кортежей дли- ны 2, первая компонента которых принадлежит Л, а вторая — В. Обозначается С=АХВ. Например, если Л={й, Ь}, В={х, г}, то С=ЛХВ={<а, х), }. Следовательно, для любого кортежа, являющегося элементом мно- жества С, истинно высказывание <а, x)sC=Ax5 ^(a^A)/\(xe.B}. Кортежи длины 2 называются упорядоченными парами, кортежи длины 3 — тройками и т. д. Декартовым произведением п множеств А\, As, ..., An называют множество C==AiXA<2X ... ХЛп, состоящее из всех кортежей дли- ны п, первая компонента которых принадлежит Ль вторая—Лз, ..., компонента п — An- Очевидно, что Лх5=0°Л=0 VB=0. Степенью s множества А называется декартово произведение одинаковых множеств Л, т. е. Л^ЛхЛх ... ХА. "Раз Считают Л^Л и Л°={0}, где 0—пустой кортеж. 31 Множество, каждый элемент которого является кортежем, на- зывается графиком. Для графиков определены две основные опе- рации: инверсия и композиция. Инверсия графика определяется через инверсию его кортежей. Кортеж ^х, у) есть инверсия корте- жа <р, <^>,если у=р и x=q. Обозначается а~1. Например, если а= =<.х, у), а-^^у, х). График R называется композицией графиков Р и Q, если (х, y)sP, тогда и только тогда, когда существует такое z, что } и 0={<у, у), <Ул z), <, , <3,1>}, и ={1,2,3}, то определим отношение (р=<{<1,2), <^2,2), <3,1)}, {1,2,3}). Графи- ческое изображение отношения ср показано на рис. 2.6. В кружках стоят цифры, соответствующие элементам отношения, а линии со стрелками показывают связь между элементами отношения. Отношение ф называется полным, если Ф=52, т. е. если выска- зывание ( Vх, у^В) [x({iy] всегда истинно. Отношение ср называется пустым, если Ф=0, т. е. если выска- зывание ( Vx, y<=B) (х(ру) всегда ложно. Отношение (р называется отношением равенства, если высказы- вание ( V х, у^В) (х(ру—>-х=у) истинно. Отношение ср называется отношением неравенства, если выска- зывание ( V,r, y^B) (х(ру->-х=?'=у) истинно. Заметим, что на отношение переносятся операции над множест- вами. Пусть <р1=\Ф1, В'/ и ср2="^Ф2, В') есть произвольные отноше- ния, заданные на одном и том же множестве В. Тогда объединением отношений (pi и фа называется отношение <рз, график которого Фз равен объединению графиков отношений 2—144 33 n>i и (pa: (рз^Ч^и^^Ф^Фа, 5). Очевидно, что x((pi U (р2.)г/ "• ^ (^cpiy)V (д-(р2У) • Аналогично определяются операции пересечения и разности отношений. Например, если (pi=<{, <Ь, с;?, <а, d>}, {а, Ь, с, d}), i tp2=<{}, {а, Ь, с, d}), то (рз=<р1П(р2=<Ф1ПФ2,В> =<{<". b). {b, с>}{а, Ь, с, d}/. Для отношений, заданных на одном и том же множестве, справед- ливы тождества, аналогичные тождествам над множествами. Также справедливы операции инверсии и композиции, которые рассматривались для графиков. Инверсией отношения ср на множестве В является отношение, график которого есть инверсия графика отношения (р=<Ф, В), т. е. ф-1=<ф-1, В). Следовательно, xw-^-'-y^x. Композиция отношений (pi=<0i, В) и ср2=<Ф2, В) определяется выражением q)з=(^)lC)Ф2=^ФlC><^'2, В/- Отношение удобно задать в виде прямоугольной таблицы (мат- рицы). Строки и столбцы матрицы отношений РФ соответствуют элементам х, у(=В. На пересечении строки, соответствующей эле- менту Xi, и столбца, соответствующего элементу х„ ставится еди- ница, если выполняется отношение хщ>х„ 'и нуль в противном слу- чае. Матрица отношения, показанного на рис. 2.6, 'имеет вид 1 2 3 Размер матрицы R

, где B={xi, хч, Хз, у\, yi}, Ф={<^г/1), <^2, УЧ/, <Хз, У\), <Хз, У2). <'/!, Xl), -х(рг). Отношение «находиться в одном кристалле ИМС» для транзи- сторов х, у, z является транзитивным отношением. Другими словами, если элементы х и у находятся на некото- ром кристалле ИМС и элементы у и г находятся на том же крис- талле, следовательно, на этом же кристалле будут находиться х и z. Отношение равенства является транзитивным, так как если х=у и y=z, то и л'=г. В практике автоматизации конструирования схем интерес пред- ставляют отношения, обладающие совокупностью свойств. Отношение (р называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Например, отношение «параллельности» прямых является отно- шением эквивалентности, так как а\\а (рефлексивность), а\\Ь—>-Ь\\а (симметричность), а||ЬЛЬ||с-»-а||с (транзитивность). Отношение «перпендикулярности» прямых не является отноше- нием эквивалентности, так как а не перпендикулярно а (рефлек- сивность не выполняется), а_1_Ь->-&_1_а (симметричность), а-1-йЛЬ_1_с не влечет а_1_с (транзитивность не выполняется). Отношение «находиться в одной и той же схеме ЭА» для ее элементов является отношением эквивалентности. Основное значение отношения эквивалентности состоит в том, что оно определяет признак, который допускает разбиение множе- ства М на непересекающиеся подмножества, называемые класса- ми эквивалентности. Все элементы, принадлежащие некоторому классу Mi разбиения множества М, связаны отношением эквива- лентности. 2* 85 Матрица Rq> отношения эквивалентности ср состоит из клеток (подматриц), расположенных по главной диагонали, причем все .элементы каждой подматрицы являются единицами. Матрица от- ношения эквивалентности может быть приведена к такому виду с :помощью перестановок строк и столбцов. Например, если пере- ставить строки и столбцы матрицы, записанной ниже, ее конфигу- рация изменится, но матрица не перестанет быть матрицей отно- шения эквивалентности. Пусть, например, на множестве .6= {ЭВМ, ЭВА, РЭА, ИМС4, ИМС5, ТЭ31, ТЭ32, ТЭЗЗ, ТЭ34} задано отно- шение эквивалентности «иметь одинаковую конструктивную реа- лизацию». Тогда множество В можно разбить на три класса, со- держащие. эквивалентные по заданному отношению элементы: Д1={ЭВМ, ЭВА, РЭА}, В2={ИМС4, ИМС5}, 5з={ТЭ31, ТЭ32, ТЭЗЗ, ТЭ34}. Матрица этого отношения запишется 1 1 1 0 о о 0 0 0 1 1 1 0 о о 0 0 0 1 1 1 0 о о 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 о о 0 1 1 1 1 0 0 о о 0 1 1 1 1 ЭВМ ЭВА РЭА ИМС4 ИМС5 ТЭ31 ТЭ32 ТЭЗЗ ТЭ34 ЭВМ ЭВА РЭА ИМС4 О ^Ф=ИМС5 О ТЭ31 ТЭ32 ТЭ32 ТЭ34 О Отношение эквивалентности позволяет разбивать множество, на котором задано отношение, на непересекающиеся классы, со- держащие эквивалентные между собой элементы. Дальнейшее пре- образование заданного множества позволяет вместо каждого клас- са исследовать один его произвольный элемент. Мы рассматривали отношения, в которых Ф могло состоять из кортежей длины 2. Такие отношения называются бинарными. Если Ф будет состоять из кортежей длины п, то в общем случае можно рассматривать п отношения. Отношение ф=<Ф, 5), заданное на множестве В, называется п, если Ф^^Bn. Отношение «образовать вычислительную систему из четырех микропроцессоров» на мно- жестве микропроцессоров одного типа является примером 4-го от- ношения. Моделью М называется совокупность множества В и конечного числа отношений, определенных на этом множестве: cpi=^0i, B'), ф2=<Ф2, В), ..., ф;=<Ф(, В>. В общем случае можно записать М=(В, Ф^ Фз, ..., Ф;). Гово- рят, что соответствие — это кортеж длины 3, первая компонента которой является подмножеством декартового произведения вто- 36 рой и третьей компонент: Г=(Ф, X, У), Ф^ХХУ, где Ф — график соответствия; Х—область отправления; У—область прибытия. Образом множества А при соответствии Г называется множе- ство Г (Л) тех элементов области прибытия У, каждый из которых соответствует в Г какому-нибудь элементу из Л. Например, пусть Г=<Ф, X, У>, где Ф={<а, 2>, <&, 3), <с, 2>, <Ь, 1)},Х={а,Ь,с}, У= {1,2,3}. Соответствие Г показано на ' рис. 2.7. Если Л={а, Ь}, то F'W А=-{а,Ь} Г(А)=Г({а, &})={!, 2, 3}. Из ^Л7^\ ^ примера видно, что Г(Л)^У. \~){. \?.}) v7) ^ Полным прообразом множест- ва В при соответствии Г называ- 1=<1'^ ется множество /^(В) тех эле- // ментов области отправления X, \^ каждому из которых соответст- г/д/ —————— —-— ^/у ^i вует какой-нибудь элемент 5s У. Рис. 2.7. Соответствие Г Если в примере (см. рис. 2.7) В ={1,3}, то Г-l(B)={b}, причем Г-ЧВ)^Х. Соответствие Г можно задать с помощью матрицы Rr разме- ром |Х|х|У|. Строки матрицы Rr соответствуют элементам х^Х, а столбцы — элементам y^Y. На пересечении i-й строки и /-го столбца ставится единица, если <^г, Ху')^Ф, и нуль в против- ном случае. Для соответствия Г=<^Ф, X, У), изображенного на рис. 2.7, матрица Rr примет вид а (I 1 и Rr = Ь 1 0 1 . с 0 1 О Над соответствиями можно выполнять те же операции, что и над множествами и отношениями. Соответствие ^=^Ф, X, У) называется функциональным, если график Ф не имеет кортежей с одинаковыми первыми и различ- ными вторыми компонентами, т. е. график не может иметь двух пар вида ^Xi, г/i), <^Хг, ys), y\^yi. В противном случае соответствие называется нефункциональным. Функциональное соответствие на- зывают однозначным, а нефункциональное — многозначным. При- мер функционального графика Ф={^а, 1)<Ь, 1)Хс, 1)<,d, !>} пока- зан на рис. 2.8. Соответствие Г=(Ф, X, Y) называется инъективным, если в гра- фике Ф не может быть двух пар вида ^х\, у^), (,Xz, г/j); x\=^Xt. В противном случае соответствие называется неинъективным. Соответствие Г=<,Ф, X, Y) называется всюду определенным, ес- ли для любого х^-Х образ Г(х) =^= 0 . Соответствие называется сюръективным, если для любого г/^У прообраз Г~l(y}^0. Произвольное соответствие Г=^Ф, X, Y^ 37 может обладать или не обладать любым из описанных свойств или их совокупностью. Соответствие Г=<,Ф, X, Y) называется биективным или взаим- но-однозначным, если оно функционально, инъективно, всюду оп- ределено и сюръективно, т. е. соотвествие Г взаимно-однозначно, если каждому элементу х соответствует один и только один эле- Рис. 2.8. Пример функцио- нального графика Ф Рис. 2.9. Взаимно-одно- значное соответствие меж- ду множествами Х и У мент у и наоборот. На рис. 2.9 показан пример взаимно-однознач- ного соответствия между множествами Х и У. Здесь а**3, b «-» 1, с ^2. Функциональные соответствия являются частным видом соот- ветствий, наиболее часто используемых при разработке алгоритмов автоматизированного конструирования ЭА. Они называются функ- циями 'и обычно обозначаются ^=<Ф, X, Y). Тот факт, что функция f имеет область отправления Х и область прибытия У, выражают словами: функция f определена в Х и принимает свои значения в У. Обозначается XJ^ У или f: X->-Y. Значение функции f на эле- менте а обозначается f(a). Если кортеж <х, у)^Ф, то образом элемента х при функции f будет элемент у. Это обычно обозначают f(x)=y и говорят, что функция f отображает элемент х^Х в эле- мент г/еУ. Элемент х называется аргументом функции f, а у — значением функции f на агрументе х. Функция ^=<Ф, X, У) называется нигде не определенной, если Ф^= 0 . Функция ^=<Ф, X, Y) называется всюду определенной, когда (V^J)(a^)]. Всюду определенную функцию называют отображением, а ото- бражение типа X_^.Y называют отображением множества Х в У. Функция f=^., X, Y) называется сюрьективной, если (VysV) (3 х^Х) [f{x) =у]. Функция ^=<Ф, X, Y) называется инъективной, если (VxsX)(3 У<=У) [f(y) =х]. Функция ^=<Ф, X, У> тогда и только тогда биективна, когда она всюду определена, сюрьективна и инъективна. Синонимом термину «биекция Х на У» является взаимно-однозначное отображение множества Х на У. Примеры сюрьективной, инъективной и биективной функции по- казаны на рис. 2.10, 2.11, 2.12 соответственно. Биективная функция или просто биекция типа t Х—>-Х назы- вается подстановкой на множестве X. Подстановку записывают в 38 виде двух строк, заключенных в круглые скобки, причем под эле- ментом хеХ записывается элемент t(x). Например, пусть Х= = {х\, xs, Хз, х^}. Тогда некоторая произвольная подстановка t мо- жет 'иметь вид fXi, Ха, Хз, Х^ \ t= xl, х^ Рис. 2.10. Сюрьективная функция /= (Ф, X, Y) Рис. 2.11. Иньективная функция /= (Ф, X, У) Такая запись означает, что элемент х\ отображается в Хч\ х-г— в Х4; Хз — в xi и ХА — в Хз. Существуют 'и обратные подстановки, которые можно применять для возвращения в исходное состояние. Для рассматриваемого примера ^Xi, Xs, Хц, Xt \ <Хз, Х\, Х^, Хч ) Отметим, что для соответствий и функций также справедливы все операции над множествами и отношениями. В практике конструирования часто приходится иметь дело с множествами, в которых нельзя указать резкую границу, отделяю- щую элементы, принадлежащие ж данно- му множеству и не принадлежащие к не- му. Такие множества называют расплыв- чатыми или 'нечеткими. Следует отличать понятия случайности и расплывчатости. Случайность связана с неопределенно- стью, относящейся к принадлежности или непр'инадлежности элемента к множеству. Расплывчатость связана с множествами, в которых могут иметься различные сте- пени принадлежности элементов к дан- ному множеству. Рис. 2.12. Биективная функ- ция /= (Ф, X, У) Пусть задано множество Х={х\, хч, ... —, Хп}. Тогда говорят, что расплывчатое множество А на множестве Х есть сово- купность кортежей A={<^(^i); л-г)}, Хг^Х, где \ад (хг) —степень принадлежности элемента л-» к Л; (ЛА —функция, отображающая -с, 39 в пространство М, называемое пространством принадлежности. Предполагается, что М—это интервал [0,1], причем 1 и 0 пред- ставляют высшую и низшую степени принадлежности. Заметим, что степень принадлежности может являться расплывчатым мно- жеством. Основное положение теории расплывчатых множеств состоит в том, что Л, несмотря на «размытость» границ, задается точно пу- тем сопоставления каждому элементу х^Х, числа, лежащего меж- ду 0 и- 1. Например, пусть Х={\, 3, 5, ...}—множество положительных нечетных чисел. Тогда расплывчатое множество Л можно, напри- мер, определить как набор кортежей вида Л ={<(),6; 1), ^0,2; 3'), <0,7; 5>....}. Носитель Л есть множество элементов х<=Х, для которого ^л(х) положительно. Точкой перехода Л называется элемент х<=Х, для которого [Лд(х)=0,5. Одноточечным расплывчатым мно- жеством (иногда используют термин нечеткие или размытые мно- жества) называется множество, носитель которого состоит из един- ственной точки. Если А — одноточечное расплывчатое множество, то его обозначают А=[Л,/Х, где [А,—степень принадлежности х к Л. Тогда одноточечное множество можно обозначить A=\jx. Расплывчатое множество часто рассматривают в виде объеди- нения входящих в него одноточечных множеств и записывают в виде A=J ^л(х)1х, Х(=Х. х Здесь знак интегрирования означает объединение одноточечных расплывчатых множеств ^д(х)/х. Если А состоит из конечного числа элементов, то п A==Ul/XiULl2/^2U ... Ul^n/^n=U^i/^i. t=l Очевидно, что' тогда конечное множество X={xi, х^, ..., x,i} можно записать в виде J=l/^iUl/X2U ... []Цхп== 3 \1х„ Пусть Х= {кристалл, плата, панель}; А—расплывчатое множе- ство, определяемое признаком «степень интеграции (СИ) элемен- тов». Тогда, например, можно записать: А=СИ большая/крис- талл U CPI средняя/плата U СИ малая/ панель. Расплывчатые сте- пени принадлежности большая, средняя, малая в данном примере можно определить как расплывчатые подмножества множества W={0- 01- 02- • 1}. Эти подмножества можно определить, на- пример, так: малая = 0,5/0,2 U 0,7/0,3 U 1/0,4; средняя = 0,6/0,4 U U 0,8/0,5 U 1/0,6; большая = 0,7/0,7 U 0,8/0,8 U 1/1. Приведем еще ряд примеров расплывчатых множеств. 40 Пусть Х={1, 2, ..., 20}, тогда расплывчатое множество' А на X, описываемое понятием «много», можно, например, записать в виде «много» = 0,5/10 U 0,6/11 U 0,7/12 U 0,8/13 U 0,9/14 U 0,9/15 U 0,9/16 U •UO,9/17UO,9,'18U 1/19 U 1/20. Пусть X — множество ЭВМ первого', второго, третьего и четвер- того поколений, запишем это так: Х= {ЭВМ1, ЭВМ2, ЭВМЗ, ЭВМ4}. Пусть А — расплывчатое множество, определяемое термином «эф- фективный» в смысле времени решения задач на ЭВМ. Тогда ус- ловно можно, например, записать А = эффективные очень сла- бо/ЭВМ! U эффективные слабо/ЭВМ2 U эффективные средне/ЭВМЗЦ U эффективные достаточно/ЭВМ4. Здесь, как и в ранее рассмот- ренных примерах, термины «очень слабо», «слабо», «средне», «до- статочно» можно 0'пределить с помощью расплывчатых множеств: Г={1, 2, 3, 4}; «очень слабо»= 1/1UO,7/2UO,1/3UO/4; «слабо»=0,7/Ш1/2иО,2/ЗиО/4; «достаточно» = О/1 UO,3/2UO,7/3U 1/4. В практических задачах конструирования функция принадлежно- сти VLA определяется эвристически из конкретных условий. Рас- плывчатые множества А и В 'называются равными, если (V х<=Х} ([Л,А(х)=1Лв{х}}. Расплывчатое множество А является подмножеством В{Ас^В), если (Vx<^X) (^д(х) s^^B(x)}. Расплывчатое множество А4 назы- вается дополнением к А, если ( Vx^X) (^л{х) =- \—^А(х)). Напри- мер, расплывчатые множества .4= {«большие» микросхемы} и А*= = {«небольшие» микросхемы} являются дополнениями друг к дру- гу, если отрицание «не» определяется как операция, заменяющая у1л(х) на 1—[iA{x}, V x^X. Говорят, что расплывчатое множество С называется пересече- нием множеств А и В, если оно определяется как наибольшее рас- плывчатое множество, содержащееся как в А, так и в В: С'=АП5; ЦА п в (х} = mm (ЦА (х), цд (х)), х^Х. Например, если А= {<0,7/ИМСЗ>, <0,3/ИМС5>, ^/ИМС^}, В= = {<0,3/ИМСЗ\ <0,2/ИМС5>, <1/ИМС1>}, тогда С=ЛПЯ= ={<0,3/ИМСЗ\ <0,2/ИМС5>, <0,9/ИМС1>}. Если А={<0,8/1>, <0,5,'3>}, а 5= {<0,2/1\ <0,7/3)}, тогда С= -АПВ={<0,2/1), <0,5/3>}. Объединением расплывчатых множеств А и В называется наи- меньшее расплывчатое множество С, содержащееся как в А, так и в В: C=AU5; [.IA u в (д')=тах(^А (•»")_), х^Х. Пусть А—множество ИМСЗ, а В—множество ИМС1, тогда С=Аив={ИМСЗили ИМС1}. Расплывчатым отношением ср на декартовом произведении мно- жеств XxY={(x, y'/, x^X, уеУ} 'называется выражение, описы- ваемое функцией принадлежности (icp, которая сопоставляет каж- дому кортежу (.х, у/ его степень принадлежности ^<р {^.х, г/)) к (р. Пусть Х={РЭА, ЭВА}, У=={ИМСЗ, ИМС1}. Тогда бинарное расплывчатое отношение «компоновка» между элементами мно- 41 жеств X и У можно, например, записать следующим образом: JCoAtnowoe/ca = <0,7/(РЭА, ИМСЗ)> U <0,9/(РЭА, ИМС1)> U U<0,8/(3BA, ИМС1)>и<0,1/(ЭВА, ИМСЗ)>. Расплывчатые отноше- ния удобно задавать с помощью матрицы отношений Rд'га'jSk. Работа машины Тьюринга состоит в изменении конфигураций. Конфигурацией машины Тьюринга называется ее полное состоя- ние, по которому можно однозначно определить дальнейшее пове- дение машины. Оно обозначается тройкой ai9iq'ia'jSk, кото- рая переводит k в k'. Совокупность всех команд, которые может выполнять машина Тьюринга, называется программой. При решении задач со входны- ми данными сопоставляется начальная конфигурация ky, а выход- ные данные определяются заключительной конфигурацией, в ко- торую машина Тьюринга переводит kg. Например, рассмотрим машину Тьюринга, переводящую после- довательность ai, as, ..., а-п в последовательность &i, by., .... bn, ра- ботающую в конфигурации, показанной на рис. 2.14,6 в соответ- ствии с программой qiaj->q'ibjSk. Считывающая головка, переме- щая ленту направо в соответствии с программой, будет стирать символы ai, az, ..., а.п и вместо них соответственно записывать вы- ходные символы b\, &2, ..., Ьп. Если потребовать, чтобы при про- смотре клетки ленты с пустым символом машина Тьюринга пере- ходила в заключительное состояние, то после остановки машины на ленте будет выходная последовательность Ь\, Ь^, ..., bn. Было показано, что на машине Тьюринга можно имитировать все алгоритмические процессы, которые когда-либо описывались математически. Тьюринг показал, что если проблемы не могут быть решены на его машине, то они не могут быть решены ни на какой другой автоматической ЭВМ, т. е. это проблемы, для которых алгоритмы не могут быть составлены даже в принципе. Следовательно, не- возможность построения машины Тьюринга означает отсутствие алгоритма решения данной проблемы. Следует отметить, что речь идет об отсутствии алгоритма, решающего всю данную проблему, что не исключает возможности решения этой проблемы в частных случаях различными для каждого случая методами. Один из основных результатов Тьюринга — разделение всех представляемых в математике проблем на два класса: 47 Предполагается, что в будущем еще более возрастут темпы автоматизации разработки новых средств РЭА и ЭВА на основе комплексных САПР. Причем основное внимание будет уделено разработке модульных САПР, способных настраиваться на реше- ние любых задач, принимать решения в расплывчатых условиях, анализировать техническое задание, производить выбор из не- скольких альтернативных вариантов, производить оптимизацию конструкции ЭА по комплексным критериям, учитывать требова- ния на механическую прочность, тепловые режимы, электромаг- нитную совместимость, оптимально анализировать электронные схемы и синтезировать конструкции, производить совместное про- ектирование, учитывая требования логического, конструкторского и технологического проектирования. Основными теоретическими вопросами при разработке матема- тического обеспечения САПР ЭА, по мнению авторов, явятся: ис- следование оптимальных графо-теоретических моделей конструк- ций ЭА; назначение элементов, контактов схем; совместная ком- поновка с размещением на основе комплексных критериев; опре- деление планарности и эффективная плоская укладка соединений; оптимальное расслоение соединений; параллельная трассировка соединений. В настоящее время наблюдается стремление к универсализа- ции алгоритмов конструирования, разработке совместных контро- лепригодных алгоритмов компоновки, размещения и трассировки, построению точных алгоритмов конструирования на основе поис- ковых методов, одновременному учету физических и топологиче- ских особенностей схем, построению алгоритмов конструирования на основе комплекса базовых подалгоритмов, разработке специа- лизированных приставок для быстрой реализации наиболее трудо- емких алгоритмов конструирования, разработке новых формаль- ных и адекватных математических моделей схем ЭА. Конструктор ЭА будущих поколений должен обладать знания- ми в области вычислительной техники, программирования, теории алгоритмов, графов, множеств, быть способным разрабатывать и эксплуатировать системы автоматизированного проектирования. Перечисленные в учебном пособии проблемы конструирования ЭА, конечно, не охватывают весь комплекс задач, стоящий перед современным конструктором, использующим вычислительную тех- нику, но они показывают, что возможности повышения эффектив- ности и качества ЭА на основе автоматизации неисчерпаемы. Конструирование и производство ЭА будущих поколений на основе автоматизации является универсальной специальностью будущего. СПИСОК ЛИТЕРАТУРЫ Основная литература 1. Деньдобренко Б. Н., Малика А. С. Автоматизация конструирования РЭА.— М.: Высшая школа, 1980. — 384 с. 2. Кузнецов О. П., Адельсон-Вельский К. М. Дискретная математика для ин- женера. — М.: Энергия, 1980. — 344 с. 3. Мелихов А. Н., Берштейн Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств. — М.: Наука, :1974. — 304 с. 4. Морозов К. К. и др. Методы разбиения схем РЭА на конструктивно закон- ченные части. — М.: Сов. радио, 1978. — '136 с. 5. Норенков И. П. Введение в автоматизированное проектирование технических устройств и систем. — М.: Высшая школа, 1980. — 308 с. 6. Основы проектирования микроэлектронной аппаратуры/Под ред. Б. Ф. Вы- соцкого. — М.: Советское радио, 1977. — 351 с. 7. Петренко А. И., Тетельбаум А. Я. Формальное конструирование электронно- вычислительной аппаратуры. — iM.: Сов. радио, il979. — 256 с. 8. Селютин В. А. Машинное конструирование электронных устройств. — М.: Сов. радио, 1977. — 384 с. 9. Сигорский В. П. Математический аппарат инженера. — Киев: Техтка, 1977. — 766 с. 10. Справочник конструктора РЭА, общие принципы конструирования/Под ред. Р. Г. Варламова. — М.: Сов. радио, 1980. — 478 с. 11. Теория и методы автоматизации проектирования вычислительных систем/Под ред. М. Брейера. — М.: Мир, 1977. — 285 с. 12. Томашевский Д. И., Масютин Г. Г., Явич А. А., Преснухин В. В. Графиче- ские средства автоматизации проектирования РЭА.—М.: Сов. радио 1980.— 244 с. Дополнительная литература 13. Абрайтис Л. В., Шейнаускас Р. И., Жилевичус В. А. Автоматизация проекти- рования ЭВМ. — М.: Сов. радио, 1978, — 272 с. 14. Автоматизация поискового конструирования/Под ред. А. И. Половинкина. — М.: Радио и связь, 1981. — 344 с. 15. Алферова 3. В. Теория алгоритмов. — М.: Статистика, 1973. — 164 с. 16. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. — 536 с. 17. Базилевич Р. П. Декомпозиционные и топологические методы автоматизиро- ванного конструирования электронных устройств. — Львов: Вища школа, изд-во при Львовском университете, 1981. — 168 с. 18. Баранов С. И., Майоров С. А., Сахаров Ю. П., Селютин В. А. Автоматиза- ция проектирования цифровых устройств. — Л.: Судостроение, 1979. — 264 с. 19. Батищев Д. И. Поисковые методы оптимального проектирования. — М.: Сов. радио, 1975. — 216 с. 20. Бахтин Б. И. Автоматизация в проектировании и производстве печатных: плат радиоэлектронной аппаратуры. — Л.: Энергия, 1979. — .120 с. 2.1. Вентцель Е. С. Исследование операций. М.: Наука, '1Э80. — 208 с. 22. Автоматизация проектирования печатных блоков с модулями произвольной. формы/Е. П. Герасименко и др. — М.: Машиностроение, 1979. — 167 с. 23. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. — М.: Мир, 1081. — 366 с. 24. Жимерин Д. Г., Мясников Д. А. Автоматизированные и автоматические си- стемы управления. — М.: Энергия, 1979. — 592 с. 25. Карапетян А. М. Автоматизация оптимального конструирования ЭВМ. — М.: Сов. радио, 1973. — 152 с. 26. Комплекс общеотраслевых руководящих методических материалов по созда- нию АСУ и САПР. Государственный комитет СССР по науке и технике. — М.: Статистика, 1980. — 119 с. 275 2.7. Конструирование и расчет БГИС, микросборок и аппаратуры на их осно- ве/Под ред. Б. Ф. Высоцкого. — М.: Радио и связь, 1981. — 215 с. 28. Кристофидес Н. Теория графов. — М.: Мир, 1978. — 432 с. 29. Кузин Л. Т. Основы кибернетики. Т. 2. — М.: Энергия, 1979. — 584 с. 30. Курейчик В. М. Автоматизация технического проектирования вычислитель- ных структур. — Электронная промышленность, 1979, вып. 4. 31. Майоров С. А., Смирнов А. А. ЭВМ — справочник по конструированию. — — М.: Сов. радио, 1975. — 504 с. 32. Морозов К. К., Одиноков В. Г. Использование ЭЦВМ при конструировании некоторых узлов РЭА. — М.: Сов. радио, 1972. — 104 с. 33. Проектирование монтажных плат на ЭВМ/К. К. Морозов, А. Н. Мелихов, В. Г. Одиноков и др. — М.: Сов. радио, '1979. — 224 с. 34. Нилсон Н. Искусственный интеллект. — М.: Мир, 1973. — 270 с. 35. Петренко А. И., Курейчик В. М. и др. Автоматизация проектирования боль- ших и сверхбольших интегральных схем. — Зарубежная радиоэлектроника, 1981, № 6- 36. Петренко А. И., Тетельбаум А. Я., Шрамченко Б. Л. Автоматизация конструи- рования электронной аппаратуры. — Киев: Вища школа, 1980. — 176 с. 37. Перснухин Л. Н., Шахнов В. А., Кустов В. А. Основы конструирования мик- роэлектронных вычислительных машин. — М.: Высшая школа, 1976. — 408 с. 38. Принс М. Д. Машинная графика и автоматизация проектирования. — М.: Сов. радио, 1975. — 232 с. 39. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980, — 478 с. 40. Рубцов В. П., Захаров В. П., Жижко В. А. Автоматизация проектирования больших интегральных схем. — Киев: Техшка, 1980. — 232 с. 41. Уокер Б. С., Гурд Дж. Р., Дроник Е. А. Интерактивная машинная графика.— М.: Машиностроение, 1980. — '168 с. 42. Шиханович Ю. А. Введение в современную математику. — М.: Наука, 1965. — 376 с. • ' J ' ПРИЛОЖЕНИЕ СПИСОК ГОСТ, РЕКОМЕНДУЕМЫХ ДЛЯ ИСПОЛЬЗОВАНИЯ ПРИ ИЗУЧЕНИИ КУРСА «АВТОМАТИЗАЦИЯ КОНСТРУИРОВАНИЯ» 1. ГОСТ 18682—73. Микросхемы интегральные. Классификация и система ус- ловных обозначений. 2. ГОСТ 17021—75. Микросхемы интегральные. Термины и определения. 3. ГОСТ 2.113—75. Групповые и базовые конструкторские документы. 4. ГОСТ 20406—75. Платы печатные. Термины и определения. 5. ГОСТ 2.105—68. Общие требования к текстовым документам. 6. ГОСТ 2.108—68. Спецификация. 7. ГОСТ 2.117—71. Согласование применения покупных изделий. 8. ГОСТ 21033—75. Система «Человек—машина». 9. ГОСТ 22487—77. Проектирование автоматизированное. Термины и опреде- ления. 10. ГОСТ 23501.0—79. Системы автоматизированного проектирования. Основные положения. 11. ГОСТ 23501.7—80. САПР. Предпроектные .исследования. 1'2. ГОСТ 23501.2—79. Системы автоматизированного проектирования. Разра- ботка, согласование и утверждение технического задания. 13. ГОСТ 23501.5—80. Системы автоматизированного проектирования. Эсниэныч проект. 1'4. ГОСТ 23501.6—80. Системы автоматизирова.иного проектирования. Техниче- ский проект. 15. ГОСТ 23501.4—79. Системы автоматизированного проектирования. Общие требования к программному обеспечению. 16. ГОСТ 23501.9—80. Системы автоматизироваяного проектирования. Общие требования •к банкам данных. 17. ГОСТ 23501.8—80. Системы автоматизированного проектирования. Клас- сификация и обозначения. •18. ГОСТ 2.413—72. Единая система конструкторской документации. Правила выполнения конструкторской документации изделий, изготовляемых с при- менением электрического монтажа. 19. ГОСТ 2.708—72. ЕСКД. Правила выполнения электрических схем цифровой вычислительной техники. 20. ГОСТ 2.031.—77. ЕСКД. Документы на перфокартах и перфолентах. Основ- ные надписи. 21. ГОСТ 19001—77. Единая система программной документации. Назначение, состав, классификация. 22. ГОСТ 19002—80. Схемы алгоритмов и программ. Правила выполнения. 23. ГОСТ 19003—80. Схемы алгоритмов и программ. Обозначения условные, графические. 24. ГОСТ 23501.15—81. Системы автоматизированного проектирования. Ввод в действие. 25. ГОСТ 23501.16—81. Системы автоматизированного проектирования. Диалого- вые средства. Общие требования. 26. ГОСТ 19105—78. ЕСПД. Общие требования к программным документам. 27. ГОСТ 19106—78. ЕСПД. Требования к программным документам, выполнен- ным печатным способом. 28. ГОСТ 23501.3—79. Системы автоматизированного проектирования. Разработ- ка, согласование, утверждение технического предложения. 29. ГОСТ 2501.1—79. Системы автоматизированного проектирования. Стадии создания. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Автоматизированное рабочее место (АРМ) 25Г Алгоритм 42 — бихевиористический 56 — 'волновой (109 — гибкой трассировки 203 — граф-схема 52. — детерминированный 49 — идентификации 56 — канальной трассировки 325 — Краскала 70 — линейного .размещения Графа 172 — логическая схема 61, 128 — локальной модифицированной рас- краски 137 — лучевой 2012, — недетерминированный 49 — порождения 56 — построения максимально полных подграфов 136, 138 — принятия решений 56 — разбиения последовательный 1113, 1118, Г2Й, 1ДЙ — — использующий метод ветвей и границ Г 14 —— итерационный 113, 139,148,153 — размещения, основанный на мето- де ветвей и границ 168, VSO —— последовательный 160 — — последовательно-итерационный 181 —— итерационный 160, 166, 196 — расплывчатый 5i5, 56 — структурная схема 58 — Флари 66 Вершина 58 — запрещенная 11211 — фиксированная 176 — локальная степень 63, М(8 • — раскраска 73, ТВ — смежная 59, Г16, Д'44 Вложение изоморфное 80 Высказывание 2'7 Гиперграф 87, 89, 90, 1127, 153 Граф 57, 90 — двудольный 75, 89, 211 — дополнение 63 — изоморфный 78, 82 — конечный 63 — неориентированный 59 — неэйлеров 66 — нуль 6Й — ориентированный 58 — планарный 81, 92 20'5 — плоский 81 — полный 6'2 — двудольный 75 — полуэйлеров 66 — расплывчатый 90 — регулярный 63 — связный 65, 84, 207 — смешанный 68 — толщина 83 График 32 Декартово произведение 31 Дерево 68, 73, 89, 94 — покрывающее 69, 2Г4 — решений 99 Дизъюнкция 27, 126 Дисплей 260 Документация конструкторская и технологическая 247 Закон: ассоциативности 30 дистрибутивности 30 идемпотентности 30 •коммутативности 30 •Моргана 30 Импликация 2.8 Инверсия отношения 34 Класс эквивалентности 35 Клика' 78 Кодировщик 2150 Компонента связности 65, 73 Компоновка 109 Конъюнкция 27, 106, 138 Координатограф 248 Коэффициент: весовой 150 'перестановочный 1113, 154 Лес вв Маршрут 63, 84 Массив ивазимннимальный 134 — •минимальный 1129, 184 Матрица: геометрии 7i2, 16 инцидентности 6Ц 85, 86 отклонений 188 пересечений 191 . расстояний 70 •смежности 60, 1Q6, 148, 180 цепей 9.2, Г28, 2Д7 Машина Тьюринга 45 Метод ветвей и границ 98 — случайных назначений 155 Микросхема интегральная 8, 9, 230, 233 Множество: бесконечное 26 конечное 25 одноэлементное 26 пустое 26 278 разбиение й2 разделяющее 66 расплывчатое 39 Мост 66 —Мультиг.раф 59, 73, 93, Мб, 169 .Неорграф 59, 85, 207 'Обеспечение информационное 13 Объединение множеств 28 Оператор 234, 342, 244 — алфавитный 43 Операция: .ветвления 98 отсечения 98 Орграф 58, 84, 92, 96 Отношение 33 — антирефлеионое 35 — антисимметричное 35 — нерн.авенства 33 — полное 33 — пустое 33 — равенства 33 — рефлексное 315 — симметричное 35 — транзитивное. 315 — эквивалентности 35 Отрицание 27 Переменные 233, 236 Пересечение множеств 29 Плоскость монтажная 169 Подграф максимально связный 85 Подмножество 26, IBS — внутренне устойчивое 136 — независимое 76 . Позиция 158 Поиск 95, 97 Покрытие 32, l'il4 Программирование: динамическое 104 линейное 103 математическое ,1104, 109 нелинейное '104 целочисленное '.1)1,7 Проектирование 15, 7 Путь 84 '' ; Разбиение 94, 99, ГШ, illl6 — коэффициент Ulil — 'неупорядоченное 'lilll — поэлементное 1113 — упорядоченное 1111 — целое Д'13 Размещение 168, 170 Разность множеств 29 Ребра 68 — инцидентные 59, Ш6, 178, 1.82 — кратные 59 Сетка Г58, 1<63, 182 — координатная 7.1 Система автоматизированного проек- тирования (САПР) 111, 14 — графического проектирования (ГСП) 2611' — интерактивная 231, 244 — классическая 1(5 Соответствие 36—38 Суграф 63, 2Q5 — плоский 2111 Схема соединений 90 Трассировка 197 — двухслойная 213 — многослойных печатных плат 221 Функция 38 — биективная 38 — инъективная 38 — оценочная 98 — сюрьективная 38 — целевая 1!27, 161L, 106 Цепь 65, 70 Цикл 65, 1'87, 196, 208, 214 — гамильтонов 67, 69, 178, 186, 205 — простой 65 — эйлеров 66, 69 Число внутренней полноты 78 — устойчивости 75, 76 — пересечений !1в2, 186, 209 — планарности 81, 209 — реберного соединения ПО — хроматическое 74 — цикломатичеокое 73 Эквивалентность 28 ОГЛАВЛЕНИЕ Стр. Предисловие ................. 3 Введение ................... 5 1. Общие вопросы автоматизации проектирования и конструирования 7 1J1',. Этапы автоматизации проектирования и конструирования ... 7 1.2. Задачи построения систем автоматизированного проектирования . . 10 1.3. Контрольные вопросы и задания .......... 2.5 2. Математические методы, используемые в системах автоматизации кон- струирования ................ 25 2.1. Основные понятия теории множеств ......... 25 2.2. Элементы теории алгоритмов ........... 42 2.3. Элементы теории графов и гиперграфов ...... . 57 2.4. Методы математического программирования при автоматизации кон- струирования ................ 94 2.5. Контрольные вопросы и задания . ......... 106 3. Алгоритмическое конструирование схем . ........ 109 ЗЛ Компоновка . . . ............. 109 3.2. Размещение элементов графа схемы на плоскости . . . . . 158 3.3. Трассировка соединений . . . .......... 197 3.4. Контрольные 'вопросы и задания .......... 2129 4. Проектирование топологии и фотошаблонов интегральных микросхем 230 4.1. О проектировании топологии интегральных микросхем .... 280 4.2. Этапы получения фотошаблонов интегральных микросхем . . . 23'2 4.3. Контроль топология . . . ........... 239 4.4. Контрольные вопросы и задания .......... 246 5. Вопросы выпуска конструкторской и технологической документации 247 5.1. Основные требования при выпуске конструкторской и технологической документации . . . . ............ 247 5.2. Средства машинной графики . .......... 2А8 5.3. Проектирование и выпуск текстовой и графической конструкторско- технологической документации ........... 256 5.4. Контрольные вопросы и задания .......... 259 6. Аппаратные средства связи конструктора и ЭВМ ...... 260 6.1. Общие положения . . ............ 260 6.2. Дисплеи . . . ............... 261 6.3. Структуры данных . . ............ 267 6.4. Программное обеспечение графической системы проектирования . . 269 6.5. Контрольные вопросы и задания .......... 273 Заключение . . . .............. 273 Список литературы . . ............. 275 Основная литература . . . ..'......... 275 Дополнительная литература . . . .......... 275 Приложение. Список ГОСТ, рекомендуемых для использования при изучении курса «Автоматизация конструирования» ..... 277 Предметный указатель . . ............ 278 к. к. МОРОЗОВ, в. г. одиноков, в. м. КУРЕЙЧИК АВТОМАТИЗИРОВАННОЕ ПРОЕКТИРОВАНИЕ КОНСТРУКЦИЙ РАДИОЭЛЕКТРОННОЙ АППАРАТУРЫ Допущено Министреством высшего и среднего специального образования СССР в качестве учебного пособия для студентов вузов, обучающихся по специальности «Конструирование и производство радиоаппаратуры» Е МОСКВА <РАДИО И СВЯЗЬ» 1983