О.Б. Лупанов - Курс лекций по математической логике (1109964), страница 6

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

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

Возьмём вершину с номером n. Если в неё не входит ни одного ребра, то ей приписанапеременная, которую мы как функцию и поставим ей в соответствие. Если в вершину входит одно ребро, тов ней записано отрицание, и мы припишем этой вершине отрицание функции той вершины, из которой в данную вершину приходит ребро. Если входит два ребра, то в этой вершине будет конъюнкция или дизъюнкцияфункций тех вершин, из которых приходят эти рёбра. Видно, что такое определение корректно.Определение. Функции, отвечающие вершинам, отмеченным ∗, называются реализуемыми данной СФЭ.Пример 2.1. Приведённая выше схема реализует функцию (x1 ∨ x2 )&(x1 &x2 ) = x1 ⊕ x2 .Существует физическая интерпретация СФЭ, в которой они рассматриваются как математические моделисоответствующих реальных электронных схем: если на вход подаётся набор значений (наличие тока соответствует единице, отсутствие — нулю), то на выходе получается значение функции на этом наборе.Определение.

Сложностью схемы S называется число элементов L(S) в ней. Сложностью функции fназывается минимальная сложность схемы для f . Функция Шеннона L(n) выражает максимальную сложностьфункций от n переменных.Построим СФЭ, реализующую функцию f = xσ1 1 . . . xσnn . Перегруппируем множители, собрав в одном местепеременные с нулевыми степенями. Тогда, перенумеровав переменные и применив правило Де Моргана, функцию можно переписать в виде f = (x1 x2 . .

. xk )(xk+1 ∨ xk+2 ∨ · · · ∨ xn ). Заметим, что в этой формуле не более nопераций. Значит, сложность схемы данной функции не превосходит n. Теперь построить схему легко.Теперь мы сможем ограничить сложность любой функции f сверху. Построим СДНФ для этой функции. Вней может быть не более 2n дизъюнкций выражений вида xσ1 1 . . . xσnn . Так как сложность каждого дизъюнктамы уже оценили числом n, то сложность всей схемы не превосходит n · 2n . Для функций, тождественно равныхнулю, можно использовать формулу f = x1 &x1 . При этом мы предполагаем, что f — функция по крайнеймере от одной переменной.

Схема будет содержать 2 элемента, значит, её сложность L(f ) = 2 6 n · 2n . Итак,сложность любой функции L(n) 6 n · 2n .Замечание. На самом деле можно сэкономить ещё в 2 раза. Действительно, если среди значений функции по всем наборам больше нулей, чем единиц, то выгодно использовать СДНФ, а если наоборот, то СКНФ15(конъюнктивную форму, т.

е. конъюнкцию дизъюнкций).3.3. Контактные схемыОпределение. Контактная схема (КС) — это конечный граф, в котором каждому ребру приписана переменная либо её отрицание и отмечены некоторые вершины — полюса. Функция проводимости полюсов a иb некоторой контактной схемы — функция fa,b , которая равна 1, если a = b; равна 0, если в КС нет цепей,соединяющих a и b; в остальных случаях f равна дизъюнкции всех цепей, соединяющих a и b, а каждая цепьравна конъюнкции всех своих рёбер. Сложностью КС называют число рёбер в ней.Пример 3.1. Здесь fa,b = x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 = x1 ⊕ x2 ⊕ x3 .Остальные цепи, соединяющие a и b, равны нулю, поскольку содержат какуюнибудь переменную вместе с её отрицанием.Если граф неориентированный, то fa,b = fb,a .Для каждой контактной схемы составим матрицу функции проводимости, вкоторую поместим значения функции проводимости на всевозможных полюсах.В примере, приведённом выше, эта матрица выглядела так:aba1x1 ⊕ x2 ⊕ x3x2x1x3abx1x2x2x3x2bx1 ⊕ x2 ⊕ x31Пусть число полюсов равно k.

Выясним, какие условия надо наложить на произвольную матрицу k × k,состоящую из функций, чтобы существовала КС с такой матрицей проводимости. Для любых трёх полюсов i, j, kнеобходимо, чтобы fi,k принимала значение 1 на всех наборах, на которых fi,j и fj,k одновременно принимаютзначение 1. Это означает, что fi,k > fi,j fj,k . Для неориентированных КС матрица должна быть симметричнаотносительно главной диагонали.

На диагонали матрицы должны стоять единицы (по определению функциипроводимости). Можно доказать, что этих трёх требований достаточно для существования КС с такой матрицейпроводимости.a13a14Оценим сверху сложность функции f от n переменных. Вос23пользуемся правилом построения СДНФ: выберем все наборыa12a1nn1(σ1 , . . . , σn ), на которых функция равна 1. Их число s не преnвосходит 2 .

Для каждого набора построим цепь, соединяющуюaa21a22a23a2nbn123два полюса схемы и реализующую функцию xσ1 1 . . . xσnn (на риσijijсунке ak := xk ). В каждой такой цепи ровно n рёбер. Отсюдаasnas1n1nследует оценка L(n) 6 n · 2 .as2as3С точки зрения физики, КС — математические модели схем23из электромагнитных реле.3.4. Метод каскадов для построения КС и СФЭПусть дана функция f (x1 , . . .

, xn ). Разложим её по переменной x1 и введём обозначения:f (x1 , . . . , xn ) = x1 f (0, x2 , . . . , xn ) ∨ x1 f (1, x2 , . . . , xn ).G0 := {f } ,g10 (x2 , . . . , xn ) := f (0, x2 , . . . , xn ),g11 (x2 , . . . , xn ) := f (1, x2 , . . . , xn ),G1 := {g10 , g11 } .1ВходДалее поступаем с функциями из G1 так же, как и с f , получаем множество0функций G2 , и так далее, т. е. на i-том шаге функции из Gi−1 раскладываем поxnИзолированнаяxnвершинапеременной xi и полученные функции от n − i переменных помещаем в Gi , покане достигнем Gn−1 ⊆ P2 (1).

Функции множества Gn−1 реализуются просто (см.рисунок). Теперь мы сможем построить любую функцию из Gi , если мы уже построили все функции из Gi+1 :добавим к нужным функциям из Gi+1 рёбра xi+1 и xi+1 , руководствуясь разложением данной функции g из Gi .Так будем продолжать, пока не дойдём до G0 = {f }.gij (0, xi+2 , . . . , xn )xi+1Метод каскадов можно применить и для построения СФЭ. Пусть на очередgij (1, xi+2 , . . . , xn )ном шаге для некоторой функции gij из множества Gi имеется разложение gij =¬= xi+1 gij (0, xi+2 , . . .

, xn ) ∨ xi+1 gij (1, xi+2 , . . . , xn ). Тогда навешиваем ФЭ на ужепостроенные функции gij (0, xi+2 , . . . , xn ) ∈ Gi+1 и gij (1, xi+2 , . . . , xn ) ∈ Gi+1 , как&&показано на рисунке.Пример 4.1. Рассмотрим построение КС методом каскадов для функции∨gij (xi+1 , . . . , xn )f = x1 ⊕ · · · ⊕ xn . Разлагая f по x1 , получим f = x1 (0 ⊕ x2 ⊕ · · · ⊕ xn ) ∨ x1 (1 ⊕⊕ x2 ⊕ · · · ⊕ xn ), тогда G1 = {x2 ⊕ · · · ⊕ xn , 1 ⊕ x2 ⊕ · · · ⊕ xn }.

Разлагая функции16из G1 по x2 , получаем x2 ⊕ · · · ⊕ xn = x2 (0 ⊕ x3 ⊕ · · · ⊕ xn ) ∨ x2 (1 ⊕ x3 ⊕ · · · ⊕ xn )и 1 ⊕ x2 ⊕ · · · ⊕ xn = x2 (0 ⊕ x3 ⊕ · · · ⊕ xn ) ∨ x2 (1 ⊕ x3 ⊕ · · · ⊕ xn ). Тогда G2 = {x3 ⊕ · · · ⊕ xn , 1 ⊕ x3 ⊕ · · · ⊕ xn }.xn−1Ясно, что |Gi | = 2, поскольку каждое множество будет содержать одну однородную и одну неоднородную линейную функцию. Cложность схемы (см. рисунок справа) равна 4n − 4,и можно доказать, что она минимальна.xn−2x2xnxn−1xn−2x1xnxn−1xn−2x1abxn−1xn−2x23.5. Оценка сложности схем при построении методом каскадовn−iПоложим As := |Gs |.

Из построения множеств Gi следует, что A0 = 1 Ai 6 2i . С другой стороны, Ai 6 22 ,поскольку Gi ⊆ P2 (n − i). Обе оценки хороши: первая полезна, когда i близко к 0, вторая — когда i близко к n.Значит, при построении число функций сначала растёт, а затем будет быстро уменьшаться — в этом и состоитэкономность метода каскадов. На каждом этапе построения мы добавляем не более 2 рёбер. Следовательно, дляn−2Pконтактных схем L(S) 6 2 + 2Ai .i=0Для СФЭ на i-том шаге можно обойтись 1 + 3Ai функциональными элементами — одним для отрицанияпеременной и тремя (2 конъюнкции и 1 дизъюнкция) для каждой новой функции.

Значит, справедлива оценкаL(S) 6n−2X(1 + 3Ai ) + 3 = n + 2 + 3i=0n−2X(1)Ai .i=0Замечание. Метод каскадов не всегда даёт схему минимальной сложности. Для функции f = x1 ⊕ · · · ⊕ xnон даёт СФЭ сложности 7n − C, в то время как для неё имеется схема сложности 4n − 4.n−2PПриступим к оценке суммыAi . Учитывая оценки для чисел Ai , разобьём нашу сумму на две части,i=0учитывая степень влияния каждой из оценок. Пусть k — «точка разбиения». Представим нашу сумму в видеn−2Xi=0Ai =n−kXn−2XAi +i=0Ai 6n−kXi2 +i=0i=n−k+1n−2Xn−i22k−1< 2n−k+1 + (22k−2+ 22k−1+ . .

. ) . 2n−k+1 + 22.i=n−k+1 n−kЗдесь первое слагаемое — сумма геометрической прогрессии 2i i=0 , а знак . означает «асимптотически меньk−2k−3ше», т. е. отброшенная часть 22+ 22+ . . . бесконечно мала по сравнению с оставленной при k → ∞.k−1Положим ϕ(k) := 2n−k+1 + 22 . Строго говоря, для нахождения минимума этой функции следовало бы найтинуль её производной, а затем в качестве k выбрать ближайшее к этому корню целое число. Уравнение ϕ′ (k) = 0легко преобразуется к виду 2k−1 + 2k = n + 2 − log2 ln 2. Однако в явном виде решение указать нельзя, поэтому мы для оценки воспользуемся точкой деления k = logn. Тогда имеем k > log2 n − 1, следовательно2log2 n−1ϕ(k) 6 2n+2−log2 n + 22nnnn6 4 2n + 2 2 . Поскольку 2 2 = on2nnпри n → ∞, его можно отбросить.

Значит, дляnКС справедлива оценка 8 2n , а для СФЭ — 12 2n . Можно показать, что L(S) ∼ 2n и для СФЭ, и для КС. Здесьмы не будем этого доказывать, но убедимся в её неулучшаемости.nnТеорема 3.5. Оценку 2n нельзя улучшить: при всяком n найдётся функция со сложностью, близкой к 2n .

Введём обозначения: N (n, h) — число функций n переменных сложности не более h, E(n, h) — числофункций сложности ровно h, и S(n, h) — число всех схем сложности h.Докажем, что S(n, h) 6 3h (h + n)2h+1 для СФЭ. В самом деле, у нас имеется не более 2h входов и h + nвыходов, каждый вход может быть присоединён к любому выходу ((h + n)2h вариантов), каждый из h элементовможет быть либо отрицанием, либо конъюнкцией, либо дизъюнкцией (3h возможностей), кроме того, один выходпомечен ∗ — ещё h + n возможностей. Поэтому оценка для S(n, h) справедлива.Ясно, что N (n, h) = E(n, h) 6 S(n, h).

Действительно, равенство следует из того, что любую схему сложностименьше h можно дополнить ничего не делающими элементами до схемы сложности h, неравенство же следуетиз того, что различных схем заведомо больше, чем различных функций: одна функция может быть реализованадвумя разными схемами, но не наоборот.nПонятно, что если N (n, h0 ) < 22 = p2 (n) для некоторого h0 , то найдётся функция со сложностью больше,0)чем h0 . Логарифмируя данное неравенство, получаем: log2 Np(n,h= log2 N (n, h0 ) − 2n < 0. Нужно убедиться2 (n)в существовании некоторого h0 , для которого это неравенство будет справедливо при достаточно больших n.nВозьмём h0 = 13 · 2n . Имеемlog2 N (n, h0 ) − 2n 6 log2 S(n, h0 ) − 2n 6 h0 log2 3 + (2h0 + 1) log2 (h0 + n) − 2n .17(2)При достаточно больших n имеем log2 (h0 + n) < n, поэтомуlog2 N (n, h0 ) − 2n <log2 3 2n2 2nlog2 3 2n1·+( ·+ 1)n − 2n =·+ n − · 2n .3n3 n3n3(3)Видно, что при n → ∞ последнее выражение стремится к −∞, и тем самым неравенство доказано.

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

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