- •Псковский государственный политехнический институт
- •Порядок выполнения контрольной работы
- •Н.В. Мотина
- •Дискретная математика
- •Методические указания по выполнению контрольных работ
- •230101 «Вычислительные машины, комплексы, системы и сети»,
- •230201 «Информационные системы и технологии»
- •Псков Издательство ппи
- •Часть 1. Краткий теоретический материал 6
- •Часть 2 47
- •Часть 1. Краткий теоретический материал
- •1. Операции над множествами
- •1.1. Понятие множества
- •1.2. Объединение, пересечение, дополнение, разность множеств
- •1.3. Прямое произведение множеств
- •Контрольные вопросы
- •2. Отношения
- •2.1. Понятие бинарного отношения
- •2.2. Обратное отношение
- •2.3. Композиция отношений
- •2.4. Векторы
- •Контрольные вопросы
- •3. Соответствия
- •Контрольные вопросы
- •4. Виды графов
- •4.1. Понятие графа
- •4.2. Связность
- •4.3. Планарность
- •4.4. Деревья
- •Контрольные вопросы
- •5. Способы задания графов
- •5.1. Матрица смежности
- •5.2. Матрица инциденций
- •Контрольные вопросы
- •6. Маршруты, цепи, циклы
- •6.1. Основные определения
- •6.2. Эйлеровы циклы
- •6.3. Гамильтоновы циклы
- •Контрольные вопросы
- •7. Преобразование логических выражений
- •7.1. Понятие логической функции
- •Продолжение табл.2
- •7.2. Тождества булевой алгебры
- •7.3. Правила преобразования некоторых логических функций
- •Контрольные вопросы
- •8. Минимизация логических функций
- •8.1. Минимизация с помощью карт Карно
- •8.2. Метод Квайна поиска СокДнф
- •8.3. Метод Квайна – Мак-Класки
- •8.4. Нахождение мкнф с помощью карты Карно
- •8.5. Минимизация логических функций, представленных в конъюнктивной форме, с использованием правил, аналогичных правилам минимизации логических функций в дизъюнктивной форме
- •8.6. Минимизация неполностью определенных логических функций с помощью карты Карно
- •8.7. Минимизация неполностью определенных логических функций без использования карты Карно
- •Контрольные вопросы
- •9. Свойства логических функций
- •Контрольные вопросы
- •Часть 2 Варианты заданий Задание 1. Операции над множествами
- •Задание 2. Отношения
- •Задание 3. Соответствия
- •Задание 4. Виды графов
- •Задание 5. Способы задания графов
- •Задание 6. Маршруты, цепи, циклы
- •Задание 7. Преобразование логических выражений
- •Задание 8. Минимизация логических функций
- •Задание 9. Свойства логических функций
- •Пример оформления контрольной работы
- •Рекомендуемая литература
- •Мотина Надежда Владимировна
8.3. Метод Квайна – Мак-Класки
Метод Квайна – Мак-Класки представляет собой модернизацию метода Квайна для нахождения простых импликант.
Основная идея метода заключается в том, что поиск склеивающихся аргументов следует вести среди конъюнкций, отличающихся друг от друга только одним аргументом.
Этапы поиска простейших импликант методом Квайна - Мак-Класки:
Закрепить за аргументами определенные места в конъюнкции.
Закодировать аргументы конъюнкций двоичными символами, причем если аргумент входит в конъюнкцию без инверсии, он кодируется единицей, если с инверсией – нулем.
Получающиеся в результате такой перекодировки двоичные числа разбиваются на группы по числу единиц.
Склеивающиеся аргументы нужно искать только между соседними группами.
На месте склеивающихся аргументов будем ставить прочерк, а склеившиеся конъюнкции будем помечать *.
Повторять шаги 3-5 до тех пор, пока среди конъюнкций не останется склеивающихся между собой.
Пример. Минимизировать функцию
=
0000 + 0001 + 0010 + 0011 + 0100 + 0110 + 0111 + +1000 + 1001 + 1011
+ 1111
0 группа: 0000 *
1: 0001 * 0010 * 0100 * 1000 *
2: 0011 * 0110 * 1001 *
3: 0111 * 1011 *
4: 1111 *
0 группа: 000- * 00-0 * 0-00 * -000 *
1: 00-1 * 001- * 0-10 * 01-0 * -001 * 100- *
2: 0-11 * 011- * -011 * 10-1 *
3: -111 * 1-11 *
0 группа: 00-- 00-- 0--0 0--0 -00- -00-
1: 0-1- 0-1- -0-1 -0-1
2: --11 --11
= 00-- + 0--0 + -00- + 0-1- + -0-1 + --11
Для нахождения тупиковых и минимальной форм воспользуемся методом импликантных матриц.
Таблица 3.
Метод импликантных матриц
Сок. ДНФ |
ДСНФ |
||||||||||
0000 |
0001 |
0010 |
0011 |
0100 |
0110 |
0111 |
1000 |
1001 |
1011 |
1111 |
|
00-- |
|
|
|
|
|
|
|
|
|
|
|
0--0 |
|
|
|
|
|
|
|
|
|
|
|
-00- |
|
|
|
|
|
|
|
|
|
|
|
0-1- |
|
|
|
|
|
|
|
|
|
|
|
-0-1 |
|
|
|
|
|
|
|
|
|
|
|
--11 |
|
|
|
|
|
|
|
|
|
|
|
МДНФ
= 0--0 + -00- + --11 =
