Определение эквивалентности двух СФЭ.
эквивалентными, если они реализуют равные системы ФАЛ
Эквивалентность схем Σ’и Σ’’из U имеет место тогда и только тогда, когда Σ’и Σ’’реализуют равные системы (матрицы) ФАЛ предполагается, что соответствующие друг другу полюса (выходы, входы) в Σ’и Σ’’ имеют одинаковые пометки, а эквивалентность Σ’ и Σ’’записывается в виде тождества t : Σ’ ∼ Σ’’
3. Определение величины 
и её верхняя оценка.
множество приведенных формул F = F (x1, . . . , xn) над базисом Б0, для которых L(F) <= L
Определение вычисляющей программы (ВП) и ее ширины, утверждение о ширине ВП, моделирующей ДНФ.
Схема Σ, Σ ∈ UCБ с монотонной нумерацией вершин называется вычисляющей программой (ВП) над базисом Б
для любой дуги номер вершины, из которой она исходит, больше номера вершины, в которую эта дуга входит.
Максимальное число отрезков вида [i, ai), где i ∈ (n, p], имеющих непустое пересечение, называется шириной ВП Σ, и определяет минимальное число ячеек памяти, необходимых для хранения ее внутренних БП un+1, . . . , u где ai —максимальный номер команды, в которой встречается ui.
число ФЭ ВП Σ характеризует время выполнения ее вычисляющих команд на одном процессоре,
Тест №3
Дать определение частично-упорядоченного множества (ЧУМ), его ширины и ранжированного ЧУМ.
Отношение, обладающее свойствами рефлексивности,транзитивности и антисимметричности, будем называть отношением частичного порядка. Если τ — отношение частичного порядка на множестве A, то пару (A, τ ) будем называть частично упорядоченным множеством.
|
|
|
Максимальная мощность цепей (антицепей) частично упорядоченного множества называется его длиной (соответственно шириной).
Частично упорядоченное множество (A, τ ) длины t называется ранжированным частично упорядоченным множеством, если все его неуплотняемые цепи имеют мощность t.
2. Выписать КНФ для ФАЛ теста для таблицы и цели контроля {(1,2), (1,3), (2,4), (4,5)}
(K1 V K2)(K1 V K2 V K3 V K4)(K1 V K2 V K4)(K1 V K2 V K4)
Дать определение функции Шеннона l(n) для длины сокращенной ДНФ и привести её оценки.
Число ЭК (ЭД) в ДНФ (соответственно КНФ) A называется ее длиной и обозначается через λ (A).
Для любого n, n ∈ N, и для почти всех ФАЛ f, f ∈ P2 (n), имеют место соотношения:
Сформулировать утверждение об особенностях ДНФ для монотонных ФАЛ.
Сокращенная ДНФ A монотонной ФАЛ f ∈ P2 (n), является единственной тупиковой ДНФ этой ФАЛ и имеет вид:
Сопоставим каждому набору β из Bn, монотонную ЭКK+β от БП X (n), состоящую из тех и только тех букв xj ,j ∈ [1, n], для которых β j = 1,
Дать определение покрытия матрицы и ФАЛ покрытия.
|
|
|
Пусть N = {α1, . . . , αs} — конечное множество, а N == (N1, . . . ,Np) — система его подмножеств, образующих покрытие множества N. Сопоставим паре (N,N) матрицу M, M ∈ Bp,s, для которой M i, j = 1 тогда и только тогда, когда αj ∈Ni . i-я строка матрицы M покрывает ее j-й столбец, если M_i, j = 1, то есть αj ∈Ni и что система строк с номерами из I, I ⊆ [1, p], образует покрытие матрицы M, если каждый ее столбец покрывается хотя бы одной строкой с номером из I, то есть система подмножеств {Ni}i∈I задает покрытие множества N.
Рассмотрим ФАЛ F (y), для которой F (β) = 1 тогда и только тогда, когда система строк матрицы M с номерами из I (β) образует ее покрытие, и будемназывать эту ФАЛ функцией покрытия матрицы M.
2. Выписать сокращённую ДНФ монотонной ФАЛ с множеством нижних единиц {(0011), (1001), (0110)}.
'x1'x2x3x4Vx1'x2'x3x4V'x1x2x3'x4
Дата добавления: 2018-05-12; просмотров: 223; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!