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

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

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

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

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

Пример. Построим таблицу значений функции f (x ₁, x ₂, x ₃) = Ø(x ₂ Ø x ₃) ~ (Ø x ₁Ú x ₂). Табл. 3 представляет последовательное вычисление этой функции.

                                                                                         Таблица 3

x 1 x 2 x 3	x 3	x 2 x 3	(x 2 x 3)	x 1	x 1 V x 2	f (x 1,   x 2, x 3)
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

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

а) вначале выполняются операции в скобках (внешние скобки у формул опускаются);

б) считается, что связка Ø сильнее любой двухместной связки;

в) связка & сильнее любой другой двухместной связки.

Кроме того, имея в виду стандартное расположение наборов, булеву функцию f() удобно задавать вектором ее значений: _f = (α₀, α₁, …, ), где координата α _i равна значению функции f() на наборе , имеющем номер i (i = 0, 1, …, 2 ⁿ   – 1).

Фиктивные и существенные переменные

Фиктивные переменные. Переменная x _i (1 £ i £ n) функции f(x ₁, …, x_n) называется фиктивной переменной, если значение функции не зависит от значения этой переменной, т. е. для любых значений переменных x₁, …, x _i-1, x _i+1,..., x _n

 f(x ₁, …, x _i-1, 0, x _i+1, …, x _n) = f(x ₁, …, x _i-1, 1, x _i+1, …, x _n).

Переменная x _i (1£ i £ n) функции f(x ₁, …, x _n) называется существенной переменной, если можно указать наборы  и , соседние по i -ой компоненте, что f() ¹ f(), т. е. f(a ₁, …, a _i-1, 0, a _i+1, …, a _n) ¹ f(a ₁, …, a _i-1, 1, a _i+1, …, a _n).

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

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

Пример. Функции f1 = x Å y, f2 = x y Å z, f3 = x Å y Å z Å 1, f4 = xy Å yz Å zx, реализованные формулами, задать векторами своих значений.

Решение. 1. Составим вначале таблицу истинности для f1, f2, f3, f4 (табл. 4).

Таблица 4

(x, y, z)			f1	f3	Xy	f2	yz	zx	f4
0	0	0	0	1	0	0	0	0	0
0	0	1	0	0	0	1	0	0	0
0	1	0	1	0	0	0	0	0	0
0	1	1	1	1	0	1	1	0	1
1	0	0	1	0	0	0	0	0	0
1	0	1	1	1	0	1	0	1	1
1	1	0	0	1	1	1	0	0	1
1	1	1	0	0	1	0	1	1	1

2. Тогда функции f1, f2, f3, f4 задаются следующими векторами своих значений: f1() = (0, 0, 1, 1, 1, 1, 0, 0); f2() = (0, 1, 0, 1, 0, 1, 1, 0);

f3() = (1, 0, 0, 1, 0, 1, 1, 0); f4() = (0, 0, 0, 1, 0, 1, 1, 1).

3. f₂ ¹ f₄, т. к. (0, 1, 0, 1, 0, 1, 1, 0) ¹ (0, 0, 0, 1, 0, 1, 1, 1) (в таблице не совпадают значения в столбцах, соответствующих этим функциям).

4. Выписываем f(0, 0, 0) = f(0, 1, 1) = f(1, 0, 1) = f(1, 1, 0) = 1 и

f(0, 0, 1) = f(0, 1, 0) = f(1, 0, 0) = f(1, 1, 1) = 0. Определим, какой переменной является x. Сравнивая значения функции на всех парах наборов, соседних по переменной x, видим, что f(0, y, z)¹ f(1, y, z), x – существенная переменная. Аналогично устанавливаем, что у и z являются существенными переменными.