Вопросы к зачету часть2 (Вопросы к зачету (ответы)), страница 6

Пусть теперь произвольная обратимая матрица размера над полем . Очевидно, . Положим и . Имеем , здесь вектора и определяют табличное задание (в лексикографическом порядке) отображений

Следовательно, задание двоичной функции может быть осуществлено заданием коэффициентов (вектор над полем ) в разложении функции относительно базисных функций со значением в поле .

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

Предварительно докажем вспомогательные утверждения.

Пусть и матрицы на полем . Матрица размера , полученная в результате замены каждого элемента матрицы на матрицу , т. е. называется тензорным (кронекеровым) произведением матриц и . Например, если , то

Из приведенного примера видно, что тензорное произведение некоммутативно.

Докажем самостоятельно следующие свойства тензорного произведения:

а) ассоциативность

б) дистрибутивность

в) .

Из свойства в) вытекает, что матрица обратима в том и только в том случае, когда обратимы матрицы и , причем выполняется свойство

с)

д) , где ,

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

где и все операции выполняются в поле .

Действительно, матрица имеет вид

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

Второе равенство докажите самостоятельно.

Используя данную лемму докажите следующее утверждение.

Теорема. Если , – матрицы на полем , то соответствующий матрице набор функций имеет вид , где

Пусть теперь – некоторая обратимая матрица над . Положим

(*)

где и .

а) Если , то по предыдущей теореме функции имеет вид

Таким образом, в этом случае разложение (*) является совершенной ДНФ функции функции .

б) Если , , , то

Поэтому разложение (*) совпадает с действительным многочленом функции .

в) Если , то . Следовательно, разложение (*) совпадает с многочленом Жегалкина функции .

г) , , . Имеем т. е. Разложение (*) в этом случае является разложением функции в ряд Фурье.

В качестве упражнения получите разложение псевдо – булевой функции . или

Представление двоичной функции в виде:

, где

Решение: