Алгоритм побудови ДНФ

1) Позбутися від всіх логічних операцій, що містяться у формулі, замінивши їх основними: кон'юнкція, диз'юнкція, запереченням. Це можна зробити, використовуючи рівносильні формули:

A → B = ך AvB A⇔B = (A ^ B) v (ך Av ך B)

2) Замінити знак заперечення, що відноситься до всього висловом, знаками заперечення, що відносяться до окремих змінним висловлювань на підставі формул:

ך (AvB) = ך A ^ ך B ך (A ^ B) = ך Av ך B

3) Позбутися від знаків подвійного заперечення.

4) Застосувати, якщо потрібно, до операцій кон'юнкції і диз'юнкції властивості дистрибутивности і формули поглинання.

Приклад побудови ДНФ

Наведемо до ДНФ формулу: F = ((X → Y) ↓ ך (Y → Z))

Висловимо логічні операції → і ↓ через: v ^ ך

F = ((ך XvY) ↓ ך (ך YvZ)) = ך ((ך XvY) v ך (ך YvZ))

В отриманій формулі перенесемо заперечення до змінних і скоротимо подвійні заперечення:

F = ך ((ך XvY) v ך (ך YvZ)) = (ך ך X ^ ך Y) ^ (ך YvZ) = (X ^ ך Y) ^ (ך YvZ)

Використовуючи закон дистрибутивности, наводимо формулу до ДНФ:

Кон'юнктивна нормальна форма (КНФ) в булевої логіки - нормальна форма, в якій булева формула має вигляд кон'юнкції діз'юнкційлітералов. Кон'юнктивна нормальна форма зручна для автоматичного доведення теорем. Будь-яка булева формула може бути приведена до КНФ. Для цього можна використовувати: Закон подвійного заперечення, Закон де Моргана, Дистрибутивність.

Приклади і контр приклади

ך A ^ (BvC) (AvB) ^ (ך BvCv ך D) ^ (Dv ך E) A ^ B

Формули не в КНФ:

ך (BvC) (A ^ B) vC A ^ (Bv (D ^ E))

Але ці 3 формули не в КНФ еквівалентні такими формулами в КНФ:

ך B ^ ך C (AvC) ^ (BvC) A ^ (BvD) ^ (BvE)

Алгоритм побудови КНФ

1) Позбутися від всіх логічних операцій, що містяться у формулі, замінивши їх основними: кон'юнкція, диз'юнкція, запереченням. Це можна зробити, використовуючи рівносильні формули:

A → B = ך AvB A↔B = (A ^ B) v (ך A ^ ך B)

2) Замінити знак заперечення, що відноситься до всього висловом, знаками заперечення, що відносяться до окремих змінним висловлювань на підставі формул:

ך (AvB) = ך A ^ ך B ך (A ^ B) = ך Av ך B

3) Позбутися від знаків подвійного заперечення.

4) Застосувати, якщо потрібно, до операцій кон'юнкції і диз'юнкції властивості дистрибутивности і формули поглинання.

Приклад побудови КНФ

Наведемо до КНФ формулу

Перетворимо формулу F до формули яка не містить →:

F = (ך XvY) ^ (ך (ך Y → Z) v ך X) = (ך XvY) ^ (ך (ך ך YvZ) v ך X)

В отриманій формулі перенесемо заперечення до змінних і скоротимо подвійні заперечення:

F = (ך XvY) ^ ((ך Y ^ ך Zv ך X) = (ך XvY) ^ ((ך Y ^ ך Z) v ך X)

Згідно із законом дистрибутивности отримаємо КНФ:

F = (ך XvY) ^ (ך Xv ך Y) ^ (ך Xv ך Z)

k -кон'юнктівной нормальною формою називають кон'юнктівную нормальну форму, в якій кожна диз'юнкція містить рівно k литералов.

Наприклад, наступна формула записана в 2-КНФ:

(AvB) ^ (ך BvC) ^ (Bv ך C)

Перехід від КНФ до СКНФ

Якщо в простій диз'юнкції не вистачає якоїсь змінної (наприклад, z), то додаємо в неї вираз. (Це не змінює самої диз'юнкції), після чого розкриваємо дужки з використанням розподільного закону:

(XvY) ^ (Xv ך Yv ך Z) = (XvYv (Z ^ ך Z)) ^ (Xv ך Yv ך Z) = (XvYvZ) ^ (XvY v ך Z) ^ (Xv ך Yv ך Z)

Таким чином, з КНФ отримана СКНФ.

Перехід від КНФ до СКНФ

Якщо в простій диз'юнкції не вистачає якоїсь змінної (наприклад, z), то додаємо в неї вираз: Z ^ ך Z = 0 (це не змінює самої диз'юнкції), після чого розкриваємо дужки з використанням розподільного закону:

(XvY) ^ (Xv ך Y ך Z) = (XvYv (Zv ך Z)) ^ (Xv ך Yv ך Z) = (XvYvZ) ^ (XvYv ך Z) ^ (Xv ך Yv ך Z) Таким чином, з КНФ отримана СКНФ.

25. Вчинені диз'юнктивні і кон'юнктівние нормальні форми і алгоритми приведення до них. Приклади.

Досконала кон'юнктивна нормальна форма (СКНФ) - це така кон'юнктивна нормальна форма. яка задовольняє трьом умовам:

в ній немає однакових елементарних диз'юнкцій

в кожній диз'юнкції немає однакових пропозіціональних змінних

кожна елементарна диз'юнкція містить кожну пропозіціональному букву з вхідних в дану КНФ пропозіціональних букв.

k -кон'юнктівной нормальною формою називають кон'юнктівную нормальну форму, в якій кожна диз'юнкція містить рівно kлітералов.

Наприклад, наступна формула записана в 2-КНФ:

Досконала діз'юнктівная нормальна форма (СДНФ) - це така ДНФ. яка задовольняє трьом умовам:

в ній немає однакових елементарних кон'юнкція

в кожній кон'юнкції немає однакових пропозіціональних букв

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

Для будь-якої функції алгебри логіки існує своя СДНФ, причому єдина.

Для того, щоб отримати СДНФ функції, потрібно скласти її таблицю істинності. Наприклад, візьмемо одну з таблиць істинності: