yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->1. 9 Минимизация булевых функций.

Математическая логика

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

Определение 1. 24. Импликантой булевой функции  f(x1,...,xn) называется

такая булева функция g(x1..,xn), которая равна единице на некоторых из тех

наборов,   на   которых   равна   единице   и   данная   функция.   Говорят,   что

импликанта   g   покрывает  своими   единицами   некоторые   единицы   данной

функции t.

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

xy  ¬xy=xy  ¬xyy                                           (закон неполного склеивания)          (1-20) xy¬xz=xy¬xzyz   (закон полного склеивания) (1-21) xxy=x (законы поглощения) (1.22) x¬xy=xy (1.23) x(xy)=x                                                                                                                                    (1.24)

Пример. Упростим формулу:

f=xyzx¬yzxy¬z¬xy¬z=xyzx¬yzxzxy¬z

Определение 1.25. Элементарное произведение, которое является импликантой функции f, но никакая его собственная часть импликантой этой функции не является, называется простой импликантой данной функции.

Длина простой импликанты уже не может быть уменьшена путем склеивания ее с другими импликантами данной функции.

Определение 1.26. Дизъюнкция всех простых импликант булевой функции называется сокращенной дизъюнктивной нормальной формой

булевой функции.

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

1,10. Метод Квайна получения  сокращенной  дизъюнктивной, нормальной формы.

Теорема 1.10. (Квайна). Если в совершенной дизъюнктивной нормальной форме булевой функции произвести все операции неполного склеивания (1.20), а затем все операции поглощения, то в результате получится сокращенная ДНФ данной функции.

Для преобразовании произвольной ДНФ к виду СДНФ необходимо применить к элементарным конъюнкциям, содержащим не асе переменные, операцию развертывания: xy(z¬z)=xyzxy¬z, .где z – недостающая переменная.

Пример. Булева функция задана и виде: f=xyzx¬y¬z¬yz. Приведем формулу к СДНФ: f=¬xyzx¬y¬z¬yz(x¬x)=¬xyzx¬y¬zx¬yz¬x¬z. Выпишем все конституенты единицы и произведем все операции неполного склеивания :

·         ¬xyz                       ¬yz

·         x¬yz                       x¬y

·         ¬x¬yz                     ¬xz

Отмечаем все склеивающиеся конъюнкции. Они поглощаются импликантами, полученными в результате склеивания. Неотмеченные конъюнкции ничем не поглощаются и являются простыми импликантами. Сокращённая ДНФ данной функции:

f = ¬yzx¬y¬xz.

 

Глава 2. АЛГЕБРА ВЫСКАЗЫВАНИЙ

 

 

12