2. Существенные и фиктивные переменные.

Переменная ( ) булевой функции называется фиктивной, если имеет место равенство

для любых значений переменных . В противном случае переменная называется существенной. Наборы значений переменных в последнем равенстве называются соседними по переменной .

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

Пусть БФ задана таблично и пусть x_k является несущественной переменной. Тогда для исключения этой переменой необходимо выполнить следующие действия:

1. вычеркнуть столбец, содержащий эту переменную;

2. вычеркнуть все строки таблицы, в которых x_k=1.

Аналогичным образом можно при необходимости ввести фиктивные переменные в состав БФ.

Критерий несущественности переменной.

Разобьем столбец значений БФ на равные отрезки длиной 2^n-k+1, где n – арность функции, k – номер переменной. Если для каждого такого отрезка значения в его верхней половине совпадают со значениями в нижней половине, то переменная x_k – фиктивная. В противном случае она является существенной.

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

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

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

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

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

Пример 1.

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

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

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

Пример2.

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

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

Пример 3.

f₁ = x₁ x₂ (конъюнкция)_; f₂ = (отрицание).

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

1) f = f₁(f₂) = ( ₁) ( ₂) – конъюнкция отрицаний;

2) f = f₂(f₁) = ( ) – отрицание конъюнкции.

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

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

Пример 4.

Построим таблицу значений функции f(x₁, x₂, x₃) = ( ) ~ ( ₁ x₂).

Таблица 9

x1 x2 x3	3	x2  3	( )	1	1 x2	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

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