Викиконспекты - Вклад участника [ru]

Полные системы функций. Теорема Поста о полной системе функций

2010-10-20T06:05:06Z

Oleg Kolobov: /* Формулировка и доказательство критерия */

== Критерий Поста ==
Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.

== Формулировка и доказательство критерия ==
{{
Теорема|statement=
Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <tex>~S,M,L,T_0,T_1</tex>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

|proof=

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

----

Докажем достаточность этого утверждения.

Рассмотрим функцию, несохраняющую 0 - <tex>f_0</tex>'''.''' <tex>f_0</tex>(0) = 1'''.''' <tex>f_0</tex>(1) может принимать два значения:

а) <tex>f_0</tex>(1) = 1, тогда <tex>f_0</tex>(x, x, x, ..., x) = <tex>~1</tex>'''.'''

б) <tex>f_0</tex>(1) = 0, тогда <tex>f_0</tex>(x, x, x, ..., x) = ¬x'''.'''

Рассмотрим функцию, несохраняющую 1 - <tex>f_1</tex>'''.''' <tex>f_1</tex>(1) = 0. <tex>f_1</tex>(0) может принимать два значения:

а) <tex>f_1</tex>(0) = 0, тогда <tex>f_1</tex>(x, x, x, ..., x) = <tex>~0</tex>'''.'''

б) <tex>f_1</tex>(0) = 1, тогда <tex>f_1</tex>(x, x, x, ..., x) = ¬x'''.'''

Возможны 4 варианта:

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <tex>f_s</tex>.

По определению найдется такой вектор <tex>x_0</tex>, что <tex>f_s</tex>(<tex>x_0</tex>) = <tex>f_s</tex>(¬<tex>x_0</tex>). <tex>x_0</tex> = (<tex>x_{01}, x_{02}, ..., x_{0k}</tex>)'''.'''

Возьмем <tex>f_s</tex>(<tex>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</tex>), где <tex>x^{x_{0i}}</tex> = x, при <tex>x_{0i}</tex> = 1 и <tex>x^{x_{0i}}</tex> = ¬x, при <tex>x_{0i}</tex> = 0'''.'''

Нетрудно заметить, что <tex>f_s</tex>(0) = <tex>f_s</tex>(1) => <tex>f_s</tex> = '''const.'''
Таким образом мы получили одну из констант'''.'''

'''2''')Мы получили '''НЕ''' и <tex>~0</tex>. '''¬'''<tex>~0</tex> = <tex>~1</tex>'''.'''

'''3''')Мы получили '''НЕ''' и <tex>~1</tex>. '''¬'''<tex>~1</tex> = <tex>~0</tex>'''.'''

'''4''')Мы получили <tex>~1</tex> и <tex>~0</tex>'''.'''

Рассмотрим немонотонную функцию <tex>f_m</tex>. Существуют такие <tex>x_1, x_2, ..., x_n</tex>, что <tex>f_m(x_1, x_2, ..., x_{i-1}, 0 , x_{i+1}, ..., x_n)</tex> = 1, <tex>f_m(x_1, x_2, ..., x_{i-1}, 1 , x_{i+1}, ..., x_n)</tex> = 0, зафиксируем все <tex>x_1, x_2, ..., x_n</tex>, тогда <tex>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</tex> = ¬x'''.'''

В итоге имеем три функции: '''НЕ''', <tex>~0</tex>, <tex>~1</tex>'''.'''

Используем нелинейную функцию <tex>f_l</tex>'''.''' Среди нелинейных членов <tex>f_l</tex>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <tex>x_1</tex> и <tex>x_2</tex>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <tex>f_l</tex> = <tex>x_1</tex>^<tex>x_2</tex> ⊕ [<tex>x_1</tex>] ⊕ [<tex>x_2</tex>] ⊕ [<tex>~1</tex>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

Рассмотрим несколько вариантов:

1) Присутствует член <tex>~1</tex>. Возьмем отрицание от <tex>f_l</tex> и член <tex>~1</tex> уберется'''.'''

2) Присутствуют 3 члена, без <tex>~1</tex>: <tex>f_l</tex> = <tex>x_1</tex>^<tex>x_2</tex> ⊕ <tex>x_1</tex> ⊕ <tex>x_2</tex>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <tex>~1</tex>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <tex>f_l</tex>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <tex>f_l</tex>.

В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''
}}

== Источники ==
* [http://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедия]
* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]

Полные системы функций. Теорема Поста о полной системе функций

2010-10-20T05:46:26Z

Oleg Kolobov:

== Критерий Поста ==
Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.

== Формулировка и доказательство критерия ==
{{
Теорема|statement=
Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <tex>~S,M,L,T_0,T_1</tex>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

|proof=

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

----

Докажем достаточность этого утверждения.

Рассмотрим функцию, несохраняющую 0 - <tex>f_0</tex>'''.''' <tex>f_0</tex>(0) = 1'''.''' <tex>f_0</tex>(1) может принимать два значения:

а) <tex>f_0</tex>(1) = 1, тогда <tex>f_0</tex>(x, x, x, ..., x) = <tex>~1</tex>'''.'''

б) <tex>f_0</tex>(1) = 0, тогда <tex>f_0</tex>(x, x, x, ..., x) = ¬x'''.'''

Рассмотрим функцию, несохраняющую 1 - <tex>f_1</tex>'''.''' <tex>f_1</tex>(1) = 0. <tex>f_1</tex>(0) может принимать два значения:

а) <tex>f_1</tex>(0) = 0, тогда <tex>f_1</tex>(x, x, x, ..., x) = <tex>~0</tex>'''.'''

б) <tex>f_1</tex>(0) = 1, тогда <tex>f_1</tex>(x, x, x, ..., x) = ¬x'''.'''

Возможны 4 варианта:

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <tex>f_s</tex>.

По определению найдется такой вектор <tex>x_0</tex>, что <tex>f_s</tex>(<tex>x_0</tex>) = <tex>f_s</tex>(¬<tex>x_0</tex>). <tex>x_0</tex> = (<tex>x_{01}, x_{02}, ..., x_{0k}</tex>)'''.'''

Возьмем <tex>f_s</tex>(<tex>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</tex>), где <tex>x^{x_{0i}}</tex> = x, при <tex>x_{0i}</tex> = 1 и <tex>x^{x_{0i}}</tex> = ¬x, при <tex>x_{0i}</tex> = 0'''.'''

Нетрудно заметить, что <tex>f_s</tex>(0) = <tex>f_s</tex>(1) => <tex>f_s</tex> = '''const.'''
Таким образом мы получили одну из констант'''.'''

'''2''')Мы получили '''НЕ''' и <tex>~0</tex>. '''¬'''<tex>~0</tex> = <tex>~1</tex>'''.'''

'''3''')Мы получили '''НЕ''' и <tex>~1</tex>. '''¬'''<tex>~1</tex> = <tex>~0</tex>'''.'''

'''4''')Мы получили <tex>~1</tex> и <tex>~0</tex>'''.'''

Рассмотрим немонотонную функцию <tex>f_m</tex>. Существуют такие <tex>x_1, x_2, ..., x_n</tex>, что <tex>f_m(x_1, x_2, ..., x_{i-1}, 0 , x_{i+1}, ..., x_n)</tex> = 1, <tex>f_m(x_1, x_2, ..., x_{i-1}, 1 , x_{i+1}, ..., x_n)</tex> = 0, зафиксируем все <tex>x_1, x_2, ..., x_n</tex>, тогда <tex>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</tex> = ¬x'''.'''

В итоге мы имеем три функции: '''НЕ''', <tex>~0</tex>, <tex>~1</tex>'''.'''

Используем нелинейную функцию <tex>f_l</tex>'''.''' Среди нелинейных членов <tex>f_l</tex>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <tex>x_1</tex> и <tex>x_2</tex>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <tex>f_l</tex> = <tex>x_1</tex>^<tex>x_2</tex> ⊕ [<tex>x_1</tex>] ⊕ [<tex>x_2</tex>] ⊕ [<tex>~1</tex>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

Рассмотрим несколько вариантов:

1) Присутствует член <tex>~1</tex>. Возьмем отрицание от <tex>f_l</tex> и член <tex>~1</tex> уберется'''.'''

2) Присутствуют 3 члена, без <tex>~1</tex>: <tex>f_l</tex> = <tex>x_1</tex>^<tex>x_2</tex> ⊕ <tex>x_1</tex> ⊕ <tex>x_2</tex>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <tex>~1</tex>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <tex>f_l</tex>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <tex>f_l</tex>.

В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''
}}
== Источники ==
* [http://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедия]
* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]

Полные системы функций. Теорема Поста о полной системе функций

2010-10-20T05:34:50Z

Oleg Kolobov:

{{
Теорема|statement=
Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <tex>~S,M,L,T_0,T_1</tex>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

|proof=

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

----

Докажем достаточность этого утверждения.

Рассмотрим функцию, несохраняющую 0 - <tex>f_0</tex>'''.''' <tex>f_0</tex>(0) = 1'''.''' <tex>f_0</tex>(1) может принимать два значения:

а) <tex>f_0</tex>(1) = 1, тогда <tex>f_0</tex>(x, x, x, ..., x) = <tex>~1</tex>'''.'''

б) <tex>f_0</tex>(1) = 0, тогда <tex>f_0</tex>(x, x, x, ..., x) = ¬x'''.'''

Возьмем функцию, несохраняющую 1 - <tex>f_1</tex>. <tex>f_1</tex>(1) = 0. <tex>f_1</tex>(0) может принимать два значения:

а) <tex>f_1</tex>(0) = 0, тогда <tex>f_1</tex>(x, x, x, ..., x) = <tex>~0</tex>'''.'''

б) <tex>f_1</tex>(0) = 1, тогда <tex>f_1</tex>(x, x, x, ..., x) = ¬x'''.'''

Возможны 4 варианта:

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <tex>f_s</tex>.

По определению найдется такой вектор <tex>x_0</tex>, что <tex>f_s</tex>(<tex>x_0</tex>) = <tex>f_s</tex>(¬<tex>x_0</tex>). <tex>x_0</tex> = (<tex>x_{01}, x_{02}, ..., x_{0k}</tex>)'''.'''

Возьмем <tex>f_s</tex>(<tex>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</tex>), где <tex>x^{x_{0i}}</tex> = x, при <tex>x_{0i}</tex> = 1 и <tex>x^{x_{0i}}</tex> = ¬x, при <tex>x_{0i}</tex> = 0'''.'''

Нетрудно заметить, что <tex>f_s</tex>(0) = <tex>f_s</tex>(1) => <tex>f_s</tex> = '''const.'''
Таким образом мы получили одну из констант'''.'''

'''2''')Мы получили '''НЕ''' и <tex>~0</tex>. '''¬'''<tex>~0</tex> = <tex>~1</tex>'''.'''

'''3''')Мы получили '''НЕ''' и <tex>~1</tex>. '''¬'''<tex>~1</tex> = <tex>~0</tex>'''.'''

'''4''')Мы получили <tex>~1</tex> и <tex>~0</tex>'''.'''

Рассмотрим немонотонную функцию <tex>f_m</tex>. Существуют такие <tex>x_1, x_2, ..., x_n</tex>, что <tex>f_m(x_1, x_2, ..., x_{i-1}, 0 , x_{i+1}, ..., x_n)</tex> = 1, <tex>f_m(x_1, x_2, ..., x_{i-1}, 1 , x_{i+1}, ..., x_n)</tex> = 0, зафиксируем все <tex>x_1, x_2, ..., x_n</tex>, тогда <tex>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</tex> = ¬x'''.'''

В итоге мы имеем три функции: '''НЕ''', <tex>~0</tex>, <tex>~1</tex>'''.'''

Используем нелинейную функцию <tex>f_l</tex>'''.''' Среди нелинейных членов <tex>f_l</tex>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <tex>x_1</tex> и <tex>x_2</tex>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <tex>f_l</tex> = <tex>x_1</tex>^<tex>x_2</tex> ⊕ [<tex>x_1</tex>] ⊕ [<tex>x_2</tex>] ⊕ [<tex>~1</tex>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

Рассмотрим несколько вариантов:

1) Присутствует член <tex>~1</tex>. Возьмем отрицание от <tex>f_l</tex> и член <tex>~1</tex> уберется'''.'''

2) Присутствуют 3 члена, без <tex>~1</tex>: <tex>f_l</tex> = <tex>x_1</tex>^<tex>x_2</tex> ⊕ <tex>x_1</tex> ⊕ <tex>x_2</tex>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <tex>~1</tex>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <tex>f_l</tex>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <tex>f_l</tex>.

В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''
}}

Полные системы функций. Теорема Поста о полной системе функций

2010-10-20T05:06:10Z

Oleg Kolobov: /* Доказательство */

==Формулировка теоремы==

Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <math>~S,M,L,T_0,T_1</math>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

==Доказательство ==

----

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

----

Докажем достаточность этого утверждения.

Рассмотрим функцию, несохраняющую 0 - <math>f_0</math>'''.''' <math>f_0</math>(0) = 1'''.''' <math>f_0</math>(1) может принимать два значения:

а) <math>f_0</math>(1) = 1, тогда <math>f_0</math>(x, x, x, ..., x) = <math>~1</math>'''.'''

б) <math>f_0</math>(1) = 0, тогда <math>f_0</math>(x, x, x, ..., x) = ¬x'''.'''

Возьмем функцию, несохраняющую 1 - <math>f_1</math>. <math>f_1</math>(1) = 0. <math>f_1</math>(0) может принимать два значения:

а) <math>f_1</math>(0) = 0, тогда <math>f_1</math>(x, x, x, ..., x) = <math>~0</math>'''.'''

б) <math>f_1</math>(0) = 1, тогда <math>f_1</math>(x, x, x, ..., x) = ¬x'''.'''

Возможны 4 варианта:

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <math>f_s</math>.

По определению найдется такой вектор <math>x_0</math>, что <math>f_s</math>(<math>x_0</math>) = <math>f_s</math>(¬<math>x_0</math>). <math>x_0</math> = (<math>x_{01}, x_{02}, ..., x_{0k}</math>)'''.'''

Возьмем <math>f_s</math>(<math>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</math>), где <math>x^{x_{0i}}</math> = x, при <math>x_{0i}</math> = 1 и <math>x^{x_{0i}}</math> = ¬x, при <math>x_{0i}</math> = 0'''.'''

Нетрудно заметить, что <math>f_s</math>(0) = <math>f_s</math>(1) => <math>f_s</math> = '''const.'''
Таким образом мы получили одну из констант'''.'''

'''2''')Мы получили '''НЕ''' и <math>~0</math>. '''¬'''<math>~0</math> = <math>~1</math>'''.'''

'''3''')Мы получили '''НЕ''' и <math>~1</math>. '''¬'''<math>~1</math> = <math>~0</math>'''.'''

'''4''')Мы получили <math>~1</math> и <math>~0</math>'''.'''

Рассмотрим немонотонную функцию <math>f_m</math>. Существуют такие <math>x_1, x_2, ..., x_n</math>, что <math>f_m(x_1, x_2, ..., x_{i-1}, 0 , x_{i+1}, ..., x_n)</math> = 1, <math>f_m(x_1, x_2, ..., x_{i-1}, 1 , x_{i+1}, ..., x_n)</math> = 0, зафиксируем все <math>x_1, x_2, ..., x_n</math>, тогда <math>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</math> = ¬x'''.'''

В итоге мы имеем три функции: '''НЕ''', <math>~0</math>, <math>~1</math>'''.'''

Используем нелинейную функцию <math>f_l</math>'''.''' Среди нелинейных членов <math>f_l</math>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <math>x_1</math> и <math>x_2</math>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ [<math>x_1</math>] ⊕ [<math>x_2</math>] ⊕ [<math>~1</math>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

Рассмотрим несколько вариантов:

1) Присутствует член <math>~1</math>. Возьмем отрицание от <math>f_l</math> и член <math>~1</math> уберется'''.'''

2) Присутствуют 3 члена, без <math>~1</math>: <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ <math>x_1</math> ⊕ <math>x_2</math>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <math>~1</math>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <math>f_l</math>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <math>f_l</math>.

Получается, что у нас есть функция '''НЕ''', а также либо функция '''И''', либо функция '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''

Полные системы функций. Теорема Поста о полной системе функций

2010-10-20T04:48:27Z

Oleg Kolobov: /* Доказательство */

==Формулировка теоремы==

Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <math>~S,M,L,T_0,T_1</math>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

==Доказательство ==
* Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным.

* Докажем достаточность этого утверждения.
У нас есть 5 функций: несохраняющая 1 - <math>f_1</math>, несохраняющая 0 - <math>f_0</math>, несамодвойственная - <math>f_s</math>, немонотонная - <math>f_m</math>, нелинейная - <math>f_l</math>'''.'''

Возьмем функцию, несохраняющую 0 - <math>f_0</math>'''.''' <math>f_0</math>(0) = 1'''.''' <math>f_0</math>(1) может принимать два значения:

а) <math>f_0</math>(1) = 1, тогда <math>f_0</math>(x, x, x, ..., x) = <math>~1</math>'''.'''

б) <math>f_0</math>(1) = 0, тогда <math>f_0</math>(x, x, x, ..., x) = ¬x'''.'''

Возьмем функцию, несохраняющую 1 - <math>f_1</math>. <math>f_1</math>(1) = 0. <math>f_1</math>(0) может принимать два значения:

а) <math>f_1</math>(0) = 0, тогда <math>f_1</math>(x, x, x, ..., x) = <math>~0</math>'''.'''

б) <math>f_1</math>(0) = 1, тогда <math>f_1</math>(x, x, x, ..., x) = ¬x'''.'''

Возможны 4 варианта:

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <math>f_s</math>.

По определению найдется такой вектор <math>x_0</math>, что <math>f_s</math>(<math>x_0</math>) = <math>f_s</math>(¬<math>x_0</math>). <math>x_0</math> = (<math>x_{01}, x_{02}, ..., x_{0k}</math>)'''.'''

Возьмем <math>f_s</math>(<math>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</math>), где <math>x^{x_{0i}}</math> = x, при <math>x_{0i}</math> = 1 и <math>x^{x_{0i}}</math> = ¬x, при <math>x_{0i}</math> = 0'''.'''

Нетрудно заметить, что <math>f_s</math>(0) = <math>f_s</math>(1) => <math>f_s</math> = '''const.'''
Таким образом мы получили одну из констант'''.'''

'''2''')Мы получили '''НЕ''' и <math>~0</math>. '''¬'''<math>~0</math> = <math>~1</math>'''.'''

'''3''')Мы получили '''НЕ''' и <math>~1</math>. '''¬'''<math>~1</math> = <math>~0</math>'''.'''

'''4''')Мы получили <math>~1</math> и <math>~0</math>'''.'''

Рассмотрим немонотонную функцию <math>f_m</math>. Существуют такие <math>x_1, x_2, ..., x_n</math>, что <math>f_m(x_1, x_2, ..., x_{i-1}, 0, x_{i+1}, ..., x_n)</math> = 1, <math>f_m(x_1, x_2, ..., x_{i-1}, 1, x_{i+1}, ..., x_n)</math> = 0, зафиксируем все <math>x_1, x_2, ..., x_n</math>, тогда <math>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</math> = ¬x'''.'''

В итоге мы имеем три функции: '''НЕ''', <math>~0</math>, <math>~1</math>'''.'''

Используем нелинейную функцию <math>f_l</math>'''.''' Среди нелинейных членов <math>f_l</math>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <math>x_1</math> и <math>x_2</math>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ [<math>x_1</math>] ⊕ [<math>x_2</math>] ⊕ [<math>~1</math>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

Рассмотрим несколько вариантов:

1) Присутствует член <math>~1</math>. Возьмем отрицание от <math>f_l</math> и член <math>~1</math> уберется'''.'''

2) Присутствуют 3 члена, без <math>~1</math>: <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ <math>x_1</math> ⊕ <math>x_2</math>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <math>~1</math>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <math>f_l</math>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <math>f_l</math>.

Получается, что у нас есть функция '''НЕ''', а также либо функция '''И''', либо функция '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''

Полные системы функций. Теорема Поста о полной системе функций

2010-10-20T04:45:36Z

Oleg Kolobov: /* Формулировка теоремы */

==Формулировка теоремы==

Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <math>~S,M,L,T_0,T_1</math>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

==Доказательство ==
'''I.''' Докажем прямую теорему'''.'''

Предположим, что '''F''' не содержит функцию, обладающую одним из перечисленных выше свойств, но тогда мы не сможем через функции, входящие в '''F''' выразить функции, обладающие этим свойством, и следовательно '''F''' не будет полной системой функций, что противоречит условию, следовательно '''F''' должна содержать все вышеперечисленные функции'''.'''

'''II.''' Докажем обратную теорему'''.'''

У нас есть 5 функций: несохраняющая 1 - <math>f_1</math>, несохраняющая 0 - <math>f_0</math>, несамодвойственная - <math>f_s</math>, немонотонная - <math>f_m</math>, нелинейная - <math>f_l</math>'''.'''

Возьмем функцию, несохраняющую 0 - <math>f_0</math>'''.''' <math>f_0</math>(0) = 1'''.''' <math>f_0</math>(1) может принимать два значения:

а) <math>f_0</math>(1) = 1, тогда <math>f_0</math>(x, x, x, ..., x) = <math>~1</math>'''.'''

б) <math>f_0</math>(1) = 0, тогда <math>f_0</math>(x, x, x, ..., x) = ¬x'''.'''

Возьмем функцию, несохраняющую 1 - <math>f_1</math>. <math>f_1</math>(1) = 0. <math>f_1</math>(0) может принимать два значения:

а) <math>f_1</math>(0) = 0, тогда <math>f_1</math>(x, x, x, ..., x) = <math>~0</math>'''.'''

б) <math>f_1</math>(0) = 1, тогда <math>f_1</math>(x, x, x, ..., x) = ¬x'''.'''

Возможны 4 варианта:

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <math>f_s</math>.

По определению найдется такой вектор <math>x_0</math>, что <math>f_s</math>(<math>x_0</math>) = <math>f_s</math>(¬<math>x_0</math>). <math>x_0</math> = (<math>x_{01}, x_{02}, ..., x_{0k}</math>)'''.'''

Возьмем <math>f_s</math>(<math>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</math>), где <math>x^{x_{0i}}</math> = x, при <math>x_{0i}</math> = 1 и <math>x^{x_{0i}}</math> = ¬x, при <math>x_{0i}</math> = 0'''.'''

Нетрудно заметить, что <math>f_s</math>(0) = <math>f_s</math>(1) => <math>f_s</math> = '''const.'''
Таким образом мы получили одну из констант'''.'''

'''2''')Мы получили '''НЕ''' и <math>~0</math>. '''¬'''<math>~0</math> = <math>~1</math>'''.'''

'''3''')Мы получили '''НЕ''' и <math>~1</math>. '''¬'''<math>~1</math> = <math>~0</math>'''.'''

'''4''')Мы получили <math>~1</math> и <math>~0</math>'''.'''

Рассмотрим немонотонную функцию <math>f_m</math>. Существуют такие <math>x_1, x_2, ..., x_n</math>, что <math>f_m(x_1, x_2, ..., x_{i-1}, 0, x_{i+1}, ..., x_n)</math> = 1, <math>f_m(x_1, x_2, ..., x_{i-1}, 1, x_{i+1}, ..., x_n)</math> = 0, зафиксируем все <math>x_1, x_2, ..., x_n</math>, тогда <math>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</math> = ¬x'''.'''

В итоге мы имеем три функции: '''НЕ''', <math>~0</math>, <math>~1</math>'''.'''

Используем нелинейную функцию <math>f_l</math>'''.''' Среди нелинейных членов <math>f_l</math>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <math>x_1</math> и <math>x_2</math>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ [<math>x_1</math>] ⊕ [<math>x_2</math>] ⊕ [<math>~1</math>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

Рассмотрим несколько вариантов:

1) Присутствует член <math>~1</math>. Возьмем отрицание от <math>f_l</math> и член <math>~1</math> уберется'''.'''

2) Присутствуют 3 члена, без <math>~1</math>: <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ <math>x_1</math> ⊕ <math>x_2</math>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <math>~1</math>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <math>f_l</math>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <math>f_l</math>.

Получается, что у нас есть функция '''НЕ''', а также либо функция '''И''', либо функция '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''

Полные системы функций. Теорема Поста о полной системе функций

2010-10-20T04:44:49Z

Oleg Kolobov: /* Формулировка теоремы */

==Формулировка теоремы==

Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <math>~S,M,L,T_0,T_1</math>, т.е. когда в ней имеется хотя бы одна [[Функция (математика)|функция]], не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

==Доказательство ==
'''I.''' Докажем прямую теорему'''.'''

Предположим, что '''F''' не содержит функцию, обладающую одним из перечисленных выше свойств, но тогда мы не сможем через функции, входящие в '''F''' выразить функции, обладающие этим свойством, и следовательно '''F''' не будет полной системой функций, что противоречит условию, следовательно '''F''' должна содержать все вышеперечисленные функции'''.'''

'''II.''' Докажем обратную теорему'''.'''

У нас есть 5 функций: несохраняющая 1 - <math>f_1</math>, несохраняющая 0 - <math>f_0</math>, несамодвойственная - <math>f_s</math>, немонотонная - <math>f_m</math>, нелинейная - <math>f_l</math>'''.'''

Возьмем функцию, несохраняющую 0 - <math>f_0</math>'''.''' <math>f_0</math>(0) = 1'''.''' <math>f_0</math>(1) может принимать два значения:

а) <math>f_0</math>(1) = 1, тогда <math>f_0</math>(x, x, x, ..., x) = <math>~1</math>'''.'''

б) <math>f_0</math>(1) = 0, тогда <math>f_0</math>(x, x, x, ..., x) = ¬x'''.'''

Возьмем функцию, несохраняющую 1 - <math>f_1</math>. <math>f_1</math>(1) = 0. <math>f_1</math>(0) может принимать два значения:

а) <math>f_1</math>(0) = 0, тогда <math>f_1</math>(x, x, x, ..., x) = <math>~0</math>'''.'''

б) <math>f_1</math>(0) = 1, тогда <math>f_1</math>(x, x, x, ..., x) = ¬x'''.'''

Возможны 4 варианта:

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <math>f_s</math>.

По определению найдется такой вектор <math>x_0</math>, что <math>f_s</math>(<math>x_0</math>) = <math>f_s</math>(¬<math>x_0</math>). <math>x_0</math> = (<math>x_{01}, x_{02}, ..., x_{0k}</math>)'''.'''

Возьмем <math>f_s</math>(<math>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</math>), где <math>x^{x_{0i}}</math> = x, при <math>x_{0i}</math> = 1 и <math>x^{x_{0i}}</math> = ¬x, при <math>x_{0i}</math> = 0'''.'''

Нетрудно заметить, что <math>f_s</math>(0) = <math>f_s</math>(1) => <math>f_s</math> = '''const.'''
Таким образом мы получили одну из констант'''.'''

'''2''')Мы получили '''НЕ''' и <math>~0</math>. '''¬'''<math>~0</math> = <math>~1</math>'''.'''

'''3''')Мы получили '''НЕ''' и <math>~1</math>. '''¬'''<math>~1</math> = <math>~0</math>'''.'''

'''4''')Мы получили <math>~1</math> и <math>~0</math>'''.'''

Рассмотрим немонотонную функцию <math>f_m</math>. Существуют такие <math>x_1, x_2, ..., x_n</math>, что <math>f_m(x_1, x_2, ..., x_{i-1}, 0, x_{i+1}, ..., x_n)</math> = 1, <math>f_m(x_1, x_2, ..., x_{i-1}, 1, x_{i+1}, ..., x_n)</math> = 0, зафиксируем все <math>x_1, x_2, ..., x_n</math>, тогда <math>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</math> = ¬x'''.'''

В итоге мы имеем три функции: '''НЕ''', <math>~0</math>, <math>~1</math>'''.'''

Используем нелинейную функцию <math>f_l</math>'''.''' Среди нелинейных членов <math>f_l</math>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <math>x_1</math> и <math>x_2</math>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ [<math>x_1</math>] ⊕ [<math>x_2</math>] ⊕ [<math>~1</math>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

Рассмотрим несколько вариантов:

1) Присутствует член <math>~1</math>. Возьмем отрицание от <math>f_l</math> и член <math>~1</math> уберется'''.'''

2) Присутствуют 3 члена, без <math>~1</math>: <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ <math>x_1</math> ⊕ <math>x_2</math>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <math>~1</math>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <math>f_l</math>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <math>f_l</math>.

Получается, что у нас есть функция '''НЕ''', а также либо функция '''И''', либо функция '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''

Полные системы функций. Теорема Поста о полной системе функций

2010-10-08T08:28:43Z

Oleg Kolobov: /* Доказательство */

==Формулировка теоремы==

'''F''' называется полной системой функций тогда и только тогда, когда она содержит функцию, ''несохраняющую'' 1, функцию, ''несохраняющую'' 0, ''немонотонную'', ''несамодвойственную'' и ''нелинейную'' функции'''.'''
----

==Доказательство ==
'''I.''' Докажем прямую теорему'''.'''

Предположим, что '''F''' не содержит функцию, обладающую одним из перечисленных выше свойств, но тогда мы не сможем через функции, входящие в '''F''' выразить функции, обладающие этим свойством, и следовательно '''F''' не будет полной системой функций, что противоречит условию, следовательно '''F''' должна содержать все вышеперечисленные функции'''.'''

'''II.''' Докажем обратную теорему'''.'''

У нас есть 5 функций: несохраняющая 1 - <math>f_1</math>, несохраняющая 0 - <math>f_0</math>, несамодвойственная - <math>f_s</math>, немонотонная - <math>f_m</math>, нелинейная - <math>f_l</math>'''.'''

Возьмем функцию, несохраняющую 0 - <math>f_0</math>'''.''' <math>f_0</math>(0) = 1'''.''' <math>f_0</math>(1) может принимать два значения:

а) <math>f_0</math>(1) = 1, тогда <math>f_0</math>(x, x, x, ..., x) = <math>~1</math>'''.'''

б) <math>f_0</math>(1) = 0, тогда <math>f_0</math>(x, x, x, ..., x) = ¬x'''.'''

Возьмем функцию, несохраняющую 1 - <math>f_1</math>. <math>f_1</math>(1) = 0. <math>f_1</math>(0) может принимать два значения:

а) <math>f_1</math>(0) = 0, тогда <math>f_1</math>(x, x, x, ..., x) = <math>~0</math>'''.'''

б) <math>f_1</math>(0) = 1, тогда <math>f_1</math>(x, x, x, ..., x) = ¬x'''.'''

Возможны 4 варианта:

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <math>f_s</math>.

По определению найдется такой вектор <math>x_0</math>, что <math>f_s</math>(<math>x_0</math>) = <math>f_s</math>(¬<math>x_0</math>). <math>x_0</math> = (<math>x_{01}, x_{02}, ..., x_{0k}</math>)'''.'''

Возьмем <math>f_s</math>(<math>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</math>), где <math>x^{x_{0i}}</math> = x, при <math>x_{0i}</math> = 1 и <math>x^{x_{0i}}</math> = ¬x, при <math>x_{0i}</math> = 0'''.'''

Нетрудно заметить, что <math>f_s</math>(0) = <math>f_s</math>(1) => <math>f_s</math> = '''const.'''
Таким образом мы получили одну из констант'''.'''

'''2''')Мы получили '''НЕ''' и <math>~0</math>. '''¬'''<math>~0</math> = <math>~1</math>'''.'''

'''3''')Мы получили '''НЕ''' и <math>~1</math>. '''¬'''<math>~1</math> = <math>~0</math>'''.'''

'''4''')Мы получили <math>~1</math> и <math>~0</math>'''.'''

Рассмотрим немонотонную функцию <math>f_m</math>. Существуют такие <math>x_1, x_2, ..., x_n</math>, что <math>f_m(x_1, x_2, ..., x_{i-1}, 0, x_{i+1}, ..., x_n)</math> = 1, <math>f_m(x_1, x_2, ..., x_{i-1}, 1, x_{i+1}, ..., x_n)</math> = 0, зафиксируем все <math>x_1, x_2, ..., x_n</math>, тогда <math>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</math> = ¬x'''.'''

В итоге мы имеем три функции: '''НЕ''', <math>~0</math>, <math>~1</math>'''.'''

Используем нелинейную функцию <math>f_l</math>'''.''' Среди нелинейных членов <math>f_l</math>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <math>x_1</math> и <math>x_2</math>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ [<math>x_1</math>] ⊕ [<math>x_2</math>] ⊕ [<math>~1</math>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

Рассмотрим несколько вариантов:

1) Присутствует член <math>~1</math>. Возьмем отрицание от <math>f_l</math> и член <math>~1</math> уберется'''.'''

2) Присутствуют 3 члена, без <math>~1</math>: <math>f_l</math> = <math>x_1</math>^<math>x_2</math> ⊕ <math>x_1</math> ⊕ <math>x_2</math>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <math>~1</math>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <math>f_l</math>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <math>f_l</math>.

Получается, что у нас есть функция '''НЕ''', а также либо функция '''И''', либо функция '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''

Полные системы функций. Теорема Поста о полной системе функций

2010-10-08T08:26:54Z

Oleg Kolobov: Новая страница: «==Формулировка теоремы== '''F''' называется полной системой функций тогда и только тогда, ког…»