Дать определение функции Шеннона l(n) для длины ДНФ и указать её значение.
Число ЭК (ЭД) в ДНФ (соответственно КНФ) A называется ее длиной и обозначается через λ (A).
Для любого n, n ∈ N, и для почти всех ФАЛ f, f ∈ P2 (n), имеют место соотношения:
Сформулировать утверждение о длине диагностического теста для почти всех таблиц.
Мощность теста называется также его длиной. Длина любого тупикового диагностического
теста для отделимой по столбцам матрицы из множества Bp,s заключена в пределах от 
до (s − 1).
A. Дать определение теста для таблицы и заданной цели контроля.
Пусть M, M ∈ Bp,s, — отделимая по столбцам матрица, а N — связанная с ней цель контроля.
Сопоставим i-й строке, i ∈ [1, p], матрицы M БП yi, а каждому набору β, β ∈ Bp, значений этих переменных y = (y1, . . . , yp) — множество строк матрицы M с номерами из множества I = I (β) ⊆ [1, p], где i ∈ I (β) тогда и только тогда, когда β _i_ = 1. Рассмотрим ФАЛ F (y), для которой F (β) = 1 тогда и только тогда, когда система строк матрицы M с номерами из I (β) образует тест для (M,N), и будем называть эту ФАЛ функцией теста для (M, N).
b. Выписать максимальную антицепь частично-упорядоченного множества целых чисел отрезка [1, 10] с отношениями делимости.
C. Дать определение функции Шеннона R(n) ранга ДНФ и указать ее значение.
число вхождений в формулу символов переменных
D. Сформулировать утверждение о длине градиентного покрытия.
Пусть для действительного γ, 0<γ<1,в каждом столбце матрицы M, M ∈ Bp,s, имеется не меньше, чем γ ·p, единиц. Тогда покрытие матрицы M, получаемое с помощью градиентного алгоритма, имеет длину не больше, чем 
|
|
|
Тест № 4
Дать определение тождества для формул, и его подстановки.
Формулы F’и F’’, реализующие равные функции f’ и F’’, называются равными или, иначе, эквивалентными. При этом равенство вида t : F’= F’’считается тождеством.Для того, чтобы выделить набор x = (xi1, . . . , xin), который состоит из всех различных БП алфавита X, встречающихся в формуле F и перечисленных в порядке возрастания их номеров, будем записывать ее в виде F = F (x). При этом формулу, которая получается из F в результате замены
каждого вхождения БП xij, j = 1, . . . , n, формулой Fj будем считать результатом подстановки формулы Fj вместо БП xij, j = 1, . . . , n, в формулу F и будем обозначать ее через F (F1, . . . , Fn).
если указанную подстановку применить к обеим частям тождества t : F’= F’’, где F’= F’(x) и F’’= F’’(x), мы получим тождество 
которое называется подстановкой для тождества t.
Дать определение подсхемы КС и указать правила применение к ней тождеств.
С хема Σ’ называется подсхемой схемы Σ, если V(Σ’)⊆ V (Σ), E(Σ’)⊆ E (Σ) и любая вершина v, v ∈ V (Σ_), которая либо относится к множеству входов (выходов) Σ, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(Σ)\E(Σ_), является входом (соответственно, выходом) Σ’. Из определений следует, что для СФЭ и КС с неразделенными полюсами, как и для формул, имеет место принцип эквивалентной замены. При этом все введенные выше для случая эквивалентных преобразований формул понятия (однократная и кратная выводимость, полнота системы тождеств и др.), а также связанные с ними обозначения переносятся на случай ЭП указанных классов схем без изменений.
|
|
|
3. Привести основные тождества, связанные с:
a) законом де Моргана для конъюнкции – в классах формул и СФЭ;
b) ветвлением выхода ФЭ отрицания – в классе СФЭ;
c) введением фиктивной БП в контакт – в классе КС.
Дата добавления: 2018-05-12; просмотров: 374; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!