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

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

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

Содержание

1 Представление функций с помощью дизъюнктивных нормальных форм. Тесты для таблиц
2 Основные классы дискретных управляющих систем. Структурные представления и эквивалентные преобразования схем, оценка их числа
3 Синтез, сложность и надежность управляющих систем

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

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

Отношение, обладающее свойствами рефлексивности, транзитивности, антисимметричности — отношение частичного порядка
Если τ — отношение частичного порядка на множестве А, то пара (А,τ) — частично упорядоченное множество (ЧУМ)
Для ЧУМ (А, τ) множество, состоящее из попарно сравнимых/несравнимых элементов а ∈ А называется цепью/антицепью
Максимальная мощность цепей/антицепей ЧУМ называется его длиной/шириной
Цепь С ⊆ А ЧУМ (А, τ) — неуплотняемая, если С представляет собой максимальное по включению множество соответствующего типа
ЧУМ (А, τ) длины 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_K₁,...,N_{K_s} не содержится ни в одной из других граней покрытия N_ƒ = N_K₁ ∪ ... ∪ N_{K_s}

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

Утверждение. Если неприводимая ДНФ 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_ƒ∈P₂(n) R(ƒ);
R(n) = n × 2^{n − 1}

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

λ(n) = max_ƒ∈P₂(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₁₁⁽ⁿ⁾

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

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

t₄
t₁₁

[править] Канонический вид КС от БП 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}.

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

Подстановка — вместо переменных функции

F (x 1,..., x n)

подставляем функции:

F (F 1,..., F n)

Тождество — $\hat{t}: F(x)' = F(x)''$ (1)

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

$\hat{t} : \hat{F}' = \hat{F}''$

где $\hat{F}' = \hat{F}'(F_1, \ldots ,F_n)$ и $\hat{F}'' = \hat{F}''(F_1, ... ,F_n)$ , которое называется подстановкой для тождества 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₈⁽ⁿ⁾

$Σ 1 = Σ 1 (x 1,...., x n; a 1,..., a m)$ $Σ 2 = Σ 2 (x 1,...., x n; a 1,..., a m)$

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

[править] !!! Определение суммарного цикломатического числа КС от БП 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_ƒ∈P₂(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=(a₁,..a_n))} 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_ƒ∈P₂(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:

|G| ≤ p * 2^S
В 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)-самокорректирующейся КС. Утверждение о сложности самокорректирующейся КС, получаемой дублированием

Основы Кибернетики

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

Календарь

	пт	пт	пт	пт	пт
Февраль		09	16	26
Март	02	09	16	23	30
Апрель	06	13	20	27
Май	04	11	18	25

Материалы к экзамену

Экзаменационные вопросы 3 потока 2007 (new!) | Алгоритмы решения задач | Теормин | Определения

Получено с http://esyr.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D0%BA%D0%B8%D0%B1%D0%B5%D1%80%D0%BD%D0%B5%D1%82%D0%B8%D0%BA%D0%B8%2C_%D0%A2%D0%B5%D0%BE%D1%80%D0%BC%D0%B8%D0%BD

@@ Строка 1: / Строка 1: @@
-== From Ebaums Inc to MurkLoar. ==
+== Представление функций с помощью дизъюнктивных нормальных форм. Тесты для таблиц ==
-We at EbaumsWorld consider you as disgrace of human race.
-Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
+=== Определение <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span>, его цепи, антицепи, длины и ширины ===
-Dig yourself a grave - you will need it.
+* Отношение, обладающее свойствами рефлексивности, транзитивности, антисимметричности — ''отношение частичного порядка''
+* Если &tau; — отношение частичного порядка на множестве А, то пара (А,&tau;) — ''частично упорядоченное множество (<span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span>)''
+* Для <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span> (А, &tau;) множество, состоящее из попарно сравнимых/несравнимых элементов а &isin; А называется ''цепью/антицепью''
+* Максимальная мощность цепей/антицепей <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span> называется его ''длиной/шириной''
+* Цепь С &sube; А <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span> (А, &tau;) — ''неуплотняемая'', если С представляет собой максимальное по включению множество соответствующего типа
+* <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span> (А, &tau;) длины t (|A| = t) называется ''ранжированным <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span>'', если все его неуплотняемые цепи имеют мощность t
+=== Определение ранжированного <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span> и утверждение о его ширине ===
+* <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span> (А,&tau;) длины t (|A| = t) называется ''ранжированным <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span>'', если все его неуплотняемые цепи имеют мощность t.
+'''Утверждение'''. Если в ранжированном частично упорядоченном множестве (A,&tau;) через каждые два элемента одного и того же яруса проходит одинаковое число неуплотняемых цепей, то ширина частично упорядоченного множества (A,&tau;) равна максимальной мощности его ярусов.
+'''Следствие'''. Ширина <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span> (B<sup>n</sup>, &le;) равна [[Изображение:Semialigned_width.png|32px]]
+=== Определение импликанты, простой импликанты и сокращенной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ===
+* <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; ''имплицирует'' <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''g'' (или, иначе, <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''g'' ''поглощает'' <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;) если N<sub>&fnof;</sub> &sube; N<sub>''g''</sub>, то есть импликация (&fnof; &rarr; ''g'') тождественно равна 1
+* <span title="элементарная конъюнкция" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЭК</span>, которая имплицирует <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;, называется ''импликантой'' этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>
+* Импликанта К <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; называется ''простой импликантой'' этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>, если она не поглощается никакой другой отличной от нее импликантой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;
+* Дизъюнкция всех простых импликант <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; называется ее ''сокращенной'' <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span>
+=== Тождество поглощения и определение неприводимой <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ===
+* Тождество поглощения: ''x''<sub>1</sub> &or; ''x''<sub>1</sub>''x''<sub>2</sub> = ''x''<sub>1</sub>
+* <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ''U'' вида ''U'' = ''K''<sub>1</sub> &or; ... &or; ''K''<sub>s</sub> называется ''неприводимой'', если соответствующее ей покрытие является неприводимым, т.е. ни одна из граней ''N<sub>K<sub>1</sub></sub>'',...,''N<sub>K<sub>s</sub></sub>'' не содержится ни в одной из других граней покрытия ''N<sub>&fnof;</sub>'' = ''N<sub>K<sub>1</sub></sub>'' &cup; ... &cup; ''N<sub>K<sub>s</sub></sub>''
+=== Формулировка утверждения, связанного с построением сокращенной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> из какой-либо КНФ ===
+'''Утверждение'''. Если неприводимая <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ''U'' получается из КНФ ''B'' <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; в результате раскрытия скобок и приведения подобных, то ''U'' &mdash; сокращенная <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;.
+=== Тождество обобщенного склеивания и определение нерасширяемой <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ===
+Тождество обобщенного склеивания: ''x<sub>i</sub>K''&lsquo; &or; ''<span style="text-decoration:overline;">x</span><sub>i</sub>K''&quot; = ''x<sub>i</sub>K''&lsquo; &or; ''<span style="text-decoration:overline;">x</span><sub>i</sub>K''&quot; &or; ''K''&lsquo;''K''&quot;
+* ''t''<sup>ОС</sup>: ''x''<sub>1</sub> & ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>3</sub> = ''x''<sub>1</sub> & ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>3</sub> ∨ ''x''<sub>2</sub> & ''x''<sub>3</sub>
+Расширение U' ДНФ U считается ''строгим'', если U' содержит ЭК, не являющуюся импликантой ни одной ЭК из U.
+=== Формулировка утверждения, связанного с построением сокращенной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> из какой-либо <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ===
+'''Утверждение'''. Из любой <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> А <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; можно получить сокращенную <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> в результате построения последовательных строгих расширений и приведения подобных до получения неприводимой <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span>, не имеющей строгих расширений.
+=== Определение тупиковой, кратчайшей и минимальной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ===
+* <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> A, реализующая <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; называется ''тупиковой'', если &fnof; &ne; A' для любой A', полученной из A удалением некоторых букв или целых <span title="элементарная конъюнкция" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЭК</span>.
+* ''Минимальная'' (''кратчайшая'') <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> &mdash; <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span>, которая имеет наименьший ранг (длину) среди всех <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> реализующих <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;.
+=== Определение ядровой точки, ядровой грани и <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> Квайна ===
+* Набор ''&alpha;, &alpha;'' &isin; ''B<sup>n</sup>'', называется ''ядровой точкой'' <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''&fnof;(x<sub>1</sub>,...,x<sub>n</sub>)'', если ''&alpha;'' &isin; ''N''<sub>&fnof;</sub> и ''&alpha;'' входит только в одну максимальную грань <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;.
+* Грань ''N<sub>K</sub>'', являющаяся максимальной гранью <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; и содержащая ядровую точку ''&alpha;'', называется ''ядровой гранью''.<br>
+* Совокупность всех различных ядровых граней <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; называется ''ядром'' <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;.<br>
+* <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span>, получающаяся из сокращенной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; удалением тех <span title="элементарная конъюнкция" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЭК</span> ''К'', для которых грань ''N<sub>K</sub>'' покрывается ядром <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;, но не входит в него, называется ''<span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> Квайна'' этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>.
+=== Определение пучка, регулярной точки и регулярной грани ===
+* Множество всех проходящих через &alpha;  ( &alpha; &isin; N<sub>&fnof;</sub> ) максимальных граней <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; называется ''пучком'' <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; через точку &alpha; (обозначается &Pi;<sub>&alpha;</sub>(&fnof;)).
+* Точка &alpha;, &alpha; &isin; N<sub>&fnof;</sub> называется ''регулярной точкой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;'', если существует такая точка &beta;, что &beta; &isin; N<sub>&fnof;</sub> и &Pi;<sub>&beta;</sub>(f) &sub; &Pi;<sub>&alpha;</sub>(&fnof;).
+* Грань N<sub>K</sub> <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; называется регулярной гранью этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>, если все точки N<sub>K</sub> регулярны.
+=== Определение <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> сумма тупиковых и критерий вхождения в нее простых импликант ===
+* ''<span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> сумма тупиковых <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> f'' - дизъюнкция всех тех различных простых импликант этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>, которые входят хотябы в одну тупиковую <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''f''.
+'''Утверждение'''. Простая импликанта К <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> f входит в <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> &sum;T тогда и только тогда, когда грань N<sub>K</sub> не является регулярной гранью этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>.
+=== Определение <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> пересечения тупиковых и критерий вхождения в неё простых импликант ===
+* ''<span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> пересечение тупиковых <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>'' &fnof; - дизъюнкция всех тех различных простых импликант этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>, которые входят в любую тупиковую <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;.
+'''Утверждение'''. <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> пересечение тупиковых <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; состоит из тех простых импликант <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;, которые соответствуют ядровым граням этой  <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>.
+=== Определение линейной <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> и особенности её <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ===
+* Линейная <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &mdash; это <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; &isin; P<sub>2</sub>(n) вида &fnof;(''x''<sub>1</sub>...''x''<sub>n</sub>) = &alpha;<sub>1</sub>''x''<sub>1</sub> &oplus; ... &oplus; &alpha;<sub>n</sub>''x''<sub>n</sub> &oplus; &alpha;<sub>0</sub>, где &alpha;<sub>0</sub>,...,&alpha;<sub>n</sub> &mdash; булевы константы.
+'''Утверждение'''. Совершенная <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> линейной существенной функции является единственной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>  от её существенных БП.
+=== Необходимые и достаточные условия единственности представления <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> в виде <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ===
+'''Утверждение'''. Совершенная <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; из P<sub>2</sub>(n) является ее единственной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> тогда и только тогда, когда во множестве N<sub>&fnof;</sub> нет соседних наборов.
+=== Определение монотонной <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> и её нижней единицы. Особенности простых импликант монотонной <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ===
+* <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; (x<sub>1</sub>,...,x<sub>n</sub>) называется ''монотонной'', если &fnof;(&alpha;) &le; &fnof;(&beta;) для любых наборов &alpha;,&beta; &isin; B<sup>n</sup> таких, что &alpha; &le; &beta;.
+* Набор &alpha; &isin; B<sup>n</sup> называется ''нижней единицей'' монотонной <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;, &fnof; &isin; P<sub>2</sub>(n), если &alpha; &isin; N<sub>&fnof;</sub> и &fnof;(&beta;) = 0 для любого отличного от &alpha; набора &beta; такого, что &beta; &le; &alpha;.
+* Если <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;(x<sub>1</sub>,...,x<sub>n</sub>) монотонно зависит от БП x<sub>i</sub>, то ни одна из ее простых импликант не может содержать букву  &not;x<sub>i</sub>
+=== Определение монотонной <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>, формулировка утверждения об особенностях <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> для монотонных <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ===
+* <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;(''x''<sub>1</sub>...''x''<sub>n</sub>) называется ''монотонной'', если &fnof;(&alpha;) &le; &fnof;(&beta;) для любых наборов &alpha; и &beta; куба ''B'' <sup>n</sup> таких, что &alpha; &le; &beta;
+'''Утверждение'''. Сокращенная <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ''U'' монотонной <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;, &fnof; &isin; P<sub>2</sub>(n), является единственной тупиковой <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> этой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> и имеет вид: ''U''(''x''<sub>1</sub>...''x''<sub>n</sub>) = &or;<sub>&beta;&isin;''N''<sub>&fnof;</sub><sup>+</sup></sub> ''K''<sub>&beta;</sub><sup>+</sup>(''x''<sub>1</sub>...''x''<sub>n</sub>)
+=== Определение цепной и циклической <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>. Особенности <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> циклической <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>, используемые в теореме Журавлева о <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> сумма минимальных ===
+* Функция &fnof;(x<sub>1</sub>,...,x<sub>n</sub>) называется ''цепной'' (''циклической'') функцией длины t, если ее сокращенная <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> с "геометрической" точки зрения представляет собой цепь (соответственно цикл) из t полседовательно соединенных ребер N<sub>1</sub>, N<sub>2</sub>, ..., N<sub>t</sub> куба B<sup>n</sup>.
+* Цепная <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof; нечетной длины t = 2k - 1 &ge; 3 имеет единственную минимальную <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span>, которая совпадает с ее <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> &Sigma;M и соответствует покрытию N<sub>1</sub> &cup; N<sub>3</sub> &cup; ... &cup; N<sub>t</sub>
+=== Формулировка теоремы Журавлева о <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> сумма минимальных ===
+'''Утверждение (теорема Журавлева)'''. При любом n &isin; &Nu;, n &ge; 3, в P<sub>2</sub>(n) существуют <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> &fnof;' и &fnof;", имеющие общую простую импликанту К, которая входит в <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> &sum;M одной, но не входит в <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> &sum;M другой из этих <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> и для которой S<sub>n-3</sub>(N<sub>K</sub>,&fnof;') = S<sub>n-3</sub>(N<sub>K</sub>,&fnof;").
+=== Определение <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> покрытия матрицы и ее свойства, утверждение о КНФ для <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> покрытия ===
+* Пусть N = {&alpha;<sub>1</sub>,...&alpha;<sub>s</sub>,} - конечное множество, а П = (N<sub>1</sub>,...,N<sub>p</sub>) - система его подмножеств, образующих покрытие множества N. Сопоставим паре (N,П) матрицу M &isin; B<sup>p,s</sup>, для которой M<nowiki><i,j></nowiki> = 1 &hArr; &alpha;<sub>j</sub> &isin; N<sub>i</sub>. Будем говорить, что i-я строка матрицы М ''покрывает'' ее j-й столбец, если M<nowiki><i,j></nowiki> = 1 и что система строк с номерами из I, I &sube; [1,p], образует ''покрытие матрицы М'', если каждый ее столбец покрывается хотябы одной строкой с номером из I, то есть система подмножеств {N<sub>i</sub>}<sub>i &isin; I</sub> задает покрытие множества N.
+* Пусть M &isin; B<sup>p,s</sup> - матрица без нулевых столбцов. Сопоставим i-й строке матрицы М БП y<sub>i</sub>, а каждому набору &beta; &isin; B<sup>p</sup> значений этих переменных y = (y<sub>1</sub>,...,y<sub>p</sub>) - множество строк матрицы М с номерами из множества I = I(&beta;) &sube; [1,p], где i &isin; I(&beta;) &hArr; &beta;<nowiki><i></nowiki> = 1. ФАЛ F(y), для которой F(&beta;) = 1 &hArr; система строк матрицы М с номерами из I(&beta;) образует ее покрытие, будем называть ''функцией покрытия'' матрицы М.
+'''Свойства ФАЛ покрытия матрицы'''<br>
+* монотонность
+* ее "нижние единицы" соответствуют тупиковым покрытиям
+'''Утверждение.''' Функция покрытия F(y<sub>1</sub>,...,y<sub>p</sub>) матрицы M &isin; B<sup>p,s</sup> без нулевых столбцов задается КНФ вида: [[Изображение:Func pokr.jpg]] (*)<br>
+'''Следствие.''' В результате раскрытия скобок и приведения подобных из КНФ (*) можно получить сокращенную ДНФ ФАЛ F(y), простые импликанты которой взаимно однозначно соответствуют тупиковым покрытиям матрицы М.
+=== Градиентный алгоритм покрытия матрицы и утверждение о длине градиентного покрытия ===
+* Градиентный алгоритм: На каждом шаге алгоритма в матрице выбирается и включается в покрытие такая строка, которая покрывает наибольшее число ещё не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером). Алгоритм заканчивается свою работу после того шага, на котором получилось покрытие.
+'''Утверждение'''. Пусть для действительного &gamma;, 0 &lt; &gamma; &le; 1, в каждом столбце матрицы ''M'', ''M'' &isin; ''B''<sup>p,s</sup>,  имеется не меньше чем &gamma;&bull;''p'' единиц. Тогда покрытие матрицы ''M'', получаемое с помощью  градиентного алгоритма, имеет длину не больше, чем [[Изображение:OcenkaProtikaniya.jpg]],  где ln<sup>+</sup>x = ln x, если x &ge; 1 и ln<sup>+</sup>x = 0, если 0 &lt; x &le; 1.
+=== Определение протыкающего множества для граней единичного куба и верхняя оценка его мощности. ===
+* Пусть N = {&alpha;<sub>1</sub>,...&alpha;<sub>s</sub>,} - конечное множество, а П = (N<sub>1</sub>,...,N<sub>p</sub>) - система его подмножеств. Множество, протыкающее систему П - такое подмножество множества N,в котором &forall; i &isin; [1,p] имеется хотябы один элемент из N<sub>i</sub>.
+'''Утверждение.''' При любых натуральных n и m, m &le; n, в кубе B<sup>n</sup> всегда найдется множество мощности не более, чем n&times;2<sup>m</sup>, протыкающее все грани ранга m.
+=== Определение функции Шеннона R(n) для ранга <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> и ее значение. ===
+*R(n) = max<sub>&fnof;&isin;P<sub>2</sub>(n)</sub> R(&fnof;);
+*R(n) = n &times; 2<sup>n &minus; 1</sup>
+=== Определение функции Шеннона λ(n) для длины <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> и ее значение. ===
+*&lambda;(n) = max<sub>&fnof;&isin;P<sub>2</sub>(n)</sub> &lambda;(&fnof;);
+*&lambda;(n) = 2<sup>n &minus; 1</sup>
+=== Определение длины <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ''&lambda;(&fnof;)'' для <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''&fnof;'' и ее оценки для почти всех <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''&fnof;'' от ''n'' переменных ===
+* ''&lambda;(&fnof;)'' = min<sub>ДНФ U, реализующим f</sub> ''&lambda;''(U)
+* Для почти всех ФАЛ из P<sub>2</sub>(n) ''&lambda;(&fnof;)''<~ (3/4)*2<sup>n &minus; 1</sup>
+=== Определение ранга <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> R(f) для <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''&fnof;'' и ее оценки для почти всех <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''&fnof;'' от ''n'' переменных ===
+* R(f) = min<sub>ДНФ U, реализующим f</sub> R(U)
+* Для почти всех ФАЛ из P<sub>2</sub>(n) R(f)<~ (3/4)*n*2<sup>n &minus; 1</sup>
+=== Определение проверяющего теста матрицы и его <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span>, утверждение и КНФ для <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> проверяющего теста ===
+Пусть есть схема &Sigma;<sub>1</sub>, которая реализует ФАЛ ''f''<sub>1</sub>. Пусть есть источник помех И. Под действием источника И схема &Sigma; может переходить в одно из неисправных состояний &Sigma;<sub>2</sub>, &hellip;, &Sigma;<sub>''s''</sub>, каждое из которых реализует ФАЛ ''f''<sub>''i''</sub>, ''i'' = <span style="border-top:solid 1px">2, s</span>.
+Пусть (&Sigma;, И) — модель ненадёжной схемы &Sigma; с возможными состояниями &Sigma;<sub>1</sub>, &hellip;, &Sigma;<sub>''s''</sub>, в которых реализуются ФАЛ ''f''<sub>1</sub>, &hellip;, ''f''<sub>''s''</sub>, определённые на множестве наборов ''A'' = {&alpha;<sub>1</sub>, &hellip;, &alpha;<sub>''p''</sub>} &sube; ''B''<sup>''n''</sup>. Рассмотрим матрицу ''M'' &isin; ''B''<sup>''p'', ''s''</sup>, ''M''[i, j] = ''f''<sub>''j''</sub>(&alpha;<sub>''i''</sub>). Множество строк матрицы ''M'' с номерами из ''T'' &sube; [1, p] называется проверяющим тестом матрицы ''M'', если для &forall;''j'' &isin; <span style="border-top:solid 1px">1, s</span>, &exist;''t'' &isin; ''T'' такое, что ''M''[''t'', 1] &ne; M[''t'', ''j''].
+'''Утверждение'''. Функция проверяющего теста ''f''(''y''<sub>1</sub>, &hellip;, ''y''<sub>''p''</sub>) для отделимой по столбцам матрицы ''M'' &isin; ''B''<sup>''p'', ''s''</sup> может быть задана с помощью КНФ
+<center>[[Изображение:Check text.png|400px]]</center>
+где '''N''' = {(1, j) | j &isin; <span style="border-top:solid 1px">1, s</span>}
+=== Утверждение об оценке длины диагностического теста для произвольной таблицы с заданным числом столбцов ===
+'''Утверждение'''. Длина любого тупикового диагностического теста для отделимой по столбцам матрицы  из множества ''B''<sup>p,s</sup> заключена в пределах от &lceil;log s&rceil; до (s &minus; 1)
+=== !!! Описание <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span>, антицепями которого являются тупиковые <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span>. ===
+Ранжированное множество длины (n+1) всех граней n-мерного единичного куба с отношением вложения. (не точно, стр. 63)
+== Основные классы дискретных управляющих систем. Структурные представления и эквивалентные преобразования схем, оценка их числа ==
+=== Индуктивное определение формулы и реализуемой ею ФАЛ ===
+Любая переменная x<sub>j</sub> из ''X'' считается ''формулой глубины 0'' над множеством Б, которая реализует функцию x<sub>j</sub>. Если &phi;(x<sub>1</sub>,...,x<sub>k</sub>) &isin; Б и для каждого i,
+i &isin; [1,k], определена формула ''F''<sub>i</sub> глубины q<sub>i</sub> над множеством Б, которая реализует функцию &fnof;<sub>i</sub> из P<sub>A</sub>, то запись ''F'' вида
+''F'' = &phi;(''F''<sub>1</sub>,...,''F''<sub>k</sub>)
+является ''формулой глубины q'' = max{q<sub>1</sub>,...,q<sub>k</sub>} + 1 над Б, которая реализует функцию &fnof; вида &fnof; = &phi;(&fnof;<sub>1</sub>,...,&fnof;<sub>k</sub>).
+=== Индуктивное определение &pi;-схемы и нахождение реализуемой ею ФАЛ ===
+Простейшей &pi;-схемой считается любая (1,1)-КС, которая состоит из одного контакта, соединяющего полюса. Если &pi;-схемы &sum;<sub>1</sub> и &sum;<sub>2</sub> уже определены, то (1,1)-КС   &sum;<sub>1</sub>(&sum;<sub>2</sub>), которая получается в результате их последовательного (параллельного) соединения тоже является &pi;-схемой.
+=== Определение разделительной по входам (выходам) КС и формулировка леммы Шеннона ===
+КС разделительна по входам (выходам), если ФАЛ проводимости для &forall; различных входов (выходов) &equiv; 0.
+'''Лемма Шеннона''': Пусть &Sigma; = &Sigma;'&#39;(&Sigma;')  - результат стыковки &rArr; F &ge; F' &times; F'&#39;. F = F' &times; F'&#39;, если &Sigma;'&#39; разделительна по входам, или &Sigma;' разделительна по выходам.
+=== Определение подсхемы &Sigma;' КС &sum; с указанием особенностей, связанных с объявлением вершин &Sigma;' её полюсами. Основное тождество t<sub>4</sub> (введение фиктивной переменной) и вспомогательное тождество t<sub>11</sub> (лемма о звезде); обобщенные тождества t<sub>4</sub><sup>(n)</sup> и t<sub>11</sub><sup>(n)</sup> ===
+Определение подсхемы &Sigma;' КС &Sigma;:<br>
+&Sigma;' — подсхема схемы &Sigma; &hArr;<br>
+# V(&Sigma;') &sube; V(&Sigma;)
+# E(&Sigma;') &sube; E(&Sigma;)
+#
+#* &forall; полюс &Sigma;, вошедший в &Sigma;' — полюс &Sigma;'
+#* &forall; вершина &Sigma;', инцидентная контакту &Sigma;\&Sigma;' - полюс &Sigma;'
+#* &forall; другая вершина м.&nbsp;б. полюсом &Sigma;'.<br>
+{|
+ !t<sub>4</sub>
+ |[[Изображение:Contact scheme t4.png|188px]]
+ |-
+ !t<sub>11</sub>
+ |[[Изображение:Contact scheme t11.png|199px]]
+ |}
+=== Канонический вид КС от БП x<sub>1</sub>,...,x<sub>n</sub> и формулировка утверждения о приведении КС от БП x<sub>1</sub>,...,x<sub>n</sub> к каноническому виду с помощью основных тождеств. ===
+&sum;^ <i>/*здесь и далее крышка пишется над сигмой*/</i> - схема канонического вида &hArr;
+) &forall; контакт &sum;^ лежит на стандартной цепи порядка n, явл. подсхемой &sum;^ с полюсами в конечных вершинах цепи.
+) &forall; внутренняя вершина &sum;^ - внутренняя вершина стандартной цепи
+) в &sum;^ отсутствуют висячие циклы и || стандартные цепи
+) в &sum;^ нет существенных транзитивных проводимостей
+<i>/*вопрос +-, комментарий лектора: отсутствует утверждение о переходе к КВ*/</i>
+&sum;^ получается из &sum; удалением &sum;' (подсхемы) и заменой &sum;' на &sum;' ' с соотв. присоединением полюсов, эквив. &sum; (принцип эквивалентной замены).
+=== Определение величины ||''U''<sup>c</sup>(''L'', ''n'')|| и её верхняя оценка ===
+* ''U''<sup>c</sup>(''L'', ''n'') — множество приведенных СФЭ &Sigma; = &Sigma;(''x''<sub>1</sub>, &hellip;, ''x''<sub>n</sub>; z<sub>1</sub>) над базисом Б<sub>0</sub>, для которых ''L''(&Sigma;) &le; ''L''.
+* ||''U''<sup>c</sup>(''L'', ''n'')|| — число попарно неэквивалентных схем в ''U''<sup>c</sup>(''L'', ''n'')
+'''Утверждение.''' Для любых натуральных ''n'' и ''L'' выполняется неравенство: ||''U''<sup>c</sup>(''L'', ''n'')|| &le; (8(''L'' + ''n''))<sup>''L'' + 1</sup>.
+===  Определение тождества для формул и его подстановки ===
+<div class="definition">'''Подстановка''' &mdash; вместо переменных функции <math>F(x_1, ... , x_n)</math> подставляем функции: <math>F(F_1, ... ,F_n)</math>.</div>
+<div align="center">Тождество &mdash; <math>\hat{t}: F(x)' = F(x)''</math>  (1)</div>
+Если к правой и левой частям (1) применить подстановку, то получим тождество:
+<div align="center"><math>\hat{t} : \hat{F}' = \hat{F}''</math></div>
+где <math>\hat{F}' = \hat{F}'(F_1, \ldots ,F_n)</math> и <math>\hat{F}'' = \hat{F}''(F_1, ... ,F_n)</math>, которое называется подстановкой для тождества t.
+=== Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого можно любую формулу преобразовать в формулу с поднятыми отрицаниями ===
+В расширенную основную систему входят следующие тождества:
+r~<sup>осн</sup> = {r<sup>M</sup>, r<sup>A</sup>, r<sup>К</sup>, r<sup>ОП</sup>, r<sup>D</sup>, r<sup>ПК</sup>, t<sup>П</sup>} /* как обычно, ~ стоит над r */
+* r<sup>A</sup> = {t<sup>A</sup><sub>&</sub>,t<sup>A</sup><sub>∨</sub>}
+* r<sup>K</sup> = {t<sup>K</sup><sub>&</sub>,t<sup>K</sup><sub>∨</sub>}
+* r<sup>ОП</sup> = {t<sup>ОП</sup><sub>&</sub>,t<sup>ОП</sup><sub>∨</sub>}
+* r<sup>D</sup> = {t<sup>D</sup><sub>&</sub>,t<sup>D</sup><sub>∨</sub>}
+* r<sup>ПК</sup> = {t<sup>ПК</sup><sub>0, &</sub>, t<sup>ПК</sup><sub>0, ∨</sub>, t<sup>ПК</sup><sub>1, &</sub>, t<sup>ПК</sup><sub>1, ∨</sub>}
+все тождества описаны [[Основы Кибернетики, Алгоритмы решения задач/Задачи на эквивалентные преобразования и структурное моделирование#Для формул|тут]].
+=== !!! Определение КС от БП ''x<sub>1</sub>'',...,''x<sub>n</sub>'' как помеченного графа и ФАЛ проводимости между её вершинами ===
+(параграф 6 главы 2)
+=== Формулировка утверждения о связи между &pi;-схемами и формулами с поднятыми отрицаниями ===
+Любой &pi;-схеме можно сопоставить эквивалентную ей формулу ''F'' из U<sup>Ф</sup> с поднятыми отрицаниями такую, что R(''F'') = L(&Sigma;) и обратно.
+=== !!! Определение эквивалентности КС &Sigma;', &Sigma;" и соответствующего тождества. Основное тождество ''t<sub>2</sub>'' (перестановка контактов в цепочке) и вспомогательное тождество ''t<sub>8</sub>'' ("расклейка" двух цепочек длины 2 с общим контактом); обобщенные тождества ''t<sub>2</sub><sup>(n)</sup>'' и ''t<sub>8</sub><sup>(n)</sup>'' ===
+<math>\Sigma_1=\Sigma_1(x_1,....,x_n;a_1,...,a_m)</math>
+<math>\Sigma_2=\Sigma_2(x_1,....,x_n;a_1,...,a_m)</math>
+<math>\Sigma_1</math> ~ <math>\Sigma_2</math> означает что для любых i,j из отрезка [1,m] ФАЛ прововодимости от <math>a_i</math> к <math>a_j</math> В КС <math>\Sigma_1</math> равна ФАЛ прововодимости от <math>a_i</math> к <math>a_j</math> В КС <math>\Sigma_2</math>
+=== !!! Определение суммарного цикломатического числа КС от БП ''x<sub>1</sub>'',...,''x<sub>n</sub>'' и формулировка утверждения о его изменениях при применении основных тождеств ===
+(глава 2, стр 72)
+Множество всех связных компонент графа обозначается через c(G).Напомним, что
+|E(G)| − |V(G)| + |c(G)| > 0
+и что левая часть неравенства называется цикломатическим числом графа G.
+=== Определение структуры CФЭ как графа специального вида и изоморфных СФЭ ===
+Под "абстрактной" схемой понимается сеть, часть пометок которой составляют входные переменные и в
+каждой вершине которой реализуется функция (столбец из функций) от этих переменных.
+При этом считается, что сама схема реализует систему (матрицу), состоящую из
+функций (соответственно столбцов функций), реализованных на её выходах. В качестве
+выходных пометок схемы используются, как правило, специальные выходные переменные,
+а схема Sigma с входными переменными (входами) x<sub>1</sub>,..x<sub>n</sub> и выходными переменными
+z<sub>1</sub>,..z<sub>m</sub> записывается в виде Sigma=Sigma(x<sub>1</sub>,..x<sub>n</sub>; z<sub>1</sub>,..z<sub>n</sub>).
+Две СФЭ считаются изоморфными, если они изоморфны как помеченные графы, и эквивалентными,
+если они реализуют равные системы ФАЛ.
+=== Определение ранга, сложности и глубины формулы, утверждение о соотношениях между ними ===
+* ''R''(''F'') — ранг формулы ''F'' — число листьев, связанного с ней дерева
+* ''L''(''F'') — сложность формулы ''F'' — число остальных вершин, связанного с ней дерева (не листьев)
+* ''D''(''F'') — глубина формулы ''F'' — глубина корня, связанного с ней дерева
+* ''R''(''F'') &le; ''L''(''F'') + 1 &le; 2<sup>''D''(''F'')</sup>
+=== !!! Понятие подформулы и применение тождества к формуле ===
+=== Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого формулу с поднятыми отрицаниями можно преобразовать в формулу со следующим порядком применения базисных функций: &not;, &, ∨ ===
+* Дистрибутивность ''t''<sub>&, ∨</sub><sup>D</sup>: ''x''<sub>1</sub> & (''x''<sub>2</sub> ∨ ''x''<sub>3</sub>) = (''x''<sub>1</sub> & ''x''<sub>2</sub>) ∨ (''x''<sub>1</sub> & ''x''<sub>3</sub>)
+* Коммутативность коньюнкции ''t''<sub>&</sub><sup>К</sup>: ''x''<sub>1</sub> & ''x''<sub>2</sub> = ''x''<sub>2</sub> & ''x''<sub>1</sub>
+=== !!! Определение матрицы ФАЛ, реализуемой КС с ''p'' входами и ''q'' выходами, определение и свойства матрицы, реализемой КС с ''m'' неразделенными полюсами ===
+Глава 2, стр. 57-58
+=== Определение величины ''||U<sup>&pi;</sup>(L,n)||'' и ее верхняя оценка ===
+* ||U<sup>&pi;</sup>(L,n)|| - число попарно не эквивалентных приведенных &pi;-схем от БП x<sub>1</sub>,...,x<sub>n</sub> сложности &le; ''L''
+* ||U<sup>&pi;</sup>(L,n)|| &le; (16n)<sup>L</sup>
+=== !!! Определение подстановки тождества для КС, связанной с управляющими БП, и ее применение к КС. Основное тождество ''t<sub>3</sub>'' (цепь из противоположных контактов) и вспомогательные тождество ''t<sub>10</sub>'' (замыкание по транзитивности); обобщенные тождества ''t<sub>3</sub><sup>(n)</sup>'' и ''t<sub>10</sub><sup>(n)</sup>'' ===
+=== !!! Примеры моделирования основных тождеств для формул в классе СФЭ, примеры тождеств ветвления и снятия для ФЭ и входов СФЭ. Формулировка утверждения о переходе от КПСТ для ЭП формул к КПСТ для ЭП СФЭ ===
+== Синтез, сложность и надежность управляющих систем ==
+=== !!! Определение сложности ''L<sup>C</sup>(F)'' системы ФАЛ ''F = (&fnof;<sub>1</sub>,...,&fnof;<sub>m</sub>)'' и ее тривиальная нижняя оценка для некоторых систем ФАЛ ===
+=== Определение функции Шеннона ''L<sup>C</sup>(n)'' и ее верхние оценки, получаемые методом Шеннона и методом О.&nbsp;Б. Лупанова ===
+* ''L<sup>C</sup>(n)'' = max<sub>&fnof;&isin;P<sub>2</sub>(n)</sub>''L<sup>C</sup>(&fnof;)''
+* Метод Шеннона: ''L<sup>C</sup>(n)'' <&sim; 8&bull;2<sup>n</sup>/n
+* Метод Лупанова: ''L<sup>C</sup>(n)'' &le; (2<sup>n</sup>/n)&bull;(1 + (5log''n'' + ''O''(1))/n)
+=== Нижняя оценка функции Шеннона ''L<sup>&pi;</sup>(n)'' и то мощностное соотношение, из которого она выводится ===
+* ''L<sup>&pi;</sup>(n)'' &ge; ''2<sup>n</sup>'' / ''log<sub>2</sub>n ''  (Асимптотически больше)
+* ''||U<sup>&pi;</sup>(L,n)|''| &le; ''(16n)<sup>L</sup>''
+=== Определение мультиплексорной ФАЛ ''M<sub>n</sub>'' порядка ''n'', утверждение о сложности ее реализации в классах ''&pi;''-схем и формул ===
+Функция вида
+µ<sub>n</sub>(x<sub>1</sub>,..x<sub>n</sub>,y<sub>0</sub>,..y<sub>2<sup>n</sup>-1</sub>) = U <sub>(a=(a<sub>1</sub>,..a<sub>n</sub>))</sub> x<sub>1</sub><sup>a<sub>1</sub></sup>...x<sub>n</sub><sup>a<sub>n</sub></sup>y<sub>v(a)</sub>
+называется мультиплексорной функцией (мультиплексором) порядка n, а переменные
+x=(x<sub>1</sub>,..x<sub>n</sub>) называются адресными,
+y=(y<sub>0</sub>,..y<sub>2<sup>n</sup>-1</sub>) - информационными БП мультиплексора µ<sub>n</sub>.
+L<sup>п</sup>(µ<sub>n</sub>) <= 3*2<sup>n</sup>-2,
+L<sup>Ф</sup>(µ<sub>n</sub>) <= 2<sup>n+2</sup>-3;
+=== !!! Определение сложности ''L<sup>K</sup>(&fnof;)'' ФАЛ ''&fnof;(x<sub>1</sub>...x<sub>n</sub>)'' в классе КС и её тривиальные нижние оценки для ФАЛ ''&fnof;'', существенно зависящей от всех своих переменных (с учетом характера этой зависимости) ===
+L<sup>K</sup> (f) > n для ФАЛ f, существенно зависящей от всех своих переменных.
+=== Определение функции Шеннона ''L<sup>&pi;</sup>(n)'' и её верхняя оценка, получаемая с помощью моделирования совершенной ДНФ на основе контактного дерева ===
+* L<sup>&pi;</sup>(n) = max<sub>&fnof;&isin;P<sub>2</sub>(n)</sub>L<sup>&pi;</sup>(&fnof;)
+* L<sup>&pi;</sup>(n) &le; 2<sup>n + 1</sup> &minus; 2 //FIXME
+=== Нижняя оценка функции Шеннона ''L<sup>c</sup>(n)'' и то мощностное соотношение, из которого она выводится ===
+* L<sup>C</sup>(n) &ge; 2<sup>n</sup> / n   (Асимптотически больше)
+* ||U<sup>C</sup>(L,n)|| &le; (8(L + n))<sup>L + 1</sup>
+=== Определение ДУМ и формулировка утверждения о свойствах стандартного ДУМ ===
+* Дизъюнктивно-универсальное множество (ДУМ) ''G'' порядка ''n'' и ранга ''p'' &hArr; &forall; ''g &isin; P<sub>2</sub>(n) &exist; g<sub>1</sub>,...,g<sub>p</sub> &isin; G : g = g<sub>1</sub>&cup;...&cup;g<sub>p</sub>''
+'''Утверждение'''. Пусть ''m'', ''S'', ''p'' &isin; ''N'': ''p * S &ge; 2<sup>m</sup>'', тогда &exist; ДУМ ''G'' порядка ''m'' и ранга ''p'':
+# |G| &le; p * 2<sup>S</sup>
+# В ''G'' &exist; система из ''p'' ортогональных функций &psi;<sub>1</sub>,...,&psi;<sub>p</sub> : &forall; g &isin; G имплицирует одну из них.
+=== Регулярные разбиения единичного куба и моделирование ФАЛ с помощью БП. Асимптотика сложности контактного дешифратора ===
+Множество &delta;, &delta; &sube; B<sup>q</sup>, называется m-регулярным множеством наборов
+куба B<sup>q</sup>, если m < q, |&delta;| = 2<sup>m</sup> и все префиксы длины m наборов из &delta; различны.
+m-регулярное разбиение куба B<sup>q</sup> — разбиение этого куба, состоящее из m-регулярных множеств &delta;<sub>1</sub>, &hellip;, &delta;<sub>q &minus; m</sub>. (???)
+моделирование ФАЛ с помощью БП - ???
+L<sup>K</sup> (Q<sub>n</sub>) ~ 2<sup>n</sup>
+=== !!! Асимптотически наилучший метод синтеза КС ===
+=== !!! Построение самокорректирующихся КС ===
+=== !!! Асимптотически наилучший метод синтеза формул в В<sub>0</sub>. Поведение функции Шеннона для глубины ФАЛ ===
+=== !!! Задача синтеза схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Методы получения верхних и нижних оценок сложности, минимальность некоторых схем ===
+=== Определение ''m''-регулярного множества наборов ===
+Множество &delta;, &delta; &sube; B<sup>q</sup>, называется ''m-регулярным'' множеством наборов куба B<sup>q</sup>, если m &lt; q, &#124;&delta;&#124; = 2<sup>m</sup> и все префиксы длины m наборов из &delta; различны.
+=== !!! Определение (p, q)-самокорректирующейся КС. Утверждение о сложности самокорректирующейся КС, получаемой дублированием ===
+{{Курс Основы Кибернетики}}