Формулировка утверждения, связанного с построением сокращённой ДНФ из какой-либо ДНФ.
Из любой ДНФ A ФАЛ f можно получить сокращенную ДНФ этой ФАЛ в результате построения последовательных строгих расширений и приведения подобных до получения неприводимой ДНФ, не имеющей строгих расширений.
Тест №2
Определение p-схемы и её сложности.
Схемы, моделирующие ДНФ или КНФ, являются частным случаем т. н. параллельно-последовательных КСили, иначе, π-схем. Простейшей π-схемой считается любая (1, 1)-КС, которая состоит из одного контакта, соединяющего полюса. Если π-схемы Σ1 и Σ2 уже определены, то (1, 1)-КС Σ’ (Σ’’), которая получается в результате их параллельного (соответственно последовательного) соединения тоже является π-схемой.
Определение приведенной СФЭ.
Будем называть (1,m)-КС приведенной, если все изолированные вершины Σ являются ее полюсами, а все контакты и остальные вершины Σ принадлежат простым проводящим цепям, соединяющим ее вход и выходы.
3. Определение величины 
и её верхняя оценка.
Обозначим через UCБ (L, n) (UΦБ(L, n) и UΦБ[D, n]) множество приведенных СФЭ Σ = Σ(x1, . . . , xn; z1) (соответственно формул F = F (x1, . . . , xn)) над базисом Б, для которых L(Σ)<=L (соответственно L(F)<=L и D(F)<=D), L(Σ) — сложность Σ, то есть число всех ее ФЭ; D(Σ) — глубина Σ, то есть максимальная глубина ее вершин.
Утверждение о соотношениях между рангом, сложностью и глубиной одной и той же формулы.
Для формулы F, F ∈ UΦ, выполняются неравенства 
|
|
|
1. Определение СФЭ в базисе {&, Ú, Ø} и её глубины.
Схемой из функциональных элементов над базисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входная выборка которой состоит из всех истоков Σ, а вершины помечены следующим образом:
1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной с ним вершины, причем различным входам (выходам)сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Σ определяется упорядоченностью сопоставленных им БП;
2. каждая отличная от истока вершина v схемы Σ помечена ФС ϕi, где ki = d+Σ (v).
D(Σ) — глубина Σ, то есть максимальная глубина ее вершин.
Определение подобных формул.
Формулы, получающиеся друг из друга эквивалентными преобразованиями на основе тождеств коммутативности и ассоциативности, называются подобными.
3. Определение величины 
и её верхняя оценка.
Uк (L, n) - множество приведенных (1, 1)-схем Σ из UA от БП X (n), для которых L(Σ) <= L.
Кол-во попарно неэквивалентных КС от n БП сложности <= L
Определение альтернирования формулы с поднятыми отрицаниями и утверждение об оптимизации подобных формул по глубине.
|
|
|
Кол-во смены & -> V и наоборот по целям ( от корня к листьям)
Для любой формулы F из UΦ существует подобная ей формула ˇF такая, что 
1. Определение (1,1) – КС от БП x1,...,xn и её функционирования (той ФАЛ, которую она реализует).
Сеть Σ с входами a_1, . . . , a_p и выходами a__ 1, . . . , a__ q , в которой все ребра (дуги) помечены переменными x1, . . . , xn или их отрицаниями x1, . . . , xn, называется (p, q)-контактной схемой (КС) от БП x1, . . . , xn
g (x1, . . . , xn) = K (C1) ∨ . . . ∨ K (Ct) можно использовать для построения (1, 1)-КС Σ_, в которой ФАЛ проводимости от входа a1 к выходу a2 описывается заданной ДНФ вида A = K1 ∨ . . . ∨ Kt,
где K1, . . . , Kt — различные ЭК, и которая «моделирует» ДНФ A. Указанная контактная схема Σ_ получается в результате проведения из a1 в a2 цепей C1, . . . , Ct без общих контактов и внутренних вершин так, что K (Ci) = Ki,i = 1, . . . , t
Дата добавления: 2018-05-12; просмотров: 269; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!