Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Досконала кон’юнктивна нормальна форма булевих функцій



Елементарна диз’юнкція називається конституентою нуля (макстермом) функції , якщо .

Конституента нуля має такі властивості.

1. Конституента нуля дорівнює нулю тільки на одному відповідному слові.

2. Конституента нуля однозначно визначається номером відповідного їй слова.

3. Диз’юнкція будь-якого числа різних конституент нуля функції дорівнює одиниці.

Приклад 1. Елементарна диз’юнкція є конституантою нуля функції на слові 01, оскільки

Елементарна диз’юнкція є конституентою нуля функції на слові 000, оскільки

Елементарна диз’юнкція є конституантою нуля функції на слові 101, оскільки

Диз’юнкція .

Досконалою кон’юктивною нормальною формою (ДКНФ) називають кон’юнкція конституент нуля.

Кожна булева функція, крім константи 1, може бути подана єдиною ДКНФ,яка є результатом кон’юнктивного розкладу (1, п. 10) булевої функції за всіма змінними:

.

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

1. Вибрати всі слова, на яких задана функція приймає значення 0.

2. Побудувати конституенти нуля на цих вибраних словах.

3. Об’єднати одержані конституенти нуля операцією кон’юнкції.

Приклад 2.Булева функція задана таблицею істинності

Побудувати ДКНФ для цієї функції.

Виконання. Вибираємо слова, на яких задана функція набуває значення 0 і виписуємо відповідні конституенти нуля.

000 ,

001 ,

011 ,

110 ,

111 .

Об’єднуємо одержані конституанти одиниці операцією диз’юнкції і одержуємо ДКНФ заданої функції:

.

 

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

1. Виключити константи. Для цього скористатися законами дій з константами:

; ; ; .

2. Опустити знаки заперечення на змінні. Для цього скористатися законами де Моргана:

; .

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

диз’юнкції відносно кон’юнкції, закони ідемпотентності

,

і закони дій із запереченням

; .

4. Побудувати конституенти нуля функції. Для цього ввести в кожну елементарну диз’юнкцію відсутні змінні використовуючи рівність

;

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

Приклад 2. Побудувати ДКНФ функції

.

Виконання. Константи у формулу не входять і тому починаємо з 2 кроку.

2 крок. Опускаємо заперечення на змінні:

.

3 крок. Будуємо КНФ:

.

4 крок: Задана функція залежить від трьох змінних, тому до елементарних кон’юнкцій вводимо відсутні змінні:

.

5 крок: Розкриваємо дужки і зводимо подібні члени

.

Отже, ДКНФ заданої функції .




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.