Совершенные нормальные формы

Совершенная дизъюнктивная нормальная форма. Элементарной конъюнкцией высказываний называется конъюнкция этих высказываний и их отрицаний.

Дизъюнктивной нормальной формой формулы А (ДНФ (Л)) называется дизъюнкция элементарных конъюнкций. Для любой формулы путем равносильных преобразований можно получить ДНФ, причем не единственную.

Совершенной дизъюнктивной нормальной формой формулы Л (СДНФ (Л)) называется дизъюнктивная нормальная форма формулы Л, удовлетворяющая следующим свойствам совершенства.

  • 1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.
  • 2. Все логические слагаемые формулы различны.
  • 3. Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.
  • 4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Правило построения СДНФ булевой функции с помощью таблиц истинности:

  • • выделяем строки, где формула принимает значение 1;
  • • составляем дизъюнкцию конъюнкций при условии, что если переменная входит в конъюнкцию со значением 1, то записываем эту переменную, если со значением 0, то ее отрицание.

Получаем СДНФ.

Совершенная конъюнктивная нормальная форма. Элементарной дизъюнкцией высказываний называется дизъюнкция этих высказываний и их отрицаний.

Конъюнктивной нормальной формой формулы А (КНФ (Л)) называется конъюнкция элементарных дизъюнкций.

Совершенной конъюнктивной нормальной формой формулы А (СКНФ (Л)) называется конъюнктивная нормальная форма формулы Л, удовлетворяющая следующим условиям.

  • 1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.
  • 2. Все логические слагаемые формулы различны.
  • 3. Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.
  • 4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Правило построения СКНФ булевой функции с помощью таблиц истинности:

  • • выделяем строки, где формула принимает значение 0;
  • • составляем конъюнкцию дизъюнкций при условии, что если переменная входит в дизъюнкцию со значением 0, то записываем эту переменную, если со значением 1, то ее отрицание.

Получаем СКНФ.

Пример 4.20. Следующую формулу привести к СДНФ:

Решение (табл. 4.18).

Таблица 4.18

Таблица истинности для решения примера 4.20

X

У

Z

“’2

л: v -«г

У ->*

(.Г V -2) -> -> 2)

1

1

1

0

1

1

1

1

1

0

1

1

0

0

1

0

1

0

1

1

1

1

0

0

1

1

1

1

0

1

1

0

0

1

1

0

1

0

1

1

0

0

0

0

1

0

0

1

1

0

0

0

1

1

1

1

Выделяем строки, где формула принимает значение 1, составляем дизъюнкцию конъюнкций и получаем СДНФ:

Пример 4.21. Следующую формулу привести к СКНФ двумя способами:

Решение (табл. 4.19).

Таблица 4.19

Таблица истинности для решения примера 4.21

X

У

Z

~*z

xv-*z

У —^ z

(х v -'z) -> (у -> г)

1

1

1

0

1

1

1

1

1

0

1

1

0

0

1

0

1

0

1

1

1

1

0

0

1

1

1

1

0

1

1

0

0

1

1

0

1

0

1

1

0

0

0

0

1

0

0

1

1

0

0

0

1

1

1

1

Для значений формулы, равных 0, составляем конъюнкцию дизъюнкций и получаем СКИФ:

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >