Основні визначення

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

f₁(x₁,x₂,…,x_n)

f₂(x₁,x₂,…,x_n)

…

f_m(x₁,x₂,…,x_n)

У таблицях 31.1, 31.2, 31.3 показаний приклад системи булевих функцій.

Таблиця 31.1

				x2	x2
			x1	x1
			·
	x3|		·	·
x4|	x3|		·	·	·
x4|		·	·	·	·

 

Якщо мінімізувати кожну функцію окремо, то вийде перша система булевих функцій:

f₁ = x_{1`</sub>x<sub>2`}x₃ Ú _`x₁x₂

f₂ = _{`</sub>x<sub>2`}x₃ Ú _{`</sub>x<sub>1`}x₂ Ú x₁x₂x₃

f₃ = _`x₁ Ú x₂x₃

Складність системи ДНФ оцінюється сімома різними кон’юнкціями або 15 символами. Можна запропонувати іншу форму системи, побудовану з урахуванням того, що функції становлять єдину систему, складність якої оцінюється в чотири різних кон’юнкції, що містять 10 символів.

f₁ = x_{1`</sub>x<sub>2`}x₃ Ú _`x₁x₂

f₂ = _{`</sub>x<sub>1`}x₂ Ú x_{1`</sub>x<sub>2`}x₃ Ú x₁x₂x₃

f₃ = _{`</sub>x<sub>1`}x₂ Ú x₁x₂x₃ Ú _`x₁x₂

Визначення. Найкоротшою ДНФ системи булевих функцій називається така система ДНФ, що містить найменше число різних кон’юнкцій, що становлять ці ДНФ.

Визначення. Мінімальною ДНФ системи булевих функцій називається така система ДНФ, що містить найменше число символів, що становлять різні кон’юнкції ДНФ).

Кожна кон’юнкція крім складових її змінних характеризується тим, у ДНФ яких функцій ця кон’юнкція входить. Множина ДНФ, приписувана кожної кон’юнкції, називається її ярликом. Систему ДНФ можна однозначно представити списком кон’юнкцій з ярликами.

Для першої системи ДНФ виходить список

x_{1`</sub>x<sub>2`}x₃ /f₁, _{`</sub>x<sub>1</sub>x<sub>2</sub> /f<sub>1</sub>, <sub>`}x_{1`</sub>x<sub>2</sub> /f<sub>2</sub>, <sub>`}x_{2`</sub>x<sub>3</sub> /f<sub>2</sub>, x<sub>1</sub>x<sub>2</sub>x<sub>3</sub> /f<sub>2</sub>, <sub>`}x₁ /f₃, x₂x₃ /f₃.

Для другої системи ДНФ виходить список

x_{1`</sub>x<sub>2`}x₃ /f₁f₂, _{`</sub>x<sub>1</sub>x<sub>2</sub> /f<sub>1</sub>f<sub>3</sub>, x<sub>1</sub>x<sub>2</sub>x<sub>3</sub> /f<sub>2</sub>f<sub>3</sub>, <sub>`}x_1`x₂ /f₂f₃.

Визначення. Простою імплікантою системи булевих функцій називається така кон’юнкція з ярликом, в якої не можна скоротити саму кон’юнкцію або збільшити ярлик, оскільки тоді кон’юнкція перестає належати хоча б одній функції ярлика.

Для розглянутої другої системи булевих функцій простими імплікантами є всі перераховані в наведеному раніше списку для системи кон’юнкції з ярликами. Існує ще ряд простих імплікант - _{`</sub>x<sub>2`}x₃ /f₂, _{`</sub>x<sub>1</sub> /f<sub>3</sub>, x<sub>2</sub>x<sub>3</sub> /f<sub>3</sub>. Тобто, простими імплікантами системи є й <sub>`}x₁x₂ /f₁f₃, і _`x₁ /f₃. У першій з них більше ярлик, у другий менше символів у кон’юнкції, тобто більше відповідний інтервал булева простору.