Xreferat.com » Рефераты по математике » Математическая логика

Математическая логика

импликант. Дизъюнкция этих импликант является сокращенной ДНФ.

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

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


5.2 Метод Квайна с применением п-мерных кубов


Данный метод устраняет недостаток предыдущего метода, т.е. устраняет необходимость попарного сравнения всех термов на первом этапе при нахождении простых импликант. Для этого строится п-мерный куб, по которому визуально можно определить те конъюнктивные термы, склеивание которых порождают простые импликанты.

При решении задачи минимизации булевой функции удобно вместо конъюнктивных термов использовать, соответствующие им, двоичные наборы.

Пример.

Минимизировать булеву функцию


Математическая логика.


Здесь в скобках стоят десятичные эквиваленты соответствующих двоичных наборов.

Представим функцию в виде СДНФ:

Математическая логика


Запишем конъюнктивные термы в виде двоичных наборов:


Математическая логика.


Построим единичный 4 – мерный куб и выделим вершины, соответствующие двоичным наборам, входящим в заданную булеву функцию (рис. 10):


Математическая логика

Рис. 10


1 этап. Определение сокращенной ДНФ.

Применим закон склеивания для отмеченных вершин (для двоичных наборов) куба, соединенных ребром:

Математическая логика

Прочерк означает, что переменная в этом месте отсутствует.

Для некоторых простых импликант склеивание можно продолжить:


Математическая логика


По закону идемпотентности: Математическая логика

Дизъюнкция полученных простых импликант является сокращенной ДНФ:


Математическая логика


2 этап. Определение тупиковой ДНФ.

Для определения тупиковой ДНФ построим таблицу покрытий, в которую следует включать и двоичные наборы, не участвовавшие в склеивании:


Простые импликанты Исходные термы

0011 0100 0101 0111 1001 1011 1100 1101
0 – 11 *

*



Математическая логикаМатематическая логика


Математическая логикаМатематическая логика


Математическая логика

Математическая логика

*



*


Математическая логика



* *




10 – 1



* *


1 – 01



*

*

Математическая логика


* *


*


Определяя минимальное число строк, покрывающих все столбцы таблицы, находим тупиковую ДНФ:


Математическая логика

Недостатком метода является само построение п – мерного куба, т.к. при числе переменных Математическая логика это построение затруднительно.


5.3 Метод Квайна – Мак-Класки


Метод Квайна – Мак-Класки представляет собой предыдущий метод, но без геометрического построения п – мерных кубов: кубы присутствуют, но абстрактно.

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

В итеративной процедуре минимизации попарное сравнение можно производить только между соседними группами.

Нахождение простых импликат на первом этапе:

1. Все исходные конъюнктивные термы записываются в виде их двоичных наборов.

2. Все наборы разбиваются на непересекающиеся группы по числу единиц. Условие образования r-куба – наличие расхождения в (r-1)-кубах только по одной координате в одном двоичном разряде и наличие общих независимых координат.

3. В i-группу включают все двоичные наборы, имеющие в своей записи i единиц.

4. Попарное сравнение производится только между соседними по номеру группами. Группы, которые различаются в двух разрядах и более, не имеет смысла сравнивать.

Пример.

(Предыдущий пример)

Минимизировать булеву функцию

Математическая логика


1 этап. Определение сокращенной ДНФ.

По двоичным наборам запишем 0-кубы:

К 0 = {0011, 0100, 0101, 0111, 1001, 1011, 1100, 1101}.

Выполним их разбиение на подгруппы по количеству единиц:


Математическая логика


Строим К 1-кубы, сравнивая соседние подгруппы:


Математическая логика


Выполним разбиение всех К 1-кубов в зависимости от положения независимой координаты Х:


Математическая логика


Выполним сравнение кубов внутри каждой подгруппы с целью построения К 2-кубов:


Математическая логика

Поскольку они одинаковы, то Математическая логика

Записываем сокращенную ДНФ, в которую входят простые импликанты из К 1 (не вошедшие в К 2) и К 2:


Математическая логика


2 этап. Определение тупиковой ДНФ.

Строим таблицу покрытий, в которую следует включать и те двоичные наборы, которые на любой итерации не участвовали ни разу в склеивании:


Простые

импликанты

Исходные термы

0011 0100 0101 0111 1001 1011 1100 1101

Математическая логика


Математическая логика

Математическая логика


0 – 11 *

*




- 011 *



*


01 – 1

* *




10 – 1



* *


1 – 01



*

*
- 10 -
* *


*

*Математическая логика



Определяя минимальное число строк, покрывающих все столбцы таблицы, находим тупиковую ДНФ:


Математическая логика

Литература


1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. – 496 с.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.

4. Сигорский В.П. Математический аппарат инженера. – М.: Техника, 1975. – 768 с.

5. Шапорев С.Д. Дискретная математика. – СПб., 2006. - 400 с.

6. Хаханов В.И., Чумаченко С.В. Дискретная математика. Конспект теоретического материала (электронная версия). ХНУРЭ, 2003.

7. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. – 272 с.

8. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: