Материал: LS-Sb89586

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

ницы (рис. 2.3). Например, (a b)3 a3 3a2b 3ab2 b3 .

3.БУЛЕВЫ ФУНКЦИИ

3.1.Определение булевой функции и примеры булевых функций

Определение. Функцию от одной или нескольких переменных, аргументы и значение которой могут принимать только значения 0 или 1, называют булевой функцией (в честь английского математика Джорджа Буля (1815–1864), одного из основателей математической логики).

Примеры:

Конъюнкция: x y = 1 тогда и только тогда, когда x и y оба равны 1. Дизъюнкция: x y = 1 тогда и только тогда, когда x и y оба равны 1.

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

При этом значения наборов переменных располагают

если значения x и y совпадают);

симметрическая разность: xXORy (значение выражения равно 1, если зна-

чения x и y не совпадают);

импликация: x y (мнемоническое правило: из нуля следует что угодно –

иноль, и единица);

отрицание: x .

21

3.2. Приоритет булевых функций

Высший приоритет у отрицания. За ним идет конъюнкция. Далее – дизъюнкция, симметрическая разность, эквивалентность, импликация. Иногда, впрочем, для дополнительного уточнения конъюнкцию заключают в скобки.

3.3.Некоторые равенства о булевых функциях двух переменных

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

1.x y x y .

2.x y x y .

3.x y x y .

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

Для функции трех переменных таблица истинности содержит 8 строк. Например: f (x, y, z) (y x) (y z) .

ные примеры для не очень сложных функций – например, f (x, y, z)

(x y)XOR(y z).

3.5.Совершенные дизъюнктивная (СДНФ)

иконъюнктивная (СКНФ) нормальные формы

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

22

Для вычисления СКНФ и СДНФ пригодится табл. 3.3.

Правило построения СДНФ: выбрать те и только те строки, в которых значение функции равно 1, затем в этих строках записать конъюнкцию x, y, z

по следующему правилу: если соответствующая переменная равна 0, то пишем ее с отрицанием, если она равна 1, то пишем без отрицания.

Например, во второй строке пишем x y z , поскольку в соответствующей строке были значения x = 0, y = 0, z = 1.

СДНФ записывают как дизъюнкцию этих выражений. При этом иногда операцию конъюнкции не пишут, подобно тому как для умножения не пишут знак умножения, то есть, например, yz означает произведение y и z.

В итоге получаем: СДНФ = x yz x yz xyz xyz .

Построение СКНФ в некотором смысле двойственно к построению СКНФ: вместо строк со значением 1 берем строки со значением 0, вместо дизъюнкции – конъюнкцию, а вместо конъюнкции – дизъюнкцию. И существует принципиальное отличие: там, где значение переменной равно 0, она берется без отрицания, а там, где это значение равно 1, – с отрицанием. Сравните первую и третью строки, в которых стоят выражения x y z и

x y z соответственно.

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

ции: СКНФ = x y z x y z x y z x y z .

23

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

x yz x yz xyz xyz x x yz xy z z yz xy .

Итак, упрощенная форма СДНФ в данном случае равна yz xy .

Но, как во многих задачах на упрощение, возникает вопрос: можно ли упростить выражение дальше? Точнее сказать – можно ли получить выражение, содержащее еще меньше букв и равное данному?

Ответ дает метод минимизирующих карт.

Для его применения составьте табл. 3.4, аналогичную табл. 3.3.

Таблица 3.4

Каждую переменную (x, y и z) снабжаем или не снабжаем отрицанием в соответствии со значениями переменных. Например, если во втором столбце стоит 001, то x и y – с отрицанием, а z – без него.

В остальных столбцах переменные сопровождаются отрицаниями в соответствии с третьим, четвертым и пятым столбцами.

Теперь производим вычеркивание по следующему принципу.

Сначала вычеркиваем все строки, в которых значение функции равно нулю. В данном примере вычеркиваются строки с номерами 1, 3, 4 и 5.

Затем в каждом столбце, если элемент был один раз вычеркнут, он вычеркивается во всех оставшихся клетках столбца. Например, если во второй сверху

клетке шестого столбца элемент x y был вычеркнут, то в третьей сверху клетке его также вычеркнем.

Теперь из оставшихся элементов, взяв по одному элементу из строки, составим самое короткое выражение.

24

В данном примере из второй и шестой строк имеет смысл взять два одинаковых выражения yz , а из седьмой и восьмой строк – два одинаковых выражения xy, поскольку при вычислении дизъюнкции получим: yz yz xy xy yz xy .

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

Если преобразования дали такой же ответ, что и метод минимизирующих карт, это добавляет уверенности в ответе.

Если они дали ответ длиннее, то, видимо, возможности упрощения не до конца использованы.

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

3.6. Композиция функции от трех переменных, дизъюнкции и конъюнкции

В качестве упражнения на булевы функции можно рассматривать вычисление функции f (x, x y, xy), где f – функция от трех переменных.

Задачу можно решать двумя способами.

Первый способ: найти значения выражений x, x y, xy для всех значений пары x, y. Затем подставить полученные значения в функцию от трех переменных.

Например: если x = y = 0, то f (x, x y, xy) f (0,0,0) 0 (по табл. 3.2).

Дополнительное условие для этой задачи: по таблице истинности необходимо определить формулу для полученной функции от двух переменных. Например, xy или x XOR y.

Второй способ: подставить в исходную формулу для функции (например, f (x, y, z) (y x) (y z) ) вместо переменной y выражение x y , а вместо переменной z – выражение x y , а затем упростить выражение.

3.7. Многочлен Жегалкина

Многочлен Жегалкина – это представление булевой функции в виде арифметического выражения, а точнее – в виде многочлена

a0 a1x a2 y a3z a12xy a23yz a13xz a123xyz ,

25