Тесты с почти всеми ответами2 (1133185)
Текст из файла
Тест №11. Определение элементарной конъюнкции и ДНФ.ФункцииX i и X i будем называть буквами БП X i и, как обычно, будем считать, что X i0 = X i , X i1 = X i .Конъюнкция (дизъюнкция) r, 1 < r < n букв различных БП из множества X (n) называется элементарнойконъюнкцией (соответственно элементарной дизъюнкцией) ранга r от булевых переменных X (n).Дизъюнкция различных элементарных конъюнкций называется дизъюнктивной нормальной формой(ДНФ)2.
Определение нерасширяемой ДНФ.Любая ДНФ A’, которую можно получить из ДНФ A путем формирования в ней с помощью тождествассоциативности и коммутативности подформул вида xiK’ ∨ не(xi)K’’, применения к этим подформуламтождества обобщенного склеивания xiK’ ∨ xiK’’ = xiK’ ∨ не(xi)K’’ ∨ K’K’’ и последующего приведенияподобных, называется расширением ДНФ A.3. Определение ДНФ сумма тупиковых.ДНФ пересечение тупиковых (сумма тупиковых) ФАЛ f, есть дизъюнкция всех тех различных простыхимпликант этой ФАЛ, которые входят в любую (соответственно хотя бы в одну) тупиковую ДНФ ФАЛ f.4.
Критерий вхождения простых импликант в ДНФ пересечение тупиковых.Дизъюнктивная нормальная форма ∩T ФАЛ f состоит из тех простых импликант ФАЛ f, которыесоответствуют ядровым граням этой ФАЛ.1. Определение импликанты и простой импликанты.Будем говорить, что ФАЛ f’ имплицирует ФАЛ f’’, если Nf’ ⊆ Nf’’ , то есть импликация (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 можно получить сокращенную ДНФ этой ФАЛ в результате построенияпоследовательных строгих расширений и приведения подобных до получения неприводимой ДНФ, неимеющей строгих расширений.Тест №21.
Определение π-схемы и её сложности.Схемы, моделирующие ДНФ или КНФ, являются частным случаем т. н. параллельно-последовательных КСили, иначе, π-схем.Простейшей π-схемой считается любая (1, 1)-КС, которая состоит из одного контакта, соединяющего полюса. Если π-схемы Σ1 и Σ2уже определены, то (1, 1)-КС Σ’ (Σ’’), которая получается в результате их параллельного (соответственно последовательного)соединения тоже является π-схемой.2.
Определение приведенной СФЭ.Будем называть (1,m)-КС приведенной, если все изолированные вершины Σ являются ее полюсами, а все контакты и остальныевершины Σ принадлежат простым проводящим цепям, соединяющим ее вход и выходы.3.Определение величиныU Ф [ D, n ]и её верхняя оценка.Обозначим через 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(Σ) — глубина Σ, то есть максимальная глубина ее вершин.4.Утверждение о соотношениях между рангом, сложностью и глубиной одной и той же формулы.Для формулы F, F ∈ UΦ, выполняются неравенства1.
Определение СФЭ в базисе {&, ∨, ¬} и её глубины.Схемой из функциональных элементов над базисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входнаявыборка которой состоит из всех истоков Σ, а вершины помечены следующим образом:1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной с ним вершины, причемразличным входам (выходам)сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Σопределяется упорядоченностью сопоставленных им БП;2. каждая отличная от истока вершина v схемы Σ помечена ФС ϕi, где ki = d+Σ (v).D(Σ) — глубина Σ, то есть максимальная глубина ее вершин.2.
Определение подобных формул.Формулы, получающиеся друг из другаассоциативности, называются подобными.3.Определение величиныU K ( L, n )эквивалентнымипреобразованияминаосноветождествкоммутативностиии её верхняя оценка.Uк (L, n) - множество приведенных (1, 1)-схем Σ из UA от БП X (n), для которых L(Σ) <= L.Кол-во попарно неэквивалентных КС от n БП сложности <= L4.Определение альтернирования формулы с поднятыми отрицаниями и утверждение об оптимизации подобныхформул по глубине.Кол-во смены & -> V и наоборот по целям ( от корня к листьям)Для любой формулы F из UΦ существует подобная ей формула ˇF такая, что1.
Определение (1,1) – КС от БП x1,...,xn и её функционирования (той ФАЛ, которую она реализует).Сеть Σ с входами a_1, . . . , a_p и выходами a__ 1, . . . , a__ q , в которой все ребра (дуги) помечены переменными x1, . . . , xn илиих отрицаниями x1, . . . , xn, называется (p, q)-контактной схемой (КС) от БП x1, . . . , xng (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, .
. . , t2. Определение эквивалентности двух СФЭ.эквивалентными, если они реализуют равные системы ФАЛЭквивалентность схем Σ’ и Σ’’ из U имеет место тогда и только тогда, когда Σ’и Σ’’ реализуют равные системы (матрицы) ФАЛпредполагается, что соответствующие друг другу полюса (выходы, входы) в Σ’ и Σ’’ имеют одинаковые пометки, а эквивалентностьΣ’ и Σ’’ записывается в виде тождества t : Σ’ ∼ Σ’’3.
Определение величиныU Ф ( L, n )и её верхняя оценка.множество приведенных формул F = F (x1, . . . , xn) над базисом Б0, для которых L(F) <= L4. Определение вычисляющей программы (ВП) и ее ширины, утверждение о ширине ВП, моделирующей ДНФ.Схема Σ, Σ ∈ UCБ с монотонной нумерацией вершин называется вычисляющей программой (ВП) над базисом Бдля любой дуги номер вершины, из которой она исходит, больше номера вершины, в которую эта дуга входит.Максимальное число отрезков вида [i, ai), где i ∈ (n, p], имеющих непустое пересечение, называется шириной ВП Σ, и определяетминимальное число ячеек памяти, необходимых для хранения ее внутренних БП un+1, .
. . , u где ai —максимальный номеркоманды, в которой встречается ui.число ФЭ ВП Σ характеризует время выполнения ее вычисляющих команд на одном процессоре,Тест №31. Дать определение частично-упорядоченного множества (ЧУМ), его ширины и ранжированного ЧУМ.Отношение, обладающее свойствами рефлексивности,транзитивности и антисимметричности, будем называть отношениемчастичного порядка.
Если τ — отношение частичного порядка на множестве A, то пару (A, τ ) будем называть частичноупорядоченным множеством.Максимальная мощность цепей (антицепей) частично упорядоченного множества называется его длиной (соответственношириной).Частично упорядоченное множество (A, τ ) длины t называется ранжированным частично упорядоченным множеством, если все егонеуплотняемые цепи имеют мощность t.2.Выписать КНФ для ФАЛ теста для таблицы и цели контроля {(1,2), (1,3), (2,4), (4,5)}01101010100101111010(K1 V K2)(K1 V K2 V K3 V K4)(K1 V K2 V K4)(K1 V K2 V K4)3.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
