logo
Elektronny_praktikum_po_MLTA_2014

1. Минимизация логических функций

Методы минимизации булевых функций:

Метод Квайна.

Метод Квайна - МакКласски.

Метод Блейка - Порецкого.

Метод диаграмм Вейча.

Метод минимизирующих карт.

Метод Петрика.

Минимизация частично определенных булевых функций.

Минимизация систем булевых функций.

Одним из методов построения минимальной ДНФ логической функции является метод Квайна - МакКласски. Формализация производится следующим образом:

  1. Все наборы единицы из СДНФ булевой функции f записываются их двоичными номерами.

  2. Все номера разбиваются на непересекающиеся группы. Признак образования i-й группы: i единиц в каждом двоичном номере наборы единицы.

  3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием).

  4. Производят всевозможные склеивания. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ далее производится по импликантной матрице.

Примеры выполнения заданий

1. Минимизируйте методом Квайна - МакКласски булеву функцию f(x1, x2 ,x3, x4) , заданную таблицей истинности:

В СДНФ функции f(x1, x2 ,x3, x4) , заменим все наборы единицы их

двоичными номерами:

f = 0001  0011  0101  0111  1110  1111.

x4x3x2x1

  f 

Образуем группы двоичных номеров. Признаком образования i - й группы является i единиц в двоичном номере наборы единицы.

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1

Номер группы

Двоичные номера

наборов единицы

0

-

1

0001

2

0011, 0101

3

0111, 1110

4

1111

Склеим номера из соседних групп таблицы. Склеиваемые номера вычеркнем (прим. - выделено цветом). Результаты склеивания занесем в следующую таблицу.

Склеим номера из соседних групп. Склеиваться могут только номера, имеющие звездочки в одинаковых позициях. Склеиваемые номера вычеркнем. Результаты склеивания занесем в таблицу:

Номер группы

Двоичные номера

наборов единицы

1

00*1, 0*01

2

0*11, 01*1

3

*111, 111*

Имеем три простые импликанты: *111, 111*, 0**1. Строим импликантную матрицу. По таблице определяем совокупность простых импликант - 0**I и 111*, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам.

Простые

импликанты

Наборы единицы

0001

0011

0101

0111

1110

1111

0**1

X

X

X

X

*111

X

X

111*

X

X

0**1 —> x4; 111* —> x1x2x3. Итак, МДНФ = x4  x1x2x3