double arrow

Основні визначення. У більшості додатків використовуються не окремі булеві функції, а системи вигляду


У більшості додатків використовуються не окремі булеві функції, а системи вигляду

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. У першій з них більше ярлик, у другий менше символів у конюнкції, тобто більше відповідний інтервал булева простору.


Сейчас читают про: