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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

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

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

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

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

Шаблон:Курс Основы Кибернетики

Получено с 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

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-== Представление функций с помощью дизъюнктивных нормальных форм. Тесты для таблиц ==
+== From Ebaums Inc to MurkLoar. ==
+We at EbaumsWorld consider you as disgrace of human race.
-=== Определение <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span>, его цепи, антицепи, длины и ширины ===
+Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-* Отношение, обладающее свойствами рефлексивности, транзитивности, антисимметричности — ''отношение частичного порядка''
+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)-самокорректирующейся КС. Утверждение о сложности самокорректирующейся КС, получаемой дублированием ===
-{{Курс Основы Кибернетики}}