Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Теорема Жегалкина




Читайте также:
  1. II закон термодинамики. Теорема Карно-Клаузиуса
  2. II. (Теорема Больцано-Вейерштрасса).
  3. Б) теория фирмы и транзакционных издержек. Теорема Р.Г.Коуза (1910)
  4. Движение тела в неинерциальных системах отсчета. Теорема Кориолиса. Силы инерции.
  5. Занятие 3. Условная вероятность. Теорема умножения вероятностей.
  6. Занятие 4. Теорема сложения вероятностей.
  7. Интегральная теорема Муавра – Лапласа.
  8. Кинетическая энергия тела, системы тел при их поступательном движении. Теорема о кинетической энергии. Теорема Кенига.
  9. Кодирование источника. Теорема Шеннона для канала без помех. Эффективные коды, принципы эффективного кодирования.
  10. Консервативные силы и потенциальные поля. Потенциальная энергия тела. Теорема о потенциальной энергии.

 

Каждая функция из может быть представлена в виде полинома Жегалкина единственным образом.

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:

, s = 0, 1, ..., n. Доказательство. Любая функция из Р2 может быть представлена формулой над {x1 & x2, x1Å x2, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции f(x1, ..., xn) от n переменных. Мы знаем, что всего таких функций, т.е. их таблиц истинности , 2n. Подсчитаем число различных полиномов Жегалкина от n переменных, т.е. число вариаций вида: . Число наборов равно числу всех подмножеств множества { x1, ..., xn }, сюда входит и пустое множество (если s = 0). Число подмножеств множества из n элементов равно 2n , а так как каждый набор входит с коэффициентом , принимающим два значения: 0 или 1, то число всевозможных полиномов будет . Так как каждому полиному соответствует единственная функция, число функций от n переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.

Определение.Функция 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. Тогда

Построим функцию:

где d = ab Å c. Если d = 0, то h(x1, x2) = x1x2. Если d = 1, то h(x1, x2) = x1x2 Å 1 и тогда Лемма доказана.

Функция f(x1, ..., xn) сохраняет константу a Î {0, 1}, если f(a, …, a) = a.



Пример 4. Функция xy сохраняет 0, сохраняет 1. Функция x®y сохраняет 1 и не сохраняет 0.


Дата добавления: 2014-11-13; просмотров: 20; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты