е задание.
Записать формулу функции f(x1,x2,x3) и минимизировать ее
графическим методом,
методом неопределенных коэффициентов,
методом минимизирующих карт Карно,
методом Квайна.
Для метода неопределенных коэффициентов вывести на экран полученную систему уравнений, ее решение, СДНФ и МДНФ.
Для метода минимизирующих карт вывести на экран последовательность минимизирующих карт, СДНФ и МДНФ.
Сравнить полученные результаты.
x1 x2 x3 f
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Решение:
Графический метод минимизации функции:
Минимизация логических функций с помощью графического представления n-мерного куба.
При количестве переменных не более 4-х все возможные тупиковые и саму минимальную формы можно просто увидеть на пространственной диаграмме — n-мерном (в нашем примере — 3-х мерном) кубе — декартовом графике (рисунок), где на осях, соответствующих переменным, отображены точки их возможных состояний (0 или 1). Точки-состояния, в которых (согласно таблице истинности) функция принимает единичные значения, изобразим более крупными:
(у нас точки (0,0,0), (0,0,1), (0,1,1), (1,0,1), (1,1,1))
Формула ребра вдоль оси-переменной не содержит этой переменной, т. к. значение функции на «склеенных» им вершинах не зависит от значения этой переменной, что соответствует операции выноса за скобки общего множителя.
Ребро ┐x •┐y соединяет точки ┐x•┐y•┐z и ┐x•┐y•z
:
( ┐x•┐y•┐z )+( ┐x•┐y•z) = ┐x•┐y •( ┐z + z) =┐x•┐y
А грань будет соответствовать z
По диаграмме задача минимизации сводится к объединению максимума вершин, на которых функция принимает единичные значения, в минимум ребер.
В нашем случае, минимальная ДНФ равна:
f(x,y,z)=(┐x•┐у)\/z
перейдем к исходным переменным х1,х2 и х3,
им соответствуют переменные x,y,z
МДНФ: f(x1,х2,х3)=(┐x1•┐x2)\/x3
Минимизация методом неопределенных коэффициентов:
Метод неопределенных коэффициентов.
Суть метода состоит в преобразовании ДСНФ в МДНФ.
На основании теоремы Жегалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):
Алгоритм определения коэффициентов:
1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности.
2. Напротив каждого выражения поставить соответствующее значение функции.
3. Выбрать строку, в которой значение функции и приравнять все к нулю.
4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть все коэффициенты, встречающиеся в нулевых строках.
5. Проанализировать оставшиеся коэффициенты в единичных строках.
6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно.
7. Записать исходный вид функции.
Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.
Представим функцию f(x1,x2,x3) в виде следующей
СДНФ:
Составляем схему:
0 0 0 0 00 00 00 000 1
1 0 0 1 00 01 01 001 1
2 0 1 0 01 00 10 010 0
3 0 1 1 01 01 11 011 1
4 1 0 0 10 10 00 100 0
5 1 0 1 10 11 01 101 1
6 1 1 0 11 10 10 110 0
7 1 1 1 11 11 11 111 1
Приравняем 0 в каждом уравнении все коэффициенты,
кроме тех, которые отвечают конъюнкциям,
которые содержат, наименьше число переменных:
Итак, получим МДНФ
Метод Квайна:
Составим СДНФ функции:
-сокращенная ДНФ
И построим матрицу Квайна
Матрица Квайна:
* *
* * * *
Выписываем
тупиковая ДНФ:
(для столбцов, где стоит одна *)
\/
Выбираем из тупиковых минимальную: \/
Минимизация, с помощью карт Карно:
исходная функция зависит от трех переменных, таблицу истинности можно представить виде:
х2
х3
—
х1 0
0 0
1 1
1 1
0
0 000 001 011 010
1 100 101 111 110
Подставив значения функции, получим
х2
х3
—
x1
0
0
0
1 1
1 1
0
0 1 1 1 0
1 0 1 1 0
СДНФ функции состоит из пяти слагаемых:
Выписываем тупиковые ДНФ:
\/ .
Выбираем из тупиковых минимальную ДНФ: \/ .
ВЫВОД:
Сравнивая МДНФ, полученную разными способами (графическим методом,
методом неопределенных коэффициентов, методом минимизирующих карт Карно, етодом Квайна. ) , видно, что МДНФ найдена верна, так как совпали результаты.
(ПОДРОБНОЕ И ЯСНОЕ РЕШЕНИЕ В ФАЙЛЕ, КОТОРЫЙ МОЖНО СКАЧАТЬ, пройдя регистрацию на сайте )
посмотреть другие задачи по дискретной математике |