Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


 ритерий полноты системы булевых функций (теорема




ѕоста) - система полна в том и только в том случае, если дл€ каждого рз классов в системе существует функци€, не

ѕринадлежаща€ этому классу, иначе говор€, система полна, если рыполнены 5 условий

‘ункции - не об€зательно различные

ѕредварительно рассмотрим 3 утверждени€, которые 'демонстрируют, как суперпозици€ми функций системы, удовлетвор€ющей условию теоремы ѕоста, выразить функции известных полных систем Ћемма 1. —уперпозици€ми несамодвойственной функции

и функции можно получить функцию-константу ≈сли , то существует набор такой, что

ѕостроим суперпозицию , где вместо

|ждого переменного функции подставл€етс€ либо X, либо ёгда [ввиду (*}] =

“аким образом а это означает, чтс - константа

—ледствие. »з функции и константы можно получить другую

рнстанту

Ћемма 2. —уперпозици€ми немонотонной функции

и функций-констант 0 и 1 можно получить функцию ≈сли , то существуют наборы и

такие, что и

, т.е. . ѕусть - набор,

где каждое - либо переменна€ X, либо константа и определ€етс€ следующим образом:

ќтметим, что если X - ќ, то ; если X = 1, то . ѕусть

. “огда , т.е.

Ћемма 3. —уперпозици€ми нелинейной функции функции и функций-констант 0 и 1 можно получить конъюнкцию

ѕостроим дл€ функции многочлен ∆егалкина. ¬ силу нелинейности среди слагаемых найдетс€ содержащее не менее 2 множителей. ѕусть это переменные “огда все слагаемые

разбиваютс€ на 4 группы: содержащие обе переменные только

одну из них и не содержащие ни одной. ќбъедин€€

слагаемые и вынос€ за скобки соответствующие множители в каждой j из трех первых групп, получим:

‘ункции завис€т от переменных , причем не

равна тождественно 0, - иначе не было бы ни одного слагаемого с произведением. . ѕодставим в функцию вместо переменных

тот набор констант , дл€ которого ;

при этом функции обращаютс€ в некоторые константы;

обозначим их соответственно . ѕолучим функцию двух

переменных

“еперь произведем еще одну подстановку: в функцию подставим функцию вместо вместо . в

«ависимости от значений кажда€ из этих функций представл€ет

собой либо , так что фактически мы подставл€ем либо

ѕеременную, либо ее отрицание. ѕолучаем функцию , равную

[после раскрыти€ робок]

[после сокращений] т.е. сумму по модулю 2

конъюнкции и константы . ≈сли последн€€ равна 0, то

построение закончено; в противном случае, т.е. если

то нужно подставить в функцию :

; “еперь доказательство теоремы ѕоста уже достаточно просто. Ќеобходимость следует из сделанного выше замечани€: если все функции системы принадлежат какому-нибудь из 5 классов (обозначим его ), то в силу замкнутости класса все суперпозиции функций системы также принадлежат ему; в то же врем€ в есть функции, соторые не принадлежат что означает неполноту системы.

ƒостаточность выводитс€ из лемм 1 -3. ѕусть в системе есть функции ' (некоторые из них могут

ювпадать). —уперпозици€ - функци€ одной

юременной, имеюща€ столбец значений ; аналогично,

- функци€ со столбцом значений

¬озможны два случа€.

- функци€ . ѕо

лемме 1, из функций можно получить константы 0 и 1.

(2)в противном случае . “огда

ѕо лемме 2, из функций и констант можно получить функцию

 ак видим, в обоих случа€х из функций системы могут быть построены обе константы и отрицание.

ѕо лемме 3, из функций , отрицани€ и констант 0 и 1

можно получить конъюнкцию . ¬ свою очередь, конъюнкци€ и

отрицание образуют полную систему, чем и завершаетс€ доказательство теоремы ѕоста.

ƒл€ проверки конкретной системы на полноту можно заполнить дл€ функций системы так называемую таблицу ѕоста: см. табл.9, в которой исследуетс€ система ("+" означает принадлежность

функции данному предполному классу).

ѕринадлежность трех данных функций классам провер€етс€

по их таблицам очень просто. “акже несложно проверить принадлежность их классу ћ (заметим, что если и не равна 0 тождественно, то

она не монотонна). ќчевидно также, что , свойство

следует из соотношени€

‘ункци€не самодвойственна, поскольку двойственна€

/

ей, как мы знаем, друга€ функци€ - конъюнкци€. ƒалее,

нелинейна, так как ее многочлен ∆егалкина содержит

произведение . Ћегко провер€етс€ также заполнение последней

строки табл.9 - дл€ функции-константы 1. Ќаконец, согласно теореме ѕоста, дл€ полноты системы в каждом столбце таблицы ѕоста должен быть хот€ бы один минус.

¬ таблице 11 дл€ каждого из п€ти рассмотренных выше классов знаками "+" и 'Х'-" показана принадлежность ему р€да известных функций: всех 4 функций одной переменной, 6 функций двух переменных и 2 функций трех переменных. ¬ отличие от предыдущей таблицы функции здесь представлены столбцами. «аметим, что в каждой —троке таблицы имеетс€ знак "-"; другими словами, дл€ каждого из п€ти классов есть не принадлежаща€ ему функци€ и, следовательно, ни один из них не совпадает с множеством всех логических функций , а каждый €вл€етс€ частью

Ќесколько примеров полных систем рассмотрены нами в І1. ќтметим интересный факт: из табл.11 можно заключить, что система, —осто€ща€ из одной функции - штриха Ўеффера - полна.

”пражнение. ѕроверьте, что ”бедитесь теперь, что

”пражнение. — помощью табл 11 установите, какие из цижеследующих систем €вл€етс€ функционально полными:

—истема функций G называетс€ независимой, если никака€ функци€ этой системы не выражаетс€ через остальные, т е. не принадлежит замыканию системы Ќезависима€ система

функций G называетс€ базисом замкнутого класса  , если вс€ка€ функци€ есть суперпозици€ функций из G. ћожно определить

пон€тие базиса и так базис замкнутого класса   - система функций, замыкание которой равно  , причем любое подмножество   (кроме самого  ) уже не обладает этим свойством.

ѕримеры: 1) —истема - независима€.

”пражнение. ”бедитьс€ в этом, использу€ соотношени€ и замкнутость классов L и “.

2) —истема не €вл€етс€ независимой, поскольку, как мы знаем, можно выразить через или, наоборот -через и

3) —истема - независима, в чем можно убедитьс€, построив дл€ нее фрагмент таблицы ѕоста (табл.10). ƒействительно, дл€ каждой из трех функций в этой таблице имеетс€ класс, которому она не принадлежит, но принадлежат две остальные и, следовательно, все их суперпозиции

¬ примерах 1-3 представлены полные системы функций. “еперь рассмотрим пример независимой системы дл€ замкнутого класса, не

совпадающего с

—истема не полна€, так как обе функции линейны, и

представл€ет базис класса L ƒействительно,

а кажда€ линейна€ функци€

выражаетс€ через Ќезависимость функций системы

также легко проверить

Ќекоторые следстви€ теоремы ѕоста.

—ледствие 1. ¬с€кий замкнутый класс содержитс€ целиком

хот€ бы в одном из 5 предполных классов иначе он

представл€л бы полную систему и, в силу замкнутости, равн€лс€ бы

—ледствие 2 объ€сн€ет название предполных классов если к какому-нибудь из них, допустим (дл€ других классов рассмотрение аналогичное) добавить любую не принадлежащую ему функцию то «амыкание системы совпадает с ƒействительно, система

шире, чем S и, в то же врем€, не может входить в какой-либо из остальных 4 классов, так как тогда в нем содержалс€ бы целиком класс S, что противоречит замечанию в конце предыдущего параграфа

»наче говор€, между предполным классом и не может существовать промежуточный замкнутый класс. ќтсюда -

—ледствие 3. ¬ существуют лишь 5 предполных классов, т е. обладающих свойством, сформулированным в следствии 2 Ёто рассмотренные Х - 'и

—ледствие 4. »з лемм 1-3 и доказательства теоремы можно заключить, что если в системе функций присутствуют константы 0 и 1, то дл€ ее полноты достаточно, чтобы в ней содержались немонотонна€ функци€ и нелинейна€ функци€.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-10-01; ћы поможем в написании ваших работ!; просмотров: 873 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—туденческа€ общага - это место, где мен€ научили готовить 20 блюд из макарон и 40 из доширака. ј майонез - это вообще десерт. © Ќеизвестно
==> читать все изречени€...

1423 - | 1390 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.047 с.