ДНФ і КНФ

Визначення 10.1. Змінна або її інверсія називається первинним термом імає узагальнене позначення:

(10.1)

Визначення 10.2. Формула виду

, (10.2)

де – двійковий набір, називається елементарною кон’юнкцією.

Визначення 10.3. Диз’юнктивною нормальною формою (ДНФ) називається диз’юнкція елементарних кон’юнкцій: .

Визначення 10.4. Формула виду

(10.3)

називається елементарною диз’юнкцією.

Визначення 10.5. Кон’юнктивною нормальною формою (КНФ) називається кон’юнкція елементарних диз’юнкцій: .

Булеву функцію, подану довільним логічним виразом, можна звести до ДНФ і КНФ шляхом застосування еквівалентних перетворень на основі законів булевої алгебри.

Приклад 10.1. Звести функцію до ДНФ і КНФ.

Розв’язок.

1. Щоб звести функцію до ДНФ, необхідно послідовно застосувати визначення операцій імплікації та еквівалентності, закони Де Моргана та дистрибутивності):

.

2. Застосування дистрибутивного закону до останнього виразу дає КНФ:

.