Определения (1133430)

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

Текст из файла

Формулы

Формула, в которой все ФС ¬ встречаются только над БП, называется формулой с поднятыми отрицаниями.

Для каждой формулы F, F ∈ UΦ, индукцией по глубине определим величину Alt (F) так, что:

1. Alt (F) = 0, если F — ЭК или ЭД;

2. Alt _F_= Alt (F) + 1, если F не является переменной;

3. Alt (F1 ◦ · · · ◦ Ft) = max {Alt (F1) , . . . , Alt (Ft)} + 1, где t => 2 и ◦ ∈ {&, ∨}, если ни одна из формул F1, . . . , Ft не является формулой вида F1 ◦ F2 и хотя бы одна из них не является буквой. Величину Alt (F) будем называть альтернированием формулы F.

СФЭ

Схемой из функциональных элементов над базисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входная выборка которой состоит из всех истоков Σ, а вершины помечены следующим образом:

1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной сним вершины, причем различным входам (выходам) сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Σ определяется

упорядоченностью сопоставленных им БП;

2. каждая отличная от истока вершина v схемы Σ помечена ФС ϕi, где ki =

Переменная, которая встречается в формуле только один раз, называется бесповторной переменной этой формулы. Формула называется бесповторной, если бесповторны все ее

БП.

Бесповторная формула F (xn+1, . . . , xn+p) называется каркасом приведенной СФЭ

Σ(x1, . . . , xn; z1), если вхождение БП xn+i, i ∈ [1, p], является i-м вхождением БП в F, а дерево формулы F отличается от наддерева СФЭ Σ только пометками листьев.

Модификации СФЭ

Схема Σ, Σ ∈ , с монотонной нумерацией вершин - вычисляющая программа (ВП) над базисом Б

Сопоставим вершине vi, i ∈ [1, p], «внутреннюю» БП ui и будем считать, что vi выполняет команду сномером i, которая является:

a) командой ввода ui = xi, если i ∈ [1, n];

b) вычисляющей командой , где

ϕ(i) — ФС от k(i) БП, приписанный вершине vi в Σ, а , j = 1, . . . , , — БП, сопоставленная начальной вершине дуги с номером j, входящей в vi, если i ∈ (n, p].

Максимальное число отрезков вида [i, ai), где i ∈ (n, p], имеющих непустое пересечение, называется шириной ВП Σ, и определяет минимальное число ячеек памяти, необходимых

для хранения ее внутренних БП un+1, . . . , up.

Положим ^Б = {Ei : ki _ 2}

Для ФЭ Ei, Ei ∈ ^Б, определим его приведенный вес ρi и приведенную задержку τi следующим образом:

Введем, далее, величины

которые назовем приведенным весом и приведенной задержкой базиса Б соответственно.

Pi-схемы

Ребро или дуга графа с пометкой называется замыкающим (соответственно

размыкающим) контактом БП xi

Сеть Σ с входами и выходами , в кото рой все ребра (дуги) помечены переменными x1, . . . , xn или их отрицаниями x1, . . . , xn, называется (p, q)-контактной схемой (КС) от БП x1, . . . , xn и обозначается Σ = Σ(x1, . . . , xn) или При этом число контактов называется сложностью КС Σ и обозначается через L(Σ)

Для вершин v и u КС Σ введем функцию проводимости от вершины v к вершине u как ФАЛ gv,u (x1, . . . , xn), которая равна 1 на наборе α = (α1, . . . , αn) ∈ Bn тогда и только тогда, когда

в сети Σ|α существует (v − u)-цепь, то есть тогда и толь ко тогда, когда в Σ имеется цепь из проводящих на набореα контактов вида , идущая из v в u.

Будем говорить также, что ФАЛ gv,u является функцией достижимости вершины u из вершины v или, иначе, реализуется между вершинами v и u.

Для множества C, состоящего из контактов вида ir в КС Σ, определим его функцию проводимости K (C) и функцию отделимости J (C) как ФАЛ вида соответственно. При этом множество C называется проводящим (отделимым), если K (C) != 0 (J (C) != 1), и нулевым (соответственно, единич-

ным) в противном случае.

Множество S, которое состоит из ребер графа G = (V,E) и обладает тем свойством, что вершина u, u ∈ V , достижима из вершины v, v ∈ V , в графе G, но не достижима из нее в графе (V,E \ S), называется (u|v)-сечением графа G.

Сечение, которое не имеет собственных подмножеств, являющихся сечением, называется тупиковым.

Схема, моделирующая совершенную ДНФ ФАЛ f, называется канонической КС для этой ФАЛ.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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