Специальные булевы функции

Рассмотрим следующие специальные булевы функции, на основе которых могут быть построены другие:

0, 1 – константы, могут рассматриваться как булевы функции от любого числа

переменных ;

– тождественная функция (или проекция );

– отрицание, обозначается также ;

– конъюнкция;

– дизъюнкция;

– сложение по модулю 2;

– стрелка Пирса;

~ – эквивалентность;

– импликация;

– штрих Шеффера.

Эти функции можно определить с помощью таблиц истинности:

x1	x2	&	Ú	Å	¯	~	®	|	Ø

Реализация функций формулами

Пусть – множество булевых функций. Понятие формулы над F определяется индуктивно:

1. Каждая переменная и каждая булева функция из F являются формулами над F.

2. Если – формулы над F, то для каждой функции из F выражение вида являются формулой над F.

Каждой формуле над F соответствует булева функция, которая называется интерпретацией этой формулы. Интерпретацию, как и формулу, можно определить индуктивно:

1. Интерпретация формулы сопоставляет элементу элемент .

2. Интерпретация формулы принимает значения , где функции дополняются, в случае необходимости, фиктивными переменными.

Пример

Пусть . Тогда , , и – формулы над F, ибо

Подставляя в формулы, получим значения интерпретаций этих формул.

Если интерпретацией формулы g является булева функция f, то формула g называется реализацией функции f. Две формулы называются равносильными, если их интерпретации равны.

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

Множество классов равносильных формул составляют булеву алгебру относительно операций:

& , Ú , Ø,

которая называется алгеброй Линденбаума – Тарского.

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

Совершенная дизъюнктивная нормальная форма

Теорема. Каждая булева функция реализуема с помощью формулы над .

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

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

Пример 1

Найдем СДНФ для функции . С этой целью составим таблицу истинности:

x1	x2	x1¯ x2

Поскольку лишь на элементе значение функции равно 1, то .

Конъюнктивная нормальная форма определяется как конъюнкция формул вида: . В силу равенств получаем соотношение:

.

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

Пример 2

Найдем СКНФ функции . Составим таблицу истинности:

x1	x2	x1® x2

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

Следствие. Системы функций являются полными.