оки4 (1155747)

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

Текст из файла

Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинЛекции по основамкибернетики(вариант 2014 г., глава 4)Москва 2014ОглавлениеВведение34 Эквивалентные преобразования управляющихсистем6§1 Задача эквивалентных преобразований схем напримере формул. Полнота системы основныхтождеств для эквивалентных преобразованийформул базиса {&, ∨, ¬} .

. . . . . . . . . . . . 6§2 Эквивалентные преобразования схем из функциональныхэлементов и моделирование с их помощью формульныхпреобразований. Моделирование эквивалентныхпреобразований формул и схем в различныхбазисах, теорема перехода . . . . . . .

. . . . . 13§3 Эквивалентные преобразования контактныхсхем. Основные тождества, выводвспомогательных и обобщенных тождеств . . . 22§4 Полнота системы основных тождестви отсутствие конечной полной системытождеств в классе контактных схем . . . . . . . 31Литература382ВведениеКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого былчл.-корр. РАН С. В. Яблонский, читается на факультетеВМиК МГУ с первых лет его существования. В настоящеевремя он читается в 6–8 семестрах и является обязательнымдля всех бакалавров (интегрированных магистров) направления 01400 — «Прикладная математика и информатика».При этом объем и, в некоторой степени, программа курса«Основы кибернетики» варьируются в зависимости от профиля.Курс «Основы кибернетики» посвящен изложению теории дискретных управляющих систем, которая представляет собой часть дискретной математики и математическойкибернетики.

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

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

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

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

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

Для каждого из них приводится система «основных» тождеств, доказывается полнота этой системы и изучаются вопросы ее избыточности.В пятой главе представлены некоторые вопросы надежности и контроля схем (построение тестов для таблиц, синтез самокорректирующихся контактных схем).Глава 4Эквивалентные преобразованияуправляющих систем§1Задача эквивалентных преобразований схемна примере формул.

Полнота системы основных тождеств для эквивалентных преобразований формул базиса {&, ∨, ¬}Эквивалентные преобразования (ЭП), то есть преобразования, не изменяющие функционирования схем, играют важную роль при решении различных задач теории управляющих систем и, в частности, задачи синтеза схем (см. §1 главы3). Следуя [?], изложим ряд вопросов ЭП схем из основныхклассов и рассмотрим сначала понятия, связанные с эквивалентными преобразованиями схем на основе тождеств напримере формул над базисом Б. Напомним, что некоторыеЭП формул базиса Б0 уже использовались для раскрытияскобок и приведения подобных при построении сокращеннойДНФ (см.

§3 главы 1), а также при оптимизации формул поглубине (см. §2).Однократное ЭП формулы F в формулу F̌ с помощьютождества t (см. §2) будем записывать в виде однократнойe в резульвыводимости вида F 7→ F̌. Аналогичное ЭП F в Ftтате применения одного из тождеств системы τ (несколькихпоследовательных применений тождеств из τ ) будем записывать в виде однократной (соответственно кратной) выво6§1. Эквивалентные преобразования формул7e (соответственно F |⇒ F).e При этомдимости вида F 7→ Fττсчитается, что тождествоeet: F=Fвыводится из системы тождеств τ , и этот факт записывается в виде выводимости τ 7→ et или τ |⇒ et в зависимостиот числа использованных переходов.

Заметим, что в силуe следует обратнаяобратимости ЭП из выводимости F |⇒ Fτe |⇒ F. Система тождеств τ называется полнойвыводимость Fτдля ЭП формул над Б, если для любых двух эквивалентныхформул F0 и F00 над Б имеет место выводимость F0 |⇒ F00 .τРассмотрим, в частности, систему τ , которая состоит изтождеств де Моргана и тождестваtПK1,& : x1 (x2 ∨ x2 ) = x1 ,— тождества подстановки константы 1 = x2 ∨ x2 в конъюнкцию (см.

тождества (2.2) из главы 1). Пример ЭП формул изUΦ с помощью системы тождеств τ дает следующая цепочкавыводимостей:x1 (x2 x3 ∨ x2 ∨ x3 ) 7→ x1 (x2 x3 ∨ x2 · x3 ) 7→ x1 .tM&tΠK1,&(1.1)Далее будем рассматривать только формулы над базисомБ0 , называя их просто формулами. Заметим, что имеют место (см., в частности, §2 главы 1, а также ??) следующиетождества ассоциативностиtA◦ : x1 ◦ (x2 ◦ x3 ) = (x1 ◦ x2 ) ◦ x3 ,тождества коммутативностиtK◦ : x1 ◦ x2 = x2 ◦ x28Глава 4. Эквивалентные преобразования управляющих системи тождества отождествления БПtOΠ: x ◦ x = x,◦где ◦ ∈ {&, ∨}, тождества дистрибутивности «◦» относительно «»tD◦, : x1 ◦ (x2 x3 ) = (x1 ◦ x2 ) (x1 ◦ x3 )и тождества («правила») де МорганаtM¬ : (x1 ) = x1 ,tM◦ : (x1 ◦ x2 ) = (x1 ) (x2 ) ,где (◦, ) ∈ {(&, ∨) , (∨, &)}, тождества подстановки констант1ΠKtΠK0,& : x1 (x2 · x2 ) = x2 · x2 , t1,& : x1 (x2 ∨ x2 ) = x1 ,tΠK0,∨ : x1 ∨ x2 · x2 = x1 ,tΠK1,∨ : x1 ∨ (x2 ∨ x2 ) = x2 ∨ x2 ,а также тождество поглощенияt Π : x1 ∨ x1 x2 = x1 ,тождество обобщенного склеиванияtOC : x1 x2 ∨ x1 x3 = x1 x2 ∨ x1 x3 ∨ x2 x3и другие.Докажем, что K M M Mиt& , τ|⇒ tKt& , t¬ |⇒ tM∨ ,∨M Mгде τ M = tM& , t¬ , t∨ .

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций