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

Функция f, зависящая от n переменных  называется булевой (или переключательной), если функция f и любой из ее аргументов  принимают значения только из множества {0,1}. Аргументы булевой функции также называются булевыми.

Способы задания булевой функции.

1. Таблицей истинности.

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

		...
0	0	0	0
0	0	...	1
...	...	...	...
1	1	1	1

Пример. Рассмотрим булеву функцию трех аргументов, называемую мажоритарной (или функцией голосования): она принимает значение 1 на тех и только тех наборах, в которых единиц больше, чем нулей (major – больший).

Ее таблица истинности будет иметь вид.

			f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2. Характеристическими множествами.

Так называются два множества:

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

, состоящее из всех наборов, на которых функция принимает значение 0, то есть ;

Пример (мажоритарная функция).

= {011,101,110,111}, = {000,001,010,100}.

3. Вектором ее значений.

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

Пример (мажоритарная функция).

00010111.

4. Единичным n – мерным кубом

В геометрическом смысле каждый двоичный набор есть n-мерный вектор, определяющий точку n-мерного пространства. Исходя из этого, все множество наборов, на которых определена функция n переменных, представляется вершинами n-мерного куба. Отмечая точками (или звездочками) вершины куба, в которых функция принимает единичные значения, получим геометрическое представление функции.

На рисунке 1 представлен общий вид n-мерного куба для 1, 2 и 3 переменных.

n=1	n=2	n=3

Рисунок 1 – Внешний вид единичного n – мерного куба.

Пример (мажоритарная функция).

5. Формулой алгебры логики.

Булева функция может быть задана формулой алгебры логики.

Если булева функция f и формула φ имеют одну и ту же таблицу истинности, то говорят, что формула φ представляет функцию f.

Такое представление не является единственным. Ниже будут рассмотрены различные способы представления булевых функций формулами. Один из них – нормальные формы.

Простой (элементарной) конъюнкцией или конъюнктом называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

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

Простой (элементарной) дизъюнкцией или дизъюнктом называется дизъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

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

Элементарная конъюнкция (дизъюнкция)

- правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);

- полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;

- монотонная, если она не содержит отрицаний переменных.

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

– конъюнкт

 – не является конъюнктом

– дизъюнкт

 – дизъюнкт и конъюнкт одновременно

– ДНФ

 – КНФ

Любую булеву функцию, заданную формулой алгебры логики с помощью элементарных преобразований можно привести к ДНФ и КНФ. Это представление не является единственным.

Алгоритм приведения формулы к ДНФ:

1. Выражают все логические операции в формуле через дизъюнкцию, конъюнкцию и отрицание.

2. Используя законы Де-Моргана, переносят все отрицания к переменным и сокращают двойные отрицания.

3. Используют закон дистрибутивности конъюнкции относительно дизъюнкции, преобразуют формулу так, чтобы все конъюнкции встречались раньше дизъюнкции.

Алгоритм приведения к КНФ аналогичен, только на шаге 3 делают так, чтобы все дизъюнкции встречались раньше конъюнкции.

Примеры выполнения типовых заданий.

Пример №1. Данную формулу с помощью равносильных преобразований привести к ДНФ и КНФ. Считая, что формула задает булеву функцию, задать ее с помощью таблицы истинности, вектора значений, характеристических множеств и единичного куба.

Решение.

Выразим все связки через  и :

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

Используем законы идемпотентности и противоречия:

 – ДНФ.

Для получения КНФ вернемся к первому шагу преобразований и применим закон дистрибутивности, но только во второй скобке:

 – КНФ.

Составим таблицу истинности для формулы:

Тогда вектор значений функции будет иметь вид:

10100011

Характеристические множества:

= {000,010,110,111}, = {001,011,100,101}.

Единичный куб будет иметь вид:

Задания для совместного решения.

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

1.

2.

3.

4.

Ответы:

	ДНФ	КНФ
1
2
3
4

Индивидуальные контрольные задания.

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

Практическая работа №4. Представление булевой функции в виде СДНФ и СКНФ.