Головна

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

  1. Аксіома Больцано-Вейєрштрасса і теорема про стягують системі відрізків
  2. Алгебра Жегалкина і лінійні функції
  3. В) Теорема про зміну моментів кількості руху для матеріальної системи (теорема моментів)
  4. Друга теорема подвійності
  5. Друга теорема Шеннона.
  6. Діфференціалданатин функціялар турали теоремалар
  7. Единственность уявлення булевих функцій поліномами Жегалкина

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

Тут єдиність розуміється з точністю до порядку доданків в сумі і порядку співмножників в кон'юнкції:

, s = 0, 1, ..., n.

Доведення. Будь-яка функція з Р2 може бути представлена ??формулою над {x1 & x2, x1A x2, 0, 1}, а ця формула після розкриття всіх дужок і приведення подібних членів дає поліном Жегалкина. Доведемо єдиність подання. Розглянемо функції f(x1, ..., xn) від n змінних. Ми знаємо, що за все таких функцій, тобто їх таблиць істинності, 2n. Підрахуємо число різних поліномів Жегалкина від n змінних, тобто число варіацій виду:  . число наборів  дорівнює числу всіх підмножин множини { x1, ..., xn }, Сюди входить і порожня множина (якщо s = 0). Число підмножин безлічі з n елементів дорівнює 2n , А так як кожен набір входить з коефіцієнтом  , Які приймають два значення: 0 або 1, то число всіляких поліномів буде  . Оскільки кожному полиному відповідає єдина функція, число функцій від n змінних дорівнює числу полиномов, то кожної функції буде відповідати єдиний поліном.

Визначення.функція f(x1, ..., xn), Поліном Жегалкина для якої має такий лінійний щодо змінних вид: f = а0 A а1х1 A а2х2 A ... A а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 A c. якщо d = 0, то h(x1, x2) = x1x2. якщо d = 1, то h(x1, x2) = x1x2 A 1 і тоді  Лема доведена.

функція f(x1, ..., xn) Зберігає константу a I {0, 1}, якщо f(a, ..., a) = a.

Приклад 4. функція xy зберігає 0, зберігає 1. Функція x®y зберігає 1 і не зберігає 0.

2.4.6. Замикання і замкнуті класи

визначення 1. нехай MIР2. замиканням М називається безліч всіх функцій з P2, Які можна виразити формулами над М. замикання М позначається [M].

визначення 2.безліч функцій М називається замкнутим класом, якщо [M] =M.

Приклад 1.

1) P2 - Замкнутий клас.

2) Множина {1,x1Ax2} Не є замкнутим класом. Його замиканням буде клас лінійних функцій: [{1, x1 A x2}] = {f(x1, ..., xn) = c0 A c1x1 A ... A cnxn}. Дійсно, за визначенням формули над М, функція f(G1, x3), Де f - Є сума по модулю 2, G1 - функція х1 A х2, Буде формулою над М: f(G1, x3) = (x1 A x2) A x3.

Замечаніе.У термінах замикання і замкнутого класу можна дати інше визначення повноти, еквівалентну вихідному:

М - Повна система, якщо [M] = P2.

3) A = {f(x1, ..., xn) | f(1, 1, ..., 1) = 0} - незамкнений клас. Візьмемо формулу над цим безліччю. нехай f, g1, ..., gn I A, Тобто f(1, 1, ..., 1) = 0, g1(1, 1, ..., 1) = 0, тоді f(g1, ..., gn) I [A]. Подивимося, чи належить функція f(g1, ..., gn) безлічі А. f(g1(1, ..., 1), g2(1, ..., 1), ..., gn(1, ..., 1) = f(0, ..., 0)), але f(0, ..., 0) не повинно бути рівним 0. Дійсно, нехай g1(x1, x2) = x1 A x2, g2(x) = x IA. візьмемо g2(g1(x1, x2)) = x1 A x2 I [A], g2(g1(1, 1)) = 1 A 1 = 0, отже, g2(g1(x1, x2)) I A, Звідси [A] ? A и А - Незамкнений клас.

Найважливіші замкнуті класи в Р2

1) Т0 - Клас функцій, що зберігають константу 0.

Т0 = { f(x1, ..., xn) | f(0, ..., 0) = 0, n = 1, 2, ...}. Покажемо, що Т0 є власним підмножиною Р2, Тобто Т0 ? ? і Т0 I Р (Не збігається з Р2). Для цього достатньо навести приклади функцій, що входять в Т0, І приклади функцій з Р2, Що не входять в Т0: x1&x2, x1Ux2, xIТ0 и x1|x2, x1 x2, IТ0. Покажемо далі, що [Т0] = Т0. вкладення Т0 I [ Т0] Очевидно, так як за визначенням формули будь-яка функція з Т0 є формулою над Т0 і, отже, належить [Т0]. Покажемо, що [Т0] I Т0. Для цього треба показати, що Ф = f(f1, ..., fm) I [ Т0], Якщо всі функції f, f1, f2, f3, ..., fm I Т0. Треба зауважити, що у формулі як функції f1 можуть бути взяті змінні, які ми домовилися вважати тотожними функціями. Тотожна функція належить класу Т0, Тому досить показати, що Ф = f (f 1, ..., fm) I Т0. Для цього розглянемо наступну функцію: Ф(0, ..., 0) = f (f 1(0, ..., 0), f 2(0, ..., 0), ...) = f(0, ..., 0) = 0.

Число функцій, що залежать від n змінних і належать Т0, Дорівнюватиме

2) T1 - клас функцій, що зберігають константу 1.

T1 = {f(x1, ...) |f(1, 1, ...) = 1}; x1&x2, x1Ux2, xIT1, х1Aх2, x1 x2IT1, отже Т1 - Власне підмножина Р2.

Покажемо, що [T1] I T1, Зворотне включення випливає з визначення формули і замикання. Так як тотожна функція входить в Т1, Можна розглянути Ф = f(f1, ..., fn) I [T1], Де f, f1, ..., fn I T1. знайдемо Ф(1, ..., 1) = f(f1(1, ..., 1), ..., fn(1, ..., 1)) = f(1, ..., 1) = 1, отже, Ф = f(f1, ..., fn) I T1, звідси випливає [T1] = T1.

3) S - клас самодвоїстих функцій.

S = {f(x1, ...) |f* = f }; x, , x1Ax2Ax3IS, x1&x2, x1Ux2, x1Ax2IS, Отже, S - Власне підмножина Р2. |S(n) | =  . Покажемо, що [S] IS. Ф = f(f1, ..., fn) I [S], Якщо f, f1, ..., fn I S, А також, що Ф I S. За принципом подвійності, Ф* = f* (f1*, ..., fn*) = f(f1, ..., fn) = Ф, звідси S - Замкнутий клас.

4) L - клас лінійних функцій.

L = {f(x1, ...) | f = c0Ac1x1A ... Acnxn}; очевидно, L ? ?, з іншого боку

L ? P2, так як x1&x2 I L. Зауважимо, що тотожна функція належить L і |L(n) | = 2n+1. Покажемо, що [L] I L. Розглянемо Ф = f(f1, ..., fm), Де f, f1, ..., fn I L. тоді Ф = а0 A а1(с10 A с11х1 A ... A c1nxn1) A a2(c20 A c21x1 A c22x2A ... A c2nxn2) A ... A an(cm0 Acm1x1 A ... A cmnxnm) = в0 A в1х1 A ... A вnхn ? ФIL.

5) М - клас монотонних функцій.

визначення. набір a'= (a1, ..., an) Передує набору b'= (b1, ..., bn) І це позначається a'?b', Якщо для 1 ?i?n ai?bi, Наприклад: a'= (0010), b'= (0110), тоді a'?b'. Чи не будь-які два набору перебувають у відношенні передування, наприклад, набори (0110) і (1010) в такому відношенні не перебувають. Ставлення передування (  ) Є відношенням порядку на безлічі наборів довжини n, Безліч таких наборів буде частково впорядкованим безліччю по відношенню до операції.

Визначення. функція f(x1, ..., xn) Називається монотонної, якщо для двох наборів ab', Таких що a'?b', Виконується f(a') ?f(b'). Функції 0, 1, x, x1&x2, x1Ux2 I M, x1?x2, x1Ax2, x1~x2 I M.

Для числа монотонних функцій, що залежать від n змінних, існують оцінки зверху і знизу, але точне число порахувати не вдається. Покажемо, що М замкнутийклас. Розглянемо функцію ФI [M], Ф = f(f1, ..., fm), Де f, f1, ..., fmIM, Причому можемо вважати, що всі вони залежать від n змінних. нехай набір a'= (a1, ..., an), b'= (b1, ..., bn). Розглянемо Ф(a1, ..., an) = f(f1(a1, ..., an), ..., fm(a1, ..., an)) І Ф(b1, ..., bn) = f(f1(b1, ..., bn), ..., fm(b1, ..., bn)). тут f1(a)? f1(b), ..., fm(a)? fm(b), Тоді набір (f1(a), ..., fm(a))? (f1(b), ..., fm(b)), але тоді Ф(a')? Ф(b'), так як fIM, звідси Ф = f(f1, ...,) - Монотонна функція.

Визначення. функція f є суперпозиція над M, якщо f реалізується певною формулою над M.

Лемма про немонотонної функції. Заперечення можна отримати суперпозицией констант 0 і 1, тотожною функції і немонотонної функції.

Доведення. нехай f(x1, ..., xn) - Немонотонна функція. Тоді існують набори и  , для яких  але  нехай i1, ..., ik є всі ті номера аргументів, для яких , p= 1, ..., k. На всіх інших аргументної місцях j маємо aj = bj. У вираженні  замінимо нулі на місцях i1, ..., ik на x. В результаті отримаємо функцію g(x), для котрої g(0) = f(  ) = 1 і g(1) = f(  ) = 0. Функція g(x) Є запереченням.

класи T0, T1, L, S, M перетинаються, але не збігаються, що видно з наступної таблиці, де «+» означає, що функція належить даному класу і «-» - не належить.

  T0 T1 L S M
x + + + + +
- - + + -
+ - + - +
- + + - +
x1x2 + + - - +

A= {x, , 0, 1, x1x2) Не є повною системою функцій так як завжди є функції I Р2 що не входять в ці класи.

завдання

1. Довести, що перетин будь-яких двох замкнутих класів замкнуто.

2. Довести, що об'єднання двох замкнутих класів не завжди замкнуто.



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   Наступна

Елементи математичної логіки. | Приклад 2. | Приклад 4. | Деякі властивості елементарних функцій | принцип подвійності | Лемма про несамодвойственной функції | Теорема про розкладання функції по змінним | Приклади використання теореми Поста. | Теорема про достатність чотирьох функцій. | можливість розв'язання |

© um.co.ua - учбові матеріали та реферати