Несущественные переменные и равенство функций

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

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

Несущественные переменные удаляются следующим образом:

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

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

Пример

. Здесь обозначает остаток от деления на 2. Составим таблицу значений:

Строку 1 сравниваем со строками, в которых . Отмечаем элементы 2-го столбца строк 1 и 3. То же самое проделываем с остальными строками. Отмечаем элементы 2-го столбца строк 2 и 4, 5 и 7, 6 и 8. Поскольку все элементы столбца 2 отмечены, то – несущественная переменная. Вычеркивая второй столбец, получаем таблицу значений некоторой функции , равной :

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

и не имеет фиктивных элементов.