termin1 - testall (1133186), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

3) Определение ДНФ сумма тупиковых.

пересечение тупиковых (сумма тупиковых) ФАЛ f есть дизъюнкция всех тех различных простых

импликант этой ФАЛ, которые входят в любую (соответственно хотя бы в одну) тупиковую ДНФ ФАЛ f.

4) Критерий вхождения простых импликант в ДНФ пересечение тупиковых.

Дизъюнктивная нормальная форма ∩T ФАЛ f состоит из тех простых импликант ФАЛ f, которые

соответствуют ядровым граням этой ФАЛ.

1) Определение импликанты и простой импликанты.

Элементарная конъюнкция,которая имплицирует ФАЛ f, называется импликантой этой ФАЛ. Импликанта K ФАЛ f называется простой импликантой этой ФАЛ, если она не поглощается никакой другой отличной от нее импликантой ФАЛ f.

2) Определение минимальной ДНФ и кратчайшей ДНФ.

минимальной (кратчайшей) ДНФ ФАЛ f, то есть ДНФ, которая имеет минимальный ранг (соответ-

ственно длину) среди всех ДНФ, реализующих f.

3) Определение ядровой точки, ядровой грани и ДНФ Квайна.

Набор α, α прин Bn, называется ядровой точкой ФАЛ f (x1, . . . , xn), если α прин. Nf и α входит только в одну максимальную грань ФАЛ f. При этом грань NK, являющаяся максимальной гранью ФАЛ f и содержащая точку α, считается ядровой гранью ФАЛ f Дизъюнктивная нормальная форма, получающаяся из сокращенной ДНФ ФАЛ f удалением тех ЭК K, для которых грань NK покрывается ядром ФАЛ f, но не входит в него, называется ДНФ Квайна этой ФАЛ.

4) Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо КНФ. Если неприводимая ДНФ A получается из КНФ B ФАЛ f в результате раскрытия скобок и приведения подобных, то A — сокращенная ДНФ ФАЛ f.

1) Определение сокращённой ДНФ.

Дизъюнкция всех простых импликант ФАЛ f называется ее сокращенной ДНФ.

2) Определение тупиковой ДНФ.

Будем говорить, что ДНФ A, реализующая ФАЛ f, является тупиковой ДНФ, если f != A! для

любой ДНФ A!, полученной из A в результате удаления некоторых букв или целых ЭК.

3) Определение пучка, регулярной точки и регулярной грани.

Для ФАЛ f (x1, . . . , xn) и набора α, α прин Nf , обозначим через Πα (f) множество всех проходящих через α максимальных граней ФАЛ f, которое мы будем называть пучком ФАЛ f через точку α.

Точку α, α прин Nf , будем называть регулярной точкой ФАЛ f, если найдется точка β, β прин Nf ,

для которой имеет место строгое включение Πβ (f) содержится в Πα (f).

Грань NK ФАЛ f называется регулярной гранью этой ФАЛ, если все точки NK регулярны.

4) Формулировка утверждения, связанного с построением сокращённой ДНФ из какой-либо ДНФ. Из любой ДНФ A ФАЛ f можно получить сокращенную ДНФ этой ФАЛ в результате построения последовательных строгих расширений и приведения подобных до получения неприводимой ДНФ, не имеющей строгих расширений.

3) Дать определение функции Шеннона (n) для длины сокращенной ДНФ и привести её оценки.

Функцию ψ (n) = max на f прин P2(n) от ψ (f) , которая характеризует максимальное значение ψ-сложности ФАЛ из P2 (n), называют, обычно, функцией Шеннона для класса ДНФ относительно функционала ψ.

λ (n) = 2^n−1, - функция Шеннона для длины сокр ДНФ.

1) Дать определение частично-упорядоченного множества (ЧУМ), его ширины и ранжированного ЧУМ.

Отношение, обладающее свойствами рефлексивности, транзитивности и антисимметричности, будем, как обычно, называть отношением частичного порядка

Если τ — отношение частичного порядка на множестве A, то пару (A, τ ) будем называть частично упорядоченным множеством.

Ширина частично упорядоченного множества

(Bn,_) равна ( n n/2)

(n i) = a!/(n! (a-n)!)

Частично упорядоченное множество (A, τ ) длины t называется ранжированным частично упорядоченным множеством, если все его неуплотняемые цепи имеют мощность t.

4) Сформулировать утверждение об особенностях ДНФ для монотонных ФАЛ.

Сокращенная ДНФ A монотонной ФАЛ f, f прин P2 (n), является единственной тупиковой ДНФ этой ФАЛ и имеет вид: A(x1, . . . , xn) = объединение всех K+β (x1, . . . , xn) таких что β принN+f

Определение функции Шеннона L^C(n) и её верхняя оценка, получаемая методом Шеннона.

L^C(n) <=6*(2ⁿ / n)

1. Нижняя мощностная оценка функции Шеннона L^Ф(n) и то соотношение, из которого она выводится.

L^Ф(n) >=2ⁿ / log n утв.: ||U^Ф(L, n)||<=(32n)^L+1

1. Нижняя мощностная оценка функции Шеннона L^k(n) и то соотношение, из которого она выводится.

L^K(n) >=2ⁿ / n утв.: ||U^K(L, n)||<=(8nL)^L

1. Верхняя оценка функции Шеннона D(n), получаемая асимптотически наилучшим способом

D(n)<=n-log(log(n))-o₌(1) – тут 2е подчеркивание

1. Нижняя мощностная оценка функции Шеннона L^C(n) и то соотношение, из которого она выводится.

L^C(n) >=2ⁿ / n утв.: ||U^C(L, n)||<=(32(L+n))^L+1

1. Верхняя оценка функции Шеннона L^Ф(n), получаемая асимптотически наилучшим способом.

L^Ф(n) <=2ⁿ / log n

1. Определение функции Шеннона L^k(n) и её верхняя оценка, получаемая методом Шеннона.

L^K(n) <=4*(2ⁿ / n)

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

D(n)>=n-log(log(n))+o⁼(1) утв.: ||U^Ф(D, n)||<=(32n)^{2^D\}

Характеристики

Список файлов ответов (шпаргалок)