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

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

Индексом простоты (или сложностью) булевой функции называется функция , определенная на множестве всех ДНФ и удовлетворяющая следующим свойствам:

1) Свойство неотрицательности: ;

2) Свойство монотонности: если , где -элементарная конъюнкция, .

3) Свойство выпуклости:

4) Свойство инвариантности: если ДНФ = получена из ДНФ = путем переименования переменных без отождествления, то .

Примеры. 1) - число букв переменных, встречающихся в записи . Под буквой понимают символ переменной или ее отрицание, если переменная входит в формулу m раз, то говорят, что формула содержит m букв . Например в выражении число переменных равно 3, а число букв равно 5, т.е. число букв равно числу вхождений переменных.

2) - число элементарных конъюнкций, входящих в .

3) - число символов отрицаний, встречающихся в записи . Каждый из указанных индексов удовлетворяет перечисленным свойствам.

Пример. Пусть задана вектором состояний. Тогда для нее может быть записана СДНФ в виде

Эту функцию можно упростить

Вычислим индексы простоты для и .

, ; , ;

, .

Следовательно, проще для всех трех индексов простоты.

Задача минимизации заданной логической функции сводится к представлению ее дизъюнктивной (или конъюнктивной) нормальной формой, имеющей наименьший индекс простоты. В качестве индекса простоты наиболее часто используется индекс .

Пример.

Дата добавления: 2015-07-02