1_Algebra_logiki

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

(x1; x2) = '(x1 ; x2 )

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

(x1; x2) = '(x1 ; x2 )

x = x 1 x = x 0

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

(x1; x2) = '(x1 ; x2 )

) (x) получена из f(x1; : : : ; xn) заменой ее аргументов на 0; 1 или на x и x. Если = 1, функция ' заменяется на инверсную.

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

(x1; x2) = '(x1 ; x2 )

) (x) получена из f(x1; : : : ; xn) заменой ее аргументов на 0; 1 или на x и x. Если = 1, функция ' заменяется на инверсную.

)(x) соответствует условиям леммы

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

(x1; x2) = '(x1 ; x2 )

) (x) получена из f(x1; : : : ; xn) заменой ее аргументов на 0; 1 или на x и x. Если = 1, функция ' заменяется на инверсную.

)(x) соответствует условиям леммы

(x1; x2) = (x1 )(x2 ) (x1 ) (x2 ) =

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

(x1; x2) = '(x1 ; x2 )

) (x) получена из f(x1; : : : ; xn) заменой ее аргументов на 0; 1 или на x и x. Если = 1, функция ' заменяется на инверсную.

)(x) соответствует условиям леммы

(x1; x2) = (x1 )(x2 ) (x1 ) (x2 ) = = x1x2 x2 x1 x1 x2

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

(x1; x2) = '(x1 ; x2 )

) (x) получена из f(x1; : : : ; xn) заменой ее аргументов на 0; 1 или на x и x. Если = 1, функция ' заменяется на инверсную.

)(x) соответствует условиям леммы

(x1; x2) = (x1 )(x2 ) (x1 ) (x2 ) = = x1x2 x2 x1 x1 x2

Полнота и замкнутость Замкнутые классы

Класс линейных функций

Лемма о нелинейной функции

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

= x1x2f1(x3; : : : ; xn) x1f2(x3; : : : ; xn) x2f3(x3; : : : ; xn) f4(x3; : : : ; xn)

Пусть f1( 3; : : : ; n) = 1

'(x1; x2) = f(x1; x2; 3; : : : ; n) = x1x2 x1 x2 , ãäå , , 2 f0; 1g.

(x1; x2) = '(x1 ; x2 )

) (x) получена из f(x1; : : : ; xn) заменой ее аргументов на 0; 1 или на x и x. Если = 1, функция ' заменяется на инверсную.

)(x) соответствует условиям леммы

(x1; x2) = (x1 )(x2 ) (x1 ) (x2 ) = = x1x2 x2 x1 x1 x2