НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Минимизация ФАЛ

Минимизация ФАЛ

Минимизация ФАЛ

Совершенно нормальные формы хотя и дают однозначные представления функции,

но являются очень громоздкими. Реализация СНФ программно или

схемотехнически является избыточной, что ведет к увеличению программного

кода, поэтому существуют методы упрощения логической записи – минимизации.

Определение: Преобразование логических функций с целью упрощения их

аналитического представления называются минимизацией.

Существуют два направления минимизации:

1. Кратчайшая форма записи (цель – минимизировать ранг каждого терма). При

этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ.

2. Получение минимальной формы записи (цель – получение минимального числа

символов для записи всей функции сразу).

При этом следует учесть, что ни один из способов минимизации не

универсален!

Существуют различные методы минимизации:

1. Метод непосредственных преобразований логических функций. (1.1)

При применении данного метода:

а) Записываются ДСНФ логических функций

б) Форма преобразуется и упрощается с использованием аксиом алгебры логики.

При этом, в частности, выявляются в исходном ДСНФ так называемые соседние

min-термы, в которых есть по одной не совпадающей переменной.

[pic]

По отношению к соседним min-термам применяется закон склейки, значит ранг

min-терма понижается на единицу.

Определение: Min-термы, образованные при склеивании называются

импликантами.

Полученные после склейки импликанты по возможности склеивают до тех пор,

пока склеивание становится невозможным.

Определение: Несклеивающиеся импликанты называются прослойками.

Определение: Формула, состоящая из простых импликант – тупиковая.

Пример:

|[pic] |[pic] |[pic] |[pic] |[pic] |

|0 |0 |0 |1 | |

|0 |0 |1 |1 | |

|0 |1 |0 |1 | |

|0 |1 |1 |1 | |

|1 |0 |0 |0 | |

|1 |0 |1 |0 | |

|1 |1 |0 |0 | |

|1 |1 |1 |0 | |

Если в процессе склейки образуется форма R, содержащая член