Ответы к экзамену 2010 (1133259), страница 2
Текст из файла (страница 2)
x1 &x2 = x2 &x16. (x1 &x2 )&x3 = x1 &(x2 &x3 )7. x&x = x8. (x1 &x1 )&x2 = x1 &x19. (x1 &x1 ) ∨ x2 = x210. x1 ∨ x2 = x2 ∨ x111. (x1 ∨ x1 )&x2 = x212. (x1 ∨ x2 ) ∨ x3 = x1 ∨ (x2 ∨ x3 )13. x ∨ x = x14. x1 &x1 = x2 &x25Билет 4. Функция Линдона. Основные тождестваA1,2,3, Bm, Cm. Полнота системы T∞В P2 для любого замкнутого класса можно выбрать конечный базис. При переходе кPk (k ≥ 3) ситуация становится более сложной - не каждый замкнутый класс имеетконечный базис.Первый такой пример в P7 был построен Линдоном. Возьмем функциюφ(x1 , x2 ) ∈ P7 . Обозначим φ(x1 , x2 ) = x1 · x2 . B = {φ}.
Kφ - класс, образованныйзамыканием функции Линдона.Функция задается таблицей0 1 2 3 4 5 60 0 0 0 0 0 0 01 0 0 1 5 6 0 02 0 0 0 0 0 0 03 0 0 0 0 0 0 04 0 0 0 0 0 0 05 0 0 5 5 5 0 06 0 0 6 6 6 0 0Тождества:6• A1,2,3 : 0 · x1 = 0; x1 · 0 = 0; x1 · (x2 · x3 )• Bm : (...((x1 · x2 ) · x3 )... · xm ) · x1 = 0; m = 1, 2...• Cm : (...((x1 · x2 ) · x3 )... · xm ) · x2 = (...(x1 · x2 ) · x3 ...) · xm ; m = 2, 3, ...Рассмотрим систему тождеств Tm = {A1,2,3 , Bi , Ci , i = 1, m}Теорема Пусть A[x1 , ..., xk ], B[x1 , ..., xk ] - две произвольные эквивалентныеформулы. Тогда существует эквивалентное преобразование из A в B при помощиTm , где m ≤ kСледствие Система∞[T∞ =Tmm=1полна в классе Kφ6Билет 5. Свойство C n.
Лемма о сохранении свойстваC n. Теорема Линдона.Kφ - класс, образованный замыканием функции Линдона.B=φОпр. Формула A обладает свойством C n , если:• A содержит x1 , x2 , ..., xn• A не содержит нулей и умножений слева• если некоторые переменные встречаются 2 раза, то между этими вхождениямиесть все остальные переменныеЛемма Пусть формула A обладает свойством C n , а B получена из A при помощитождеств A1,2,3 , Bm , Cm , где m < n. Тогда формула B тоже удовлетворяет свойствуCnСледствие Эквивалентность Bn не может быть получена при помощи тождествA1,2,3 , Bm , Cm , m < nТеорема (Линдона) В классе формул Kφ не существует конечной полнойсистемы тождеств.Д-воПусть в Kφ есть КПСТ. 000 A1 = A1... A0 = A00rrОбозначим через n наибольший номер переменной x, встречающийся в этихтождествах.
На основании теоремы данная система тождеств может быть полученаиз системы {A1,2,3 , Bm , Cm , m ≤ n}В то же время она полная, значит, из нее можно вывести тождество Bn+1 , чтопротиворечит следствию пред. леммы.77Существование КПСТ для СФЭОпр.Схемы Σ0 = Σ0 (x1 , ..., xn , z1 , ..., zp ) и Σ00 = Σ00 (x1 , ..., xn , z1 , ..., zp ) называютсяэквивалентными, если уравнения0 z1 = f1 (x1 , ..., xn )... z = f 0 (x , ..., x )pnp 1и00 z1 = f1 (x1 , ..., xn )... z = f 00 (x , ..., x )p1npописывающие их функционирование имеют равные правые части.Схемы с одинаковыми входами и без выходных полюсов считаются эквивалентнымиОпр.Пусть Σ1 - часть схемы Σ, которая является СФЭ.
Тогда она называетсяподсхемой схемы Σ. При этом полюсами (входными и выходными) подсхемы Σ1являются полюса исходной схемы Σ, попавшие в Σ1 , а также вершины (связи),соединяющие Σ1 с остальной частью схемы, и некоторые выходы эл-тов из Σ1Опр.Операция подстановки состоит в замене подсхемы Σ1 на Σ2 , у которойстолько же входов и выходов, как и у Σ1Опр.Если Σ2 эквивалентна Σ1 и подстановка согласована с соответствиемполюсов при их эквивалентности, то мы имеем эквивалентную подстановку.
ДляСФЭ справедлив принцип эквивалентной заменыОпр.Тождество Σ1 Σ2 понимается с точностью до переименования переменныхиз алфавитов X и ZТеорема (Горбовицкая) Для СФЭ в базисе из инверторов, конъюнкторов идизъюнкторов существует конечная полная система тождеств8Билет 7. Тождества в КС. Доказательство тождествI-VII. Лемма о звездах.
Теорема Мурского ополноте системы T∞Опр.КС Σ0 и Σ00 называются эквивалентными, если существуетвзаимнооднозначное соответствие T между их полюсами, такое, что матрицы fij0 и T fij00 T −1равны, т.е. состоят из соотв. равных функцийОпр.Подмножество Σ1 , состоящее из некоторых вершин схемы Σ и частиконтактов их соединяющих называется подсхемой схемы Σ, если в нем выделеныполюса так, что• Если вершина из Σ1 является полюсом в Σ, то она является также полюсомв Σ1• Если вершина из Σ1 инцидентна контакту из Σ\Σ1 , то она является полюсомв Σ18• Некоторое подмножество вершин из Σ1 (возможно, и пустое) считаетсяполюсами Σ1Опр.Если КС Σ1 и Σ2 эквивалентны и Т - взаимнооднозначное соответствиеих полюсов, обеспечивающее эквивалентность, и Σ1 - подсхема схемы Σ, топодстановка вместо Σ1 схемы Σ2 , согласованная с T, будет эквивалентнойподстановкой.Тождества - Рис.1Рис. 1: Тождества ti − tvimПусть I - цепочка, соответствующая конъюнкции x1 &...&xn .Тождества - Рис.2Рис.
2: Тождества T I − T V IIЛемма Тождества TI - TVII могут быть получены из тождеств ti - tvi mleqnпри помощи эквивалентных преобразованийЛемма (о звезде) Тождества (*) (Рис.3) выводимы из TI-TVII9Рис. 3: Тождества (*)Теорема Если Σ0 и Σ00 две эквивалентные s-полюсные КС над x1 , ..., xn , x1 , ..., xn ,то существует эквивалентное преобразование из Σ0 в Σ00 при помощи тождеств ti-tvi(m ≤ n)Следствие Система тождеств ti-tvi (m=1, 2...) является полной в классе КС9Билет 8.
Индекс схемы. Невыводимость тождестваtvin из тождеств ti − tvim(m < n). Теорема онесуществовании КПСТ для КСПусть Σ - КС над x1 , ...xn , x1 , ..., xnВведем функцию φΣ (α1 , ..., αn ) = p − b + k, где р - числе ребер в графе,получающемся из Σ при подстановке x1 = α1 , ..., xn = αn (контакт xσ переходитв ребро при xσ = 1 и выбрасывается при xσ = 0); b - число вершин данного графа, k- число связных компонентполучившегося графа.PВведем IndΣ = ( α1 , ..., αn )(mod2)Лемма Если схемы Σ0 и Σ00 над алфавитом x1 , ..., xn , x1 , ..., xn , и Σ00 получена изΣ0 эквивалентными преобразованиями ti − tvim (m < n), то IndΣ0 = IndΣ00Следствие Тождество tvin+1 невыводимо из ti − tvim (m ≤ n)Теорема Для КС не существует КПСТ10Билет 9.
Полиномиальная сводимость языков.Классы P и NP. Язык 2-выполнимости. NPполные языкиОпр.Машина Тьюринга (МТ) - абстрактная вычислительная машина. В данномслучае рассматриваем МТ с односторонней лентой, бесконечной вправо. Алфавит10МТ - А. Множество состояний - Q. A, Q - конечны. q1 - начальное состояние. a1 пустой символ.Считается, что в начальный момент времени слово ω = b1 b2 ...bn обрабатываетсяМТ, записано в первых n ячейках ленты, все остальные ячейки содержат символ a1 .Опр.Детерминированная МТ - для каждой пары вида (a, q), где a - символвходного алфавита, q - символ состояния, в программе МТ присутствует не болееодной команды вида aq → a0 q 0 dОпр.Конфигурацией (мгновенным описанием), соответствующим такту t (вэто время в процессе работы МТ на ленте записано слово ω = b1 b2 ...bm ) называетсяслово вида Ct = b1 ...bk−1 qj bk ...bm .Конфигурация, соответствующая первому тексту - начальная, последнему (еслиМТ остановилась) - заключительнаяОпр.Вычислением МТ М на входе ω называется последовательность конфигурацийC1 , C2 , ..., Ct , ..., возникающая при работенад словом ωЕсли вычисление бесконечно, tm (ω) = ∞.Среди состояний МТ имеются выделенные заключительные состояния.
Онибывают принимающие и отвергающие, соответственно результат вычислений можетбыть принять“ или отвергнуть“.””Опр.Недетерминированная МТ (НМТ) - для пары вида (a, q) в программеМТ может присутствовать несколько команд, начинающихся с aq, поэтомуМТ, находясь в состоянии q может выбрать любую команду из возможных(при этом считается, что МТ создает две копии самой себя и прослеживаетпоследовательность вычислений обоих способов действия)Опр.Вычислением НМТ на входе ω называется последовательность конфигурацийC1 , ..., Ct , ..., в которой C1 = q1 ω, а Ct+1 получается из Ct с помощью одной изкоманд, соответствующих a(t)q(t)Всякое вычисление можно изобразить ориентированной цепью, где вершины конфигурации, дуга - соединяет две последовательные вершины. ДетерминированнаяМТ - вычисление однозначно определяется входом.
НМТ - объединение цепей,соответствующих вычислениям с ω на входе; представляет собой ориентированноедерево (от корня) с корнем C1 = q1 ω10.1Распознавание языковA - конечный алфавитAω - множество всех слов конечной длины в алфавите Аkωk - длина словаL ⊂ Aω - язык в алфавите А.Опр.МТ (НМТ) с двумя заключительными состояниями (принимающим иотвергающим) распознает язык L, если для любого слова ω ∈ Aω принимающеевычисление М с ω на входе существует тогда и только тогда, когда ω ∈ L.Если ω ∈/ L - либо вычисление бесконечное, либо отвергающееОпр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
