Определение ДУМ и описание стандартного ДУМ.
Множество ФАЛ G, G ⊆ P2 (m), называется дизъюнктивно-универсальным множеством (ДУМ) порядка m и ранга p, если любая ФАЛ g, g ∈ P2 (m), может быть представлена в виде g = g1 ∨ . . . ∨ gp, где gi ∈ G при всех i, i = 1, . . . , p. Стандартный способ построения таких множеств связан с разбиениями единичного куба. Пусть Π = (π1, . . . , πp) — разбиение куба Bm, и пусть для всех i, i = 1, . . . , p, ФАЛ χi (x1, . . . , xm) — характеристическая ФАЛ множества πi, а G(i) — множество всех тех ФАЛ g, g ∈ P2 (m), которые обращаются в 0 вне πi. Заметим, что множество ФАЛ G вида
G = G(1) ∪ . . . ∪ G(p) является ДУМ порядка m и ранга p. Действительно, любая ФАЛ g, g ∈ P2 (m), может быть представлена в виде g = g1 ∨ . . . ∨ gp, где gi = χig и, следовательно, gi ∈ G(i) для всех i, i = 1, . . . , p.
1. Определение сложности LФ(f) ФАЛ f(x1...xn) в классе формул и её тривиальная нижняя оценка для существенной ФАЛ.
LФ(f)=minL(Σ) - сложность ФАЛ f в классе UФ относ функционала L
Σ реал f,
UФ Э Σ
LФ(f)>=n-1
2. Определение функции Шеннона Lk(n) и её верхняя оценка, получаемая методом Шеннона.
L(n) = max L(f), f принадлежит P2(n)-Функция Шеннона для класса Uk относительно функционала сложности L.
Нижняя мощностная оценка функции Шеннона D(n) и то соотношение, из которого она выводится.
Аналогичным образом на основе неравенства и равенства c использованием леммы 4.1, где q = 22n,y = 2D(n), γ = 0, α = 1 и a = 64n, устанавливается справедливость при ε (n) = 12/log n.
4. Верхняя оценка функции Шеннона LC(n), получаемая асимптотически наилучшим способом.
5. Формулировка утверждения, из которого следует минимальность контактного дерева в классе разделительных КС.
Дата добавления: 2018-05-12; просмотров: 265; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!