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

Для упрощения изложения введем параметр и обозначение следующим образом.

,

(8.1)

В частности,

, , , .

Отсюда следует что

Непосредственно проверяется, что булеву функцию

можно записать в виде

. (8.2)

Введем необходимые понятия.

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

/*Пример 8.1

Формулы , ― элементарные конъюнкции, формулы , ― не элементарные конъюнкции.*/

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

/* Пример 8.2

Формула ― ДНФ. */

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

(8.3)

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

/*Пример 8.3

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

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

Выполнение.В этом случаи дизъюнктивное разложение (8.3) примет вид

.

Вычислим:

;

;

;

.

С учетом этого дизъюнктивное разложение заданной функции по переменным и запишется в виде

. */

/*Пример 8.4

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

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

Выполнение.В этом случаи формула (8.3) запишется как

.

Вычислим:

,

.

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

. */

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 5

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

по:

a) переменным и ;

b) переменной .

Выполнение.

a)

.

Вычислим:

;

;

;

.

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

.

b)

.

Вычислим:

;

.

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

.

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Вариант
1.	.
2.	.
3.	.
4.	.
5.	.
6.	.
7.	.
8.	.
9.	.
10.	.
11.	.
12.	.
13.	.
14.	.
15.	.
16.	.
17.	.
18.	.
19.	.
20.	.
21.	.
22.	.
23.	.
24.	.
25.	.

9. СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА БУЛЕВОЙ ФУНКЦИИ

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

.

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

– конституэнта единицы равна 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 шаг. Строим СДНФ:

.

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

. */

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 6

Упражнение 1. Построить СДНФ логической функции .

Выполнение.По номеру функции строим таблицу истинности

.

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

000 ,

011 ,

110 ,

111 .

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

.

Упражнение 2. Построить СДНФ функции

.

Выполнение.Преобразовываем логическую формулу в формулу булевой алгебры:

.

Это ДНФ функции. В каждую элементарную конъюнкцию вводим отсутствующие переменные и строим СДНФ функции:

.

В результате

.

Упражнение 3.Функция равная единицы на 9, 17, 56 словах. Построить СДНФ этой функции.

Выполнение.

9 00 1001

17 01 0001

56 11 1000

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Вариант			Номер слов
1.	124.	.	23, 45, 62.
2.	149.	.	7, 34, 49.
3.	137.	.	10, 25, 59.
4.	123.	.	21, 56, 60.
5.	175.	.	24, 34, 54.
6.	157.	.	17, 28, 45.
7.	187.	.	23, 56, 61.
8.	136.	.	12, 34, 57.
9.	201.	.	25, 46, 61.
10.	147.	.	0, 34, 53.
11.	188.	.	14, 56, 63.
12.	158.	.	17, 45, 55.
13.	173.	.	2, 29, 49.
14.	112.	.	5, 34, 57.
15.	138.	.	8, 45, 56.
16.	150.	.	9, 15, 61.
17.	125.	.	15, 38, 40.
18.	197.	.	12, 36, 58.
19.	158.	.	1, 6, 46.
20.	138.	.	4, 5, 57.
21.	123.	.	9, 23, 53.
22.	132.	.	13, 46, 51.
23.	148.	.	23, 37, 49.
24.	130.	.	25, 46, 55.
25.	175.	.	33, 56, 62.

10. КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ

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

/* Пример 10.1

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

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

/*Пример 10.2

Формула

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

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

(10.1)

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

/*Пример 10.3

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

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

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

.

Вычислим:

;

;

:

.

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

*/

/*Пример 10.4

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

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

Выполнение.

,

,

.

*/

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 7

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

по:

a) переменным и ;

b) переменной .

Выполнение.

а) По формуле (10.1)

.

Вычисляем:

;

;

;

.

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

.

b) По формуле (1)

.

Вычисляем:

,

.

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

.

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Вариант
1.	.
2.	.
3.	.
4.	.
5.	.
6.	.
7.	.
8.	.
9.	.
10.	.
11.	.
12.	.
13.	.
14.	.
15.	.
16.	.
17.	.
18.	.
19.	.
20.	.
21.	.
22.	.
23.	.
24.	.
25.	.

11. СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА БУЛЕВЫХ ФУНКЦИЙ

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

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

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

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

/*Пример 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 шаг. Раскрываем скобки и приводим подобные члены:

.

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

. */

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 8

Упражнение 1. Записать СКНФ булевой функции по ее номеру k.

Выполнение.Строим таблицу истинности, учитывая что

.

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

;

.

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

.

Упражнение 2. Записать СКНФ булевой функции

преобразованиями соответствующей логической формулы.

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

.

Константы в эту формулу не входят, отрицания опущены на переменные, поэтому начнем с 3-го шага:

.

Получили КНФ, в которой все элементарные дизъюнкции содержат все переменные, т. е. конституэнтами нуля. Это означает, что КНФ есть и СКНФ.

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

.

Упражнение 3.Функция равна 0 на 12, 18, 57 словах. Построить СДНФ этой функции.

Выполнение.

12 00 1100

18 01 0010

57 11 1001

.

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ