Задача на минимизацию булевых функций от трех переменных

задача на минимизацию булевых функций от трех переменных
[ Скачать с сервера (152.5Kb) ] 24.01.2012, 18:12

е задание.
Записать формулу функции 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

СДНФ функции состоит из пяти слагаемых:

Выписываем тупиковые ДНФ:
\/ .
Выбираем из тупиковых минимальную ДНФ:  \/ .
ВЫВОД:
Сравнивая МДНФ, полученную разными способами (графическим методом,
методом неопределенных коэффициентов, методом минимизирующих карт Карно, етодом Квайна. ) , видно, что МДНФ найдена верна, так как совпали результаты.

(ПОДРОБНОЕ И ЯСНОЕ РЕШЕНИЕ В ФАЙЛЕ, КОТОРЫЙ МОЖНО СКАЧАТЬ, пройдя регистрацию на сайте )

посмотреть другие задачи по дискретной математике

Loading