Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Дискретная математика для 1 курса.docx
Скачиваний:
276
Добавлен:
09.04.2015
Размер:
647.83 Кб
Скачать

Тема 4. Булевы функции

4.1. Определение булевой функции

Определение 4.1. Булевой функцией f(x1, x2, ... , xn) называется произвольная функция n переменных, аргументы которой x1, x2, ... , xn и сама функция f принимают значения 0 или 1, т. е. xi {0, 1},i = 1, 2, ... , n; f(x1, x2, ... , xn) {0, 1}.

Одной из важнейших интерпретаций теории булевых функций является теория переключательных функций. Первоначально математический аппарат теории булевых функций был применен для анализа и синтеза релейно-контактных схем с операциями последовательного и параллельного соединения контактов. Подробнее это приложение теории булевых функций будет рассмотрено в разделе 4.9.

Любая булева функция может быть представлена таблицей, в левой части которой перечислены все наборы переменных (их 2n), а в правой части – значения функции. Пример такого задания представлен в таблице 4.1.

Таблица 4.1

x1 x2 x3

f(x1, x2, x3)

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

0

0

0

1

0

1

1

1

Для формирования столбца значений переменных удобен лексико-графический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100 = 011+ 1.

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

Функций одной переменной – 4. Из них выделим функцию “отрицание x”(обозначается x). Эта функция представлена в таблице 4.2.

Таблица 4.2

x

x

0

1

1

0

Булевых функций двух переменных – 16 (22при n = 2). Те из них, которые имеют специальные названия, представлены в таблице 4.3.

Таблица 4.3

x1 x2

x1Vx2

x1& x2

x1x2

x1~x2

x1 x2

x1¯ x2

x1ï x2

0 0

0 1

1 0

1 1

0

1

1

1

0

0

0

1

1

1

0

1

1

0

0

1

0

1

1

0

1

0

0

0

1

1

1

0

В таблице 4.3 представлены следующие функции двух переменных:

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

x1& x2 конъюнкция;

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

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

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

x1¯x2 стрелка Пирса;

x1ï x2 штрих Шеффера.

Остальные функции специальных названий не имеют и могут быть выражены через перечисленные выше функции.

4.2. Формулы логики булевых функций

Определение 4.2. Формула логики булевых функций определяется индуктивно следующим образом:

1. Любая переменная, а также константы 0 и 1 есть формула.

2. Если A и B – формулы, то A, AVB, A&B, A B, A ~ B есть формулы.

3. Ничто, кроме указанного в пунктах 1–2, не есть формула.

Пример 4.1.

Выражение (xVy)&((y z) ~ x) является формулой.

Выражение x&y z  ~x не является формулой.

Часть формулы, которая сама является формулой, называется подформулой.

Пример 4.2.

x&(yz) – формула; yz – ее подформула.

Определение 4.3. Функция f есть суперпозиция функций f1, f2, ... , fn если f получается с помощью подстановок этих формул друг в друга и переименованием переменных.

Пример 4.3.

f1 = x1&x2 (конъюнкция); f2 = x (отрицание).

Возможны две суперпозиции:

1) f = f1(f2) = (x1)&(x2) – конъюнкция отрицаний;

2) f = f2(f1) = (x1&x2) – отрицание конъюнкции.

Порядок подстановки задается формулой.

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

Пример 4.4.

Построим таблицу значений функции f(x1, x2, x3) = (x2 x3) ~ (x1Vx2).

Таблица 4.4 представляет последовательное вычисление этой функции.

Таблица 4.4

x1 x2 x3

x3

x2 x3

(x2 x3)

x1

x1Vx2

f(x1, x2, x3)

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

1

0

1

0

1

0

1

0

1

1

1

0

1

1

1

0

0

0

0

1

0

0

0

1

1

1

1

1

0

0

0

0

1

1

1

1

0

0

1

1

0

0

0

1

1

1

0

1

Таким образом, формула каждому набору аргументов ставит в соответствие значение функции. Следовательно, формула так же, как и таблица, может служить способом задания функции. В дальнейшем формулу будем отождествлять с функцией, которую она реализует. Последовательность вычислений функции задается скобками. Принято соглашение об опускании скобок в соответствии со следующей приоритетностью операций: , &, V, и ~.