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

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

Параграфф 2

Лемма 2.1. Ширина частично упорядоченного множества

( ) равна .

Параграфф 3

Теорема 3.1. Пусть A1 и A2 — сокращенные ДНФ ФАЛ f1 и f2_ соответственно, а неприводимая ДНФ A получается из формулы A1 · A2_ в результате раскрытия скобок

и приведения подобных. Тогда A — сокращенная ДНФ ФАЛ f = f1 · f2.

Следствие. Если неприводимая ДНФ A получается из КНФ B ФАЛ f в результате раскрытия скобок и приведения подобных, то A — сокращенная ДНФ ФАЛ f.

Теорема 3.2. Неприводимая ДНФ является сокращенной ДНФ тогда и только тогда, когда она не имеет строгих расширений.

Следствие. Из любой ДНФ A ФАЛ f можно получить сокращенную ДНФ этой ФАЛ в результате построения последовательных строгих расширений и приведения подоб-

ных до получения неприводимой ДНФ, не имеющей строгих расширений.

Параграфф 4

Лемма 4.1. Дизъюнктивная нормальная форма ∩T ФАЛ f состоит из тех простых импликант ФАЛ f, которые соответствуют ядровым граням этой ФАЛ.

Теорема 4.1 ([6, 9, 10]). Простая импликанта K ФАЛ f входит в ДНФ ΣT тогда и только тогда, когда грань NK не является регулярной гранью этой ФАЛ.

Параграфф 5

Лемма 5.1. Совершенная ДНФ ФАЛ f из P2 (n) является ее единственной ДНФ от БП X (n) тогда и только тогда, когда во множестве Nf нет соседних наборов.

Следствие. Совершенная ДНФ линейной существенной ФАЛ является единственной ДНФ этой ФАЛ от ее существенных БП.

Лемма 5.2. Сокращенная ДНФ A монотонной ФАЛ f, f ∈ P2 (n), является единственной тупиковой ДНФ этой ФАЛ и имеет вид:

При этом все наборы из N+f являются ядровыми точками ФАЛ f.

Следствие. Монотонная ФАЛ является ядровой ФАЛ.

Теорема 5.1 (ср. [6, 9, 10]). При любом n ∈ N, n 3, в P2 (n) существуют ФАЛ f1 и f2, имеющие общую простую импликанту K, которая входит в ДНФ ΣM одной, но не

входит в ДНФ ΣM другой из этих ФАЛ и для которой Sn−3 (NK, f1) = Sn−3 (NK, f2).

Параграф 6

Лемма 6.1. Функция покрытия F (y1, . . . , yp) матрицы M, M ∈ , без нулевых столбцов задается КНФ вида:

Следствие. В результате раскрытия скобок и приведения подобных из КНФ (6.1) можно получить сокращенную ДНФ ФАЛ F (y), простые импликанты которой взаимно

однозначно соответствуют тупиковым покрытиям матрицы M.

Теорема 6.1 ([6]). Пусть для действительного γ, 0<γ <=1, в каждом столбце матрицы M, M ∈ , имеется не меньше, чем γ ·p, единиц. Тогда покрытие матрицы M, получаемое с помощью градиентного алгоритма, имеет длину не больше, чем

Лемма 6.2 ([18]). При любых натуральных n и m, m <= n, в кубе всегда найдется подмножество мощности не более, чем , протыкающее все грани ранга m.

Параграф 7

Лемма 7.1. Число тупиковых (минимальных) ДНФ у ФАЛ f из P2 (n), n >= 4, вида

равно (соответственно ).

Теорема 7.1. Для любого n, n принадлежит N, и для почти всех ФАЛ f, f принадлежит P2(n), имеют место:

Параграф 8

Лемма 8.1. Функция теста f (y1, . . . , yp) для отделимой по столбцам матрицы M, M ∈ Bp,s, и цели контроля N может быть задана с помощью КНФ

Следствие. Каждая элементарная конъюнкция вида yt1 · · · ytr сокращенной ДНФ функции f (y1, . . . , yp), получа ющаяся из КНФ (8.1) в результате раскрытия скобок и приведения подобных, соответствует тупиковому тесту, связанному с множеством T = {t1, . . . , tr} и обратно.

Лемма 8.2. Длина любого тупикового диагностического теста для отделимой по столбцам матрицы из множества заключена в пределах от до (s − 1).

Лемма 8.3. Пусть ϕ (s), t(s) и p (s) — целочисленные неотрицательные функции натурального аргумента s, для которых

Тогда у почти всех отделимых по столбцам матриц из первые t (s) строк образуют диагностический тест.

Следствие. Для любой неотрицательной и неограниченно возрастающей функции ϕ (s) у почти всех отделимых по столбцам матриц из длина минимального диагности-

ческого теста не больше, чем 2 log s + ϕ (s)

Глава 2

Параграф 2

Лемма 2.1. Для формулы F, F ∈ , выполняются неравенства

Следствие.

Лемма 2.2. Пусть F — формула вида x1 ◦ · · · ◦ xt, где ◦ ∈ {&, ∨}, и пусть для целых неотрицательных чисел d, d1, . . . , dt выполнено неравенство . Тогда

существует подобная F формула ˇF, в которой исходящая глубина входа xi, i = 1, . . . , t, не больш е, чем d − di.

Следствие. Для ЭК или ЭД F1 существует подобная формула ^F1 такая, что

Лемма 2.3. Для любой формулы F из UΦ существует подобная ей формула ˇF такая, что

Следствие. Для любой ДНФ или КНФ U существует по-

добная ей формула ˇU такая, что

Теорема 3.1. Для любых натуральных n, L, D выполняются неравенства

, ,

Параграф 4

Лемма 4.1. Для любой формулы F, F ∈ , выполняются неравенства

Теорема 4.1. Для любых L >= 0, T => 0 и любого натурального n справедливы неравенства

где c — некоторая константа, зависящая от базиса Б.

Параграф 5

Лемма 5.1. Любой π-схеме Σ можно сопоставить эквивалентную ей формулу F из с поднятыми отрицаниями такую, что R(F) = L(Σ) и обратно.

Лемма 5.2. При любых натуральных L и n выполняется неравенство

Лемма 5.3. При любых натуральных L и n выполняется неравенство

Параграф 6

Лемма 6.1. Пусть КС Σ является результатом стыковки вида Σ = ( ), а F, и — матрицы, реализуемые КС и соответственно. Тогда

если КС разделительна по входам или КС разделительна по выходам.

Следствие 1. В случае разделительности КС по вхо дам в каждой вершине КС Σ, Σ = (Σ), которая соответствует выходу КС , реализуется тот же самый столбец

ФАЛ, что и в КС .

Следствие 2. Равенство (6.3) выполняется на любом наборе значений БП, на котором КС разделительна по входам или КС разделительна по выходам.

Лемма 6.2. Стыковка КС вида является правильной, если хотя бы одна из КС слаборазделительна.

Глава 3

Параграф 1

Теорема 1.1. Если τ — конечная полная система тождеств для ЭП формул из

, то — конечная полная система тождеств для ЭП СФЭ из

Параграф 2

Лемма 2.2. Любую формулу F (x1, . . . , xn), реализующую ФАЛ f, с помощью ЭП на основе системы тождеств τ осн можно преобразовать в совершенную ОДНФ ФАЛ f от БП X (n).

Теорема 2.1. Система τ осн — полная система тождеств.

Следствие. Система тождеств — КПСТ для ЭП СФЭ из .

Параграф 3

Лемма 3.1. Если базис Б допускает квазибесповторное моделирование в базисе , то для любой формулы F из существует эквивалентная ей формула из такая, что

где c1, c2, c3 — некоторые константы, зависящие только от базисов Б, .

Лемма 3.2. Существуют квазибесповторные формулы F¬,F& и F∨ над базисом Б, которые реализуют ФАЛ x1, x1 ·x2 и x1 ∨ x2 соответственно.

Теорема 3.1 (теорема перехода). Пусть τ — КПСТ для ЭП формул из , а и Π — системы тождеств для перехода от базиса Б к базису и от базиса к базису Б соответственно. Тогда система тождеств {Π_ (τ ) ,Π_ (Π)} является КПСТ для ЭП формул из .

Следствие. Из системы тождеств τ осн для ЭП формул из указанным в теореме способом можно получить КПСТ для ЭП формул в любом базисе Б.

Параграф 4

Параграф 5

Лемма 5.1. Для любой КС Σ, где Σ ∈ UK и Σ = Σ(x1, . . . , xn; a1, . . . , am), и любой эквивалентной Σ КС ^Σ(x1, . . . , xn; a1, . . . , am) канонического вида существует

ЭП

Теорема 5.1. Для любых двух эквивалентных КС от БП x1, . . . , xn существует ЭП вида

Следствие 1. Система τn является КПСТ для ЭП КС из от БП x1, . . . , xn.

Следствие 2. Система τ∞ является ПСТ для ЭП КС из .

Лемма 5.2. Если , то

делится на .

Теорема 5.2. В классе не существует конечной полной системы тождеств

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)