Лабораторные работы Прикладная теория цифровых автоматов
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 5.00 (1 Голос)

3.  ЛАБОРАТОРНАЯ РАБОТА № 3.Применение операции вычитания интервалов

Цель работы: изучение операции вычитания интервалов и ее применения для решения некоторых задач дискретной математики.

4.1. Теоретические сведения

Одной из эффективных и алгоритмически легко выполняемых операций преобразования интервальных форм представления булевых функций является операция вычитания интервалов. В САПР цифровых схем, в системах искусственного интеллекта на основе этой операции выполняются многие сложные преобразования:

сведение всех интервалов произвольной ДНФ к максимальным и самой ДНФ - к безызбыточной;

построение полных проверяющих тестов цифровых схем;

вычисление дополнительных тестовых наборов при обнаружении неисправности для ее диагноза,

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

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

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

Пример выполнения задания иллюстрируется следующим диалогом обучаемого с системой.

1)  Проверка интервалов на пересечение: если интервалы ортогональны, то разность равна уменьшаемому:

 

x1

x2

x3

x4

x5

u1

0

--

0

0

--

# u2

0

--

--

1

0

0

--

0

0

--

2) Проверка поглощения вычитаемым уменьшаемого: разность пуста:

 

x1

x2

x3

x4

x5

u1

0

--

0

0

--

# u2

0

--

--

0

--

uр = Æ

3) Построение не пустой разности: если первые две ситуации не реализованы, то интервалы пересекаются, и разность не пуста и содержит k интервалов - число внутренних переменных уменьшаемого, которые являются внешними в вычитаемом:k=3,

 

x1

x2

x3

x4

x5

u1

0

--

--

1

--

# u2

0

1

0

1

0

uр1

0

0

--

1

--

uр2

0

1

1

1

--

uр3

0

1

0

1

1

 

Рассмотрим применение операции вычитания в двух задачах: сведение заданного интервала к максимальному и проверка избыточности заданного интервала в ДНФ. Пусть задано следующее множество интервалов:

u1 x1x2x3x4

u2 x1x3x4

u3 x2x4

u4 x2x3

u5 x1x2

Сначала нужно свести с помощью операции склеивания интервал u1 к максимальному.

Инвертируем его по переменной х1:

u1 x1x2x3x4

Полученный интервал ортогонален ко всем остальным интервалам по переменной х2.

Переходим к следующей переменной. Инвертируем интервал по переменной х2:

u1 x1x2x3x4

Вычитаем интервал u3:

u1 x1x2x3x4

u3 # х2х3

_________

Ǿ

Т. е. интервал расширяется по переменной х2.

u1 x1x3x4.

Теперь проверим по переменной х3:

u1 x1 x3x4

# x2x3x4

х1 x2x3x4

Остальные интервалы ортогональны по х2. Следовательно, интервал не расширяется по х3.

Проверяем по переменной х4.

u2 x2x3x4

# х2 х4

_________

Ǿ

Таким образом, расширяем интервал по переменной х4.

Окончательно получаем.

u1 x1x3

u2 x1x3x4

u3 x2x4

u4 x2x3

u5 x1x2

Теперь приступаем ко второй задаче. Убедимся, что интервалы u2 и u5 избыточны. Вычитаем из u2 интервал u1:

u2 x1x3x4

# х1 х3

_________

Ǿ

Интервал u2 удаляем из ДНФ.

Теперь рассмотрим интервал u5.

u5 x1x2

# х1 х3

_________

х1х2х3

Вычитаем u4:

х1х2х3

# х2 х3

_________

Ǿ

Удаляем u5 и окончательно получаем:

u1 x1x3

u2 x2x4

u3 x2x3

4.2. Постановка задачи

1.  Задана булева функция пяти переменных в матричной форме (п.3.4). Получить интервальную форму представления булевой функции. Для одного из интервалов (выбрать самостоятельно) проверить, является ли он максимальным.

2.  Проверить, является ли данное интервальное представление безызбыточным.

3.  В полученное интервальное представление ввести еще один (лишний) интервал, поглощаемый сразу несколькими интервалами ДНФ, и с помощью операции вычитания доказать, что этот интервал – лишний.

4.3. Контрольные вопросы

4.  Сформулировать правило выполнения операции вычитания интервалов вида #.

5.  Сформулировать правило выполнения операции вычитания интервалов вида \ .

6.  Как определяется количество интервалов разности?

7.  Дать определение максимального интервала.

8.  Какая ДНФ булевой функции называется безызбыточной?

9.  Дать определение ортогональных интервалов.

10.  Каким свойством обладает двоичное представление ортогональных интервалов?

11.  Каким свойством обладает двоичное представление поглощаемого и поглощающего интервалов?

 

Лабораторная работа - Применение операции вычитания интервалов - 5.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство