Практические занятия Прикладная теория цифровых автоматов
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Занятие 1. Метод Закревского минимизации булевых функций по матричной форме, обобщение метода для систем булевых функций

Цель занятия. Представление булевой функции 4 и 5 переменных на матричной форме. Формулировка метода Закревского минимизации булевых функций по матричной форме. Поиск максимальных интервалов с большим числом покрытых элементов. Метод граничного перебора.

Теоретические положения и примеры решения задач.

Итак, начинаем с функций 4 переменных. У точек относительно малое число соседей. Пример.

Описание: C:\Documents and Settings\Tatiyana\Мои документы\Ded\1.bmp

Подсчитываем число соседей для всех элементов.

 

Рисунок 1. Матричная форма задания и подсчет числа соседей.

Начинаем с элементов с меньшим числом соседей. Элемент 0011 имеет 1 соседа, поэтому без всяких колебаний он склеивается по переменной х2 и интервал 0-11 записывается в ответ. Элементы 0011 и 0111 отмечаются как покрытые. Далее выбирается элемент 1001, склеивающийся по переменной х4, и в ответ записывается интервал 100-. Элементы 1001 и 1000 отмечаются как покрытые. Далее выбирается элемент 0000 с числом соседей 2 и склеивается по переменным х1 и х2. Получается интервал --00. Элементы 0000.0100,1100 и 0100 отмечаются как покрытые. Наконец выбирается элемент 1110 с 2 соседями и в ответ записывается интервал -1-0. Элементы 1110, 0110,1100 и 0100 отмечаются как покрытые. Все элементы множества М1 покрыты. ДНФ построена:

F(x1,x2,x3,x4)=х1х3 х4 Vx1x2x3Vx3x4Vx2x4.

Рисунок 2. Еще одна булева функция 4-х переменных.

Подсчитываются числа соседей.

Рисунок 3. Подсчитаны числа соседей.

Выбирается элемент 0000 и строится интервал --00, наборы 0000,1000, 1100 и 0100 считаются покрытыми. Далее выбирается элемент 0011 с двумя соседями. Он может склеиться с элементами 1011 или с 0111, но только с каждым в отдельности. Выберем интервал -011. Наборы 0011 и 1011 считаются покрытыми. Далее выбирается набор 1010 с тремя соседями, но элемент 1011 уже покрыт, поэтому выбирается интервал 1--0. Наборы 1000, 11001, 1010 и 1110 покрыты. Выбирается очередной не покрытый элемент 0110 и для него выбирается интервал 01--. Наборы 0100,0110,0111 и 0101 покрыты. Последним выбирается набор1001 с тремя соседями, но остается всего один не покрытый элемент 1101, поэтому выбирается максимальный интервал 1-0-. Все наборы множества М1 покрыты, получается ДНФ:

F(x1,x2,x3,x4)=х3х4Vx2x3x4Vx1x4Vx1x2Vx1x3.

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

Рисунок 4. Булева функция 5-и переменных.

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

Хвп=

х1

х2

х3

х5

интервал

 

1

1

   

- - 1 0 0

 

1

   

1

- 0 1 0 -

   

1

1

 

1 - - 0 0

   

1

   

Не максимальный

     

1

1

1 0 - 0 -

Рисунок 5. Иллюстрация метода граничного перебора.

Переменная х4 входит в множество внешних переменных всех интервалов, так как набор 10100 не склеивается по этой переменной.

Теперь вернемся к основной теме – минимизации булевой функции 5 переменных.

Рисунок 6. Подсчитаны числа соседей для всех точек.

Уже подсчитаны числа соседей для всех элементов. Начинаем с элемента с минимумом числа соседей 00010 с двумя соседями, Вместе они не склеиваются, оба интервала содержат по два не покрытых набора, но интервал -0010 покрывает элемент с меньшим числом соседей, поэтому он и выбирается. Наборы 00010 и 10010 отмечаются как покрытые – переводятся в множество Мх наборов, которые уже не нужно покрывать, но с которыми можно склеиваться. Следующий элемент 11111 с двумя соседями образует единственный интервал - --111. Наборы 01111,11111, 10111 и 00111 переводятся в множество Мх. Выбирается набор 01001 с двумя соседями и снова – единственный интервал --001 выбирается в решение. Следующий набор 11000 имеет уже три соседних элемента, один из которых уже покрыт. Поэтому выбирается интервал 1--00, наборы 10000, 11000, 11100 и 10100 переводятся в множество Мх. Выбирается Набор 01100 с тремя соседями, но набор 11100 уже покрыт, поэтому выбирается интервал 0-1-0. Наборы 01100, 01110, 00100 и 00110 переводятся в множество Мх. Остались два набора 10101 и 00101, которые покрываются оба одним максимальным интервалом -0--01 и переводятся в множество Мх. Минимизация булевой функции завершена, получена ДНФ:

F(x1,x2,x3,x4,х5 )=х2х3х4х5Vх3x4х5Vx3x4х5Vx1x4х5Vx1х3x5Vх2х4х5.

Наконец, обобщим метод Закревского на системы булевых функций.

Рисунок 7. Функции F1 и F2 четырех переменных и их интервальное покрытие.

Домашние задания: минимизировать булеву функцию четырех переменных[1, стр.160], построить множество максимальных интервалов, покрывающих заданную точку[1,стр. 172], минимизировать ту же булеву функцию, минимизировать систему двух булевых функций[1, стр. 183]

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


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

По темам:

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

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

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

Информатика

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

Статистика

География

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

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

Генетика

Разное

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

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

Филология

Философия

Химия

Экология

Социология

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

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

Педагогика

История

Психология

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

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

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

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

Маркетинг

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

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

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

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

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

Творчество

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