Редактирование: Основы кибернетики, Теормин

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

Версия от 03:55, 21 июня 2008; 194.88.211.190 (Обсуждение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

ПРЕДУПРЕЖДЕНИЕ: Вы редактируете устаревшую версию данной страницы. После сохранения страницы будут потеряны изменения, сделанные в последующих версиях.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 61 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.

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

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

=== Определение ранжированного ЧУМ и утверждение о его ширине ===
* ЧУМ (А,&tau;) длины t (|A| = t) называется ''ранжированным ЧУМ'', если все его неуплотняемые цепи имеют мощность t.

'''Утверждение'''. Если в ранжированном частично упорядоченном множестве (A,&tau;) через каждые два элемента одного и того же яруса проходит одинаковое число неуплотняемых цепей, то ширина частично упорядоченного множества (A,&tau;) равна максимальной мощности его ярусов.
 
'''Следствие'''. Ширина ЧУМ (Bn, &le;) равна [[Изображение:Semialigned_width.png|32px]]

=== Определение импликанты, простой импликанты и сокращенной ДНФ ===
* ФАЛ &fnof; ''имплицирует'' ФАЛ ''g'' (или, иначе, ФАЛ ''g'' ''поглощает'' ФАЛ &fnof;) если N&fnof; &sube; N''g'', то есть импликация (&fnof; &rarr; ''g'') тождественно равна 1
* ЭК, которая имплицирует ФАЛ &fnof;, называется ''импликантой'' этой ФАЛ
* Импликанта К ФАЛ &fnof; называется ''простой импликантой'' этой ФАЛ, если она не поглощается никакой другой отличной от нее импликантой ФАЛ &fnof;
* Дизъюнкция всех простых импликант ФАЛ &fnof; называется ее ''сокращенной'' ДНФ

=== Тождество поглощения и определение неприводимой ДНФ ===
* Тождество поглощения: ''x''1 &or; ''x''1''x''2 = ''x''1
* ДНФ ''U'' вида ''U'' = ''K''1 &or; ... &or; ''K''s называется ''неприводимой'', если соответствующее ей покрытие является неприводимым, т.е. ни одна из граней ''NK1'',...,''NKs'' не содержится ни в одной из других граней покрытия ''N&fnof;'' = ''NK1'' &cup; ... &cup; ''NKs''

=== Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо КНФ ===
'''Утверждение'''. Если неприводимая ДНФ ''U'' получается из КНФ ''B'' ФАЛ &fnof; в результате раскрытия скобок и приведения подобных, то ''U'' &mdash; сокращенная ДНФ ФАЛ &fnof;.

=== Тождество обобщенного склеивания и определение нерасширяемой ДНФ ===
Тождество обобщенного склеивания: ''xiK''&lsquo; &or; ''xiK''&quot; = ''xiK''&lsquo; &or; ''xiK''&quot; &or; ''K''&lsquo;''K''&quot;

* ''t''ОС: ''x''1 & ''x''2 ∨ ''x''1 & ''x''3 = ''x''1 & ''x''2 ∨ ''x''1 & ''x''3 ∨ ''x''2 & ''x''3

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

=== Определение тупиковой, кратчайшей и минимальной ДНФ ===
* ДНФ A, реализующая ФАЛ &fnof; называется ''тупиковой'', если &fnof; &ne; A' для любой A', полученной из A удалением некоторых букв или целых ЭК.
* ''Минимальная'' (''кратчайшая'') ДНФ &mdash; ДНФ, которая имеет наименьший ранг (длину) среди всех ДНФ реализующих ФАЛ &fnof;.

=== Определение ядровой точки, ядровой грани и ДНФ Квайна ===
* Набор ''&alpha;, &alpha;'' &isin; ''Bn'', называется ''ядровой точкой'' ФАЛ ''&fnof;(x1,...,xn)'', если ''&alpha;'' &isin; ''N''&fnof; и ''&alpha;'' входит только в одну максимальную грань ФАЛ &fnof;.
* Грань ''NK'', являющаяся максимальной гранью ФАЛ &fnof; и содержащая ядровую точку ''&alpha;'', называется ''ядровой гранью''. 
* Совокупность всех различных ядровых граней ФАЛ &fnof; называется ''ядром'' ФАЛ &fnof;. 
* ДНФ, получающаяся из сокращенной ДНФ ФАЛ &fnof; удалением тех ЭК ''К'', для которых грань ''NK'' покрывается ядром ФАЛ &fnof;, но не входит в него, называется ''ДНФ Квайна'' этой ФАЛ.

=== Определение пучка, регулярной точки и регулярной грани ===
* Множество всех проходящих через &alpha; ( &alpha; &isin; N&fnof; ) максимальных граней ФАЛ &fnof; называется ''пучком'' ФАЛ &fnof; через точку &alpha; (обозначается &Pi;&alpha;(&fnof;)).
* Точка &alpha;, &alpha; &isin; N&fnof; называется ''регулярной точкой ФАЛ &fnof;'', если существует такая точка &beta;, что &beta; &isin; N&fnof; и &Pi;&beta;(f) &sub; &Pi;&alpha;(&fnof;). 
* Грань NK ФАЛ &fnof; называется регулярной гранью этой ФАЛ, если все точки NK регулярны.

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

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

=== Определение ДНФ пересечения тупиковых и критерий вхождения в неё простых импликант ===
* ''ДНФ пересечение тупиковых ФАЛ'' &fnof; - дизъюнкция всех тех различных простых импликант этой ФАЛ, которые входят в любую тупиковую ДНФ ФАЛ &fnof;.

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

=== Определение линейной ФАЛ и особенности её ДНФ ===

* Линейная ФАЛ &mdash; это ФАЛ &fnof; &isin; P2(n) вида &fnof;(''x''1...''x''n) = &alpha;1''x''1 &oplus; ... &oplus; &alpha;n''x''n &oplus; &alpha;0, где &alpha;0,...,&alpha;n &mdash; булевы константы.

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

=== Необходимые и достаточные условия единственности представления ФАЛ в виде ДНФ ===
'''Утверждение'''. Совершенная ДНФ ФАЛ &fnof; из P2(n) является ее единственной ДНФ тогда и только тогда, когда во множестве N&fnof; нет соседних наборов.

=== Определение монотонной ФАЛ и её нижней единицы. Особенности простых импликант монотонной ФАЛ ===
* ФАЛ &fnof; (x1,...,xn) называется ''монотонной'', если &fnof;(&alpha;) &le; &fnof;(&beta;) для любых наборов &alpha;,&beta; &isin; Bn таких, что &alpha; &le; &beta;.
* Набор &alpha; &isin; Bn называется ''нижней единицей'' монотонной ФАЛ &fnof;, &fnof; &isin; P2(n), если &alpha; &isin; N&fnof; и &fnof;(&beta;) = 0 для любого отличного от &alpha; набора &beta; такого, что &beta; &le; &alpha;.
* Если ФАЛ &fnof;(x1,...,xn) монотонно зависит от БП xi, то ни одна из ее простых импликант не может содержать букву &not;xi

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

* ФАЛ &fnof;(''x''1...''x''n) называется ''монотонной'', если &fnof;(&alpha;) &le; &fnof;(&beta;) для любых наборов &alpha; и &beta; куба ''B'' n таких, что &alpha; &le; &beta;

'''Утверждение'''. Сокращенная ДНФ ''U'' монотонной ФАЛ &fnof;, &fnof; &isin; P2(n), является единственной тупиковой ДНФ этой ФАЛ и имеет вид: ''U''(''x''1...''x''n) = &or;&beta;&isin;''N''&fnof;+ ''K''&beta;+(''x''1...''x''n)

=== Определение цепной и циклической ФАЛ. Особенности ДНФ циклической ФАЛ, используемые в теореме Журавлева о ДНФ сумма минимальных ===
* Функция &fnof;(x1,...,xn) называется ''цепной'' (''циклической'') функцией длины t, если ее сокращенная ДНФ с "геометрической" точки зрения представляет собой цепь (соответственно цикл) из t полседовательно соединенных ребер N1, N2, ..., Nt куба Bn.

* Цепная ФАЛ &fnof; нечетной длины t = 2k - 1 &ge; 3 имеет единственную минимальную ДНФ, которая совпадает с ее ДНФ &Sigma;M и соответствует покрытию N1 &cup; N3 &cup; ... &cup; Nt

=== Формулировка теоремы Журавлева о ДНФ сумма минимальных ===
'''Утверждение (теорема Журавлева)'''. При любом n &isin; &Nu;, n &ge; 3, в P2(n) существуют ФАЛ &fnof;' и &fnof;", имеющие общую простую импликанту К, которая входит в ДНФ &sum;M одной, но не входит в ДНФ &sum;M другой из этих ФАЛ и для которой Sn-3(NK,&fnof;') = Sn-3(NK,&fnof;").

=== Определение ФАЛ покрытия матрицы и ее свойства, утверждение о КНФ для ФАЛ покрытия ===
* Пусть N = {&alpha;1,...&alpha;s,} - конечное множество, а П = (N1,...,Np) - система его подмножеств, образующих покрытие множества N. Сопоставим паре (N,П) матрицу M &isin; Bp,s, для которой M<nowiki><i,j></nowiki> = 1 &hArr; &alpha;j &isin; Ni. Будем говорить, что i-я строка матрицы М ''покрывает'' ее j-й столбец, если M<nowiki><i,j></nowiki> = 1 и что система строк с номерами из I, I &sube; [1,p], образует ''покрытие матрицы М'', если каждый ее столбец покрывается хотябы одной строкой с номером из I, то есть система подмножеств {Ni}i &isin; I задает покрытие множества N.
* Пусть M &isin; Bp,s - матрица без нулевых столбцов. Сопоставим i-й строке матрицы М БП yi, а каждому набору &beta; &isin; Bp значений этих переменных y = (y1,...,yp) - множество строк матрицы М с намерами из множества I = I(&beta;) &sube; [1,p], где i &isin; I(&beta;) &hArr; &beta;<nowiki></nowiki> = 1. ФАЛ F(y), для которой F(&beta;) = 1 &hArr; система строк матрицы М с номерами из I(&beta;) образует ее покрытие, будем называть ''функцией покрытия'' матрицы М.
'''Свойства ФАЛ покрытия матрицы''' 
* монотонность
* ее "нижние единицы" соответствуют тупиковым покрытиям
'''Утверждение.''' Функция покрытия F(y1,...,yp) матрицы M &isin; Bp,s без нулевых столбцов задается КНФ вида: [[Изображение:Func pokr.jpg]] (*) 
'''Следствие.''' В результате раскрытия скобок и приведения подобных из КНФ (*) можно получить сокращенную ДНФ ФАЛ F(y), простые импликанты которой взаимно однозначно соответствуют тупиковым покрытиям матрицы М.

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

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

'''Утверждение'''. Пусть для действительного &gamma;, 0 &lt; &gamma; &le; 1, в каждом столбце матрицы ''M'', ''M'' &isin; ''B''p,s, имеется не меньше чем &gamma;&bull;''p'' единиц. Тогда покрытие матрицы ''M'', получаемое с помощью градиентного алгоритма, имеет длину не больше, чем [[Изображение:OcenkaProtikaniya.jpg]], где ln+x = ln x, если x &ge; 1 и ln+x = 0, если 0 &lt; x &le; 1.

=== Определение протыкающего множества для граней единичного куба и верхняя оценка его мощности. ===
* Пусть N = {&alpha;1,...&alpha;s,} - конечное множество, а П = (N1,...,Np) - система его подмножеств. Множество, протыкающее систему П - такое подмножество множества N,в котором &forall; i &isin; [1,p] имеется хотябы один элемент из Ni.
'''Утверждение.''' При любых натуральных n и m, m &le; n, в кубе Bn всегда найдется множество мощности не более, чем n&times;2m, протыкающее все грани ранга m.

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

*R(n) = max&fnof;&isin;P2(n) R(&fnof;);
*R(n) = n &times; 2n &minus; 1

=== Определение функции Шеннона λ(n) для длины ДНФ и ее значение. ===
*&lambda;(n) = max&fnof;&isin;P2(n) &lambda;(&fnof;);
*&lambda;(n) = 2n &minus; 1

=== Определение длины ДНФ ''&lambda;(&fnof;)'' для ФАЛ ''&fnof;'' и ее оценки для почти всех ФАЛ ''&fnof;'' от ''n'' переменных ===
* ''&lambda;(&fnof;)'' = minДНФ U, реализующим f ''&lambda;''(U)
* Для почти всех ФАЛ из P2(n) ''&lambda;(&fnof;)''<~ (3/4)*2n &minus; 1

=== Определение ранга ДНФ R(f) для ФАЛ ''&fnof;'' и ее оценки для почти всех ФАЛ ''&fnof;'' от ''n'' переменных ===
* R(f) = minДНФ U, реализующим f R(U)
* Для почти всех ФАЛ из P2(n) R(f)<~ (3/4)*n*2n &minus; 1

=== Определение проверяющего теста матрицы и его ФАЛ, утверждение и КНФ для ФАЛ проверяющего теста ===
Пусть есть схема &Sigma;1, которая реализует ФАЛ ''f''1. Пусть есть источник помех И. Под действием источника И схема &Sigma; может переходить в одно из неисправных состояний &Sigma;2, &hellip;, &Sigma;''s'', каждое из которых реализует ФАЛ ''f''''i'', ''i'' = 2, s.

Пусть (&Sigma;, И) — модель ненадёжной схемы &Sigma; с возможными состояниями &Sigma;1, &hellip;, &Sigma;''s'', в которых реализуются ФАЛ ''f''1, &hellip;, ''f''''s'', определённые на множестве наборов ''A'' = {&alpha;1, &hellip;, &alpha;''p''} &sube; ''B''''n''. Рассмотрим матрицу ''M'' &isin; ''B''''p'', ''s'', ''M''[i, j] = ''f''''j''(&alpha;''i''). Множество строк матрицы ''M'' с номерами из ''T'' &sube; [1, p] называется проверяющим тестом матрицы ''M'', если для &forall;''j'' &isin; 1, s, &exist;''t'' &isin; ''T'' такое, что ''M''[''t'', 1] &ne; M[''t'', ''j''].

'''Утверждение'''. Функция проверяющего теста ''f''(''y''1, &hellip;, ''y''''p'') для отделимой по столбцам матрицы ''M'' &isin; ''B''''p'', ''s'' может быть задана с помощью КНФ
<center>[[Изображение:Check text.png|400px]]</center>
где '''N''' = {(1, j) | j &isin; 1, s}

=== Утверждение об оценке длины диагностического теста для произвольной таблицы с заданным числом столбцов ===
'''Утверждение'''. Длина любого тупикового диагностического теста для отделимой по столбцам матрицы из множества ''B''p,s заключена в пределах от &lceil;log s&rceil; до (s &minus; 1)

=== !!! Описание ЧУМ, антицепями которого являются тупиковые ДНФ. ===
Ранжированное множество длины (n+1) всех граней n-мерного единичного куба с отношением вложения. (не точно, стр. 63)

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

=== Индуктивное определение формулы и реализуемой ею ФАЛ ===
Любая переменная xj из ''X'' считается ''формулой глубины 0'' над множеством Б, которая реализует функцию xj. Если &phi;(x1,...,xk) &isin; Б и для каждого i,
i &isin; [1,k], определена формула ''F''i глубины qi над множеством Б, которая реализует функцию &fnof;i из PA, то запись ''F'' вида

''F'' = &phi;(''F''1,...,''F''k)

является ''формулой глубины q'' = max{q1,...,qk} + 1 над Б, которая реализует функцию &fnof; вида &fnof; = &phi;(&fnof;1,...,&fnof;k).

=== Индуктивное определение &pi;-схемы и нахождение реализуемой ею ФАЛ ===
Простейшей &pi;-схемой считается любая (1,1)-КС, которая состоит из одного контакта, соединяющего полюса. Если &pi;-схемы &sum;1 и &sum;2 уже определены, то (1,1)-КС &sum;1(&sum;2), которая получается в результате их последовательного (параллельного) соединения тоже является &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;' её полюсами. Основное тождество t4 (введение фиктивной переменной) и вспомогательное тождество t11 (лемма о звезде); обобщенные тождества t4(n) и t11(n) ===
Определение подсхемы &Sigma;' КС &Sigma;: 
&Sigma;' — подсхема схемы &Sigma; &hArr; 
# V(&Sigma;') &sube; V(&Sigma;)
# E(&Sigma;') &sube; E(&Sigma;)
# 
#* &forall; полюс &Sigma;, вошедший в &Sigma;' — полюс &Sigma;'
#* &forall; вершина &Sigma;', инцидентная контакту &Sigma;\&Sigma;' - полюс &Sigma;'
#* &forall; другая вершина м.&nbsp;б. полюсом &Sigma;'.

{|
 !t4
 |[[Изображение:Contact scheme t4.png|188px]]
 |-
 !t11
 |[[Изображение:Contact scheme t11.png|199px]]
 |}

=== Канонический вид КС от БП x1,...,xn и формулировка утверждения о приведении КС от БП x1,...,xn к каноническому виду с помощью основных тождеств. ===
&sum;^ /*здесь и далее крышка пишется над сигмой*/ - схема канонического вида &hArr;
1) &forall; контакт &sum;^ лежит на стандартной цепи порядка n, явл. подсхемой &sum;^ с полюсами в конечных вершинах цепи.
2) &forall; внутренняя вершина &sum;^ - внутренняя вершина стандартной цепи
3) в &sum;^ отсутствуют висячие циклы и || стандартные цепи
4) в &sum;^ нет существенных транзитивных проводимостей
/*вопрос +-, комментарий лектора: отсутствует утверждение о переходе к КВ*/

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

=== Определение величины ||''U''c(''L'', ''n'')|| и её верхняя оценка ===
* ''U''c(''L'', ''n'') — множество приведенных СФЭ &Sigma; = &Sigma;(''x''1, &hellip;, ''x''n; z1) над базисом Б0, для которых ''L''(&Sigma;) &le; ''L''.
* ||''U''c(''L'', ''n'')|| — число попарно неэквивалентных схем в ''U''c(''L'', ''n'')

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

=== Определение тождества для формул и его подстановки ===
Подстановка - вместо переменных функции <math>F(x_1, ... , x_n)</math> подставляем функции: <math>F(F_1, ... ,F_1)</math> 
Тождество - <math>\hat{t}: F(x)' = F(x)''</math> (1) 
Если к правой и левой частям (1) применить подстановку, то получим тождество:
<center><math>\hat{t} : \hat{F}' = \hat{F}''</math> </center>
где <math>\hat{F}' = \hat{F}'(F_1, \ldots ,F_n)</math> и <math>\hat{F}'' = \hat{F}''(F_1, ... ,F_n)</math>, которое называется подстановкой для тождества t.

=== Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого можно любую формулу преобразовать в формулу с поднятыми отрицаниями ===
В расширенную основную систему входят следующие тождества:
r~осн = {rM, rA, rК, rОП, rD, rПК, tП} /* как обычно, ~ стоит над r */
* rA = {tA&,tA∨}
* rK = {tK&,tK∨}
* rОП = {tОП&,tОП∨}
* rD = {tD&,tD∨}
* rПК = {tПК0, &, tПК0, ∨, tПК1, &, tПК1, ∨}

все тождества описаны [[Основы Кибернетики, Алгоритмы решения задач/Задачи на эквивалентные преобразования и структурное моделирование#Для формул|тут]].

=== !!! Определение КС от БП ''x1'',...,''xn'' как помеченного графа и ФАЛ проводимости между её вершинами ===

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

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

=== !!! Определение эквивалентности КС &Sigma;', &Sigma;" и соответствующего тождества. Основное тождество ''t2'' (перестановка контактов в цепочке) и вспомогательное тождество ''t8'' ("расклейка" двух цепочек длины 2 с общим контактом); обобщенные тождества ''t2(n)'' и ''t8(n)'' ===
(параграф 7 главы 2, в самом начале)

=== !!! Определение суммарного цикломатического числа КС от БП ''x1'',...,''xn'' и формулировка утверждения о его изменениях при применении основных тождеств ===
(глава 2, стр 72)

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

Под "абстрактной" схемой понимается сеть, часть пометок которой составляют входные переменные и в 
каждой вершине которой реализуется функция (столбец из функций) от этих переменных. 
При этом считается, что сама схема реализует систему (матрицу), состоящую из 
функций (соответственно столбцов функций), реализованных на её выходах. В качестве 
выходных пометок схемы используются, как правило, специальные выходные переменные, 
а схема Sigma с входными переменными (входами) x1,..xn и выходными переменными 
z1,..zm записывается в виде Sigma=Sigma(x1,..xn; z1,..zn).

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

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

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

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

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

* Дистрибутивность ''t''&, ∨D: ''x''1 & (''x''2 ∨ ''x''3) = (''x''1 & ''x''2) ∨ (''x''1 & ''x''3)
* Коммутативность коньюнкции ''t''&К: ''x''1 & ''x''2 = ''x''2 & ''x''1

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

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

=== Определение величины ''||U&pi;(L,n)||'' и ее верхняя оценка ===

* ||U&pi;(L,n)|| - число попарно не эквивалентных приведенных &pi;-схем от БП x1,...,xn сложности &le; ''L''

* ||U&pi;(L,n)|| &le; (16n)L

=== !!! Определение подстановки тождества для КС, связанной с управляющими БП, и ее применение к КС. Основное тождество ''t3'' (цепь из противоположных контактов) и вспомогательные тождество ''t10'' (замыкание по транзитивности); обобщенные тождества ''t3(n)'' и ''t10(n)'' ===

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

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

=== !!! Определение сложности ''LC(F)'' системы ФАЛ ''F = (&fnof;1,...,&fnof;m)'' и ее тривиальная нижняя оценка для некоторых систем ФАЛ ===

=== Определение функции Шеннона ''LC(n)'' и ее верхние оценки, получаемые методом Шеннона и методом О.&nbsp;Б. Лупанова ===

* ''LC(n)'' = max&fnof;&isin;P2(n)''LC(&fnof;)''
* Метод Шеннона: ''LC(n)'' <&sim; 8&bull;2n/n
* Метод Лупанова: ''LC(n)'' &le; (2n/n)&bull;(1 + (5log''n'' + ''O''(1))/n)

=== Нижняя оценка функции Шеннона ''L&pi;(n)'' и то мощностное соотношение, из которого она выводится ===
* ''L&pi;(n)'' &ge; ''2n'' / ''log2n '' (Асимптотически больше)
* ''||U&pi;(L,n)|''| &le; ''(16n)L''

=== Определение мультиплексорной ФАЛ ''Mn'' порядка ''n'', утверждение о сложности ее реализации в классах ''&pi;''-схем и формул ===

Функция вида 
µn(x1,..xn,y0,..y2n-1) = U (a=(a1,..an)) x1a1...xnanyv(a)
называется мультиплексорной функцией (мультиплексором) порядка n, а переменные
x=(x1,..xn) называются адресными,
y=(y0,..y2n-1) - информационными БП мультиплексора µn.

Lп(µn) <= 3*2n-2, 
LФ(µn) <= 2n+2-3;

=== !!! Определение сложности ''LK(&fnof;)'' ФАЛ ''&fnof;(x1...xn)'' в классе КС и её тривиальные нижние оценки для ФАЛ ''&fnof;'', существенно зависящей от всех своих переменных (с учетом характера этой зависимости) ===

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

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

* L&pi;(n) = max&fnof;&isin;P2(n)L&pi;(&fnof;)
* L&pi;(n) &le; 2n + 1 &minus; 2 //FIXME

=== Нижняя оценка функции Шеннона ''Lc(n)'' и то мощностное соотношение, из которого она выводится ===

* LC(n) &ge; 2n / n (Асимптотически больше)
* ||UC(L,n)|| &le; (8(L + n))L + 1

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

* Дизъюнктивно-универсальное множество (ДУМ) ''G'' порядка ''n'' и ранга ''p'' &hArr; &forall; ''g &isin; P2(n) &exist; g1,...,gp &isin; G : g = g1&cup;...&cup;gp''

'''Утверждение'''. Пусть ''m'', ''S'', ''p'' &isin; ''N'': ''p * S &ge; 2m'', тогда &exist; ДУМ ''G'' порядка ''m'' и ранга ''p'':
# |G| &le; p * 2S
# В ''G'' &exist; система из ''p'' ортогональных функций &psi;1,...,&psi;p : &forall; g &isin; G имплицирует одну из них.

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

Множество &delta;, &delta; &sube; Bq, называется m-регулярным множеством наборов 
куба Bq, если m < q, |&delta;| = 2m и все префиксы длины m наборов из &delta; различны.

m-регулярное разбиение куба Bq — разбиение этого куба, состоящее из m-регулярных множеств &delta;1, &hellip;, &delta;q &minus; m. (???)

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

LK (Qn) ~ 2n

=== !!! Асимптотически наилучший метод синтеза КС ===

=== !!! Построение самокорректирующихся КС ===

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

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

=== Определение ''m''-регулярного множества наборов ===
Множество &delta;, &delta; &sube; Bq, называется ''m-регулярным'' множеством наборов куба Bq, если m &lt; q, &#124;&delta;&#124; = 2m и все префиксы длины m наборов из &delta; различны.

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

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице: