Властивості скороченої ДНФ

Скорочена ДНФ має деякі важливі властивості.

Теорема 8.29. Якщо скорочена ДНФ булевої функції не має жодної букви, яка входить до неї одночасно із запереченням і без заперечення, то ця форма є мінімальною ДНФ.

Доведення. До ДНФ f, яка не має жодної букви одночасно із запереченням і без заперечення, не можна застосувати рівносильність узагальненого склеювання. Це саме стосується диз'юнкції довільної кількості членів цієї форми. Якщо f - скорочена ДНФ, то їїможна відновити за допомогою узагальненого склеювання з мінімальної ДНФ, яка складає деяку частину f. Отже, у цьому випадку мінімальна ДНФ збігається із скороченою ДНФ. ▲

Теорема 8.30. Скорочена ДНФ монотонної функції f не має заперечень змінних.

Доведення. Нехайk_р- проста імпліканта функції f, що має заперечення змінних. Позначимо к кон'юнкцію всіх змінних, які входять вk_р без заперечень. Побудуємо набір значеньзмінних так: усім змінним, які входять вk, припишемо значення 1, арешті змінним - значення 0. Цілком очевидно, що імпліканта k_p, а, отже, і функція f перетворюються на цьому наборі в 1. З іншого боку, кон'юнкція k перетворюється в 1 лише на наборах (зокрема, і на наборі ).Але на всіх таких наборах функція f, за визначенням монотонності, також дорівнює 1.Отже, k-імплікантафункції f, а імплікантаk_р-не проста. Суперечність. ▲

Наслідок. Скорочена ДНФ монотонної функції є одночасно ймінімальною ДНФ цієї функції. ▲