Основы кибернетики, Теормин

Материал из eSyr's wiki.

Содержание 1 Представление функций с помощью дизъюнктивных нормальных форм. Тесты для таблиц 1.1 Определение ЧУМ, его цепи, антицепи, длины и ширины 1.2 Определение ранжированного ЧУМ и утверждение о его ширине 1.3 Определение импликанты, простой импликанты и сокращенной ДНФ 1.4 Тождество поглощения и определение неприводимой ДНФ 1.5 Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо КНФ 1.6 Тождество обобщенного склеивания и определение нерасширяемой ДНФ 1.7 Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо ДНФ 1.8 Определение тупиковой, кратчайшей и минимальной ДНФ 1.9 Определение ядровой точки, ядровой грани и ДНФ Квайна 1.10 Определение пучка, регулярной точки и регулярной грани 1.11 Определение ДНФ сумма тупиковых и критерий вхождения в нее простых импликант 1.12 Определение ДНФ пересечения тупиковых и критерий вхождения в неё простых импликант 1.13 Определение линейной ФАЛ и особенности её ДНФ 1.14 Необходимые и достаточные условия единственности представления ФАЛ в виде ДНФ 1.15 Определение монотонной ФАЛ и её нижней единицы. Особенности простых импликант монотонной ФАЛ 1.16 Определение монотонной ФАЛ, формулировка утверждения об особенностях ДНФ для монотонных ФАЛ 1.17 Определение цепной и циклической ФАЛ. Особенности ДНФ циклической ФАЛ, используемые в теореме Журавлева о ДНФ сумма минимальных 1.18 Формулировка теоремы Журавлева о ДНФ сумма минимальных 1.19 Определение ФАЛ покрытия матрицы и ее свойства, утверждение о КНФ для ФАЛ покрытия 1.20 Градиентный алгоритм покрытия матрицы и утверждение о длине градиентного покрытия 1.21 Определение протыкающего множества для граней единичного куба и верхняя оценка его мощности. 1.22 Определение функции Шеннона R(n) для ранга ДНФ и ее значение. 1.23 Определение функции Шеннона λ(n) для длины ДНФ и ее значение. 1.24 Определение длины ДНФ λ(ƒ) для ФАЛ ƒ и ее оценки для почти всех ФАЛ ƒ от n переменных 1.25 Определение ранга ДНФ R(f) для ФАЛ ƒ и ее оценки для почти всех ФАЛ ƒ от n переменных 1.26 Определение проверяющего теста матрицы и его ФАЛ, утверждение и КНФ для ФАЛ проверяющего теста 1.27 Утверждение об оценке длины диагностического теста для произвольной таблицы с заданным числом столбцов 1.28 !!! Описание ЧУМ, антицепями которого являются тупиковые ДНФ. 2 Основные классы дискретных управляющих систем. Структурные представления и эквивалентные преобразования схем, оценка их числа 2.1 Индуктивное определение формулы и реализуемой ею ФАЛ 2.2 Индуктивное определение π-схемы и нахождение реализуемой ею ФАЛ 2.3 Определение разделительной по входам (выходам) КС и формулировка леммы Шеннона 2.4 Определение подсхемы Σ' КС ∑ с указанием особенностей, связанных с объявлением вершин Σ' её полюсами. Основное тождество t4 (введение фиктивной переменной) и вспомогательное тождество t11 (лемма о звезде); обобщенные тождества t4(n) и t11(n) 2.5 Канонический вид КС от БП x1,...,xn и формулировка утверждения о приведении КС от БП x1,...,xn к каноническому виду с помощью основных тождеств. 2.6 Определение величины ||Uc(L, n)|| и её верхняя оценка 2.7 Определение тождества для формул и его подстановки 2.8 Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого можно любую формулу преобразовать в формулу с поднятыми отрицаниями 2.9 !!! Определение КС от БП x1,...,xn как помеченного графа и ФАЛ проводимости между её вершинами 2.10 Формулировка утверждения о связи между π-схемами и формулами с поднятыми отрицаниями 2.11 !!! Определение эквивалентности КС Σ', Σ" и соответствующего тождества. Основное тождество t2 (перестановка контактов в цепочке) и вспомогательное тождество t8 ("расклейка" двух цепочек длины 2 с общим контактом); обобщенные тождества t2(n) и t8(n) 2.12 !!! Определение суммарного цикломатического числа КС от БП x1,...,xn и формулировка утверждения о его изменениях при применении основных тождеств 2.13 Определение структуры CФЭ как графа специального вида и изоморфных СФЭ 2.14 Определение ранга, сложности и глубины формулы, утверждение о соотношениях между ними 2.15 !!! Понятие подформулы и применение тождества к формуле 2.16 Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого формулу с поднятыми отрицаниями можно преобразовать в формулу со следующим порядком применения базисных функций: ¬, &, ∨ 2.17 !!! Определение матрицы ФАЛ, реализуемой КС с p входами и q выходами, определение и свойства матрицы, реализемой КС с m неразделенными полюсами 2.18 Определение величины ||Uπ(L,n)|| и ее верхняя оценка 2.19 !!! Определение подстановки тождества для КС, связанной с управляющими БП, и ее применение к КС. Основное тождество t3 (цепь из противоположных контактов) и вспомогательные тождество t10 (замыкание по транзитивности); обобщенные тождества t3(n) и t10(n) 2.20 !!! Примеры моделирования основных тождеств для формул в классе СФЭ, примеры тождеств ветвления и снятия для ФЭ и входов СФЭ. Формулировка утверждения о переходе от КПСТ для ЭП формул к КПСТ для ЭП СФЭ 3 Синтез, сложность и надежность управляющих систем 3.1 !!! Определение сложности LC(F) системы ФАЛ F = (ƒ1,...,ƒm) и ее тривиальная нижняя оценка для некоторых систем ФАЛ 3.2 Определение функции Шеннона LC(n) и ее верхние оценки, получаемые методом Шеннона и методом О. Б. Лупанова 3.3 Нижняя оценка функции Шеннона Lπ(n) и то мощностное соотношение, из которого она выводится 3.4 Определение мультиплексорной ФАЛ Mn порядка n, утверждение о сложности ее реализации в классах π-схем и формул 3.5 !!! Определение сложности LK(ƒ) ФАЛ ƒ(x1...xn) в классе КС и её тривиальные нижние оценки для ФАЛ ƒ, существенно зависящей от всех своих переменных (с учетом характера этой зависимости) 3.6 Определение функции Шеннона Lπ(n) и её верхняя оценка, получаемая с помощью моделирования совершенной ДНФ на основе контактного дерева 3.7 Нижняя оценка функции Шеннона Lc(n) и то мощностное соотношение, из которого она выводится 3.8 Определение ДУМ и формулировка утверждения о свойствах стандартного ДУМ 3.9 Регулярные разбиения единичного куба и моделирование ФАЛ с помощью БП. Асимптотика сложности контактного дешифратора 3.10 !!! Асимптотически наилучший метод синтеза КС 3.11 !!! Построение самокорректирующихся КС 3.12 !!! Асимптотически наилучший метод синтеза формул в В0. Поведение функции Шеннона для глубины ФАЛ 3.13 !!! Задача синтеза схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Методы получения верхних и нижних оценок сложности, минимальность некоторых схем 3.14 Определение m-регулярного множества наборов 3.15 !!! Определение (p, q)-самокорректирующейся КС. Утверждение о сложности самокорректирующейся КС, получаемой дублированием

[править] Представление функций с помощью дизъюнктивных нормальных форм. Тесты для таблиц

[править] Определение ЧУМ, его цепи, антицепи, длины и ширины

• Отношение, обладающее свойствами рефлексивности, транзитивности, антисимметричности — отношение частичного порядка
• Если τ — отношение частичного порядка на множестве А, то пара (А,τ) — частично упорядоченное множество (ЧУМ)
• Для ЧУМ (А, τ) множество, состоящее из попарно сравнимых/несравнимых элементов а ∈ А называется цепью/антицепью
• Максимальная мощность цепей/антицепей ЧУМ называется его длиной/шириной
• Цепь С ⊆ А ЧУМ (А, τ) — неуплотняемая, если С представляет собой максимальное по включению множество соответствующего типа
• ЧУМ (А, τ) длины t (|A| = t) называется ранжированным ЧУМ, если все его неуплотняемые цепи имеют мощность t

[править] Определение ранжированного ЧУМ и утверждение о его ширине

• ЧУМ (А,τ) длины t (|A| = t) называется ранжированным ЧУМ, если все его неуплотняемые цепи имеют мощность t.

Утверждение. Если в ранжированном частично упорядоченном множестве (A,τ) через каждые два элемента одного и того же яруса проходит одинаковое число неуплотняемых цепей, то ширина частично упорядоченного множества (A,τ) равна максимальной мощности его ярусов.

Следствие. Ширина ЧУМ (Bⁿ, ≤) равна

[править] Определение импликанты, простой импликанты и сокращенной ДНФ

• ФАЛ ƒ имплицирует ФАЛ g (или, иначе, ФАЛ g поглощает ФАЛ ƒ) если N_ƒ ⊆ N_g, то есть импликация (ƒ → g) тождественно равна 1
• ЭК, которая имплицирует ФАЛ ƒ, называется импликантой этой ФАЛ
• Импликанта К ФАЛ ƒ называется простой импликантой этой ФАЛ, если она не поглощается никакой другой отличной от нее импликантой ФАЛ ƒ
• Дизъюнкция всех простых импликант ФАЛ ƒ называется ее сокращенной ДНФ

[править] Тождество поглощения и определение неприводимой ДНФ

• Тождество поглощения: x₁ ∨ x₁x₂ = x₁
• ДНФ U вида U = K₁ ∨ ... ∨ K_s называется неприводимой, если соответствующее ей покрытие является неприводимым, т.е. ни одна из граней N_K1,...,N_Ks не содержится ни в одной из других граней покрытия N_ƒ = N_K1 ∪ ... ∪ N_Ks

[править] Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо КНФ

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

[править] Тождество обобщенного склеивания и определение нерасширяемой ДНФ

Тождество обобщенного склеивания: x_iK‘ ∨ x_iK" = x_iK‘ ∨ x_iK" ∨ K‘K"

• t^ОС: x₁ & x₂ ∨ x₁ & x₃ = x₁ & x₂ ∨ x₁ & x₃ ∨ x₂ & x₃

Расширение U' ДНФ U считается строгим, если U' содержит ЭК, не являющуюся импликантой ни одной ЭК из U.

[править] Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо ДНФ

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

[править] Определение тупиковой, кратчайшей и минимальной ДНФ

• ДНФ A, реализующая ФАЛ ƒ называется тупиковой, если ƒ ≠ A' для любой A', полученной из A удалением некоторых букв или целых ЭК.
• Минимальная (кратчайшая) ДНФ — ДНФ, которая имеет наименьший ранг (длину) среди всех ДНФ реализующих ФАЛ ƒ.

[править] Определение ядровой точки, ядровой грани и ДНФ Квайна

• Набор α, α ∈ Bⁿ, называется ядровой точкой ФАЛ ƒ(x₁,...,x_n), если α ∈ N_ƒ и α входит только в одну максимальную грань ФАЛ ƒ.
• Грань N_K, являющаяся максимальной гранью ФАЛ ƒ и содержащая ядровую точку α, называется ядровой гранью.
  
• Совокупность всех различных ядровых граней ФАЛ ƒ называется ядром ФАЛ ƒ.
  
• ДНФ, получающаяся из сокращенной ДНФ ФАЛ ƒ удалением тех ЭК К, для которых грань N_K покрывается ядром ФАЛ ƒ, но не входит в него, называется ДНФ Квайна этой ФАЛ.

[править] Определение пучка, регулярной точки и регулярной грани

• Множество всех проходящих через α ( α ∈ N_ƒ ) максимальных граней ФАЛ ƒ называется пучком ФАЛ ƒ через точку α (обозначается Π_α(ƒ)).
• Точка α, α ∈ N_ƒ называется регулярной точкой ФАЛ ƒ, если существует такая точка β, что β ∈ N_ƒ и Π_β(f) ⊂ Π_α(ƒ).
• Грань N_K ФАЛ ƒ называется регулярной гранью этой ФАЛ, если все точки N_K регулярны.

[править] Определение ДНФ сумма тупиковых и критерий вхождения в нее простых импликант

• ДНФ сумма тупиковых ФАЛ f - дизъюнкция всех тех различных простых импликант этой ФАЛ, которые входят хотябы в одну тупиковую ДНФ ФАЛ f.

Утверждение. Простая импликанта К ФАЛ f входит в ДНФ ∑T тогда и только тогда, когда грань N_K не является регулярной гранью этой ФАЛ.

[править] Определение ДНФ пересечения тупиковых и критерий вхождения в неё простых импликант

• ДНФ пересечение тупиковых ФАЛ ƒ - дизъюнкция всех тех различных простых импликант этой ФАЛ, которые входят в любую тупиковую ДНФ ФАЛ ƒ.

Утверждение. ДНФ пересечение тупиковых ФАЛ ƒ состоит из тех простых импликант ФАЛ ƒ, которые соответствуют ядровым граням этой ФАЛ.

[править] Определение линейной ФАЛ и особенности её ДНФ

• Линейная ФАЛ — это ФАЛ ƒ ∈ P₂(n) вида ƒ(x₁...x_n) = α₁x₁ ⊕ ... ⊕ α_nx_n ⊕ α₀, где α₀,...,α_n — булевы константы.

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

[править] Необходимые и достаточные условия единственности представления ФАЛ в виде ДНФ

Утверждение. Совершенная ДНФ ФАЛ ƒ из P₂(n) является ее единственной ДНФ тогда и только тогда, когда во множестве N_ƒ нет соседних наборов.

[править] Определение монотонной ФАЛ и её нижней единицы. Особенности простых импликант монотонной ФАЛ

• ФАЛ ƒ (x₁,...,x_n) называется монотонной, если ƒ(α) ≤ ƒ(β) для любых наборов α,β ∈ Bⁿ таких, что α ≤ β.
• Набор α ∈ Bⁿ называется нижней единицей монотонной ФАЛ ƒ, ƒ ∈ P₂(n), если α ∈ N_ƒ и ƒ(β) = 0 для любого отличного от α набора β такого, что β ≤ α.
• Если ФАЛ ƒ(x₁,...,x_n) монотонно зависит от БП x_i, то ни одна из ее простых импликант не может содержать букву ¬x_i

[править] Определение монотонной ФАЛ, формулировка утверждения об особенностях ДНФ для монотонных ФАЛ

• ФАЛ ƒ(x₁...x_n) называется монотонной, если ƒ(α) ≤ ƒ(β) для любых наборов α и β куба B ⁿ таких, что α ≤ β

Утверждение. Сокращенная ДНФ U монотонной ФАЛ ƒ, ƒ ∈ P₂(n), является единственной тупиковой ДНФ этой ФАЛ и имеет вид: U(x₁...x_n) = ∨_β∈Nƒ⁺ K_β⁺(x₁...x_n)

[править] Определение цепной и циклической ФАЛ. Особенности ДНФ циклической ФАЛ, используемые в теореме Журавлева о ДНФ сумма минимальных

• Функция ƒ(x₁,...,x_n) называется цепной (циклической) функцией длины t, если ее сокращенная ДНФ с "геометрической" точки зрения представляет собой цепь (соответственно цикл) из t полседовательно соединенных ребер N₁, N₂, ..., N_t куба Bⁿ.

• Цепная ФАЛ ƒ нечетной длины t = 2k - 1 ≥ 3 имеет единственную минимальную ДНФ, которая совпадает с ее ДНФ ΣM и соответствует покрытию N₁ ∪ N₃ ∪ ... ∪ N_t

[править] Формулировка теоремы Журавлева о ДНФ сумма минимальных

Утверждение (теорема Журавлева). При любом n ∈ Ν, n ≥ 3, в P₂(n) существуют ФАЛ ƒ' и ƒ", имеющие общую простую импликанту К, которая входит в ДНФ ∑M одной, но не входит в ДНФ ∑M другой из этих ФАЛ и для которой S_n-3(N_K,ƒ') = S_n-3(N_K,ƒ").

[править] Определение ФАЛ покрытия матрицы и ее свойства, утверждение о КНФ для ФАЛ покрытия

• Пусть N = {α₁,...α_s,} - конечное множество, а П = (N₁,...,N_p) - система его подмножеств, образующих покрытие множества N. Сопоставим паре (N,П) матрицу M ∈ B^p,s, для которой M<i,j> = 1 ⇔ α_j ∈ N_i. Будем говорить, что i-я строка матрицы М покрывает ее j-й столбец, если M<i,j> = 1 и что система строк с номерами из I, I ⊆ [1,p], образует покрытие матрицы М, если каждый ее столбец покрывается хотябы одной строкой с номером из I, то есть система подмножеств {N_i}_{i ∈ I} задает покрытие множества N.
• Пусть M ∈ B^p,s - матрица без нулевых столбцов. Сопоставим i-й строке матрицы М БП y_i, а каждому набору β ∈ B^p значений этих переменных y = (y₁,...,y_p) - множество строк матрицы М с номерами из множества I = I(β) ⊆ [1,p], где i ∈ I(β) ⇔ β<i> = 1. ФАЛ F(y), для которой F(β) = 1 ⇔ система строк матрицы М с номерами из I(β) образует ее покрытие, будем называть функцией покрытия матрицы М.

Свойства ФАЛ покрытия матрицы

• монотонность
• ее "нижние единицы" соответствуют тупиковым покрытиям

Утверждение. Функция покрытия F(y₁,...,y_p) матрицы M ∈ B^p,s без нулевых столбцов задается КНФ вида: (*)
Следствие. В результате раскрытия скобок и приведения подобных из КНФ (*) можно получить сокращенную ДНФ ФАЛ F(y), простые импликанты которой взаимно однозначно соответствуют тупиковым покрытиям матрицы М.

[править] Градиентный алгоритм покрытия матрицы и утверждение о длине градиентного покрытия

• Градиентный алгоритм: На каждом шаге алгоритма в матрице выбирается и включается в покрытие такая строка, которая покрывает наибольшее число ещё не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером). Алгоритм заканчивается свою работу после того шага, на котором получилось покрытие.

Утверждение. Пусть для действительного γ, 0 < γ ≤ 1, в каждом столбце матрицы M, M ∈ B^p,s, имеется не меньше чем γ•p единиц. Тогда покрытие матрицы M, получаемое с помощью градиентного алгоритма, имеет длину не больше, чем , где ln⁺x = ln x, если x ≥ 1 и ln⁺x = 0, если 0 < x ≤ 1.

[править] Определение протыкающего множества для граней единичного куба и верхняя оценка его мощности.

• Пусть N = {α₁,...α_s,} - конечное множество, а П = (N₁,...,N_p) - система его подмножеств. Множество, протыкающее систему П - такое подмножество множества N,в котором ∀ i ∈ [1,p] имеется хотябы один элемент из N_i.

Утверждение. При любых натуральных n и m, m ≤ n, в кубе Bⁿ всегда найдется множество мощности не более, чем n×2^m, протыкающее все грани ранга m.

[править] Определение функции Шеннона R(n) для ранга ДНФ и ее значение.

• R(n) = max_ƒ∈P2(n) R(ƒ);
• R(n) = n × 2^{n − 1}

[править] Определение функции Шеннона λ(n) для длины ДНФ и ее значение.

• λ(n) = max_ƒ∈P2(n) λ(ƒ);
• λ(n) = 2^{n − 1}

[править] Определение длины ДНФ λ(ƒ) для ФАЛ ƒ и ее оценки для почти всех ФАЛ ƒ от n переменных

• λ(ƒ) = min_{ДНФ U, реализующим f} λ(U)
• Для почти всех ФАЛ из P₂(n) λ(ƒ)<~ (3/4)*2^{n − 1}

[править] Определение ранга ДНФ R(f) для ФАЛ ƒ и ее оценки для почти всех ФАЛ ƒ от n переменных

• R(f) = min_{ДНФ U, реализующим f} R(U)
• Для почти всех ФАЛ из P₂(n) R(f)<~ (3/4)*n*2^{n − 1}

[править] Определение проверяющего теста матрицы и его ФАЛ, утверждение и КНФ для ФАЛ проверяющего теста

Пусть есть схема Σ₁, которая реализует ФАЛ f₁. Пусть есть источник помех И. Под действием источника И схема Σ может переходить в одно из неисправных состояний Σ₂, …, Σ_s, каждое из которых реализует ФАЛ f_i, i = 2, s.

Пусть (Σ, И) — модель ненадёжной схемы Σ с возможными состояниями Σ₁, …, Σ_s, в которых реализуются ФАЛ f₁, …, f_s, определённые на множестве наборов A = {α₁, …, α_p} ⊆ Bⁿ. Рассмотрим матрицу M ∈ B^{p, s}, M[i, j] = f_j(α_i). Множество строк матрицы M с номерами из T ⊆ [1, p] называется проверяющим тестом матрицы M, если для ∀j ∈ 1, s, ∃t ∈ T такое, что M[t, 1] ≠ M[t, j].

Утверждение. Функция проверяющего теста f(y₁, …, y_p) для отделимой по столбцам матрицы M ∈ B^{p, s} может быть задана с помощью КНФ

где N = {(1, j) | j ∈ 1, s}

[править] Утверждение об оценке длины диагностического теста для произвольной таблицы с заданным числом столбцов

Утверждение. Длина любого тупикового диагностического теста для отделимой по столбцам матрицы из множества B^p,s заключена в пределах от ⌈log s⌉ до (s − 1)

[править]  !!! Описание ЧУМ, антицепями которого являются тупиковые ДНФ.

Ранжированное множество длины (n+1) всех граней n-мерного единичного куба с отношением вложения. (не точно, стр. 63)

[править] Основные классы дискретных управляющих систем. Структурные представления и эквивалентные преобразования схем, оценка их числа

[править] Индуктивное определение формулы и реализуемой ею ФАЛ

Любая переменная x_j из X считается формулой глубины 0 над множеством Б, которая реализует функцию x_j. Если φ(x₁,...,x_k) ∈ Б и для каждого i, i ∈ [1,k], определена формула F_i глубины q_i над множеством Б, которая реализует функцию ƒ_i из P_A, то запись F вида

F = φ(F₁,...,F_k)

является формулой глубины q = max{q₁,...,q_k} + 1 над Б, которая реализует функцию ƒ вида ƒ = φ(ƒ₁,...,ƒ_k).

[править] Индуктивное определение π-схемы и нахождение реализуемой ею ФАЛ

Простейшей π-схемой считается любая (1,1)-КС, которая состоит из одного контакта, соединяющего полюса. Если π-схемы ∑₁ и ∑₂ уже определены, то (1,1)-КС ∑₁(∑₂), которая получается в результате их последовательного (параллельного) соединения тоже является π-схемой.

[править] Определение разделительной по входам (выходам) КС и формулировка леммы Шеннона

КС разделительна по входам (выходам), если ФАЛ проводимости для ∀ различных входов (выходов) ≡ 0.

Лемма Шеннона: Пусть Σ = Σ''(Σ') - результат стыковки ⇒ F ≥ F' × F''. F = F' × F'', если Σ'' разделительна по входам, или Σ' разделительна по выходам.

[править] Определение подсхемы Σ' КС ∑ с указанием особенностей, связанных с объявлением вершин Σ' её полюсами. Основное тождество t₄ (введение фиктивной переменной) и вспомогательное тождество t₁₁ (лемма о звезде); обобщенные тождества t₄⁽ⁿ⁾ и t₁₁⁽ⁿ⁾

Определение подсхемы Σ' КС Σ:
Σ' — подсхема схемы Σ ⇔

1. V(Σ') ⊆ V(Σ)
2. E(Σ') ⊆ E(Σ)
3. • ∀ полюс Σ, вошедший в Σ' — полюс Σ'
   • ∀ вершина Σ', инцидентная контакту Σ\Σ' - полюс Σ'
   • ∀ другая вершина м. б. полюсом Σ'.
     

t4
t11

[править] Канонический вид КС от БП x₁,...,x_n и формулировка утверждения о приведении КС от БП x₁,...,x_n к каноническому виду с помощью основных тождеств.

∑^ /*здесь и далее крышка пишется над сигмой*/ - схема канонического вида ⇔ 1) ∀ контакт ∑^ лежит на стандартной цепи порядка n, явл. подсхемой ∑^ с полюсами в конечных вершинах цепи. 2) ∀ внутренняя вершина ∑^ - внутренняя вершина стандартной цепи 3) в ∑^ отсутствуют висячие циклы и || стандартные цепи 4) в ∑^ нет существенных транзитивных проводимостей /*вопрос +-, комментарий лектора: отсутствует утверждение о переходе к КВ*/

∑^ получается из ∑ удалением ∑' (подсхемы) и заменой ∑' на ∑' ' с соотв. присоединением полюсов, эквив. ∑ (принцип эквивалентной замены).

[править] Определение величины ||U^c(L, n)|| и её верхняя оценка

• U^c(L, n) — множество приведенных СФЭ Σ = Σ(x₁, …, x_n; z₁) над базисом Б₀, для которых L(Σ) ≤ L.
• ||U^c(L, n)|| — число попарно неэквивалентных схем в U^c(L, n)

Утверждение. Для любых натуральных n и L выполняется неравенство: ||U^c(L, n)|| ≤ (8(L + n))^{L + 1}.

[править] Определение тождества для формул и его подстановки

Если к правой и левой частям (1) применить подстановку, то получим тождество:

где и , которое называется подстановкой для тождества t.

[править] Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого можно любую формулу преобразовать в формулу с поднятыми отрицаниями

В расширенную основную систему входят следующие тождества: r~^осн = {r^M, r^A, r^К, r^ОП, r^D, r^ПК, t^П} /* как обычно, ~ стоит над r */

• r^A = {t^A_&,t^A_∨}
• r^K = {t^K_&,t^K_∨}
• r^ОП = {t^ОП_&,t^ОП_∨}
• r^D = {t^D_&,t^D_∨}
• r^ПК = {t^ПК_{0, &}, t^ПК_{0, ∨}, t^ПК_{1, &}, t^ПК_{1, ∨}}

все тождества описаны тут.

[править]  !!! Определение КС от БП x₁,...,x_n как помеченного графа и ФАЛ проводимости между её вершинами

(параграф 6 главы 2)

[править] Формулировка утверждения о связи между π-схемами и формулами с поднятыми отрицаниями

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

[править]  !!! Определение эквивалентности КС Σ', Σ" и соответствующего тождества. Основное тождество t₂ (перестановка контактов в цепочке) и вспомогательное тождество t₈ ("расклейка" двух цепочек длины 2 с общим контактом); обобщенные тождества t₂⁽ⁿ⁾ и t₈⁽ⁿ⁾

Σ₁ = Σ₁(x₁,....,x_n;a₁,...,a_m) Σ₂ = Σ₂(x₁,....,x_n;a₁,...,a_m)

Σ₁ ~ Σ₂ означает что для любых i,j из отрезка [1,m] ФАЛ прововодимости от a_i к a_j В КС Σ₁ равна ФАЛ прововодимости от a_i к a_j В КС Σ₂

[править]  !!! Определение суммарного цикломатического числа КС от БП x₁,...,x_n и формулировка утверждения о его изменениях при применении основных тождеств

(глава 2, стр 72) Множество всех связных компонент графа обозначается через c(G).Напомним, что |E(G)| − |V(G)| + |c(G)| > 0 и что левая часть неравенства называется цикломатическим числом графа G.

[править] Определение структуры CФЭ как графа специального вида и изоморфных СФЭ

Под "абстрактной" схемой понимается сеть, часть пометок которой составляют входные переменные и в каждой вершине которой реализуется функция (столбец из функций) от этих переменных. При этом считается, что сама схема реализует систему (матрицу), состоящую из функций (соответственно столбцов функций), реализованных на её выходах. В качестве выходных пометок схемы используются, как правило, специальные выходные переменные, а схема Sigma с входными переменными (входами) x₁,..x_n и выходными переменными z₁,..z_m записывается в виде Sigma=Sigma(x₁,..x_n; z₁,..z_n).

Две СФЭ считаются изоморфными, если они изоморфны как помеченные графы, и эквивалентными, если они реализуют равные системы ФАЛ.

[править] Определение ранга, сложности и глубины формулы, утверждение о соотношениях между ними

• R(F) — ранг формулы F — число листьев, связанного с ней дерева
• L(F) — сложность формулы F — число остальных вершин, связанного с ней дерева (не листьев)
• D(F) — глубина формулы F — глубина корня, связанного с ней дерева
• R(F) ≤ L(F) + 1 ≤ 2^D(F)

[править]  !!! Понятие подформулы и применение тождества к формуле

[править] Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого формулу с поднятыми отрицаниями можно преобразовать в формулу со следующим порядком применения базисных функций: ¬, &, ∨

• Дистрибутивность t_{&, ∨}^D: x₁ & (x₂ ∨ x₃) = (x₁ & x₂) ∨ (x₁ & x₃)
• Коммутативность коньюнкции t_&^К: x₁ & x₂ = x₂ & x₁

[править]  !!! Определение матрицы ФАЛ, реализуемой КС с p входами и q выходами, определение и свойства матрицы, реализемой КС с m неразделенными полюсами

Глава 2, стр. 57-58

[править] Определение величины ||U^π(L,n)|| и ее верхняя оценка

• ||U^π(L,n)|| - число попарно не эквивалентных приведенных π-схем от БП x₁,...,x_n сложности ≤ L

• ||U^π(L,n)|| ≤ (16n)^L

[править]  !!! Определение подстановки тождества для КС, связанной с управляющими БП, и ее применение к КС. Основное тождество t₃ (цепь из противоположных контактов) и вспомогательные тождество t₁₀ (замыкание по транзитивности); обобщенные тождества t₃⁽ⁿ⁾ и t₁₀⁽ⁿ⁾

[править]  !!! Примеры моделирования основных тождеств для формул в классе СФЭ, примеры тождеств ветвления и снятия для ФЭ и входов СФЭ. Формулировка утверждения о переходе от КПСТ для ЭП формул к КПСТ для ЭП СФЭ

[править] Синтез, сложность и надежность управляющих систем

[править]  !!! Определение сложности L^C(F) системы ФАЛ F = (ƒ₁,...,ƒ_m) и ее тривиальная нижняя оценка для некоторых систем ФАЛ

[править] Определение функции Шеннона L^C(n) и ее верхние оценки, получаемые методом Шеннона и методом О. Б. Лупанова

• L^C(n) = max_ƒ∈P2(n)L^C(ƒ)
• Метод Шеннона: L^C(n) <∼ 8•2ⁿ/n
• Метод Лупанова: L^C(n) ≤ (2ⁿ/n)•(1 + (5logn + O(1))/n)

[править] Нижняя оценка функции Шеннона L^π(n) и то мощностное соотношение, из которого она выводится

• L^π(n) ≥ 2ⁿ / log₂n (Асимптотически больше)
• ||U^π(L,n)|| ≤ (16n)^L

[править] Определение мультиплексорной ФАЛ M_n порядка n, утверждение о сложности ее реализации в классах π-схем и формул

Функция вида µ_n(x₁,..x_n,y₀,..y_2ⁿ-1) = U _{(a=(a1,..an))} x₁^a₁...x_n^a_ny_v(a) называется мультиплексорной функцией (мультиплексором) порядка n, а переменные x=(x₁,..x_n) называются адресными, y=(y₀,..y_2ⁿ-1) - информационными БП мультиплексора µ_n.

L^п(µ_n) <= 3*2ⁿ-2, L^Ф(µ_n) <= 2ⁿ⁺²-3;

[править]  !!! Определение сложности L^K(ƒ) ФАЛ ƒ(x₁...x_n) в классе КС и её тривиальные нижние оценки для ФАЛ ƒ, существенно зависящей от всех своих переменных (с учетом характера этой зависимости)

L^K (f) > n для ФАЛ f, существенно зависящей от всех своих переменных.

[править] Определение функции Шеннона L^π(n) и её верхняя оценка, получаемая с помощью моделирования совершенной ДНФ на основе контактного дерева

• L^π(n) = max_ƒ∈P2(n)L^π(ƒ)
• L^π(n) ≤ 2^{n + 1} − 2 //FIXME

[править] Нижняя оценка функции Шеннона L^c(n) и то мощностное соотношение, из которого она выводится

• L^C(n) ≥ 2ⁿ / n (Асимптотически больше)
• ||U^C(L,n)|| ≤ (8(L + n))^{L + 1}

[править] Определение ДУМ и формулировка утверждения о свойствах стандартного ДУМ

• Дизъюнктивно-универсальное множество (ДУМ) G порядка n и ранга p ⇔ ∀ g ∈ P₂(n) ∃ g₁,...,g_p ∈ G : g = g₁∪...∪g_p

Утверждение. Пусть m, S, p ∈ N: p * S ≥ 2^m, тогда ∃ ДУМ G порядка m и ранга p:

1. |G| ≤ p * 2^S
2. В G ∃ система из p ортогональных функций ψ₁,...,ψ_p : ∀ g ∈ G имплицирует одну из них.

[править] Регулярные разбиения единичного куба и моделирование ФАЛ с помощью БП. Асимптотика сложности контактного дешифратора

Множество δ, δ ⊆ B^q, называется m-регулярным множеством наборов куба B^q, если m < q, |δ| = 2^m и все префиксы длины m наборов из δ различны.

m-регулярное разбиение куба B^q — разбиение этого куба, состоящее из m-регулярных множеств δ₁, …, δ_{q − m}. (???)

моделирование ФАЛ с помощью БП - ???

L^K (Q_n) ~ 2ⁿ

[править]  !!! Асимптотически наилучший метод синтеза КС

[править]  !!! Построение самокорректирующихся КС

[править]  !!! Асимптотически наилучший метод синтеза формул в В₀. Поведение функции Шеннона для глубины ФАЛ

[править]  !!! Задача синтеза схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Методы получения верхних и нижних оценок сложности, минимальность некоторых схем

[править] Определение m-регулярного множества наборов

Множество δ, δ ⊆ B^q, называется m-регулярным множеством наборов куба B^q, если m < q, |δ| = 2^m и все префиксы длины m наборов из δ различны.

[править]  !!! Определение (p, q)-самокорректирующейся КС. Утверждение о сложности самокорректирующейся КС, получаемой дублированием