2015-06-28
351
У більшості додатків використовуються не окремі булеві функції, а системи вигляду
f1(x1,x2,…,xn)
f2(x1,x2,…,xn)
…
fm(x1,x2,…,xn)
У таблицях 31.1, 31.2, 31.3 показаний приклад системи булевих функцій.
Таблиця 31.1
| x2 | x2 | ||||
| x1 | x1 | ||||
| · | |||||
| x3| | · | · | |||
| x4| | x3| | · | · | · | |
| x4| | · | · | · | · |
Якщо мінімізувати кожну функцію окремо, то вийде перша система булевих функцій:
f1 = x1`x2`x3 Ú `x1x2
f2 = `x2`x3 Ú `x1`x2 Ú x1x2x3
f3 = `x1 Ú x2x3
Складність системи ДНФ оцінюється сімома різними кон ’ юнкціями або 15 символами. Можна запропонувати іншу форму системи, побудовану з урахуванням того, що функції становлять єдину систему, складність якої оцінюється в чотири різних кон ’ юнкції, що містять 10 символів.
f1 = x1`x2`x3 Ú `x1x2
f2 = `x1`x2 Ú x1`x2`x3 Ú x1x2x3
f3 = `x1`x2 Ú x1x2x3 Ú `x1x2
Визначення. Найкоротшою ДНФ системи булевих функцій називається така система ДНФ, що містить найменше число різних кон’юнкцій, що становлять ці ДНФ.
Визначення. Мінімальною ДНФ системи булевих функцій називається така система ДНФ, що містить найменше число символів, що становлять різні кон’юнкції ДНФ).
|
|
|
Кожна кон ’ юнкція крім складових її змінних характеризується тим, у ДНФ яких функцій ця кон ’ юнкція входить. Множина ДНФ, приписувана кожної кон ’ юнкції, називається її ярликом. Систему ДНФ можна однозначно представити списком кон ’ юнкцій з ярликами.
Для першої системи ДНФ виходить список
x1`x2`x3 /f1, `x1x2 /f1, `x1`x2 /f2, `x2`x3 /f2, x1x2x3 /f2, `x1 /f3, x2x3 /f3.
Для другої системи ДНФ виходить список
x1`x2`x3 /f1f2, `x1x2 /f1f3, x1x2x3 /f2f3, `x1`x2 /f2f3.
Визначення. Простою імплікантою системи булевих функцій називається така кон’юнкція з ярликом, в якої не можна скоротити саму кон’юнкцію або збільшити ярлик, оскільки тоді кон’юнкція перестає належати хоча б одній функції ярлика.
Для розглянутої другої системи булевих функцій простими імплікантами є всі перераховані в наведеному раніше списку для системи кон ’ юнкції з ярликами. Існує ще ряд простих імплікант - `x2`x3 /f2, `x1 /f3, x2x3 /f3. Тобто, простими імплікантами системи є й `x1x2 /f1f3, і `x1 /f3. У першій з них більше ярлик, у другий менше символів у кон ’ юнкції, тобто більше відповідний інтервал булева простору.
