9
правок
Изменения
Новая страница: «==Формулировка теоремы== '''F''' называется полной системой функций тогда и только тогда, ког…»
==Формулировка теоремы==
'''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''' - полная система функций'''.'''
'''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''' - полная система функций'''.'''
