Дипломная работа 1 страница. Система подвержена действию 3-х видов двоичных входных сигналов (факторов) X1, X2, X3

Часть 2

Часть 1

Система подвержена действию 3-х видов двоичных входных сигналов (факторов) x ₁, x ₂, x ₃. Реакция системы определяется двоичными выходными сигналами y ₁, y ₂, y ₃. Соответствие между входными (i) и выходными (j) двоичными наборами задается таблицей, где i, j - десятичные номера наборов.

i
j

Требуется:

1. Дать формальное описание данной системы, как конечного автомата без памяти, составить таблицы истинности описывающих ФАЛ y_k = f_k (x ₁, x ₂, x ₃), к = 1,2,3.

2. Исследовать каждую из ФАЛ f ₁, f ₂, f ₃,на наличие фиктивных аргументов, при обнаружении таковых осуществить соответствующие упрощения.

3. Записать СДНФ, СКНФ, полином Жегалкина ФАЛ f ₁, f ₂, f ₃, на основе использования карт Вейча, найти их МДНФ и МКНФ, а затем наилучшие скобочные формы, сравнить их по сложности (числу букв).

4. Установить принадлежность f ₁, f ₂, f ₃ предполным классам: Р ₀, P ₁, L, М, S.

5. Составить логическую сеть из элементов "не", "и", "или", реализующую данный конечный автомат без памяти.

6. Записать перестановочную (инцидентную) матрицу данного конечного автомата.

7. Определить - зависимы ли f ₁, f ₂, f ₃, при положительном ответе выразить зависимость в аналитической форме.

8. Установить, существует ли система ФАЛ: Z ₁= f ₁ (y ₁, y ₂, y ₃,); Z ₂= f ₂ (y ₁, y ₂, y ₃,), позволяющая различать следующие наборы входных факторов x ₁, x ₂, x ₃: <000>, <010>, <101>, <111>. В случае положительного ответа получить одно из решений, совместив доопределение ФАЛ и их минимизацию в классе ДНФ.

ДАНО: Два графа G (X, F) и H (Y, P).

НЕОБХОДИМО:

1. Построить аналитически и графически объединение, пересечения, разность графов G и H, дополнение графа G по отображению до универсального.

2. Для графа S = G U H построить матрицы смежности, инцидентности, достижимости; конденсацию и базу графа; минимальные и наименьшее доминирующие множества.

3. Для графа S = G U H построить Гамильтонов и Эйлеров путь (если они не существуют, то дополнить граф необходимыми дугами, обозначив их на графе). Гамильтонов путь построить с использованием алгоритма Робертса и Флореса [6].

Варианты заданий для курсовой работы приведены в Приложении.

ЛИТЕРАТУРА

1. Босин П.Л., Булыгии В.С., Кулешов К.Г. Лабораторные работы но курсу «Основы теории конечных динамических систем», — М.: МАИ, 1985.

2. Булыгин B.C. Логические основы теории дискретных устройств: учеб. пособие. - M.: МАИ, 1983.

3. Булыгин B.C. Основы проектирования дискретных устройств АСУ: учеб. пособие. - M.: МАИ, 1982.

4. Поспелов Д.А. Логические методы анализа и синтеза схем. - М.: Энергия, 1968.

5. Просветов Г.И. Дискретная математика:задачи и решения: учебное пособие. – М.:БИНОМ. Лаборатория знаний,2008. – 222 с.

6. Кристофидес Н, Теория графов: Алгоритмический подход. - М.: Мир, 1978.

7. Булыгин B.C., Ескин В.И.. Модели дискретных устройств с памятью в АСУ: Учеб. пособие. - M.: Изд-во МАИ, 1993. - 72 с.: ил.

8. Мелихов A.H. Ориентированные графы и конечные автоматы. - M.: Наука, 1971.

ПРИЛОЖЕНИЕ

Варианты заданий для поиска гамильтонова пути в графе

Вариант 1. Вариант 2.

Вариант 3. Вариант 4.

Вариант 5. Вариант 6.

Вариант 7. Вариант 8.

Вариант 9. Вариант 10.

Варианты заданий для поиска эйлерового пути в графе

Вариант 1. Вариант 2.

Вариант 3. Вариант 4.

Вариант 5. Вариант 6.

Вариант 7. Вариант 8.

Вариант 9. Вариант 10.

Варианты заданий для поиска компонент связности в графе

Вариант 1 Вариант 2

Вариант 3 Вариант 4

Дата добавления: 2017-01-13