Ответы: Контрольные работы (2014)

Распознанный текст из изображения:

~ \ 1. Определение покрытия матрицы М, М Е В"", понятие тупикового и минимального покрытия. Таблица Квайна ФАЛ ~; соотношения между тупиковыми ДНФ ФАЛ ~ и покрытиями ее редуцированной таблицы Квайна. 2. Определение протыкающего множества для граней заданного ранга в единичном кубе и утвержде-

ние о верхней оценке его мощности (вывести эту оценку из оценки длины градиентного покрытия). 3. Вероятностная модель ФАЛ из Р~(п) и связанные с ней случайные величины, которые характеризуют длину ее совершенной ДНФ, а также длину ДНФ, получающейся в результате разложения этои ФАЛ по БП х~,...,х„. Математические ожидания и дисперсии указанных случайных величин; полученные с их помощью оценки длин упомянутых ДНФ для почти всех ФАЛ. 4. Определение функции Шеннона Л„„~(п) для длины сокращенной ДНФ у ФАЛ от п БП, ее ниж.-- — няя оценка и пример симметрической ФАЛ, на которой эта оценка достигается (с обоснованием — — указанной достижимости). 5. Определение теста для отделимой по столбцам матритпл М М Е Вя"

, и цели контроля 3ч, где Л— ) — множество неупорядоченных пар, состоящих из различных чисел —. ~1, ],

—.~ езка ~, я], понятие тупикового и минимального теста для (М, ЛГ). Определение ФАЛ Р(у~,..., у„) теста для (М, Л/), ее свойства и связь с тупиковымн тестами. :;4 1. На основе ФАЛ покрытия для редуцированной таблицы Квайна построить все тупиковые, минимальные и кратчайшие ДНФ функции ДУ4), заданной сокращенной ДНФ:

РсокрЦ) = хзжз ~l хзж4 Ч Х1х4 ~ ззхзх4 Ч х1жзх4 Ч хзжзх4 ~ з1~2~3. + 2. В контактной схеме возможна одна из следующих четырех неисправностей: 1) обрыв контактов ж1,. 2) замыкание контактов зз, 3) обрыв контактов Уз, 4) замыкание контактов х1, У1,

(а

Построить все тупиковые диагностические тесты,

Распознанный текст из изображения:

Вариант 1ОЗ

Группа

Студент .

Номер зачетной книжки

-Осокр® — х1х2 Ч х1х2 Ч х2х4 / х2хз Ч х1х4 ~/ х1хз Ч хзх4

2. В контактной схеме возможна одна из следующих четырех неисправностей:

1) замыкание контактов х1,

2) замыкание контактов х1,'

3) обрыв контактов х2, хз,

а

4) обрыв контактов х1, хз.

Построить все тупиковые диагностические тесты.

1. На основе ФАЛ покрытия для редуцированной таблицы Квайна построить все тупиковые, минимальные и кратчайшие ДНФ функции ~(х4), заданной сокращенной ДНФ:

Распознанный текст из изображения:

Группа

Студент

Номер зачетной книжки

Вариант 1ОЗ

1. Линейная зависимость ФАЛ от одной или всех БП и особенности ее импликант (с обоснованием); монотонная зависимость ФАЛ от одной или всех БП и особенности ее простых импликант (с обоснованием);

2. Градиентный алгоритм построения покрытия матрицы. Верхняя оценка доли тех столбцов матрицы М, М е В"", которые остались не покрытыми после 1 шагов применения градиентного алгоритма, если в каждом столбце матрицы М имеется не меньше, чем ~. р единиц, где О ( -~ < 1, и ее обоснование.

3. Определение функции Шеннона Л(п) для длины кратчайших ДНФ, реализующих ФАЛ от д БП. Поведение функции Шеннона Л(л,) (идея получения верхней оценки и пример ФАЛ, на которой достигается нижняя оценка, с обоснованием этой достижимости).

4. Дать определение окрестности порядка г, г = О, 1,..., максимальной грани Жь- ФАЛ ~. Указать (с обоснованием) порядок такой окрестности этой грани, знание которой позволяет однозначно ответить на вопрос о вхождении Хк в ДНФ Г~Т и ДНФ ЕТ ФАЛ ~.

5. Определение диагностического теста отделимой по столбцам матрицы М, М е В"", понятие тупикового и минимального диагностического теста. Формулировка утверждения об оценках длины диагностического теста для почти всех матриц указанного вида, где О = р(8) и я = 1, 2,....

Распознанный текст из изображения:

Вариант

Группа

Студент

Номер зачетной книжки

1. На основе ФАЛ покрытия для редуцированной таблицы Квайна построить все тупиковые, минимальные и кратчайшие ДНФ функции ~(х'), заданной сокращенной ДНФ:

Осокр® У2Уз Ч Узх4 Ч У2У4 Ч У1т4 ~/ х1х2х4 Ч х1хзх4 Ч х1х2хъ.

2. В контактной схеме возможна одна из следующих четырех неисправностей:

1) замыкание контактов х1,

2) обрыв контактов У2,

3) замыкание контактов хз,

4) обрыв контактов т1, Т1.

Построить все тупиковые диагностические тесты.

х,

Распознанный текст из изображения:

Студент

Номер зачетной книжки

Группа Вариант 9О2

1. Определение монотонной ФАЛ и ее «нижних» единиц. Утверждение о сокращенной ДНФ монотонной ФАЛ и обоснование единственности ее тупиковой ДНФ.

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

3. Определение длины Л® и ранга В® для ДНФ, реализующих ФАЛ ~. Точная и развернутая формулировка утверждения о верхней оценке значений функционалов Л® и В® для почти всех ФАЛ ~ от и БП, идея его доказательства.

4. Определение функций Шеннона т(п) и р(п) для числа тупиковых и числа минимальных ДНФ у ФАЛ от и БП, их нижние оценки и пример ФАЛ, на которой указанные оценки достигаются (с обоснованием этой достижимости).

5. Определение теста для отделимой по столбцам матрицы М, М е В"", и цели контроля Л/, где Л~— множество неупорядоченных пар, состоящих из различных чисел отрезка [1, 8~, понятие тупикового и минимального теста для (М,Л~). Сведение задачи о построении теста (тупикового теста) для (М,Л ) к задаче о построении покрытия (тупикового покрытия) для модифицированной матрицы М.

Распознанный текст из изображения:

Вариант ЗОЗ

Группа

Студент

Номер зачетной книжки

1. Построить минимальную (1, 1) — КС для ФАЛ ~, заданной равенством

~(Х1,Х2,ХЗ, Х4,ХЗ) = (Х1 ~/Х2) Я ХЗХ4.

2. С помощью метода каскадов, последовательно разлагая реализуемые ФАЛ по х1, х2, хз, х4, построить (1, 2) — КС Е для системы ФАЛ Г = ф, Я и СФЭ Я для ФАЛ ~1, где ~1 — — (1001 0100 0100 0001),

~2 = Х2(ХЗ ~В Х4) / Х2Х4(Х1 ~ ХЗ).

3. Применяя методы самокоррекции однородных подсхем к т-схеме, которая моделирует формулу, подобную формуле (х1х2 ~/ (хз ~l хб)хз)(х2х4 Ч хзхз ~/ х4хб), построить эквивалентную ей (1,0)- самокорректирующуюся КС сложности не больше, чем 19.

4. Установить асимптотику сложности реализации схемами из функциональных элементов самой сложной из тех ФАЛ ~(х1,..., х„), и > 4, для которых выполняется неравенство ~(х1,..., х„) <

(Х1 Я Х2) (ХЗ Ы Х4) .

Распознанный текст из изображения:

Студент

Номер зачетной книжки

Группа

Вариант ®З

1. Определение сложности Ьс® ФАЛ ~ в классе СФЭ. Формулировка утверждения о нижней оценке

сложности реализации ФАЛ ~ в классе СФЭ, получаемой с помощью "забивания" константами

одной из ее БП. Мультиплексорная ФАЛ р„порядка и и получение с помощью этого утверждения—

нижней оценки для ее сложности Ьс(р„). Верхние оценки даййой сложности и ее асимптотическое

поведение.

2. Операция присоединения одного или двух противоположных контактов к выходам КС и ее свой-

ства, определение каскадной КС. Формулировка утверждения о переходе от заданной каскадной КС к инверсной каскадной КС и идея его доказательства.

3. Определение функции Шеннона Ьс®(п)) и 1РЯ(п)) для сложности реализации ФАЛ из класса Я

схемами из функциональных элементов и контактными схемами соответственно. Формулировка утверждения о нижней мощностной оценке этих функций. Определение инвариантного класса ФАЛ и его мощностной последовательности. Формулировка" утверждения о поведении функции Шеннна для сложности реализации ФАЛ из инвариантного класса Я схемами из функциойальйых элементов (с "расшифровкой" всех используемых ооозйачений).

4. Определение КС, корректирующей р обрывов и О замыканий, сложности реализации ФАЛ в классе таких схем и соответствующей функции Шеннона ХР (и). Построение КС корректирующих

Ьч)

1 обрыв (1 замыкаие) на основе самокоррекции в подсхемах ("звездах") из однотипных контактов, формулировка утверждения о сложности.полученных,.КС,.и.идея его. доказательства. Утверждение об асимптотическом поведении Функций Шеннона Д'~, ®(и) и й~~, ~п~, его обоснование.

Распознанный текст из изображения:

Группа .. Вариант 4О1

Студент

Номер зачетной книжки

1. Построить минимальную (1, 1) — КС для ФАЛ ~, заданной равенством

~(Х1) Х2, ХЗ, Х4, Х5) = (Х1 / Х2 Ч ХЗ)Х4 Ч (Х1 Ч Х2 Ч ХЗ)Х5.

2. С помощью метода каскадов, последовательно разлагая реализуемые ФАЛ по х1, х2, хз, х4, построить (1, 2) — КС Е для системы ФАЛ Г = ®, Я и СФЭ Я для ФАЛ ~1, где ~1 — — (0110 1000 1000 0101), ,~2 = Х1Х2(ХЗ Я Х4) '/ Х1Х2Х4.

3. Применяя методы самокоррекции однородных подсхем к 7т-схеме, которая моделирует формулу, подобную формуле (х1х2х5 ~l х2(х1 ч х4)) (х1 ~/ хзх5(х2 ч х4) ), построить эквивалентную ей (О, 1)- самокорректирующуюся КС сложности не больше, чем 19.

4. Установить асимптотику сложности реализации схемами из функциональных элементов самой сложной из тех ФАЛ ~(х1,..., х ), и > 1, которые на любой паре противоположных наборов принимают одинаковые значения.

Распознанный текст из изображения:

Группа

Студент

Номер зачетной книжки

Вариант 4О1

1. Определение сложности Ь~~(Р) системы ФАЛ Х' = ®,..., ~ ) в классе СФЭ над базисом Б и формулировка утверждения о простейшей нижней оценке этой сложности. Универсальная система ФАЛ Р2(п) порядка и и нижняя оценка указанного вида для ее сложности. Верхняя оценка этой сложности и ее обоснование.

2. Определение КС, корректирующей р обрывов и О замыканий, сложности реализации ФАЛ в классе таких схем. Построение КС, корректирующих р обрывов и д замыканий с помощью дублирования, формулировка утверждения о верхней оценке их сложности и идея его доказательства.

3. Определение функции Шеннона Ь~(п) (со всеми необходимыми "промежуточными" понятиями). Нижняя мощностная оценка этой функции и ее обоснование. Верхняя оценка данной функции Шеннона, получаемая с помощью моделирования совершенной ДНФ с использованием контактного дерева. Построить с помощью моделирования совершенной ДНФ на основе контактного дерева формулу (Тг — схему), реализующую ФАЛ ~(х1, х2, хз), где й~ = (0111 0110).

4. Утверждение о сложности КС, получаемых асимптотически наилучшим методом синтеза, и вытекающая из него верхняя оценка соответствующей функции Шеннона. Описание разложения (представления) ФАЛ, на котором основано доказательство этого утверждения, и структуры соответствующей схемы с указанием основной по сложности подсхемы.

Распознанный текст из изображения:

Вариант ЗОО

Студент

Номер зачетной книжки

Группа

1. Построить минимальную (1, 1) — КС для ФАЛ ~, заданной равенством

,1 (Х1~ Х2~ ХЗ, Х4) = (Х1 9 Х2)ХЗХ4 Ч Х1Х2 ~l Х1Х2.

2. С помощью метода каскадов, последовательно разлагая реализуемые ФАЛ по х1, х2, хз, х4, построить (1, 2) — КС Е для системы ФАЛ Г = ®, Я и СФЭ Я для ФАЛ Л, где ~1 — — (1001 0110 1001 0111),

12 = Х1(ХЗ Ч Х4) Ч Х1(Х2 Я ХЗ Я Х4).

3. Применяя методы самокоррекции однородных подсхем к тг-схеме, которая моделирует формулу, подобную формуле ((х1 ~/ х4)хзхз ~l х1х2)(х1хб Ч х2 ~l хзх4), построить эквивалентную ей (1, О)- самокорректирующуюся КС сложности не больше, чем 19.

4. Установить асимптотику сложности реализации схемами из функциональных элементов самой сложной из тех ФАЛ ~(х1,...,х„), где и > 1, которые равны 1 на всех наборах с нечетным числом единиц.

Распознанный текст из изображения:

Студент

Номер зачетной книжки

Группа

Вариант З®

1. Определение сложности Ьк(~) ФАЛ ~ в классе КС и формулировка утверждения о простейшей нижней оценке этой сложности. Линейная ФАЛ порядка и и нижняя оценка указанного вида для ее сложности. Верхняя оценка этой сложности получаемая на основе схемы Кардо, и структура данной схемы. 2. Определение ДУМ; описание ДУМ порядка т и ранга О, связанного с разбиением куба В на р непустых подмножеств. Описание стандартного ДУМ порядка т и высоты 8, его ранг и мощность. Построить таблицу значений ФАЛ, образующих стандартное ДУМ порядка 3 и высоты 3. 3. Определение функции Шеннона Ьс(п) (со всеми необходимыми "промежуточными" понятиями) Нижняя мощностная оценка этой функции и ее обоснование. Верхняя-оценка — данной-функции Шенйона, получаем я методом еннона. остроить с помощью метода Шеннона, разлагая ФАЛ ~(т~. т2, тз)., где лху = ~0001 0111) по БП х1, т2, реализующую ее СФЭ. 4. Утверждение о сложности формул, получаемых асимптотически наилучшим методом синтеза, и вытекающая из него верхняя оценка соответствующей функции Шеннона; поведение функции Шеннона для глубины ФАЛ. Описание разложения (представления) ФАЛ, на котором основано доказательство этого утверждения, и структуры соответствующей формулы.

в . Ю

Распознанный текст из изображения:

Вариант 5О6

Студент

Номер зачетной книжки

Группа

1. Построить минимальную (1, 1) — КС для ФАЛ ~, заданной равенством

,1 (Х1) Х2, ХЗ, Х4) = Х1Х2ХЗХ4 Ч Х1Х2ХЗХ4 Ч Х1Х2ХЗХ4 Ч Х1Х2ХЗХ4.

2. С помощью метода каскадов, последовательно разлагая реализуемые ФАЛ по Х1, Х2, хз, Х4, построить (1, 2) — КС Е для системы ФАЛ Е = ®, Я и СФЭ Я для ФАЛ ~1, где ~1 = (0110 1001 1010 0000),

12 = Х1Х2(ХЗ ® Х4) ~/Х1ХЗХ4.

3. Применяя методы самокоррекции однородных подсхем к т-схеме, которая моделирует формулу, подобную формуле (х1Х2 ~/ хз)(Х2х5 ~/ Х4)(хзх4Х5 ~/ х1 ~/ хб), построить эквивалентную ей (О, 1)- самокорректирующуюся КС сложности не больше, чем 19.

4. Установить асимптотику сложности реализации схемами из функциональных элементов самой сложной из тех ФАЛ ~(Х1,...,х„), п > 3, для которых ФАЛ ~(х1,Х2, о.з,..., о.„) при любых (~73,..., ~т„) является одной из ФАЛ Х1, Х2, Х1 х2, Х1 9 Х2.

Распознанный текст из изображения:

Группа

Студент

Номер зачетной книжки

Вариант 506

1. Определение сложности 1Р(Г) системы ФАЛ Г = ®,..., ~ ) в классе КС и формулировка ~тверждения о (нетривиальной) нижней оценке этой сложности. Дизъюнктивный дешифратор У„порядка и и получение с помощью указанного утверждения нижней оценки его сложности Лк(1„).

Верхние оценки данной сложности и ее асимптотическое поведение.

2. Определение т — регулярного множества наборов куба В~, О ) т, от БП т1,...,х и его свойства. Формулировка утверждения о моделировании ФАЛ с помощью БП или их отрицаний на компонентах т — регулярного разбиения куба В~. Построить 2 — регулярное разбиение куба В от БП х1, х2, хз, т4 на каждой компоненте которого ФАЛ У1 У2 и х2 — ~ х1 совпадают с одной из ФАЛ хз, хз, х4, х4.

3. Определение функции Шеннона Л~(п) (со всеми необходимыми "промежуточными" понятиями). Нижняя мощностная оценка этой функции и ее обосноада Иа Церхняя оценка данной функции Шеннона, получаемая методом Шеннона. Построить с помощью метода Шеннона, разлагая ФАЛ ~(х1, т2, тз), где й р = (1000 1110), по БП х1, х2, реализующую ее (1, 1) — КС.

4. Утверждение о сложности СФЭ, получаемых асимптотически наилучшим методом синтеза, и вытекающая из него верхняя оценка соответствующей функции Шеннона. Описание разложения (представления) ФАЛ, на котором основано доказательство этого утверждения, и структуры получаемой схемы с указанием основного по сложности блока.

Распознанный текст из изображения:

Вариант З09

Группа

Студент

Номер зачетной книжки

т =(1,:(хдс1Х2)охз=хдо(х2охз)~ое(Й1~I)), т =(1,:хдох2=Х2охд~ое(~1'1/)),

т = (1О: Хд О Хд — — Хд ~ О Е (Й1Ч) )1 т = (1~~,. 'Хд(Х2 дl ХЗ) = Хдх2 Ч ХдхЗ )1

т = (1„: хд — — хд, 1~,. Хдх2 = хд ЧХ21 1,,: хд ЧХ2 = хдх2) т = (1: хд Чхдх2 = хд ),

М М.=, . М. — — М, — — п г и,

т = ( ЙО2.. Хд(Х2х2) = х2х21 йд,2,. хд(х2 Ч х2) = хд, йо~. Хд Ч (Х2х2) = хд, 11~2. хд Ч (Х2 ~l х2) = Х2 Ч х2).

пк пк. — — пк. — пк., — пк.

1 2 1 2

Х1 Х2 Х2 Х1

1о: 1о — — ~2 — 1о — — ~2

1о: 1о — — — о2 1о о2

(„,) 1

Хт

1о — — о2 1

1. С помощью расширенной системы основных тождеств т"" построить ЭП для формул У и ~:

~/ = (Х12 3) ' (ХЗ ~/ (Х12 2 Ч Т1Х2 ~/ ТЗ) (12 2 Ч Ж1)) .

У = Хдж2 Ч (т2 ~/ (Хд Ч УЗ) (ХЗ Ч тд)),

2. С помощью системы основных тождеств т построить ЭП для КС Г и Е", указать (с обоснованием) минимальное г, при котором данное ЭП возможно с использованием тождеств 11 — 1з, 16,..., 1

(1) (2)

Упрощенный вариант задачи: преобразовать КС Г описанным способом в КС, все контакты которой лежат на цепях, соединяющих различные полюса и не имеющих общих внутренних вершин.

Распознанный текст из изображения:

Группа

Студент

Номер зачетной книжки

Вариант 1О9

1. Определение подформулы данной формулы, принцип эквивалентной замены. Определение тождества для формул и его подстановки; описание указанной подстановки одного из основных тождеств, результатом которой является тождество х1х~(хз ~/ х4) = х1х2хз ~/ х1х2х4. Описание однократного и многократного ЭП формул с помощью тождеств, понятие полной системы тождеств для ЭП формул в заданном базисе.

2. Тождества ветвления и снятия, приведение с их помощью СФЭ к системе формул. Привести с

помощью указанных тождеств к системе формул СФЭ из одного ФЭ Й, выход которого имеет пометки ~1, з2, ~з.

3. Тождества перехода от формул в одном базисе к формулам в другом базисе. Утверждение о моделировании ЭП формул в различных базисах (теорема перехода) и идея его доказательства.

4. Канонический вид КС из неориентированных контактов с неразделенными полюсами. Утверждение о приведении КС к каноническому виду с помощью основных ~обобщенных) тождеств и его основные этапы; идея устранения тех внутренних вершин КС, которые не являются внутренними вершинами канонических цепочек. Вывод из данного утверждения утверждения о полноте системы основных тождеств.

Распознанный текст из изображения:

Вариант 6О6

Группа

Студент

Номер зачетной книжки

т" = ( 8",: (х1 2 х2) о хз = х1 о (х2 о хз) ~ 12 Е (Й1Ч) ), т = ( 8,: х1 о х2 = х2 о х1 ( о Е (Йо 'I) )1

т = ( 1„: х1 с1 х1 = х1 ! ~ Е (Й1 1/) ), т = ( 1~~, . 'х1(х2 1l хз) = х1Х2 ~l х1хз ),

м ~ м.= м. —, —, м., — —,1 п г п.

т = (1: х1 — — х1, 1~,. х1х2 = х1Чх21 1,,: х1~/х2 =х1х2) т = (1:х1Чх1х2 =х1)1

т = ( 1д~,. х1(х2х2) = х2х21 112.. х1(х2 Ч х2) = х1, 1О~. х1 Ч (х2х2) = х1, 11~: х1 Ч (х2Ч х2) = х2 М х2 ).

1 2 1 2

12: 1о — — о2 1о — — ~2

:1:1

1о: 1о — — о2 — 1о о2

(„„) 1

1о — *о2 — 1

1. С помощью расширенной системы основных тождеств т"" построить ЭП для формул У' и 6:

.У' = ~(Х1 1/ ХЗХ2) / ХЗ) (Х1ХЗ 1/ Х2) ) Д вЂ” (Х1 1/ (ХЗХ2 1/ Х2ХЗ)) ' (Х1ХЗ(Х1 1/ Х2 Ч ХЗ) 1/ Х2) .

2. С помощью системы основных тождеств т построить ЭП для КС Г и Г', указать (с обоснованием) минимальное г, при котором данное ЭП возможно с использованием тождеств 11 — 1з, 86,..., 16 .

(1) (2)

Упрощенный вариант задачи: преобразовать КС Е' описанным способом в КС, все контакты которой лежат на цепях, соединяющих различные полюса и не имеющих общих внутренних вершин.

3

Распознанный текст из изображения:

Студент

Номер зачетной книжки

Группа Вариант

1. Определение подсхемы данной СФЭ, принцип эквивалентной замены. Определение тождества для

СФЭ и его полстановкип Моделирование формульных тождеств в классе СФЭ на примере ф~.

Описание однократного и многократного ЭП СФЭ с помощью тождеств, понятие полной системы

тождеств для ЭП СФЭ.

2 Описать ЭП произвольной ДНФ, реализующей ФАЛ ~(х1,...,х„) ф О, в совершенную ДНФ

ФАЛ ~, указав какие группы основных тождеств и каким образом при этом используются.

3. Обобщенное тождество ~ для ЭП КС, идея его вывода из основных или других обобщенных

(и)

тождеств. Описать тот этап приведения КС от БП х1,..., х„к каноническому" виду, на котором

используется данное тождество, и указать характер этого использования.

4. Суммарное цикломатическое число КС и характер его изменения при ЭП КС на базе различных

основных тождеств. Обоснование отсутствия конечной полной подсистемы в системе,„.основных

тождеств и отсутствия КПСТ в классе всех КС.

Распознанный текст из изображения:

Вариант ОО5

Группа

Студент

Номер зачетной книжки

Т =(1а.'(Х1ОХ2)ОХЗ=хдО(Х2ОХД)~ОЕ(Й1Ч))1 Х =(1о.'Х10Х2=Х2Охд~О~(~1~))1

Т = (~„: Хд О Хд = Хд ~ О Е (8Е1Ч) )1 Т = (8~,, . 'Хд(Х2 Ч Х2) = Хдх2 Ч Хдхд )1

Т = (Й:хд =Х1, 'Йц~.'Х1Х2 =Х1ЧХ21 1сс,'Х1ЧХ2 =Х1Х2) T — (Й:Х1ЧХ1Х2 =Х111

т" = ( йд~,. Хд(Х2х2) = Х2Х2, йд~. хд(Х2 ~/ Х2) = хд, Йо~ ' хд ~l (Х2Х2) = хд, йд~. Хд 'I (Х2 'I Х2) = х2 Ч х2 ).

° г Я

1

Х1

1с — — ~2 1о — — о2

1с — — ~2 — 1о о2

1т,)

хо

О1

1о — -о2 1

1. С помощью расширенной системы основных тождеств У"" построить ЭП для формул У и 0:

У = (хзЧ(хд~/х2)(х2Чтд)) (ха~/(хдх2 Ч хдт2))1 0 = (хдх2хз) (хзЧхд~lх2) (х2Ч(хд ~/ хз)(хд Ч хз)).

Х1

1о — — о2

Х2

хд Х2

2. С помощью системы основных тождеств т построить ЭП для КС Г и Г', указать (с обоснованием) минимальное г, при котором данное ЭП возможно с использованием тождеств 11 — 1д, 16,..., 16 .

11) И

Упрощенный вариант задачи: преобразовать КС Е' описанным способом в КС, все контакты которой лежат на цепях, соединяющих различные полюса и не имеющих общих внутренних вершин.

Распознанный текст из изображения:

Группа

Студент

Номер зачетной книжки

Вариант ОО5

1. Определение языка и описание языка ВЫПОЛНИМОСТЬ. Полиномиальная сводимость языков,

определение классов Р и ИР. Понятие ИР-трудного и ИР-полного языков, формулировка теоремы

Кука.

2. Описать ЭП произвольной формулы стандартного базиса в формулу, которая представляет собой

конъюнкцию букв или дизъюнкцию таких конъюнкций, указав какие группы основных тождеств

и каким образом при этом используются.

3. Обощенное тождество 14 для ЭП КС, )идея его вывода из основных или других обобщенных

(и)

тождеств. Описать тот этап приведения КС от БП х1,..., х„к каноническому виду, на котором

используется данное тождество, и указать характер этого использования.

4. Канонический вид формул в базисе Бв — — (х1 х2, х1 Ч х2, У1) и этапы ЭП на основе системы г„„,

которое приводит произвольную формулу над Бо к каноническому виду, с указанием особенностей

формул, получаемых на каждом из них. Определение полной системы тождеств и утверждение о

полноте системы основных тождеств, идея его доказательства.

Распознанный текст из изображения:

Студент

Номер зачетной книжки

Группа

Вариант

1. Тождество обобщенного «склеивания», определение расширения и строгого расширения ДНФ. Критерий сокращенности ДНФ.

2. Определение ядровой точки, ядровой грани и ядра ФАЛ; ДНФ о~, критерий вхождения в нее простых импликант и идея его доказательства, ДНФ Квайна.

3. Опираясь на следчощую таблип~ Квайна ФАЛ Х,

указать ~с необходимыми ссылками на соответствующие определения и утверждения) все ядровые и регулярные точки этой ФАЛ, все ее ядровые и регулярные грани, ДНФ ЙТ и ДНФ ЕТ, а также ДНФ Квайна.

4. Построить с помощью карты Карно сокращенную ДНФ ФАЛ Л~~.-г столбец значений которой имеет вид Ь = ' 0100 ~11~ ~ ~~~~ ~~Г10',

Распознанный текст из изображения:

Студент

Группа

Вариант

Номер зачетной книжки

1. Описание алгоритма построения сокращенной ДНФ ФАЛ из какой-либо ДНФ (КНФ) этой ФАЛ,

2. Определение пучка, регулярной точки и регулярной грани. ФАЛ;.. ДНФ ~~ и критерий вхождения в нее простых импликант, идеи доказательства его необходимости и достаточности.

3, Опираясь на следующую таблицу Квайна ФАЛ У,

указать (с необходимымй ссылками на соответствующие определения и утверждения) все ядровые и регулярные' точки этой ФАЛ, все ее ядровые и регулярные грани, ДНФ ИТ и ДНФ ХТ, а также ДНФ Квайна.

° 4. Построить с помощью карты Карно сокращенную ДНФ ФАЛ .Л~ .~' ~' г~», столбец значений которой имеет вид «7

Распознанный текст из изображения:

Студент

Номер зачетной книжки

Группа

Вариант

1. Индуктивное определение формулы-слова в базисе (х~ ~/ х2, х~ — х2, х~) и реализуемой ею ФАЛ, построение дерева и квазидерева, соответствующего данной формуле.

2. Определение эквивалентных КС. Утверждение о верхней оценке числа попарно неэквивалентных (1, 1)-КС от БП т~,..., х имеющих сложность не больше, чем Л, и аналогичная оценка для КС, состоящих из замыкающих контактов.

3. Определение подобных формул, формул с поднятыми отрицаниями и их альтернирования. Утверждение об оптимизации подобных формул по глубине, идея его доказательства.

4. Для ДНФ т~ ~/ т2 ~/ т4х5 Ч хб '/ хз ~/ х4У7 Ч х5Г8 выписать (с расстановкой всех скобок) подобную

ей формулу минимальной глубины (минимальность, по возможности, обосновать).

5. Промоделировать г-схемой формулу (т~к2 Ч х~У2) (х2 Ч тз) ~/ т~х2хз.

Распознанный текст из изображения:

Группа

Студент

Номер зачетной книжки

Вариант 404

1. Определение КС с разделенными полюсами как помеченного графа, определение ФАЛ проводимости между ее вершинами и матрицы ФАЛ, реализуемой этой КС. Представление ФАЛ, реализуемой (1, 1)-КС, в виде ДНФ, связанной с системой цепей, соединяющих полюса КС.

2. Определение эквивалентных т-схем, утверждение о верхней оценке числа попарно не эквивалентных 7г-схем от БП х1,..., х„сложности не более, чем Л, и аналогичная оценка для ~т-схем, состоящих из размыкающих контактов.

3. Определение основных функционалов сложности формул и СФЭ (ранг, сложность, глубина), их содержательный смысл. Утверждение о соотношениях между сложностью, рангом и глубиной формул в стандартном базисе, идея его доказательства. Формулировка аналогичного утверждения для СФЭ.

4. Для ДНФ х1х2 ~/ хз ~l х4хб ~/ т5 ~/ х1У~х7УЗ выписать (с расстановкой всех скобок) подобную ей

формулу минимальной глубины (минимальность, по возможности, обосновать).

5. Промоделировать 7г-схемои формулу ((т1 ~/ У2) (У1 '/ жз) ~/ х1х2хз) (У4х5 ~l ж~х; ~l Т~х~).

Распознанный текст из изображения:

у Лая

еииа) аее кароаь$е и ре$ ~лмрйые и>чу

нце грани, ДИФ ОТ и ДНФ ЕТ. а также,Д4Ф Квайиа~„тЪфа у 1

4, Поетроитт, е иомошью карты Карно еокраайииум Д ' 'о т

Й~ = ~ 0100 1111 11101610)

' етолбец значений ко горой имеет аид Ь = ~

г Р'и

с',~

ф

Распознанный текст из изображения:

л И;/'г~ Студент Ж!...'.""~ б4~' -~ .: ' .... Грчпиа ' ' Вариант 203 Номер зачетной книжки Р '~У (~ '~"-'." + .... с,, С Определение сдожиос|и Ег '' (1 фдЛ ~ а классе СФЭ. Формулировка утверждения о нижней оценке сдожпостн реалнзацин ФАЛ .Г а классе СФЭ, получаемой с помоаью "заоивання" констан™н ' одной из ее БП. Мудьгнплексорна» ФАЛ р«порядка и и получение с помощью зтого утвержденна

й« . « ' ж С'1~~~.«~ ««««е Й м~««~ «

поведение. «м 2. Операцня прцсоедцнеущ одЛогц или двух пооти оп т нт в в дмкснеесвой став.' оп(~еде»ение каскадной кс, Формул~реала утверждения о. цеРехо«де от, заданной каскадной КС к нпасрсйой каскадной КС н идея его доказательства;,,: . « .:, ' — 3. Определение функции шеннона ь я и) н х, я(п -4ц)ляджййфьхн;:Рвдюе~ацнн Флл нз класса ~ схемами из Функциональных здементов, и найт~;.;:~~:."соответственно. Форму про~~а утверждения о нижней мо остной:о' " " '','з«га()~::;: '" """ ' .':,''.:.: "" "'"" ' ' ' класса ФАЛ и его мощностной,последе "'' ''' """" '""'-"''. "' """."'""'""''йЭ~Г.=:.',""«"" '"ения о 'цоведенни Шенина для сложности: " ' ' '" ' ',;:, '".: щ "« "'""" "'""": ":;-'~л«ясхе«а': а~емвми нз кцнонааьных злементов (с "раЕЭпнфров)рхй";:::~ц'"!!,,' „",.;..'"„,; .:,;.;~4йййМйй«в« ° 'О - ~~~:::,,- "":"':-"-"-':: '-'' - '"' ') '„"~ф~~~-;",:~"""':,"~~й«';::щ~~~~н~~~тн реализации ФАЛ в клас-

, '""~я"."'~""';щ )."й$йй~ ф~Мйф~ффВ~йх:,(«'ЗВВздах") 'нз Однотипных контактов,

':н, ' о . Утверждение

,,ЬМ',-'А(г,:ау~ё н«,:. ~ад~(и), его обоснование. ,-,-,,",~~;:.::;;-':.:„"-::::,".:::::."-::,::::~".':~'':~~:. -: -,~-:: у~.-г ~ ~Г~

~х Д~~р~ЛЖ А, " '~~~!~~'.:,:." ' '.ф:ф '.'~х' '~, В К.4 юГ г«с' Р "Г

-..дЮ~ж .ж, ,фу~ф"..,'-':';:, ',::.::-': ~юфф".,::-я,фя'„':.''::4"«

"'"' """ "-""'~"-'"""""" ~'::::-:::""'':"'-""''",'м~''"-"::'РМФф+Р~

:х ' (,(~,) ~Г+ 3( —,«)