Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2017-11-22 | 311 |
5.00
из
|
Заказать работу |
|
|
Алгебра Буля – частный случай булевых алгебр и кроме него существует бесконечное число булевых алгебр.Одна из них – алгебра Жегалкина.
Это к-значная алгебра вида: А = < М, Å, & >
Она подчиняется следующим законам:
х Å у = у Å х
х (у Å z) = xy Åxz
х Å х =Æ Любую булеву функцию можно представить с помощью алгебры Жегалкина.
Например:
Операция отрицания: = х Å 1
Операция сложения: х + у = = (х Å 1)(у Å 1) Å 1 = ху Å х Å у Å 1 Å Å 1 = ху Å х Å у
следовательно, исходя из теоремы Шинона, через операции сложения по mod 2 (Å) и конъюнкции (&) может быть выражена любая функция.
f(х1,х2,х3) = х1 2х3 + 1х3 = x2 1х3 & 1х3 = (х1х3(х2 Å 1) Å 1) & (х3(х1 Å 1)) Å 1 =(х1х2х3 Å х1х3 Å 1)(х1х3 Å х3 Å 1) Å 1 = х1х2х3 Å х1х2х3 Å х1х2х3 Å х1х3 Å х1х3 Å х1х3 Å х1х3 Å х3 Å 1 Å 1 = х1х2х3 Å х3
Любая функция,представленная с помощью алгебры Жегалкина, называется полиномом Жегалкина.
Функция линейная, если она представлена полиномом Жегалкина вида:
f(х1,х2,….хn) = ai xi + j
- сумма по модулю 2
ai - произв. коэффициент
j - свободный коэффициент
Класс линейных функций так же замкнут.
Пример: f(х1,х2,х3) = х1 Å х3 a1 = 1, a2 = 0, a3 = 1, j = 0
С помощью линейного полинома Жегалкина можно представить функцию отрицания: f(1,x2.1) = g(x2) = 2
Полином Жегалкина через нелинейные функции содержит слагаемые, являющиеся произведением множителей из слагаемых выберем то, которое состоит из мин. числа сомножителей и обозначим К,
а слагаемые: xj1,xj2,…,xjk
Предположим, что хj1 и х j2 принимают произвольные значения функции,
а xj3 = xj4 = …= xjk = 1; a xjk+1 = xjk+2 = … = xjk+n = 0
Тогда функция от аргументов имеет вид:
f (x1,…,xn) = xj1xj2 Å axj1 Å bxj2 Å j
где a, b, j - произ. коэффициенты
|
Полином данного вида называется нелинейным полиномом Жегалкина.
Покажем, что при любых a, b, j для функции fi (xj1,xj2) может быть получена конъюнкция (используем функцию отрицания q(x) = ).
Для этого составим таблицу, где для удобства обозначим: xj1 = x; xj2 = y
f(x,y) = xy Å ax Å by Å j
fi | a b j | & Å | & — | xy |
f0 | 0 0 0 | xy | xy | f0(xy) = xy |
f1 | 0 0 1 | xy Å 1 | xy | g(f1(xy)) = xy |
f2 | 0 1 0 | xy Å y | y | f2(g(x),y) = xy |
f3 | 0 1 1 | xy Å y Å 1 | y | G(f3(g(x),y)) = xy |
f4 | 1 0 0 | xy Å x | x | f4(x,g(y)) = xy |
f5 | 1 0 1 | xy Å x Å 1 | x | G(f5(x,g(y))) = xy |
f6 | 1 1 0 | xy Å x Å y | g(f6(g(x),g(y))) = xy | |
f7 | 1 1 1 | xy Å x Å y Å 1 | f7(g(x),g(y)) = xy |
Таким образом с помощью суперпозиции нелинейных функции и функции отрицания можно получать функцию коньюнкции.
Пример: f(x1,x2,x3) = x1 2 + 1x3 + x2
Преобразуем функцию в мин.форму, представив с помощью операции сложения по
mod 2 и конъюнкции
f(х1,х2,х3) = x1 2 & 1x3 & 2 = ((х1(х2 Å 1)) Å 1)) & ((х3(х1 Å 1) Å 1) & (х2 Å Å1) Å 1 = (х1х2 Å х1 Å 1)(х1х3 Å х3 Å 1)(х2 Å 1) Å 1 = (х1х2х3 Å х1х2 Å х1х3 Å Åх1 Å х3 Å 1)(х2 Å 1) = х1х2х3 Å х1х2 Å х2х3 Å х2 Å х1х3 Å х1 Å х3 Å 1
Выберем в качестве мин. слагаемого х1х2 Þ х3 = 0
f(x1,x2, Æ) = x1x2 Å x1 Å x2 Å 1 = 1 2
x1x2 = f(q(x1),q(x2),Æ)
|
|
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!