2015-10-22
1523Тема: Совершенные нормальные формы булевых функций. Минимизация булевых функций
Цели работы:
4) научиться представлять булеву функцию в виде совершенной ДНФ;
5) научиться представлять булеву функцию в виде совершенной КНФ;
6) научиться представлять булеву функцию (N £ 3) в виде минимальной ДНФ графическим методом.
Пояснения:
Совершенная дизъюнктивная нормальная форма (СДНФ) – это ДНФ, в которой в каждой элементарной конъюнкции находятся все переменные или их отрицания, входящих в данную функцию.
СКНФ – это КНФ, в которой в каждой элементарной дизъюнкции находятся все переменные или их отрицания, входящих в данную функцию.
Свойства СДНФ и СКНФ:
- СДНФ и СКНФ не содержат двух одинаковых конъюнкций, дизъюнкций;
- ни одна элементарная конъюнкция, дизъюнкция не содержит двух одинаковых переменных;
- ни одна элементарная конъюнкция, дизъюнкция не содержит одновременно некоторую переменную и её отрицание.
Правило приведения формулы к совершенной форме:
1) формулу необходимо привести к ДНФ, к КНФ;
|
|
|
2) добавить вместо недостающей переменной для СДНФ: 1, и в дальнейшем расписать её как дизъюнкцию недостающей переменной и её отрицание; для СКНФ: 0, и представляем его как конъюнкцию недостающей переменной и её отрицание;
3) применяем закон дистрибутивности;
4) удаляем всё кроме одинаковой элементарной конъюнкции или элементарной дизъюнкции.
Оборудование, аппаратура, материалы и их характеристики: персональные компьютеры с лицензионным программным обеспечением; доска, маркеры; рабочие тетради; раздаточный материал.
Порядок выполнения работы:
Студенты получают задания по вариантам. Метод решения выбирается студентами самостоятельно и зависит от приобретенных в процессе обучения навыков. В процессе выполнения практической работы преподаватель проводит как групповые, так и индивидуальные консультации по вопросам дополнительного разъяснения отдельных понятий и аспектов изученных тем, задания и оформления отчета.
1. Записать формулы в виде ДНФ, КНФ и СДНФ, СКНФ.
Таблица 1 – Задание № 1
| № варианта | Исходные данные |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
2. Постройте совершенные ДНФ и КНФ и соответствующие минимальные формы для булевых функций, заданных таблично.
| x y z | f1 | f2 | f1 | f2 | f1 | f2 | f1 | f2 | f1 | f2 | f1 | f2 | f1 | f2 | f1 | f2 | f1 | f2 | f1 | f2 |
| 0 0 0 | ||||||||||||||||||||
| 0 0 1 | ||||||||||||||||||||
| 0 1 0 | ||||||||||||||||||||
| 0 1 1 | ||||||||||||||||||||
| 1 0 0 | ||||||||||||||||||||
| 1 0 1 | ||||||||||||||||||||
| 1 1 0 | ||||||||||||||||||||
| 1 1 1 |
Таблица 2 – Задание № 2
|
|
|
Требования к отчету: Отчет должен содержать:
- название практической работы;
- формулировку цели работы;
- краткие теоретические сведения по теме работы в виде таблиц, графиков, диаграмм, схем, рисунков и формул;
- результаты решения заданий;
- выводы по работе;
- краткие письменные ответы на контрольные вопросы.
Текст отчета набирается на компьютере. Допускается тип шрифта Times New Roman, размер 12 – 14, межстрочный 1,5 интервал, выравнивание текста по ширине странице, абзацный отступ 1,25.
Контрольные вопросы:
1) Что такое алгебра логики?
2) Назовите базовые операции булевой алгебры.
3) Какие основные законы и аксиомы алгебры логики Вы знаете?
4) Дайте определение булевой функции.
5) Что такое СДНФ и СКНФ?
6) Что такое таблица истинности?
7) Для чего применяют карты Карно?
Учебная и специальная литература:
1) Спирина М.С., Спирин В.В. Дискретная математика: Учебник. – М.: Издательский центр «Академия», 2009. – 370 с.
2) Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для высш. учеб. заведений. – М.: Издательский центр «Академия», 2009. – 304 с.
3) Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ – Петербург, 2008. – 352 с.
