|
|
|
|
|
|
|
|
40 |
|
|
|
где xα |
|
ìx, еслиα =1; |
|
|
|
|
|||||
= í |
|
|
. |
|
|
|
|
|
|||
|
|
îx, еслиα = 0, |
|
|
|
|
|||||
Например, |
представить |
функцию f (a,b,c) = |
|
|
|||||||
ab Ú c в виде СКНФ. |
|||||||||||
Таблица истинности для данной функции имеет вид: |
|||||||||||
|
|
|
|
|
|
|
|
|
|
||
a |
|
|
|
b |
|
c |
|
f(a, b, c) |
|||
0 |
|
0 |
|
0 |
|
0 |
|
|
|
||
0 |
|
0 |
|
1 |
|
1 |
|
|
|
||
0 |
|
1 |
|
0 |
|
1 |
|
|
|
||
0 |
|
1 |
|
1 |
|
1 |
|
|
|
||
1 |
|
0 |
|
0 |
|
0 |
|
|
|
||
1 |
|
0 |
|
1 |
|
1 |
|
|
|
||
1 |
|
1 |
|
0 |
|
0 |
|
|
|
||
1 |
|
1 |
|
1 |
|
1 |
|
|
|
||
В соответствии с данной таблицей функция f (a,b,c) принимает
нулевые значения на наборах 0, 4, 6. Тогда в соответствии с (1) получим: f (a,b,c) = (a Ú b Ú c)× (a Ú b Ú c)× (a Ú b Ú c).
3.ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1.Ознакомиться с теоретическими сведениями.
2.Получить вариант задания у преподавателя.
3.Выполнить задание.
4.Продемонстрировать выполнение работы преподавателю.
5.Оформить отчет.
6.Защитить лабораторную работу.
4.ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ ОТЧЕТА
Отчет по лабораторной работе должен содержать следующие разделы:
·титульный лист;
·цель работы:
·задание на лабораторную работу;
·ход работы;
·ответы на контрольные вопросы;
·выводы по проделанной работе.
5.ЗАДАНИЕ НА РАБОТУ
Приведенные логические выражения (таблица 5):
·преобразовать в СДНФ;
·преобразовать в СКНФ;
·преобразовать в базис «И-ИЛИ-НЕ» и минимизировать.
|
41 |
Таблица 5. Варианты заданий на работу |
|
Вариант |
f(a, b, c, d) |
1(ac Ú b × cd )Å ad
2abc Ú abcd Ú ac Ú (a ¯ cd)
3ad Ú ac Ú abd Ú (ac / d )
4(ac Ú b × cd Ú abcd Ú ad )Å a
5abc Ú abcd Ú ac Ú ac
6a Ú ad Ú abd Ú (ac / abd )
6.КОНТРОЛЬНЫЕ ВОПРОСЫ
1.В чем отличие булевой алгебры от алгебры логики?
2.Чем отличаются совершенная нормальная и нормальная формы представления функций?
3.Перечислите способы представления функций булевой алгебры.
4.Какие операции составляют базис булевой алгебры? Является ли эта алгебра полной?
5.Какое высказывание называется абсолютно истинным?
6.Какие значения может принимать булева переменная?
7.ЛИТЕРАТУРА
1.Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. — 3-е изд., стереотип. — М.: Издательство МГТУ им. Н.Э. Баумана, 2004. — 744 с.
2.Савельев А.Я. Основы информатики. — М.: Издательство МГТУ имени Н.Э.Баумана, 2001. — 328 с.
42
ЛАБОРАТОРНАЯ РАБОТА №7
МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ С ПОМОЩЬЮ КАРТ КАРНО
1. ЦЕЛЬ РАБОТЫ
Изучить методы преобразования выражений булевой алгебры.
2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Карта Карно — это двумерная табличная форма представления булевой функции, позволяющая в графической наглядной форме легко отыскать минимальные ДНФ логических функций. Карта Карно, это преобразованная таблица истинности булевой функции. Карта содержит 2n клеток, где n – число аргументов функции. Таким образом, каждому из наборов значений аргументов (СДНФ) соответствует одна клетка карты, и в эти клетки вписываются нули или единицы, представляющие значения функции на данном наборе.
Минимизирующие карты обычно используют для ручной минимизации булевых функций при небольшом числе переменных.
Правила минимизации следующие:
1.Две соседние клетки (два 0-куба) образуют один 1-куб. При этом клетки, лежащие на границах карты, также являются соседними по отношению друг к другу.
2.Четыре вершины могут объединяться, образуя 2-куб, содержащий две независимые координаты.
3.Восемь вершин могут объединяться, образуя один 3-куб.
4.Шестнадцать вершин, объединяясь, образуют один 4-куб и т.д.
При числе переменных равном или большем пяти строят
комбинированную карту, состоящую из совокупности четырехмерных (шестнадцатиклеточных) карт. Соседними клетками, в этом случае, являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра. Пример минимизации функции пяти аргументов приведен на рис. 20.
Рис. 20. Минимизация функции пяти переменных с помощью карты Карно
43
Следует отметить, что целесообразно выделять области максимально возможного размера (даже если эти области перекрываются) для более эффективной минимизации логического выражения.
Карты Карно удобны для минимизации и неполностью определенных функций, которые будут рассмотрены ниже. Неопределенные значения можно заменить любыми — 0 или 1. Покрывая таблицу минимальным числом максимальных квадратов (или прямоугольников) со сторонами, равными степени двойки, так, чтобы они обязательно покрыли все единицы и не покрывали ни одного нуля, получим минимальную ДНФ всех возможных функций.
Схема построения комбинированной карты при большом числе аргументов минимизируемой функции многократным отражением карты с шестнадцатью клетками показана на рис. 21.
Рис. 21. Построение карты Карно с помощью шестнадцатиклеточных карт
Особенную роль в процессе минимизации логических формул играют
не полностью определенные или частичные функции, область определения которых меньше, чем полное множество наборов значений n аргументов.
Главным свойством не полностью определенных функций является то, что, проводя минимизацию, можно произвольно доопределять функцию, подбирая такие ее значения на запрещенных наборах, которые позволяют произвести покрытие наилучшим образом.