Минимизация логических функций методом Петрика

Второй этап

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

Таблица 2.10 – Импликантная матрица Квайна

							1001
_ _01	´		´				´		´
1_0_						´	´	´	´
01_ _		´	´	´	´
_10_		´	´					´	´

Т.о. простая импликанта х₂ ù х₃ - лишняя.

Отсюда минимальная ДНФ нашей функции:

F = ù х₃ х₄ Ú х₁ ù х₃ Ú ù х₁ х₂.

Петрик формализовал второй этап минимизации, т.е. нахождение минимальной ДНФ – исключение лишних простых импликант. Данный метод позволяет свести работу с импликантной матрицей к аналитическим выражениям. По импликантной матрице строится так называемое конъюнктивное представление импликантной матрицы.

Алгоритм метода:

1. Все простые импликанты обозначаются буквами.

2. Для каждого i – го столбца матрицы строится дизъюнкция всех букв, обозначающих строки матрицы, пересечение которых с i – м столбцом отмечено ´.

3. Конъюнкция построенных дизъюнкций для всех столбцов матрицы и есть конъюнктивное представление импликантной матрицы.

4. К данному выражению можно применять все законы булевой алгебры с целью его упрощения. После раскрытия скобок и всех возможных поглощений получаем дизъюнкцию конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ.

Пример: Имеем после первого этапа минимизации следующую импликантную матрицу (смотри метод Квайна – Мак-Класки):

Таблица 2.11 – Импликантная матрица

	ù х1 ù х2 ù х3 х4	ù х1 х2 ù х3 ù х4	ù х1 х2 ù х3 х4	ù х1 х2 х3 ù х4	ù х1 х2 х3 х4	х1 ù х2 ù х3 ù х4	х1 ù х2 ù х3 х4	х1 х2 ù х3 ù х4	х1 х2 ù х3 х4
ù х3 х4 = A	´		´				´		´
х1 ù х3 = B						´	´	´	´
ù х1 х2 = C		´	´	´	´
х2 ù х3 = D		´	´					´	´
F	A	C Ú D	A Ú C Ú D	C	C	B	A Ú B	B Ú D	A Ú B Ú D

Отсюда конъюнктивное представление импликантной матрицы:

F = A (C Ú D) (A Ú C Ú D) C C B (AÚ B) (B Ú D) (A Ú B Ú D).

После раскрытия скобок и поглощений получаем минимальную ДНФ:

F = A C B = ù х₃ х₄ Ú ù х₁ х₂ Ú х₁ ù х₃

Пример: Имеем после первого этапа минимизации следующую импликантную матрицу (смотри метод Квайна – Мак-Класки):

Таблица 2.12 – Импликантная матрица

	х1 х2 х3	х1 ù х2 х3 ù	ù х1 ù х2 х3	ù х1 ù х2 ù х3	х1 х2 ù х3
Х1 х3 = A	´	´
Х1 х2 = B	´				´
ù х2 х3 = C		´	´
ù х1 ù х2 = D			´	´
F	A Ú B	A Ú C	C Ú D	D	B

Отсюда:

F = (A Ú B) (A Ú C) (C Ú D) D B = (A Ú C) D B = A D B Ú C D B.

Т.е. имеем две минимальные ДНФ:

F₁ = х₁ х₃ Ú ù х₁ ù х₂ Ú х₁ х₂,

F₂ = ù х₂ х₃ Ú ù х₁ ù х₂ Ú х₁ х₂ .

Дата добавления: 2015-08-31