Теормин (билеты 8 - 11) (2014) (спасибо Денису) (1133373)
Текст из файла
8. ФОД!У1УЛЫ Н С110СОбЫ 11~ ЗВ!ДйЕ111Я, Э1~~11НйЛОНтЯОСтБ ф0Д!У!УЛ 1~ фУ111СЦ11ОНйЛЫ ~1~ сл0~1~я0ст~1. Оптнв1изйция п0д0бяы~ ф0дв1ул п0 рлу611яО ФООМУЛЗ Пусть Х = (хт,хз, ..., х„„...) — счетный упорядоченный алфавит входных БП и пусть Б = [грт, где ° грь) — базис, где ФАЛ грь! = 1 ... Ь зависит от (сь (с! > 1, БП и является существенной ФАЛ, если (с; > 2. Предполагается, что базис полный, и допускается, в общем случае, наличие в нем равных ФАЛ. Любая переменная х; из Х считается формулой глубины О или тривиальной формулой над базисом Б, которая реализует функцию хи Если! Е [1„Ь) и для каждого/,) Е [1,(сг(, определена формулами глубины ц над Б, которая реализует ФАЛ ~, то запись вида У = гр!(Ут, ..., Ук,) является формулой глубины ц над Б, где с( = гвх 1дт, ..., с(к,) + 1, которая реализует ФАЛ 1 вида ! = гр! [!т, ..., Я. Все записи, полученные в результате укаэанного индуктивного построения, и только они считаются формулами над базисом Б.
При этом формулы, полученные в процессе индуктивного построения формулы У, называются ее подформулами, а те подформулы Ут, ..., У„,, из которых на последнем шаге индуктивного построения строится формула У, считаются ее главными подформулами. Под сложностью (рангом) формулы У понимается число вхождений в нее функциональных символов (соответственно символов переменных), которое обозначается через Е[У) (соответственно В[У)).
«Графически» совпадающие формулы называются изоморфными, а формулы, реализующие равные функции, — эквивалентными. Множество всех формул над базисом Б будем обозначать через И~~ и положим И~~ = И~. ЗЗДВЯзте фОДЯУАы Б Бил ДОГОВО Индукцией по глубине любой формуле глубины с! над Б можно сопоставить упорядоченное ориентированное корневое дерево глубины с(, каждому листу которого приписана БП из Х, а каждой внутренней вершине — функциональный символ (ФС) из Б. Формуле х глубины О сопоставим «тривиальное» дерево с единственной вершиной, являющейся корнем и листом одновременно, которой приписана БП х .
Ранг В[У) формулы У равен числу листьев связанного с ней дерева Ю, ее сложность ЦУ) равна числу остальных вершин Ю, а ее глубина 0[У) — глубине его корня. ЛОММЗ Для формулы У, У Е П, выполняются неравенства ~ Ю = Ьв,ч(Я + 1 < !.[У) + 1 ~ 2 где Ьв ч(У) — число ФС й н 'х' в формуле У. Следствие 0[,г-) > [(с~[Ь[т) + 1)1. 3!сВзтВВлОЯз йод !т(зОО6(тВВОВОЯт!е 13Й) Если позиционную подформулу вида У' (вида У''! формулы У заменить, учитывая тождество г: У' = У", эквивалентной ей формулой У" (соответственно У'), то полученная в результате такой замены формула будет эквивалентна формуле У.
Гз Одобяьте формулы Формулы из П~, получающиеся друг из друга эквивалентными преобразованиями на основе тождеств Гц, Гч, СЭ, Сч называются подобными. 70ЯсдестЯЯ Д9 МОРГЯЯВ Формулы из И можно оптимизировать также по числу отрицаний с помощью эквивалентных преобразований на основе тождеств с~:(х,) =х, см: (хт ~гхз) = хт 'хз с,: (х, х,) = х, ч х,, ФОРМУЛ2 С ХЮДЯЯТЫМЯ ОТРЯЦЯЯЯЯМЯ Формула, в которой все ФС отрицания встречаются только над БП, называется формулой с поднятыми отрицаниями.
Аяятеяяряяяяяе формуяы с яодяятымя Отряцяяяямя Лт (У) — максимальное число изменений типов ФС й и Ч в цепях дерева, соответствующего формуле. ТРОРЯМЯ Для любой формулы У с поднятыми отрицаниями из П существует подобная ей формула У такая, что () ~ж(() )1 () Следствие 1 Для любой ЭК или ЭД К существует подобная формула К такая, что П(К) = Ис~(ЦК) + Ц1, которая минимальна по глубине. Следствие 2 Для любой ДНФ или КНФ т1 существует подобная формула Й такая, что О® < Г1сц(ЦЖ+1)1+1.
9. Схемы из фуиициоиальиых злемеитои (т".ФЗ) и операции их ирииедеиия. Оцеииа числа формул и СФЗ и базисе Бо —— (й,Ч, — ) (. еаза Набор вида Д = (6; Г; У'), где 6 — граф, а У' и У" — выборки из множества У(6) длины р и с) соответственно, причем выборка )г' является выборкой без повторений, называется (р, д)-сетью. Схема из фуитсциоиальиых злемеитоа ((:ФЗ) Пусть 2' — счетный упорядоченный алфавит выходных БП, который не имеет общих БП с алфавитом Х. Сопоставим каждому функциональному символу (ФС) грь ( = 1, ..., Ь, функциональный элемент (ФЭ) Яь имеющий )с; входов, причем входу с номером/соответствует1ая БП х ФАЛ грь где/ = 1, ...,)сь и один выход, на котором эта ФАЛ реализуется. Схемой из функциональных элементов над базисом Б называется ориентированная ациклическая упорядоченная сеть Х, входная выборка которой состоит из всех истоков Х, а вершины помечены следующим образом: 1.
каждому входу (выходу) Х сопоставлена БП иэ Х (соответственно Я), являющаяся пометкой связанной с ним вершины, причем различным входам (выходам) сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Х определяется упорядоченностью сопоставленных им БП; 2. каждая отличная от истока вершина о схемы Х помечена ФС грь где )с; = с(~~(тг). Каазидереао Схема Х, которая получается из дерева Ю, связанного с формулой У из Ив, в результате отождествления листьев с одинаковыми пометками и приписывания его корню выходной БП из 2', называется квазидеревом, соответствующим формуле л. Кзоморфиые и зеаиаалеитгиые (:ФЗ Две СФЭ называются изоморфными, если они изоморфны как помеченные графы, и эквивалентными, если они реализуют равные системы ФАЛ. Изменение нумерации дуг, входящих в такую вершину о схемы Х, которой сопоставлен ФЭ Я; с симметрической ФАЛ грь не изменяет ФАЛ, реализуемую в вершине и, а значит, не влияет на функционирование СФЭ.
Схемы, получающиеся друг иэ друга в результате указанных преобразований, называются квази-изоморфными. Ирааедеииаа СФЗ Вершина СФЭ называется висячей, если она является стоком, но не является выходом схемы. Схема называется приведенной, если в ней нет висячих вершин. Фуиэсциоиалы елоагиос ги СФЗ Для каждой СФЭ Х, Х е 12в~, определены следующие функционалы сложности: 1. ЦХ) — сложность Х, т. е. число всех ее ФЭ 2.
Р(Х) — глубина Х, т. е. максимальная глубина ее вершин 3. Я(Х) — ранг Х, т. е. число дуг, исходящих из ее входов Лемма Для приведенной СФЭ Х, Х е Пс, с одним выходом выполняются неравенства )1(Х) < Ьа (Х) + 1 < Е(Х) + 1 < 2пГз~, где Ьа (Х) — число ФЭ8 ну вХ. Обозначим через Пьф(Ь, п) и Пьф [Р, и) множества формул У = У(х,, ..., х„) над базисом Б, для которых ЦУ) < Ь и Р(У) < Р.
Индекс Б0 будем опускать. Лемэтз Обозначим ~П~~ ЦП~~~) — число попарно не изоморфных (попарно не эквивалентных) схем в Пф. Для любых натуральных п, А, Р выполняются неравенства )П'(1„п) ! < (1Оп)'+' ((ПФ(1 )(! < (8 )1+1 ()П~~Р, тг) (! < (8эт)~ Следствие Число попарно не квазиизоморфных формул с поднятыми отрицаниями от БП Х(п) ранга не больше, чем й, не превосходит (12п)я. Люээмз Для любых натуральных и и ~ выполняется неравенство ((П~(Ь,п)(! < (8(Ь+ п)) +~.
Сеть Х с входами а,', ..., ар и выходами а,", ..., а", в которой все ребра (дуги) помечены переменными хт, ..., х„или их отрицаниями, называется ~р, д)-контактной схемой (КС) от БП хн ..., х„и обозначается Х = Х(хт, ..., х„) или Х = Х(хт, ..., х„; и.„'..., ар, а~', ... „а"). При этом число контактов называется сложностью КС и обозначается ЦХ). Фу~кцвя йронод~мосз зг для нер1~йя Пусть Х вЂ” КС от БП Х(п) и а = (ан ..., а„) — набор из В".
Определим сеть Х) „как сеть, получающуюся из Х путем удаления всех ребер с пометками х, ', ..., х„", то есть ребер, которые не проводят на наборе а, и снятия пометок с остальных ребер. Для вершин р и и КС Х введем функцию проводимости от вершины р к вершине и как ФАЛ ,д, „(х,, ..., х„), которая равна 1 на наборе а = (а,, ..., а„) тогда и только тогда, когда в сети Х) „существует (р — и) — цепь, то есть тогда и только тогда, когда в Х имеется цепь из проводящих на наборе а контактов вида х, ', ..., х„", идущая из р в и.
ФАЛ д„(хт, ..., х„) называют также функцией достижимости вершины и из вершины р (д, „ реализуется между вершинами р и и). Кзоморфкые м эквлинлйкгяые схемы Две схемы называются изоморфными, если изоморфны соответствующие им графы, и эквивалентными, если они реализуют равные системы ФАЛ. Фуяец~й пронодйззосзн для ззяонсеГ~нз еов'гйетон Для множества С, состоящего из контактов вида х; ', ..., х," в КС Х, определим его функцию проводимостиК(С) ифункциюотделимостиИС) какФАЛ видах,.' ... х,.' их,.' Ч ...Чх,.'соответственно.
При этом множество С называется проводящим (отделимым), если К(С) Ф О ЯС) Ф 1), и нулевым ~соответственно, единичным) в противном случае. Простейшей тс-схемой считается любая (1, 1)-КС, которая состоит из одного контакта, соединяющего полюса. Если и-схемы Х,, Х, уже определены, то (1,1)-КС Х'(Х"), которая получается в результате их параллельного (последовательного) соединения, тоже является п-схемой.
Леммй Любой и-схеме Х можно сопоставить эквивалентную ей формулу У Б Иф с поднятыми отрицаниями, такую, что В(У) = ЦХ) и обратно. тзртзиедеяязя й",С (1,гп)-КС называется приведенной, если все изолированные вершины Х являются ее полюсами, а все контакты и остальные вершины Х принадлежат простым проводящим цепям, соединяющим ее вход и выходы. Оковки числа К(: равлкчвыж тзтаов Пусть 11» и 'П вЂ” множество всех КС из неориентированных контактов и множество всех и -схем соответственно. Через 11~(1„п) (соответственно И (1„п)) будем обозначать множество приведенных (1, 1)- схем Х из 11» (соответственно И") от БП Х(п), для которых ЦХ) < 1,.
Обозначим )11) ЦТ1))) — число попарно не изоморфных (попарно не эквивалентных) схем в И. Лемма При любых натуральных Х и и выполняется неравенство ))11 (Е,и))) < (12п)~. Лемма При любых натуральных Х и и выполняется неравенство ))и (1„п))) < (ВпЦ'. Оеобе1тяост11 футттсцтто11йроззаяття К(: е яесеолькттьттт Входазш Будем считать, что в каждой вершине (р, г))-КС Х реализуется столбец, составленный из р ФАЛ проводимости от входов Х к этой вершине, а сама КС Х реализует матрицу, которая состоит из д столбцов, реализованных на ее выходах. Таким образом, функционирование КС Х = Х(хт, ..., х„; а~, ..., а„'; а,", ..., а„'') представляет собой матрицу Р = Р(хт, ... „х„) с р строками, ц столбцами и элементами из Рг(п), для которой Р(1,1) — ФАЛ, реализуемая между а; 'и а", где1 Б 11, р), 1 Б 11,д].
Функционирование КС Х = Х(хт, ..., х„; аи ..., а ) с неразделенными полюсами определяется как функционирование КС с разделенными полюсами вида Х = Х(хт, ... „х„; ат, ..., а; ат, ..., а ). В этом случае матрица выявляется рефлексивной и транэитивной матрицей, а если, кроме того, Х— неориентированная сеть, то и симметричной магирицей. Любая симметрическая, транзитивная и рефлексивная матрица Р, Р Б (Рг(п))"', реализуется КС Х = Х(хт, ...,х„; ат, ..., а '), которая представляет собой объединение всех КС Х; = Х; (хт, ...
„х„; а;; а ), где 1 < 1 </ < т, а КСХ; является и-схемой и построена по совершенной ДНФ ФАЛ Р(1,Я и считается канонической КС матрицы Р. ЙРЯСОЕДЯЯВЯЯВ БРОТЯВОБОЛО"КЯЬ$Х КОЯТВКТОВ Пусть (1, т)-КС Х получается из (1, тп)-КС Х в результате добавления новой выходной вершины у, которая соединяется с выходными вершинами юв и т КС Х контактами х; и х; соответственно. Если в вершинах юэ и ют реализовывались функции дэ и дт соответственно, то в вершине и будет реализовываться функция д = х;д„У х;д . КЯСКБДЯВЯ КОЯЕпВКТЯВЯ СХЕМВ Приведенная КС без изолированных полюсов, которая может быть получена из системы тождественных вершин в результате ряда операций присоединения одного или двух противоположных контактов и операций переименования выходов.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
