Элементарные булевы функции

Элементарными булевыми функциями называются функции с арностью 0, 1 и 2. При этом нужно заметить, что множество функций двух переменных включают в себя все 0-местные и 1-местные функции, в описании которых присутствует две или одна фиктивная переменная соответственно. Множество всех элементарных булевых функций может быть представлено в виде таблицы, содержащей 4 строки и 16 столбцов. Каждый столбец определяет одну из элементарных булевых функций. Наиболее употребимыми являются двуместные функции: {&,,,,,,}, одноместные функции f(x)=x и f(x)=x, и две 0-местные функции: константа 0 и константа 1, не имеющие ни одной существенной переменной (других таких функций в множестве элементарных булевых функций нет).

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

• Пропозициональная переменная есть формула.

• Если А и В формулы, то любое слово АВ – формула, если {&,,,,,,}. Слово А также является формулой.

• Других формул нет.

Для формулы может быть построена таблица истинности, которая является ее интерпретацией. Говорят, что пропозициональная формула задает булеву функцию. Соответственно, булева функция реализует ту формулу, которая задает функцию. Очевидно, формула задает единственную булеву функцию. Обратное не справедливо.

Формулы, определяемые суперпозицией функций, могут преобразовываться как алгебраические выражения с использованием множества аксиом и тождеств. Основными из них являются аксиомы тождественности (идемпотентности), коммутативности, ассоциативности, дистрибутивности, поглощения, закон двойного отрицания, правило де-Моргана. Целью преобразования формул является приведение их к каноническому виду. В теории булевых функций используются канонические представления: дизъюнктивная нормальная форма (ДНФ), конъюнктивная нормальная форма (КНФ), полиномиальная нормальная форма. (ПНФ). Для выполнения преобразований используется правило подстановки, которое формулируется следующим образом: если формула образована суперпозицией функций над некоторым множеством функций, то замена вхождения какой-либо функции на равносильную ей не меняет логическое значение функции. Это можно представить как , если с точностью до фиктивных переменных.

Теорема Шеннона о разложении булевых функций по переменным

Первичным термом называется функция

Здесь - пропозициональная переменная, - пропозициональная константа.

Свойства первичного терма:

• ,

• .

Функция называется элементарной конъюнкцией ранга r. Функция называется элементарной дизъюнкцией ранга r. Элементарная конъюнкция ранга n над множеством всех n переменных называется минтермом или конституентой единицы. Элементарная дизъюнкция ранга n над множеством всех n переменных называется макстермом или конституентой нуля.

Произвольная булева функция n переменных может быть представлена разложением по любому числу переменных в следующем виде:

.

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

Одним из следствий этой теоремы является разложение булевой функции по всем переменным:

.

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

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

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

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

Теорема Произвольная булева функция может быть представлена суперпозицией формул над множеством связок {&, , }.

Действительно, если функция не равна тождественно 0 или 1, ее можно представить в СДНФ или в СКНФ. Если функция есть константа 0, ее можно представить как или как , т.е формулой над тем же множеством связок. Формула над множеством связок {&, , } называется булевой формулой.

Кроме двух указанных формул в теории булевых функций используется также совершенная полиномиальная нормальная форма, представляющая собой сумму по модулю 2 всех конституент единицы данной функции.

Например, для трехместной булевой функции, заданной вектором ,совершенные нормальные формы имеют вид:

СДНФ= ;

СКНФ= ;

СПНФ=(0,2,3,5,7)= .