![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Теорема Жегалкина
Каждая функция из Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:
Определение.Функция f(x1, ..., xn), полином Жегалкина для которой имеет следующий линейный относительно переменных вид: f = а0 Å а1х1 Å а2х2 Å ... Å аnхn, называется линейной. Лемма о нелинейной функции. Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию. Доказательство. Пусть f(x1, ..., xn) – нелинейная функция. Тогда полином Жегалкина содержит для нее слагаемое, в котором присутствует произведение xixj. Будем считать для простоты, что x1x2 в многочлене Жегалкина является этим произведением. Произведя группировку слагаемых, функцию f представим в виде Функция h0 не есть тождественный нуль, иначе в полиноме Жегалкина отсутствует слагаемое с произведением x1x2. Тогда существует набор (a3, …, an) из 0 и 1, для которого h0(a3, …, an) = 1. Пусть h1(a3, …, an) = a, h2(a3, …, an) = b, h3(a3, …, an) = c. Тогда Построим функцию:
Функция f(x1, ..., xn) сохраняет константу a Î {0, 1}, если f(a, …, a) = a. Пример 4. Функция xy сохраняет 0, сохраняет 1. Функция x®y сохраняет 1 и не сохраняет 0.
|