За допомогою рівносильних перетворень

Алгоритм знаходження ДДНФ (ДКНФ) для даної булевої функції

1) Позбавитися у формулі від входжень знаків всіх логічних зв'язок, крім ;

2) Користуючись законами де Моргана, добитися того, щоб знак стояв тільки перед змінними;

3) Поповнити елементарні кон’юнкції (диз’юнкції) до повних так: якщо змінна не входить у формулу , то оскільки (), то ();

4) Користуючись законами ідемпотентності, з однакових членів отриманої диз’юнкції (кон’юнкції) залишити тільки один.

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

Розв’язання: Знайдемо ДДНФ:

– позбавимося у формулі від входження знаків та :

– користуючись законом де Моргана, доб'ємося того, щоб знак стояв тільки перед змінними:

– отримали ДНФ, елементарні кон’юнкції якої поповнимо до повних:

– отримали ДДНФ.

Знайдемо ДКНФ:

………………………………

– отримали ДНФ, з якої за дистрибутивністю отримаємо КНФ:

поповнимо елементарні диз’юнкції до повних:

– отримали ДКНФ.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Алгоритм знаходження ДДНФ (ДКНФ) для даної булевої функції	\|	Повні системи булевих функцій

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.