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

Элементарная конъюнкция называется конституэнтой единицы (минтермом) функции , если

.

Конституэнта единицы имеет такие свойства:

– конституэнта единицы равна 1 только на одном соответствующим ей слове;

– конъюнкция любого числа разных конституэнт единицы функции равна нулю.

/*Пример 9.1

Элементарная конъюнкция ― конституэнта единицы функции на слове 10:

Это подтверждается следующей таблицей истинности

.

Элементарная конъюнкция ― конституэнта единицы функции на слове 111, а конъюнкция ―на слове 110.При этом (свойство 3). */

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

Каждая булева функция, кроме константы 0, может быть представлена единственной СДНФ―результатом дизъюнктивного разложения (8.1) функции по всем переменным:

(9.1)

По этой формуле можно сформулировать такой алгоритм построения СДНФ булевой функции, представленной таблицей истинности.

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

2. Построить конституэнты единицы на этих словах.

3. Объединить полученные конституэнты единицы операцией дизъюнкции.

/*Пример 9.2

Булева функция задана таблицей истинности

.

Построить СДНФ этой функции.

Выполнение. Выбираем слова, на которых функция принимает значения единицы, и выписываем соответствующие конституэнты единицы:

010 ;

100 ;

101 .

Объединяем полученные конституэнты единицы операцией дизъюнкции и получим СДНФ заданной функции:

. */

Если булева функция задана формулой булевой алгебры, то построение СДНФ осуществляется по такому алгоритму.

1. Исключить константы. Для этого использовать законами действий з константами:

; ; ; .

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

; .

3. Построить ДНФ булевой функции, используя дистрибутивный закон

,

конъюнкции относительно дизъюнкции, законами идемпотентности

и

и законами действий с отрицанием

, .

4. Построить конституэнты единицы функции. Для этого ввести в каждую элементарную конъюнкцию отсутствующие переменные, используя тождество

.

5. Построить СДНФ булевой функции используя дистрибутивный закон и законы идемпотентности.

/*Пример 9.3

Построить СДНФ функции

.

Выполнение. Константы в формулу не входят и поэтому начинаем со 2 шага.

2 шаг. Опускаем отрицания на переменные:

.

3 шаг. Строим ДНФ:

.

4 шаг. Заданная функция зависит от трех переменных, поэтому в элементарные дизъюнкции вводим отсутствующие переменные:

5 шаг. Строим СДНФ:

.

В результате:

. */

Элементарной дизъюнкцией называется дизъюнкция любого числа булевых переменных, с отрицанием или без него, в котором каждая переменная встречается не больше одного раза. Константа 0 ― элементарная дизъюнкция, содержащая ноль переменных.

/* Пример 10.1

, , , ―примеры элементарных дизъюнкций. */

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

/*Пример 10.2

Формула

есть примером конъюнктивной нормальной формы (КНФ). */

Любая булева функция может быть представлена конъюнктивным разложением

(10.1)

Запись обозначает многократную конъюнкцию, которая берется для всех возможных наборов значений .

/*Пример 10.3

Записать конъюнктивное разложение функции

по переменным и

Выполнение. По формуле (9.1)

.

Вычислим:

;

;

:

.

Окончательно:

*/

/*Пример 10.4

Построить конъюнктивное разложение функции

по переменной

Элементарная дизъюнкция называется конституэнтой нуля (макстермом) функции , если .

Конституэнта нуля имеет такие свойства:

– конституэнта нуля равна нулю только на одном соответствующем слове,

– дизъюнкция любого числа различных конституэнт нуля функции равна единице.

/*Пример 11.1

Элементарная дизъюнкция ― конституэнта нуля функции на слове 01, так как

Элементарная дизъюнкция ― конституэнта нуля функции на слове 000, так как

Элементарная дизъюнкция ― конституэнта нуля функции на слове 101, так как

Дизъюнкция . */

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

Каждая булева функция, кроме константы 1, может быть представлена е динственной СКНФ, которая есть результатом конъюнктивного разложения (10.1) булевой функции по всем переменным:

.

По этой формуле можно сформулировать такой алгоритм построения СКНФ булевой функции, заданной таблицей истинности.

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

2. Построить конституэнты нуля на этих словах.

3. Объединить полученные конституэнты нуля операцией конъюнкции.

/*Пример 11.2

Булева функция задана таблицей истинности

.

Построить СКНФ этой функции.

Выполнение. Выбираем слова, на которых функция принимает значение 0, и выписываем соответствующие конституэнты нуля.

000 ,

001 ,

011 ,

110 ,

111 .

Объединяем конституэнты единицы операцией дизъюнкции и получаем СКНФ функции:

. */

Если булева функция задана формулой булевой алгебры, то построения СКНФ осуществляется по такому алгоритму.

1. Исключить константы. Для этого использовать законы действия с константами:

; ; ; .

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

; .

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

дизъюнкции относительно конъюнкции, законы идемпотентности

,

и законы действий с отрицанием

; .

4. Построить конституэнты нуля функции. Для этого ввести в каждую элементарную дизъюнкцию отсутствующие переменные, используя тождество

;

5. Построить СКНФ булевой функции. Для этого необходимо использовать дистрибутивный закон дизъюнкции относительно конъюнкции и законами идемпотентности.

/* Пример 11.3

Построить СКНФ функции

.

Выполнение. Константы в формулу не входят, и поэтому начнем со 2-го шага.

2 шаг. Опускаем отрицания на переменные:

.

3 шаг. Строим КНФ:

.

4 шаг. Заданная функция зависит от трех переменных, поэтому в элементарные конъюнкции вводимо отсутствующие переменные:

.

5 шаг. Раскрываем скобки и приводим подобные члены:

.

Окончательно:

. */