Информатика и вычислительная техника
Преобразование и минимизация логических выражений
При использовании аналитических форм преобразования логических функций обычно стремятся к их упрощению, выражая сложные логические функции через более простые.
Система логических функций называется функционально полной, или базисом, если любую логическую функцию можно представить в аналитической форме через эти функции, взятые в любом конечном числе экземпляров каждая.
Возможность представления любой логической функции в ДСНФ или КСНФ означает, что логические функции конъюнкции, дизъюнкции и отрицания (И, ИЛИ, НЕ) образуют функционально полную систему, или основной базис.
Базис И, ИЛИ, НЕ является избыточным, так как из него всегда можно исключить, используя формулу де Моргана, либо функцию И, заменяя ее на ИЛИ и НЕ:
х & у = х ? у,
либо функцию ИЛИ, заменяя ее на И и НЕ:
х ? y = х & у.
Базисы функции И, НЕ и ИЛИ, НЕ называются нормальными базисами. При удалении из них хотя бы одной функции функционально полная система становится неполной.
Функциональной полнотой обладают также системы, состоящие из одной логической функции: отрицания конъюнкции х & у (И - НЕ), названной операцией Шеффера, или отрицания дизъюнкции х ? у (ИЛИ - НЕ), названной операцией Пирса. С помощью любой из этих функций, образующих универсальный базис, можно выразить основные логические функции: конъюнкцию, дизъюнкцию и отрицание, а следовательно - и любую другую логическую функцию.
Процесс упрощения аналитического выражения логических функций называют минимизацией. В результате минимизации сокращаются затраты оборудования в процессе технической реализации. Помимо минимизации, числа логических функций, участвующих в исходном выражении, стремятся к их однородности (однотипности).
Существуют различные методы минимизации, из которых мы рассмотрим два метода: метод непосредственных преобразований логического выражения и метод минимизирующих карт Карно.
Метод непосредственных преобразований основан на последовательном исключении переменных исходного выражения с использованием законов алгебры логики.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий