Answers (почти все билеты на 22 страницы)

Ответы на вопросы по курсу «Основы Кибернетики»1. Определение Дизъюнктивных нормальных форм (ДНФ). Геометрическаяинтерпретация ДНФ. Совершенная ДНФ. Сложность ДНФ, минимальные ДНФ,кратчайшие ДНФ, функция Шеннона для ДНФ.Введем понятие степени:Х=Х, если=1;=Х, если=0;Рассмотрим конъюнкцию вида:Х1 1 * Х2 2 * Х3 3 ... Хn n – и назовем ее элементарнымпроизведением/конъюнкцией (ЭК).Опр. Дизъюнкция элементарных конъюнкций – ДНФ.Опр. Гиперкуб размерности n называют множество наборов длины n наборов из 0 и 1.Существует 2n наборов вида < 1, 2, ...

n >. Поставим в соответствие каждой конъюнкции(*) номер набора i (i = 0.. 2n – 1) и образуем дизъюнкцию всех конъюнкций:i(Х11* Х22* Х33n... Хn)Существует Теорема: любая функция алгебры логики (ФАЛ), зависящая от 'n' аргументов,может быть представлена в форме:F(Х1, Х2,... Хi... Хn)=Х11* Х2 2... ХiiF( 1,2,...i,Xi+1,...Xn)Из этой теоремы вытекает ряд важных следствий:1. Она дает возможность перейти от табличного задания функции к аналитическойформе и сделать обратный переход.2. Устанавливает так называемую функциональную полноту связок (базиса) " , , -",т.к. позволит построить в этом базисе произвольную ФАЛ от произвольного числааргументов.Примечание:1.

Если i n, то соответствующая форма функции называется дизъюнктивнойнормальной формой (ДНФ).2. Если i=n, то каноническая форма функции носит название совершенной ДНФ(СДНФ). Дизъюнкции берутся по тем наборам, на которых функцияf(X1,X2,...,Xn)=1Комментарий:Аналогичная теорема справедлива и для представления функции в конъюнктивнойнормальной форме (КНФ):f(Х1, Х2,..., Хn)=&( Х11Х22...Хi i) f( 1,2,...i,Xi+1...Xn)или при представлении в совершенной КНФ (СКНФ):f(Х1, Х2,…, Хn)=&( Х11Х22Х33...Хn n)где: & означает, что конъюнкции берется по тем наборам, на которыхf(Х1, Х2, ... Хn)=0.Переход от табличной формы функции к СДНФ или правило записи функции по единицам:1.

Выбрать те наборы аргументов, на которых f(Х1, Х2, ... Хn)=1.X1 Х2 f(Х1, Х2)2. Выписать все конъюнкции для этих наборов. Если при этом Хi имеет значение '1',0 0 0то этот множитель пишется в прямом виде, если '0', то с отрицанием.0 1 13. Все конъюнктивные члены соединить знаком дизъюнкции .1 0 1Пример:f(Х1, Х2)= Х1Х2 Х1Х2 Х1Х21 1 1Правило перехода от табличной формы задания функции к СКНФ или правило записи функции понулям.1.

Выбрать те наборы аргументов, на которых f(Х1, Х2, ... Хn)=0.X1 Х2 f(Х1, Х2)2.Если при этом Хi имеет значение '0', то остается без изменений. Если '1', то с0 0 10 1 01 0 11 1 0отрицанием.3. Все дизъюнктивные члены соединить знаком конъюнкции .Пример:f(Х1, Х2)= (Х1 Х2) ( Х1 Х2 )Опр. Сложность ДНФ – число букв (литералов). Длина ДНФ – число элем-хконъюнкций.Опр. ДНФ называется минимальной ДНФ если в ней минимальное кол-во букв, теминимальная сложность. При минимизации ДНФ стремятся получит форму в которойменьше букв чем в исходной, за счет построения таких элементарных произведений,которые своими единицами покрывают не одну единицу исходной функции, а несколько.По отношению к исходной ее называют сокращенной ДНФ. Кратчайшая ДНФ –имеющая минимальное число элем-х конъюнкций, те минимальную длину для заданнойфункции.Опр.

Функция Шеннона для ДНФ – пусть Φ - множество всех ФАЛ, а Σ(f) - множествовсех схем реализующих f ∈ Φ, тогда L(n) = Max(rang(Schema(f) : на Schema(f) достигаетсяmin(rang(Σ(f))))) для всевозможных f с n переменными.Геометрическая интерпретация: Рассмотрим наборы длины n(пусть n = 3 для простоты) из {0, 1}. Тогда можно изобразить этинаборы на n-мерном кубе. Все вершины куба можно занумеровать,так как показано на рисунке. Теперь рассмотрим набор γ=(γ1,γ2,...,γn)на множестве {0, 1, 2}. Пусть Гγ это множество таких вершинα=(α1,α2,...,αn) (каждая вершина – это набор длины n из {0, 1}), гдеαi=γi, для всех i для которых γi≠2. Число (n-r) равное числу «двоек» вγ называют размерностью грани, а число r рангом грани.2.

Тупиковая ДНФ. Сокращенная ДНФ и метод ее построения.Опр. Конституентой единицы функции называют функцию, принимающую значениеединицы только на одном наборе аргументов. Обычно конституенты единицы выражаютчерез произведение всех переменных, от которых зависит функция. СДНФ – дизъюнкцияконституент единицы.Опр. Ранг произведения – число букв, входящих в него.Опр. Собственной частью называется произведение, полученное путем отбрасыванияодной или нескольких переменных.

Например, Х1*Х2*Х3*Х4, где Х1, Х1*Х2, Х1*Х2*Х3 –некоторые собственные части.Опр. Если функция ϕ равна нулю на наборах аргументов, на которых обращается в нульфункция φ, то говорят, что ϕ является импликантой функции φ (т.е. нулей у импликантыне меньше, чем у функции).Опр. Простой импликантой называется произведение, которое само входит в выражениефункции, но никакая его собственная часть в выражение функции не входит.Опр. Максимальные грани – грани соответствующие простым импликантам.Опр. Ядровая точка (ЯТ) – точка содержащаяся только в одной максимальной грани.Ядровая грань (ЯГ) – грань содержащая ЯТ.

Ядро f – савокупность всех ЯГ.Опр. Сокращенной ДНФ называется дизъюнкция всех простых импликант. Ейсоответсвует покрытие всеми max гранями f.Опр. Тупиковой ДНФ назовем такую ДНФ что любая ДНФ полученная из нее путемудаления отдельных букв или ЭК уже не реализует функцию f. Из определения следуетчто тупиковая ДНФ задает тупиковое покрытие Nf максимальными гранями f.Проще это понять на множествах:покрытие множества - набор множеств, который в объединения содержит в себеуказанное множествосокр. ДНФ - это покрытие множества, каждая компонента которого не содержитцеликом другую компоненту.тупиковая ДНФ - покрытие, не содержащие подпокрытий, т.е. любое объединениекомпонент , не содержит в себе компоненты, не вошедшие в объединение.Пример: Пусть есть f(х1, х2, х3) f = 1 на {(001), (000), (100), (110)} тогда сокр. ДНФвыглядит так f = X 1 X 2 ∪ X 2 X 3 ∪ X 1 X 3 а тупиковая выглядит f = X 1 X 2 ∪ X 1 X 3 тетупиковая ДНФ является сокращенной, вот сокр.

не всегда является тупиковой.Теорема Квайна:Если в СДНФ в начале произвести все операции неполного склеивания, а затем всеоперации поглощения, то в результате получится сокращенная ДНФ.Опр. ДНФ Квайна – получается из сокращенной ДНФ удалением неядровых конъюнкийдля которых соотв им грани покрываются ядром.Спосбоы построения сокращенных ДНФКарта Карно (для ФАЛ: n = 4)Рассматриваются цилиндры и квадраты из «едениц» состоронами равные степени 2.

Выбираем по очереди цилиндры,смотрим какие переменные не меняют на его протяжении своизначения, их заносим в импликанту с отрицанием если ихзначение «0» и без отрицания если их значение «1». Дляданной картинки сокращенная ДНФ равнаf = X1 X 2 ∪ X 2 X 4 ∪ X 3 X1 ∪ X 4 X 3 ∪ X 2 X 4 ∪ X1 X 4 ∪ X 2 X 3Геометрическое построениеПусть есть функция f заданная своимизначениями: (0001, 1011, 1101, 1111) возьмем4хмерный куб и те вершины на которыхфункция обращается в «1» пометим. Послеэтого объеденим те вершины, которыеобразуют грани, и выпишем нерасширяемыеграни: (--11)(-11-)(1-0-)(-1-0)(1--1)(11--) тамгде стоит «0» берется отрицание переменной:f = x3 x 4 ∪ x 2 x3 ∪ x1 x3 ∪ x 2 x 4 ∪ x1 x 4 ∪ x1 x 2Через КНФВыписывается КНФ и раскрываются скобки используя:Тождество: X 1 * X 2 ∪ X 1 * X 3 = X 1 * ( X 2 ∪ X 3 )Тождество: X 1 * X 2 ∪ X 1 * X 3 = X 1 * X 2 ∪ X 1 * X 3 ∪ X 2 * X 33.

ДНФ типа суммы тупиковых. Критерий вхождения конъюнкции в ДНФ типасуммы тупиковых. Алгоритм построения всех тупиковых покрытий матрицы.Опр. ДНФ Σ тупиковых – дизъюнкция всех тупиковых ДНФ с поледующимприведением. ДНФ Σ тупиковых получается из сокращенной ДНФ путем выбрасываниянекоторых элем-х конъюнкций, до тех пор пока ДНФ не станет неприводимой.Опр. Пучком Пα(f) назовем множество всех проходящих через α максимальных граней f,а точку α назовем регулярной точкой f, если найдется такая точка β: β ∈ Nf для которойимеет место строгое включение Пβ(f) ⊂ Пα(f). Грань Гγ нызовем регулярной граньюесли все её точки регулярны.Опр.

Говорят что набор α ≤ β, если выполняется αi ≤ βi для любого номера i. Говорят чтоα < β если выполняется αi ≤ βi и ∃j: αj≠βj.Опр. Функция f(α) называется монотонной если f(α) ≤ f(β), для любых α,β: α ≤ β.Функция f(α) называется монотонной по переменной хi если f(α) ≤ f(β), для любыхсоседних по хi наборов α,β: α ≤ β. Из определения следует, что если функция монотонна,то она монотонна по всем своим переменным и наоборот.Утверждение Если f(α) монотонно зависит от хi, то ни одна из ее простых импикант неможет содержать отрицание хi. Следствие Монотонноая функция не содержит отрицаниев своей ДНФ.Таблица Квайна.

Строки – простые импликанты в еесокращенной ДНФ. Столбцы соответствуют наборам накоторых функция обращается в еденицу. На пересечении iстроки и j столбца ставят единицу если данная импликантаобращается в еденицу на данном наборе.Пусть функция выполняется на наборах{100,110,010,011,001,101} иf = x1 x3 ∪ x2 x3 ∪ x2 x1 ∪ x3 x1 ∪ x3 x2 ∪ x1 x2 , тогдасоответствующая таблица Квайна показана слева.Задача для данной матрицы выделить все тупиковые подпокрытия. Покрытие строк – вкаждом столбце есть хотя бы одна единица.

Тупиковое покрытие – покрытие из которогоничего нельзя выкинуть.Алгоритм построения ДНФ ΣТ: функция покрытия матрицы задается КНФ вида:f =∧ ( ∨ К i ) , после раскрытия скобок получается ДНФ ΣТ.по всем столбцам j i: M < i, j> = 14. ДНФ суммы минимальных и алгоритмические трудности ее построения.Опр. ДНФ называется минимальной ДНФ если в ней минимальное кол-во букв, теминимальная сложность. Кратчайшая ДНФ – имеющая минимальное число элем-хконъюнкций, те минимальную длину для заданной функции.Опр.

ДНФ суммы минимальных – дизъюнкция всех минимальных ДНФ.Опр. Локальный алгоритм – алгоритм в котором преобразование граней зависит от«состояния» «окрестности» заданного порядка.Теорема Журавлева. ДНФ Σmin не строится в классе локальных алгоритмов.Док-во: предположим что строится, и существует локальный алгоритм, которому на входпоступает 2х диагональная матрица Квайна, (с «1» на диагоналях) то на втором шагеалгоритм остановится т.к.