Главная » Просмотр файлов » ОК_Часть_2_2015_(320-328)_v03-09

ОК_Часть_2_2015_(320-328)_v03-09 (1132806), страница 8

Файл №1132806 ОК_Часть_2_2015_(320-328)_v03-09 (С.А. Ложкин - Лекции по основам кибернетики (2015)) 8 страницаОК_Часть_2_2015_(320-328)_v03-09 (1132806) страница 82019-05-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Изоморфные КС, очевидно, эквивалентны.Для множества C, состоящего из контактов видаxσi11 , . . . , xσirr в КС Σ, определим его функцию проводимости K (C) и функцию отделимости J (C) как ФАЛ вида xσi11 · · · xσirr и xσi11 ∨ . . . ∨ xσirr соответственно. При этоммножество C называется проводящим (отделимым), еслиK (C) 6= 0 (J (C) 6= 1), и нулевым (соответственно единичным) в противном случае. Заметим, что в результате приведения подобных (см. §4) отличная от 0 ФАЛ K (C) и отличная от 1 ФАЛ J (C) могут быть преобразованы в ЭК иЭД соответственно.

Очевидно, также, чтоK C 0 > K (C) и J C 0 6 J (C) ,если C 0 ⊆ C.Из введенных определений (см. также §1) следует, чтоФАЛ g, реализуемая КС Σ (x1 , . . . , xn ; a1 ; a2 ), обращается в 1§6. Контактные схемы и π-схемы, оценка их числаxn• a0xn• a153•x1•x2x2••x2••1•x1x2...ai•/ xσ1 . . . xσnn1•xn• a2n −2•xn• a2n −1a)a0 •xn•a1 •a2n −2 •xn•x2••x2x2•xn•x1•x1•ax2•a2n −1 •xnb)Рис. 6.4: (1, 2n )- и (2n , 1)- контактные деревья порядка n54Глава 2. Основные классы управляющих систем(обращается в 0) на наборе α, α ∈ B n , тогда и только тогда,когда в Σ существует множество контактов C, образующеепростую проводящую (a1 − a2 )-цепь (соответственно тупиковое отделимое (a1 |a2 ))-сечение), для которого K (C) = 1(соответственно J (C) = 0) на наборе α.

Таким образом,g (x1 , . . . , xn ) = K (C1 ) ∨ . . . ∨ K (Ct ) == J (S1 ) & . . . &J (Sr ) , (6.1)где C1 , . . . , Ct и S1 , . . . , Sr — все простые проводящие(a1 − a2 )-цепи и все тупиковые отделимые (a1 |a2 )-сеченияКС Σ.Заметим, что первая из формул (6.1) может быть преобразована в ДНФ, а вторая — в КНФ, в результате приведения подобных (см. §3), если g 6≡ 0 и g 6≡ 1 соответственно.Так, в КС, показанной на рис. 6.3b, имеются три простыепроводящие цепи C1 , C2 и C3 , которые идут из a1 в a2 . ПриэтомK (C1 ) = x1 x2 x3 , K (C2 ) = x1 x2 x1 = x1 x2 , K (C3 ) = x1 x3и, следовательно,g (x1 , x2 , x3 ) = x1 x2 x3 ∨ x1 x2 ∨ x1 x3 == x1 x2 ∨ x2 x3 ∨ x3 x1 = H (x1 , x2 , x3 ) .Рассмотрим теперь параллельно-последовательные или,иначе, π-схемы, которые являются частным случаем КС.Простейшей π-схемой считается любая (1, 1)-КС, которая состоит из одного контакта, соединяющего полюса(см.

рис. 6.6a). Если π-схемы Σ1 и Σ2 уже определены, то(1, 1)-КС Σ0 (Σ00 ), которая получается в результате их параллельного (соответственно последовательного) соединения (см. рис. 6.6b и 6.6c) тоже является π-схемой. Заметим,§6. Контактные схемы и π-схемы, оценка их числа55C1a1a2Cta)a1•···S1a2•Spb)Рис. 6.5: КС, моделирующие ДНФ и КНФчто при этом вход (выход) Σ0 является результатом отождествления входов (соответственно выходов) Σ1 и Σ2 , тогда как входом Σ00 является вход Σ1 , выходом Σ00 — выходΣ2 , а выход Σ1 отождествляется с входом Σ2 и становитсявнутренней вершиной Σ00 .

Легко видеть, что π-схема, показанная на рис. 6.6a, реализует ФАЛ xσi , а π-схемы Σ0 и Σ00(см. рис. 6.6b и 6.6c) — ФАЛ f1 ∨ f2 и f1 &f2 соответственно,где f1 и f2 — ФАЛ, реализуемые π-схемами Σ1 и Σ2 соответственно.Лемма 6.1. Любой π-схеме Σ можно сопоставить эквивалентную ей формулу F из UΦ с поднятыми отрицаниямитакую, что R (F) = L (Σ) и обратно.Доказательство.

Построим формулу F индукцией по строению π-схемы Σ. Если Σ — простейшая π-схема вида xσi , тоположим F = xσi . Если π-схемам Σ1 и Σ2 уже сопоставлены формулы F1 и F2 с поднятыми отрицаниями, то π-схемеΣ0 (Σ00 ), получающейся в результате параллельного (соответственно последовательного) соединения Σ1 и Σ2 , сопоставим формулу F0 = F1 ∨ F2 (соответственно F00 = F1 &F2 ).56Глава 2. Основные классы управляющих системa1xσiΣ1a2Σ0:a1a2Σ2a)b)Σ00 : a1Σ1•Σ2a2c)Рис. 6.6: к определению π-схемыПри этомR F0 = R F00 = R (F1 ) + R (F2 )и, следовательно, по индуктивному предположению,R F0 = R F00 = L (Σ1 ) + L (Σ2 ) = L (Σ) .Аналогичным образом, индукцией по строению формулы Fс поднятыми отрицаниями можно найти эквивалентную ейπ-схему Σ такую, что L (Σ) = R (F).Лемма доказана.На рис 6.7a показана π-схема, которая реализует ФАЛH (x1 , x2 , x3 ) и соответствует формуле:H (x1 , x2 , x3 ) = x1 (x2 ∨ x3 ) ∨ x2 x3 ,а на рис.

6.7b — π-схема, которая построена на основе контактного дерева и реализует ФАЛ µn — мультиплексорную§6. Контактные схемы и π-схемы, оценка их числа•x2x1x3a1x257a2x3•a)xn•xn••x1•x2x2••x2•y0•a1x1x2y1a2y2n −2•xn•xn••b)Рис. 6.7: примеры π-схемy2n −158Глава 2. Основные классы управляющих системФАЛ порядка n, — в соответствии с формулойµn (x1 , . . . , xn , y0 , . . .

, y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · ·  .σ1 ∈Bσ2 ∈Bσn ∈BСхема, моделируюшая совершенную ДНФ ФАЛ f ,называется канонической КС для этой ФАЛ.Будем называть (1, m)-КС приведенной, если все изолированные вершины Σ являются ее полюсами, а все контактыи остальные вершины Σ принадлежат простым проводящимb коцепям, соединяющим ее вход и выходы. При этом КС Σ,торая получается из КС Σ удалением «лишних», то есть непринадлежащих цепям указанного вида, неполюсных вершин и контактов, является эквивалентной Σ приведеннойb 6 L (Σ). Заметим, что приведенная КСКС такой, что L(Σ)не содержит петель, а приведенная КС, не реализующая нулевых ФАЛ, является связным графом.

Так, КС, показанная на рис. 6.3c, не является приведенной, а соответствующая ей приведенная КС получается из нее удалением вершины v.Рассмотрим теперь некоторые оценки числа контактныхсхем различных типов. Пусть UK и Uπ — множество всех КСиз неориентированных контактов и множество всех π-схемсоответственно. Если UA — один из указанных классов схем,то через UA (L, n) будем обозначать множество приведенных(1, 1)-схем Σ из UA от БП X (n), для которых L (Σ) 6 L.

Длялюбого множества схем U в соответствии с §1 через |U| и kUkбудем по-прежнему обозначать число попарно не изоморфных и попарно не эквивалентных схем в U соответственно.При этом для любого из введенных выше множеств схемнеравенство (1.7) будет выполняться.§6. Контактные схемы и π-схемы, оценка их числа59Лемма 6.2. При любых натуральных L и n выполняетсянеравенствоkUπ (L, n)k 6 (12n)L .(6.2)Доказательство. В силу леммы 6.1, достаточно доказать,что число попарно не эквивалентных формул F (x1 , . . . , xn )с поднятыми отрицаниями над базисом Б0 , для которыхR (F) 6 L, не превосходит (12n)L .

Требуемая оценка вытекает из следствия к лемме 4.2.Лемма доказана.Лемма 6.3. При любых натуральных L и n выполняетсянеравенство KU (L, n) 6 (8nL)L .Доказательство. Возьмем произвольную КС Σ=K= Σ(x1 , . . . , xn ; a1 ; a2 ), Σ ∈ U (L, n), и выделим в нейостовное дерево D с корнем a2 так, чтобы в D вошли всеинцидентные a2 контакты Σ, а вершина a1 была листом D.Пусть, далее, D0 — связанное с D остовное наддерево КСΣ, которое получается путем присоединения каждого изне вошедших в D ребер Σ к одной из своих концевых вершин, отличной от a1 (см. §1).

Рассмотрим ориентированноеупорядоченное дерево D00 , получающееся из D0 введением (условной) ориентации всех его ребер по направлению ккорню и таким их упорядочением, при котором вершина a1становится первым листом D00 (см. §1).Заметим, что число ребер (вершин, листьев) дерева D00не больше, чем L (соответственно L + 1, L), и поэтому, всилу (1.4), число таких деревьев с учетом пометок их ребер символами x1 , . . .

, xn , x1 , . . . , xn не больше, чем (8n)L .Заметим также, что КС Σ может быть получена в результате присоединения каждого листа дерева D00 к одной из еговершин, отличной от a2 . Следовательно, K U (L, n) 6 UK (L, n) 6 (8nL)L .60Глава 2. Основные классы управляющих системЛемма доказана.Рассмотрим, в заключение, особенности функционирования КС с несколькими входами.

Будем считать,что в каждой вершине (p, q)-КС Σ реализуется столбец, составленный из p ФАЛ проводимости от входовΣ к этой вершине, а сама КС Σ реализует матрицу,которая состоит из q столбцов, реализованных на еевыходах. Таким образом, функционированиеКС Σ =000000= Σ x1 , . . . , xn ; a1 , . . . , ap ; a1 , . . . , aq представляет собойматрицу F = F (x1 , .

. . , xn ) с p строками, q столбцами и элементами из P2 (n), для которой F hi, ji — ФАЛ, реализуемаямежду a0i и a00j , где i ∈ [1, p] и j ∈ [1, q], то есть при любом α, α ∈ B n , матрица F (α) является матрицей достижимости сети Σ|α . В частности, функционирование (1, q)-КСпредставляет собой набор (строку) из q ФАЛ проводимости от ее входа к выходам, а функционирование (p, 1)-КС —столбец из p ФАЛ проводимости от ее входов к выходу.Так, КС Σ (x1 , x2 , x3 ; a1h, v; a2i, a3 ), показанная на рисунке 6.3c реализует матрицу ll3 ll3 от БП X(3), а на рис. 6.4b3 3приведено (2n , 1)-КД порядка n от БП X (n), которое имеет вид D (x1 , .

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

Тип файла
PDF-файл
Размер
843,13 Kb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее