м |
|
| Строка 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. |
| - | * Если τ — отношение частичного порядка на множестве А, то пара (А,τ) — ''частично упорядоченное множество (<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> (А, τ) длины 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> (А,τ) длины t (|A| = t) называется ''ранжированным <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span>'', если все его неуплотняемые цепи имеют мощность t.
| + | |
| - | | + | |
| - | '''Утверждение'''. Если в ранжированном частично упорядоченном множестве (A,τ) через каждые два элемента одного и того же яруса проходит одинаковое число неуплотняемых цепей, то ширина частично упорядоченного множества (A,τ) равна максимальной мощности его ярусов.
| + | |
| - |
| + | |
| - | '''Следствие'''. Ширина <span title="частично упорядоченное множество" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ЧУМ</span> (B<sup>n</sup>, ≤) равна [[Изображение: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> ƒ ''имплицирует'' <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> ƒ) если N<sub>ƒ</sub> ⊆ N<sub>''g''</sub>, то есть импликация (ƒ → ''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> ƒ, называется ''импликантой'' этой <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> ===
| + | |
| - | * Тождество поглощения: ''x''<sub>1</sub> ∨ ''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> ∨ ... ∨ ''K''<sub>s</sub> называется ''неприводимой'', если соответствующее ей покрытие является неприводимым, т.е. ни одна из граней ''N<sub>K<sub>1</sub></sub>'',...,''N<sub>K<sub>s</sub></sub>'' не содержится ни в одной из других граней покрытия ''N<sub>ƒ</sub>'' = ''N<sub>K<sub>1</sub></sub>'' ∪ ... ∪ ''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> ƒ в результате раскрытия скобок и приведения подобных, то ''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> ===
| + | |
| - | Тождество обобщенного склеивания: ''x<sub>i</sub>K''‘ ∨ ''<span style="text-decoration:overline;">x</span><sub>i</sub>K''" = ''x<sub>i</sub>K''‘ ∨ ''<span style="text-decoration:overline;">x</span><sub>i</sub>K''" ∨ ''K''‘''K''"
| + | |
| - | | + | |
| - | * ''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>
| + | |
| - | | + | |
| - | === Формулировка утверждения, связанного с построением сокращенной <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>, не имеющей строгих расширений.
| + | |
| - | | + | |
| - | === Определение тупиковой, кратчайшей и минимальной <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> ƒ называется ''тупиковой'', если ƒ ≠ 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> — <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> Квайна ===
| + | |
| - | * Набор ''α, α'' ∈ ''B<sup>n</sup>'', называется ''ядровой точкой'' <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''ƒ(x<sub>1</sub>,...,x<sub>n</sub>)'', если ''α'' ∈ ''N''<sub>ƒ</sub> и ''α'' входит только в одну максимальную грань <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> ƒ и содержащая ядровую точку ''α'', называется ''ядровой гранью''.<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> ƒ.<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> ƒ удалением тех <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>.
| + | |
| - | | + | |
| - | === Определение пучка, регулярной точки и регулярной грани ===
| + | |
| - | * Множество всех проходящих через α ( α ∈ N<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> ƒ через точку α (обозначается Π<sub>α</sub>(ƒ)).
| + | |
| - | * Точка α, α ∈ N<sub>ƒ</sub> называется ''регулярной точкой <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ƒ'', если существует такая точка β, что β ∈ N<sub>ƒ</sub> и Π<sub>β</sub>(f) ⊂ Π<sub>α</sub>(ƒ).
| + | |
| - | * Грань 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>, если все точки 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> ∑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>'' ƒ - дизъюнкция всех тех различных простых импликант этой <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>.
| + | |
| - | | + | |
| - | === Определение линейной <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> ƒ ∈ P<sub>2</sub>(n) вида ƒ(''x''<sub>1</sub>...''x''<sub>n</sub>) = α<sub>1</sub>''x''<sub>1</sub> ⊕ ... ⊕ α<sub>n</sub>''x''<sub>n</sub> ⊕ α<sub>0</sub>, где α<sub>0</sub>,...,α<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> в виде <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> ƒ из P<sub>2</sub>(n) является ее единственной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> тогда и только тогда, когда во множестве N<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> ===
| + | |
| - | * <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ƒ (x<sub>1</sub>,...,x<sub>n</sub>) называется ''монотонной'', если ƒ(α) ≤ ƒ(β) для любых наборов α,β ∈ B<sup>n</sup> таких, что α ≤ β.
| + | |
| - | * Набор α ∈ B<sup>n</sup> называется ''нижней единицей'' монотонной <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ƒ, ƒ ∈ P<sub>2</sub>(n), если α ∈ N<sub>ƒ</sub> и ƒ(β) = 0 для любого отличного от α набора β такого, что β ≤ α.
| + | |
| - | * Если <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ƒ(x<sub>1</sub>,...,x<sub>n</sub>) монотонно зависит от БП x<sub>i</sub>, то ни одна из ее простых импликант не может содержать букву ¬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> ƒ(''x''<sub>1</sub>...''x''<sub>n</sub>) называется ''монотонной'', если ƒ(α) ≤ ƒ(β) для любых наборов α и β куба ''B'' <sup>n</sup> таких, что α ≤ β
| + | |
| - | | + | |
| - | '''Утверждение'''. Сокращенная <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> ƒ, ƒ ∈ 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>) = ∨<sub>β∈''N''<sub>ƒ</sub><sup>+</sup></sub> ''K''<sub>β</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> сумма минимальных ===
| + | |
| - | * Функция ƒ(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> ƒ нечетной длины t = 2k - 1 ≥ 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> ΣM и соответствует покрытию N<sub>1</sub> ∪ N<sub>3</sub> ∪ ... ∪ N<sub>t</sub>
| + | |
| - | | + | |
| - | === Формулировка теоремы Журавлева о <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> сумма минимальных ===
| + | |
| - | '''Утверждение (теорема Журавлева)'''. При любом n ∈ Ν, n ≥ 3, в 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> ∑M одной, но не входит в <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> ∑M другой из этих <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> и для которой S<sub>n-3</sub>(N<sub>K</sub>,ƒ') = S<sub>n-3</sub>(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> покрытия ===
| + | |
| - | * Пусть N = {α<sub>1</sub>,...α<sub>s</sub>,} - конечное множество, а П = (N<sub>1</sub>,...,N<sub>p</sub>) - система его подмножеств, образующих покрытие множества N. Сопоставим паре (N,П) матрицу M ∈ B<sup>p,s</sup>, для которой M<nowiki><i,j></nowiki> = 1 ⇔ α<sub>j</sub> ∈ N<sub>i</sub>. Будем говорить, что i-я строка матрицы М ''покрывает'' ее j-й столбец, если M<nowiki><i,j></nowiki> = 1 и что система строк с номерами из I, I ⊆ [1,p], образует ''покрытие матрицы М'', если каждый ее столбец покрывается хотябы одной строкой с номером из I, то есть система подмножеств {N<sub>i</sub>}<sub>i ∈ I</sub> задает покрытие множества N.
| + | |
| - | * Пусть M ∈ B<sup>p,s</sup> - матрица без нулевых столбцов. Сопоставим i-й строке матрицы М БП y<sub>i</sub>, а каждому набору β ∈ B<sup>p</sup> значений этих переменных y = (y<sub>1</sub>,...,y<sub>p</sub>) - множество строк матрицы М с намерами из множества I = I(β) ⊆ [1,p], где i ∈ I(β) ⇔ β<nowiki><i></nowiki> = 1. ФАЛ F(y), для которой F(β) = 1 ⇔ система строк матрицы М с номерами из I(β) образует ее покрытие, будем называть ''функцией покрытия'' матрицы М.
| + | |
| - | '''Свойства ФАЛ покрытия матрицы'''<br>
| + | |
| - | * монотонность
| + | |
| - | * ее "нижние единицы" соответствуют тупиковым покрытиям
| + | |
| - | '''Утверждение.''' Функция покрытия F(y<sub>1</sub>,...,y<sub>p</sub>) матрицы M ∈ B<sup>p,s</sup> без нулевых столбцов задается КНФ вида: [[Изображение:Func pokr.jpg]] (*)<br>
| + | |
| - | '''Следствие.''' В результате раскрытия скобок и приведения подобных из КНФ (*) можно получить сокращенную ДНФ ФАЛ F(y), простые импликанты которой взаимно однозначно соответствуют тупиковым покрытиям матрицы М.
| + | |
| - | | + | |
| - | === Градиентный алгоритм покрытия матрицы и утверждение о длине градиентного покрытия ===
| + | |
| - | | + | |
| - | * Градиентный алгоритм: На каждом шаге алгоритма в матрице выбирается и включается в покрытие такая строка, которая покрывает наибольшее число ещё не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером). Алгоритм заканчивается свою работу после того шага, на котором получилось покрытие.
| + | |
| - | | + | |
| - | '''Утверждение'''. Пусть для действительного γ, 0 < γ ≤ 1, в каждом столбце матрицы ''M'', ''M'' ∈ ''B''<sup>p,s</sup>, имеется не меньше чем γ•''p'' единиц. Тогда покрытие матрицы ''M'', получаемое с помощью градиентного алгоритма, имеет длину не больше, чем [[Изображение:OcenkaProtikaniya.jpg]], где ln<sup>+</sup>x = ln x, если x ≥ 1 и ln<sup>+</sup>x = 0, если 0 < x ≤ 1.
| + | |
| - | | + | |
| - | === Определение протыкающего множества для граней единичного куба и верхняя оценка его мощности. ===
| + | |
| - | * Пусть N = {α<sub>1</sub>,...α<sub>s</sub>,} - конечное множество, а П = (N<sub>1</sub>,...,N<sub>p</sub>) - система его подмножеств. Множество, протыкающее систему П - такое подмножество множества N,в котором ∀ i ∈ [1,p] имеется хотябы один элемент из N<sub>i</sub>.
| + | |
| - | '''Утверждение.''' При любых натуральных n и m, m ≤ n, в кубе B<sup>n</sup> всегда найдется множество мощности не более, чем n×2<sup>m</sup>, протыкающее все грани ранга m.
| + | |
| - | | + | |
| - | === Определение функции Шеннона R(n) для ранга <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> и ее значение. ===
| + | |
| - | | + | |
| - | *R(n) = max<sub>ƒ∈P<sub>2</sub>(n)</sub> R(ƒ);
| + | |
| - | *R(n) = n × 2<sup>n − 1</sup>
| + | |
| - | | + | |
| - | === Определение функции Шеннона λ(n) для длины <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> и ее значение. ===
| + | |
| - | *λ(n) = max<sub>ƒ∈P<sub>2</sub>(n)</sub> λ(ƒ);
| + | |
| - | *λ(n) = 2<sup>n − 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> ''ƒ'' и ее оценки для почти всех <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''ƒ'' от ''n'' переменных ===
| + | |
| - | * ''λ(ƒ)'' = min<sub>ДНФ U, реализующим f</sub> ''λ''(U)
| + | |
| - | * Для почти всех ФАЛ из P<sub>2</sub>(n) ''λ(ƒ)''<~ (3/4)*2<sup>n − 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> ''ƒ'' и ее оценки для почти всех <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> ''ƒ'' от ''n'' переменных ===
| + | |
| - | * R(f) = min<sub>ДНФ U, реализующим f</sub> R(U)
| + | |
| - | * Для почти всех ФАЛ из P<sub>2</sub>(n) R(f)<~ (3/4)*n*2<sup>n − 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> проверяющего теста ===
| + | |
| - | Пусть есть схема Σ<sub>1</sub>, которая реализует ФАЛ ''f''<sub>1</sub>. Пусть есть источник помех И. Под действием источника И схема Σ может переходить в одно из неисправных состояний Σ<sub>2</sub>, …, Σ<sub>''s''</sub>, каждое из которых реализует ФАЛ ''f''<sub>''i''</sub>, ''i'' = <span style="border-top:solid 1px">2, s</span>.
| + | |
| - | | + | |
| - | Пусть (Σ, И) — модель ненадёжной схемы Σ с возможными состояниями Σ<sub>1</sub>, …, Σ<sub>''s''</sub>, в которых реализуются ФАЛ ''f''<sub>1</sub>, …, ''f''<sub>''s''</sub>, определённые на множестве наборов ''A'' = {α<sub>1</sub>, …, α<sub>''p''</sub>} ⊆ ''B''<sup>''n''</sup>. Рассмотрим матрицу ''M'' ∈ ''B''<sup>''p'', ''s''</sup>, ''M''[i, j] = ''f''<sub>''j''</sub>(α<sub>''i''</sub>). Множество строк матрицы ''M'' с номерами из ''T'' ⊆ [1, p] называется проверяющим тестом матрицы ''M'', если для ∀''j'' ∈ <span style="border-top:solid 1px">1, s</span>, ∃''t'' ∈ ''T'' такое, что ''M''[''t'', 1] ≠ M[''t'', ''j''].
| + | |
| - | | + | |
| - | '''Утверждение'''. Функция проверяющего теста ''f''(''y''<sub>1</sub>, …, ''y''<sub>''p''</sub>) для отделимой по столбцам матрицы ''M'' ∈ ''B''<sup>''p'', ''s''</sup> может быть задана с помощью КНФ
| + | |
| - | <center>[[Изображение:Check text.png|400px]]</center>
| + | |
| - | где '''N''' = {(1, j) | j ∈ <span style="border-top:solid 1px">1, s</span>}
| + | |
| - | | + | |
| - | === Утверждение об оценке длины диагностического теста для произвольной таблицы с заданным числом столбцов ===
| + | |
| - | '''Утверждение'''. Длина любого тупикового диагностического теста для отделимой по столбцам матрицы из множества ''B''<sup>p,s</sup> заключена в пределах от ⌈log s⌉ до (s − 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>. Если φ(x<sub>1</sub>,...,x<sub>k</sub>) ∈ Б и для каждого i,
| + | |
| - | i ∈ [1,k], определена формула ''F''<sub>i</sub> глубины q<sub>i</sub> над множеством Б, которая реализует функцию ƒ<sub>i</sub> из P<sub>A</sub>, то запись ''F'' вида
| + | |
| - | | + | |
| - | ''F'' = φ(''F''<sub>1</sub>,...,''F''<sub>k</sub>)
| + | |
| - | | + | |
| - | является ''формулой глубины q'' = max{q<sub>1</sub>,...,q<sub>k</sub>} + 1 над Б, которая реализует функцию ƒ вида ƒ = φ(ƒ<sub>1</sub>,...,ƒ<sub>k</sub>).
| + | |
| - | | + | |
| - | === Индуктивное определение π-схемы и нахождение реализуемой ею ФАЛ ===
| + | |
| - | Простейшей π-схемой считается любая (1,1)-КС, которая состоит из одного контакта, соединяющего полюса. Если π-схемы ∑<sub>1</sub> и ∑<sub>2</sub> уже определены, то (1,1)-КС ∑<sub>1</sub>(∑<sub>2</sub>), которая получается в результате их последовательного (параллельного) соединения тоже является π-схемой.
| + | |
| - | | + | |
| - | === Определение разделительной по входам (выходам) КС и формулировка леммы Шеннона ===
| + | |
| - | КС разделительна по входам (выходам), если ФАЛ проводимости для ∀ различных входов (выходов) ≡ 0.
| + | |
| - | | + | |
| - | '''Лемма Шеннона''': Пусть Σ = Σ''(Σ') - результат стыковки ⇒ F ≥ F' × F''. F = F' × F'', если Σ'' разделительна по входам, или Σ' разделительна по выходам.
| + | |
| - | | + | |
| - | === Определение подсхемы Σ' КС ∑ с указанием особенностей, связанных с объявлением вершин Σ' её полюсами. Основное тождество t<sub>4</sub> (введение фиктивной переменной) и вспомогательное тождество t<sub>11</sub> (лемма о звезде); обобщенные тождества t<sub>4</sub><sup>(n)</sup> и t<sub>11</sub><sup>(n)</sup> ===
| + | |
| - | Определение подсхемы Σ' КС Σ:<br>
| + | |
| - | Σ' — подсхема схемы Σ ⇔<br>
| + | |
| - | # V(Σ') ⊆ V(Σ)
| + | |
| - | # E(Σ') ⊆ E(Σ)
| + | |
| - | #
| + | |
| - | #* ∀ полюс Σ, вошедший в Σ' — полюс Σ'
| + | |
| - | #* ∀ вершина Σ', инцидентная контакту Σ\Σ' - полюс Σ'
| + | |
| - | #* ∀ другая вершина м. б. полюсом Σ'.<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> к каноническому виду с помощью основных тождеств. ===
| + | |
| - | ∑^ <i>/*здесь и далее крышка пишется над сигмой*/</i> - схема канонического вида ⇔
| + | |
| - | 1) ∀ контакт ∑^ лежит на стандартной цепи порядка n, явл. подсхемой ∑^ с полюсами в конечных вершинах цепи.
| + | |
| - | 2) ∀ внутренняя вершина ∑^ - внутренняя вершина стандартной цепи
| + | |
| - | 3) в ∑^ отсутствуют висячие циклы и || стандартные цепи
| + | |
| - | 4) в ∑^ нет существенных транзитивных проводимостей
| + | |
| - | <i>/*вопрос +-, комментарий лектора: отсутствует утверждение о переходе к КВ*/</i>
| + | |
| - | | + | |
| - | ∑^ получается из ∑ удалением ∑' (подсхемы) и заменой ∑' на ∑' ' с соотв. присоединением полюсов, эквив. ∑ (принцип эквивалентной замены).
| + | |
| - | | + | |
| - | === Определение величины ||''U''<sup>c</sup>(''L'', ''n'')|| и её верхняя оценка ===
| + | |
| - | * ''U''<sup>c</sup>(''L'', ''n'') — множество приведенных СФЭ Σ = Σ(''x''<sub>1</sub>, …, ''x''<sub>n</sub>; z<sub>1</sub>) над базисом Б<sub>0</sub>, для которых ''L''(Σ) ≤ ''L''.
| + | |
| - | * ||''U''<sup>c</sup>(''L'', ''n'')|| — число попарно неэквивалентных схем в ''U''<sup>c</sup>(''L'', ''n'')
| + | |
| - | | + | |
| - | '''Утверждение.''' Для любых натуральных ''n'' и ''L'' выполняется неравенство: ||''U''<sup>c</sup>(''L'', ''n'')|| ≤ (8(''L'' + ''n''))<sup>''L'' + 1</sup>.
| + | |
| - | | + | |
| - | === Определение тождества для формул и его подстановки ===
| + | |
| - | Подстановка - вместо переменных функции F(x<sub>1</sub>, ... , x<sub>n</sub>) подставляем функции: F(F<sub>1</sub>, ... ,F<sub>n</sub>)<br>
| + | |
| - | Тождество - t^: F(x)' = F(x)'' (1)<br>
| + | |
| - | Если к правой и левой частям (1) применить подстановку, то получим тождество:
| + | |
| - | <center>t^ : F^' = F^'' /*здесь и далее ^ стоит над буквой ей предшествующей.*/</center>
| + | |
| - | где F^' = F^'(F<sub>1</sub>, ... ,F<sub>n</sub>) и F^'' = F^''(F<sub>1</sub>, ... ,F<sub>n</sub>), которое называется подстановкой для тождества 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)
| + | |
| - | | + | |
| - | === Формулировка утверждения о связи между π-схемами и формулами с поднятыми отрицаниями ===
| + | |
| - | Любой π-схеме можно сопоставить эквивалентную ей формулу ''F'' из U<sup>Ф</sup> с поднятыми отрицаниями такую, что R(''F'') = L(Σ) и обратно.
| + | |
| - | | + | |
| - | === !!! Определение эквивалентности КС Σ', Σ" и соответствующего тождества. Основное тождество ''t<sub>2</sub>'' (перестановка контактов в цепочке) и вспомогательное тождество ''t<sub>8</sub>'' ("расклейка" двух цепочек длины 2 с общим контактом); обобщенные тождества ''t<sub>2</sub><sup>(n)</sup>'' и ''t<sub>8</sub><sup>(n)</sup>'' ===
| + | |
| - | (параграф 7 главы 2, в самом начале)
| + | |
| - | | + | |
| - | === !!! Определение суммарного цикломатического числа КС от БП ''x<sub>1</sub>'',...,''x<sub>n</sub>'' и формулировка утверждения о его изменениях при применении основных тождеств ===
| + | |
| - | (глава 2, стр 72)
| + | |
| - | | + | |
| - | === Определение структуры 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'') ≤ ''L''(''F'') + 1 ≤ 2<sup>''D''(''F'')</sup>
| + | |
| - | | + | |
| - | === !!! Понятие подформулы и применение тождества к формуле ===
| + | |
| - | | + | |
| - | === Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого формулу с поднятыми отрицаниями можно преобразовать в формулу со следующим порядком применения базисных функций: ¬, &, ∨ ===
| + | |
| - | | + | |
| - | * Дистрибутивность ''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>π</sup>(L,n)||'' и ее верхняя оценка ===
| + | |
| - | | + | |
| - | * ||U<sup>π</sup>(L,n)|| - число попарно не эквивалентных приведенных π-схем от БП x<sub>1</sub>,...,x<sub>n</sub> сложности ≤ ''L''
| + | |
| - | | + | |
| - | * ||U<sup>π</sup>(L,n)|| ≤ (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 = (ƒ<sub>1</sub>,...,ƒ<sub>m</sub>)'' и ее тривиальная нижняя оценка для некоторых систем ФАЛ ===
| + | |
| - | | + | |
| - | === Определение функции Шеннона ''L<sup>C</sup>(n)'' и ее верхние оценки, получаемые методом Шеннона и методом О. Б. Лупанова ===
| + | |
| - | | + | |
| - | * ''L<sup>C</sup>(n)'' = max<sub>ƒ∈P<sub>2</sub>(n)</sub>''L<sup>C</sup>(ƒ)''
| + | |
| - | * Метод Шеннона: ''L<sup>C</sup>(n)'' <∼ 8•2<sup>n</sup>/n
| + | |
| - | * Метод Лупанова: ''L<sup>C</sup>(n)'' ≤ (2<sup>n</sup>/n)•(1 + (5log''n'' + ''O''(1))/n)
| + | |
| - | | + | |
| - | === Нижняя оценка функции Шеннона ''L<sup>π</sup>(n)'' и то мощностное соотношение, из которого она выводится ===
| + | |
| - | * ''L<sup>π</sup>(n)'' ≥ ''2<sup>n</sup>'' / ''log<sub>2</sub>n '' (Асимптотически больше)
| + | |
| - | * ''||U<sup>π</sup>(L,n)|''| ≤ ''(16n)<sup>L</sup>''
| + | |
| - | | + | |
| - | === Определение мультиплексорной ФАЛ ''M<sub>n</sub>'' порядка ''n'', утверждение о сложности ее реализации в классах ''π''-схем и формул ===
| + | |
| - | | + | |
| - | Функция вида
| + | |
| - | µ<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>(ƒ)'' ФАЛ ''ƒ(x<sub>1</sub>...x<sub>n</sub>)'' в классе КС и её тривиальные нижние оценки для ФАЛ ''ƒ'', существенно зависящей от всех своих переменных (с учетом характера этой зависимости) ===
| + | |
| - | | + | |
| - | L<sup>K</sup> (f) > n для ФАЛ f, существенно зависящей от всех своих переменных.
| + | |
| - | | + | |
| - | === Определение функции Шеннона ''L<sup>π</sup>(n)'' и её верхняя оценка, получаемая с помощью моделирования совершенной ДНФ на основе контактного дерева ===
| + | |
| - | | + | |
| - | * L<sup>π</sup>(n) = max<sub>ƒ∈P<sub>2</sub>(n)</sub>L<sup>π</sup>(ƒ)
| + | |
| - | * L<sup>π</sup>(n) ≤ 2<sup>n + 1</sup> − 2 //FIXME
| + | |
| - | | + | |
| - | === Нижняя оценка функции Шеннона ''L<sup>c</sup>(n)'' и то мощностное соотношение, из которого она выводится ===
| + | |
| - | | + | |
| - | * L<sup>C</sup>(n) ≥ 2<sup>n</sup> / n (Асимптотически больше)
| + | |
| - | * ||U<sup>C</sup>(L,n)|| ≤ (8(L + n))<sup>L + 1</sup>
| + | |
| - | | + | |
| - | === Определение ДУМ и формулировка утверждения о свойствах стандартного ДУМ ===
| + | |
| - | | + | |
| - | * Дизъюнктивно-универсальное множество (ДУМ) ''G'' порядка ''n'' и ранга ''p'' ⇔ ∀ ''g ∈ P<sub>2</sub>(n) ∃ g<sub>1</sub>,...,g<sub>p</sub> ∈ G : g = g<sub>1</sub>∪...∪g<sub>p</sub>''
| + | |
| - | | + | |
| - | '''Утверждение'''. Пусть ''m'', ''S'', ''p'' ∈ ''N'': ''p * S ≥ 2<sup>m</sup>'', тогда ∃ ДУМ ''G'' порядка ''m'' и ранга ''p'':
| + | |
| - | # |G| ≤ p * 2<sup>S</sup>
| + | |
| - | # В ''G'' ∃ система из ''p'' ортогональных функций ψ<sub>1</sub>,...,ψ<sub>p</sub> : ∀ g ∈ G имплицирует одну из них.
| + | |
| - | | + | |
| - | === Регулярные разбиения единичного куба и моделирование ФАЛ с помощью БП. Асимптотика сложности контактного дешифратора ===
| + | |
| - | | + | |
| - | Множество δ, δ ⊆ B<sup>q</sup>, называется m-регулярным множеством наборов
| + | |
| - | куба B<sup>q</sup>, если m < q, |δ| = 2<sup>m</sup> и все префиксы длины m наборов из δ различны.
| + | |
| - | | + | |
| - | m-регулярное разбиение куба B<sup>q</sup> — разбиение этого куба, состоящее из m-регулярных множеств δ<sub>1</sub>, …, δ<sub>q − m</sub>. (???)
| + | |
| - | | + | |
| - | моделирование ФАЛ с помощью БП - ???
| + | |
| - | | + | |
| - | L<sup>K</sup> (Q<sub>n</sub>) ~ 2<sup>n</sup>
| + | |
| - | | + | |
| - | === !!! Асимптотически наилучший метод синтеза КС ===
| + | |
| - | | + | |
| - | === !!! Построение самокорректирующихся КС ===
| + | |
| - | | + | |
| - | === !!! Асимптотически наилучший метод синтеза формул в В<sub>0</sub>. Поведение функции Шеннона для глубины ФАЛ ===
| + | |
| - | | + | |
| - | === !!! Задача синтеза схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Методы получения верхних и нижних оценок сложности, минимальность некоторых схем ===
| + | |
| - | | + | |
| - | === Определение ''m''-регулярного множества наборов ===
| + | |
| - | Множество δ, δ ⊆ B<sup>q</sup>, называется ''m-регулярным'' множеством наборов куба B<sup>q</sup>, если m < q, |δ| = 2<sup>m</sup> и все префиксы длины m наборов из δ различны.
| + | |
| - | | + | |
| - | === !!! Определение (p, q)-самокорректирующейся КС. Утверждение о сложности самокорректирующейся КС, получаемой дублированием ===
| + | |
| - | | + | |
| - | {{Курс Основы Кибернетики}}
| + | |
